Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 0531b5db61ded49c008b780fc360790094f08601) +++ src/GenPoly/Box.cc (revision 89173242fa881839c7c59a2867fdd746dd50df8e) @@ -30,4 +30,5 @@ #include "FindFunction.h" #include "ScopedMap.h" +#include "ScopedSet.h" #include "ScrubTyVars.h" @@ -118,5 +119,5 @@ 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,6 +179,4 @@ 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,7 +205,8 @@ 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,5 +214,9 @@ }; - /// 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,8 +229,64 @@ 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 << ""; + } + + os << std::endl; + Expression::print( os, indent ); + } + + private: + StructInstType *type; }; @@ -633,5 +693,5 @@ 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,31 +783,4 @@ } - 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,6 +795,9 @@ 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,12 +1646,16 @@ ++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,4 +1669,187 @@ 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(); }