Changeset 89173242

Timestamp:

Mar 10, 2016, 4:56:53 PM (9 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

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

Children:

b3f9a0cb

Parents:

0531b5d

Message:

Added first draft of use of layout functions

File:

• src/GenPoly/Box.cc (modified) (11 diffs)

src/GenPoly/Box.cc

@@ -30 +30 @@
 #include "FindFunction.h"
 #include "ScopedMap.h"
+#include "ScopedSet.h"
 #include "ScrubTyVars.h"
 
@@ -118 +119 @@
                         typedef std::vector< Instantiation > ValueList;
                         /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
-                        typedef ScopedMap< Key*, std::vector< Instantiation > > InnerMap;
+                        typedef ScopedMap< Key*, ValueList > InnerMap;
 
                         InnerMap instantiations;  ///< instantiations
@@ -178 +179 @@
                         virtual void doEndScope();
                   private:
-                        /// Makes a new temporary array holding the offsets of the fields of `type`, and returns a new variable expression referencing it
-                        Expression *makeOffsetArray( StructInstType *type );
                         /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
                         void passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
@@ -206 +205 @@
                         ObjectDecl *makeTemporary( Type *type );
 
-                        std::map< std::string, DeclarationWithType *> assignOps;
-                        ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps;
-                        ScopedMap< std::string, DeclarationWithType* > adapters;
+                        std::map< std::string, DeclarationWithType *> assignOps;     ///< Currently known type variable assignment operators
+                        ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps;  ///< Currently known assignment operators
+                        ScopedMap< std::string, DeclarationWithType* > adapters;     ///< Set of adapter functions in the current scope
+                        
                         DeclarationWithType *retval;
                         bool useRetval;
@@ -214 +214 @@
                 };
 
-                /// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
+                class OffsetPackExpr;  // forward declaration so that it can be mutated by Pass2
+
+                /// * Moves polymorphic returns in function types to pointer-type parameters
+                /// * adds type size and assertion parameters to parameter lists
+                /// * does dynamic calculation of type layouts
                 class Pass2 : public PolyMutator {
                   public:
@@ -225 +229 @@
                         virtual Type *mutate( PointerType *pointerType );
                         virtual Type *mutate( FunctionType *funcType );
+                        virtual Expression *mutate( SizeofExpr *sizeofExpr );
+                        virtual Expression *mutate( AlignofExpr *alignofExpr );
+                        virtual Expression *mutate( OffsetofExpr *offsetofExpr );
+                                Expression *mutate( OffsetPackExpr *offsetPackExpr );
+
+                        virtual void doBeginScope();
+                        virtual void doEndScope();
                   private:
                         void addAdapters( FunctionType *functionType );
+                        /// Makes a new variable in the current scope with the given name, type & optional initializer
+                        ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 );
+                        /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns
+                        bool findGeneric( Type *ty );
+                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
+                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
 
                         std::map< UniqueId, std::string > adapterName;
+                        ScopedSet< std::string > knownLayouts;          ///< Set of generic type layouts known in the current scope, indexed by sizeofName
+                        ScopedSet< std::string > knownOffsets;          ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName
+                };
+
+                /// Special internal expression for offset arrays inserted by Pass1 and replaced by Pass2
+                class OffsetPackExpr : public Expression {
+                public:
+                        OffsetPackExpr( StructInstType *type_, Expression *aname_ = 0 ) : Expression( aname_ ), type( type_ ) {
+                                        add_result( new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0, false, false ) );
+                        }
+                        
+                        OffsetPackExpr( const OffsetPackExpr &other ) : Expression( other ), type( maybeClone( other.type ) ) {}
+                        virtual ~OffsetPackExpr() { delete type; }
+
+                        StructInstType *get_type() const { return type; }
+                        void set_type( StructInstType *newValue ) { type = newValue; }
+
+                        virtual OffsetPackExpr *clone() const { return new OffsetPackExpr( *this ); }
+                        virtual void accept( Visitor &v ) { /* do nothing */ }
+                        virtual Expression *acceptMutator( Mutator &m ) {
+                                // only act if the mutator is a Pass2, which knows about this class
+                                if ( Pass2 *m2 = dynamic_cast< Pass2* >( &m ) ) {
+                                        return m2->mutate( this );
+                                } else {
+                                        return this;
+                                }
+                        }
+
+                        virtual void print( std::ostream &os, int indent = 0 ) const {
+                                os << std::string( indent, ' ' ) << "Offset pack expression on ";
+
+                                if ( type ) {
+                                        type->print(os, indent + 2);
+                                } else {
+                                        os << "<NULL>";
+                                }
+
+                                os << std::endl;
+                                Expression::print( os, indent );
+                        }
+                        
+                private:
+                        StructInstType *type;
                 };
 
@@ -633 +693 @@
 
                 DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
-                        // if this is a polymorphic assignment function, put it in the map for this scope
+                        // if this is a assignment function, put it in the map for this scope
                         if ( Type *assignedType = isAssignment( functionDecl ) ) {
                                 if ( ! dynamic_cast< TypeInstType* >( assignedType ) ) {
@@ -723 +783 @@
                 }
 
-                Expression *Pass1::makeOffsetArray( StructInstType *ty ) {
-                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
-
-                        // make a new temporary array
-                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
-                        std::stringstream lenGen;
-                        lenGen << baseMembers.size();
-                        ConstantExpr *lenExpr = new ConstantExpr( Constant( offsetType->clone(), lenGen.str() ) );
-                        ObjectDecl *arrayTemp = makeTemporary( new ArrayType( Type::Qualifiers(), offsetType, lenExpr, false, false ) );
-
-                        // build initializer list for temporary
-                        std::list< Initializer* > inits;
-                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
-                                DeclarationWithType *memberDecl;
-                                if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
-                                        memberDecl = origMember->clone();
-                                } else {
-                                        memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
-                                }
-                                inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
-                        }
-                        arrayTemp->set_init( new ListInit( inits ) );
-
-                        // return variable pointing to temporary
-                        return new VariableExpr( arrayTemp );
-                }
-
                 void Pass1::passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) {
                         Type *polyBase = hasPolyBase( parmType, exprTyVars );
@@ -762 +795 @@
                                 if ( dynamic_cast< StructInstType* >( polyBase ) ) {
                                         if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) {
-                                                arg = appExpr->get_args().insert( arg, makeOffsetArray( argBaseStructType ) );
-                                                arg++;
+                                                // zero-length arrays are forbidden by C, so don't pass offset for empty struct
+                                                if ( ! argBaseStructType->get_baseStruct()->get_members().empty() ) {
+                                                        arg = appExpr->get_args().insert( arg, new OffsetPackExpr( argBaseStructType ) );
+                                                        arg++;
+                                                }
                                         } else {
                                                 throw SemanticError( "Cannot pass non-struct type for generic struct" );
@@ -1610 +1646 @@
                                         ++last;
 
-                                        if ( dynamic_cast< StructInstType* >( polyBase ) ) {
-                                                offsetParm = newPtr.clone();
-                                                offsetParm->set_name( offsetofName( polyBase ) );
-                                                last = funcType->get_parameters().insert( last, offsetParm );
-                                                ++last;
+                                        if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyBase ) ) {
+                                                // NOTE zero-length arrays are illegal in C, so empty structs have no offset array
+                                                if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
+                                                        offsetParm = newPtr.clone();
+                                                        offsetParm->set_name( offsetofName( polyBase ) );
+                                                        last = funcType->get_parameters().insert( last, offsetParm );
+                                                        ++last;
+                                                }
                                         }
 
                                         seenTypes.insert( sizeName );
+                                        knownLayouts.insert( sizeName );  // make sure that any type information passed into the function is accounted for
                                 }
                         }
@@ -1629 +1669 @@
                         scopeTyVars = oldtyVars;
                         return funcType;
+                }
+
+                ObjectDecl *Pass2::makeVar( const std::string &name, Type *type, Initializer *init ) {
+                        ObjectDecl *newObj = new ObjectDecl( name, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, init );
+                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
+                        return newObj;
+                }
+
+                void Pass2::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) {
+                        for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
+                                if ( findGeneric( *param ) ) {
+                                        // push size/align vars for a generic parameter back
+                                        layoutCall->get_args().push_back( new NameExpr( sizeofName( *param ) ) );
+                                        layoutCall->get_args().push_back( new NameExpr( alignofName( *param ) ) );
+                                } else {
+                                        layoutCall->get_args().push_back( new SizeofExpr( *param ) );
+                                        layoutCall->get_args().push_back( new AlignofExpr( *param ) );
+                                }
+                        }
+                }
+
+                /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
+                bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
+                        bool hasDynamicLayout = false;
+
+                        std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
+                        std::list< Expression* >::const_iterator typeParam = typeParams.begin();
+                        for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
+                                // skip non-otype parameters
+                                if ( (*baseParam)->get_kind() != TypeDecl::Any ) continue;
+                                TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( *typeParam );
+                                assert( typeExpr && "all otype parameters should be type expressions" );
+
+                                Type *type = typeExpr->get_type();
+                                out.push_back( type );
+                                if ( isPolyType( type ) ) hasDynamicLayout = true;
+                        }
+                        assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
+
+                        return hasDynamicLayout;
+                }
+                
+                bool Pass2::findGeneric( Type *ty ) {
+                        if ( dynamic_cast< TypeInstType* >( ty ) ) {
+                                // NOTE this assumes that all type variables will be properly bound, and thus have their layouts in scope
+                                return true;
+                        } else if ( StructInstType *structTy = dynamic_cast< StructInstType* >( ty ) ) {
+                                // check if this type already has a layout generated for it
+                                std::string sizeName = sizeofName( ty );
+                                if ( knownLayouts.find( sizeName ) != knownLayouts.end() ) return true;
+                                
+                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
+                                std::list< Type* > otypeParams;
+                                if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
+
+                                // insert local variables for layout and generate call to layout function
+                                knownLayouts.insert( sizeName );  // done early so as not to interfere with the later addition of parameters to the layout call
+                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+
+                                int n_members = structTy->get_baseStruct()->get_members().size();
+                                if ( n_members == 0 ) {
+                                        // all empty structs have the same layout - size 1, align 1
+                                        makeVar( sizeName, layoutType, new SingleInit( new ConstantExpr( Constant::from( (unsigned long)1 ) ) ) );
+                                        makeVar( alignofName( ty ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from( (unsigned long)1 ) ) ) );
+                                        // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
+                                } else {
+                                        ObjectDecl *sizeVar = makeVar( sizeName, layoutType );
+                                        ObjectDecl *alignVar = makeVar( alignofName( ty ), layoutType->clone() );
+                                        ObjectDecl *offsetVar = makeVar( offsetofName( ty ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from( n_members ) ), false, false ) );
+
+                                        // generate call to layout function
+                                        UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( "__layoutof_" + structTy->get_baseStruct()->get_name() ) );
+                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
+                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
+                                        layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
+                                        addOtypeParamsToLayoutCall( layoutCall, otypeParams );
+
+                                        stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
+                                }
+                                
+                                return true;
+                        } else if ( UnionInstType *unionTy = dynamic_cast< UnionInstType* >( ty ) ) {
+                                // check if this type already has a layout generated for it
+                                std::string sizeName = sizeofName( ty );
+                                if ( knownLayouts.find( sizeName ) != knownLayouts.end() ) return true;
+                                
+                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
+                                std::list< Type* > otypeParams;
+                                if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
+
+                                // insert local variables for layout and generate call to layout function
+                                knownLayouts.insert( sizeName );  // done early so as not to interfere with the later addition of parameters to the layout call
+                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+
+                                ObjectDecl *sizeVar = makeVar( sizeName, layoutType );
+                                ObjectDecl *alignVar = makeVar( alignofName( ty ), layoutType->clone() );
+                                
+                                // generate call to layout function
+                                UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( "__layoutof_" + unionTy->get_baseUnion()->get_name() ) );
+                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
+                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
+                                addOtypeParamsToLayoutCall( layoutCall, otypeParams );
+
+                                stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
+
+                                return true;
+                        }
+                        
+                        return false;
+                }
+                
+                Expression *Pass2::mutate( SizeofExpr *sizeofExpr ) {
+                        Type *ty = sizeofExpr->get_type();
+                        if ( findGeneric( ty ) ) {
+                                Expression *ret = new NameExpr( sizeofName( ty ) );
+                                delete sizeofExpr;
+                                return ret;
+                        }
+                        return sizeofExpr;
+                }
+
+                Expression *Pass2::mutate( AlignofExpr *alignofExpr ) {
+                        Type *ty = alignofExpr->get_type();
+                        if ( findGeneric( ty ) ) {
+                                Expression *ret = new NameExpr( alignofName( ty ) );
+                                delete alignofExpr;
+                                return ret;
+                        }
+                        return alignofExpr;
+                }
+
+                Expression *Pass2::mutate( OffsetofExpr *offsetofExpr ) {
+                        findGeneric( offsetofExpr->get_type() );
+                        return offsetofExpr;
+                }
+
+                Expression *Pass2::mutate( OffsetPackExpr *offsetPackExpr ) {
+                        StructInstType *ty = offsetPackExpr->get_type();
+
+                        Expression *ret = 0;
+                        if ( findGeneric( ty ) ) {
+                                // pull offset back from generated type information
+                                ret = new NameExpr( offsetofName( ty ) );
+                        } else {
+                                std::string offsetName = offsetofName( ty );
+                                if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
+                                        // use the already-generated offsets for this type
+                                        ret = new NameExpr( offsetName );
+                                } else {
+                                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
+                                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+
+                                        // build initializer list for offset array
+                                        std::list< Initializer* > inits;
+                                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
+                                                DeclarationWithType *memberDecl;
+                                                if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
+                                                        memberDecl = origMember->clone();
+                                                } else {
+                                                        memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
+                                                }
+                                                inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
+                                        }
+
+                                        // build the offset array and replace the pack with a reference to it
+                                        ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from( baseMembers.size() ) ), false, false ),
+                                                        new ListInit( inits ) );
+                                        ret = new VariableExpr( offsetArray );
+                                }
+                        }
+
+                        delete offsetPackExpr;
+                        return ret;
+                }
+
+                void Pass2::doBeginScope() {
+                        knownLayouts.beginScope();
+                        knownOffsets.beginScope();
+                }
+                
+                void Pass2::doEndScope() {
+                        knownLayouts.endScope();
+                        knownOffsets.beginScope();
                 }