Changes in / [53ba273:78885b5]

Location:

src

Files:

• CodeGen/CodeGenerator.cc (modified) (2 diffs)
• CodeGen/CodeGenerator.h (modified) (1 diff)
• GenPoly/Box.cc (modified) (21 diffs)
• GenPoly/ScopedMap.h (modified) (5 diffs)
• GenPoly/ScopedSet.h (added)
• InitTweak/InitModel.h (modified) (1 diff)
• ResolvExpr/AlternativeFinder.cc (modified) (1 diff)
• ResolvExpr/AlternativeFinder.h (modified) (1 diff)
• SymTab/Indexer.cc (modified) (1 diff)
• SymTab/Indexer.h (modified) (1 diff)
• SynTree/Expression.cc (modified) (1 diff)
• SynTree/Expression.h (modified) (1 diff)
• SynTree/Mutator.cc (modified) (1 diff)
• SynTree/Mutator.h (modified) (1 diff)
• SynTree/SynTree.h (modified) (1 diff)
• SynTree/Visitor.cc (modified) (1 diff)
• SynTree/Visitor.h (modified) (1 diff)
• Tuples/FlattenTuple.cc (modified) (1 diff)
• Tuples/FlattenTuple.h (modified) (1 diff)

src/CodeGen/CodeGenerator.cc

@@ -455 +455 @@
 
         void CodeGenerator::visit( UntypedOffsetofExpr *offsetofExpr ) {
-                assert( false );
+                assert( false && "UntypedOffsetofExpr should not reach code generation" );
         }
 
@@ -464 +464 @@
                 output << ", " << mangleName( offsetofExpr->get_member() );
                 output << ")";
+        }
+
+        void CodeGenerator::visit( OffsetPackExpr *offsetPackExpr ) {
+                assert( false && "OffsetPackExpr should not reach code generation" );
         }
   

src/CodeGen/CodeGenerator.h

@@ -65 +65 @@
                 virtual void visit( UntypedOffsetofExpr *offsetofExpr );
                 virtual void visit( OffsetofExpr *offsetofExpr );
+                virtual void visit( OffsetPackExpr *offsetPackExpr );
                 virtual void visit( LogicalExpr *logicalExpr );
                 virtual void visit( ConditionalExpr *conditionalExpr );

src/GenPoly/Box.cc

@@ -30 +30 @@
 #include "FindFunction.h"
 #include "ScopedMap.h"
+#include "ScopedSet.h"
 #include "ScrubTyVars.h"
 
@@ -62 +63 @@
                 FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
 
-                /// Key for a unique concrete type; generic base type paired with type parameter list
-                struct ConcreteType {
-                        ConcreteType() : base(NULL), params() {}
-
-                        ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); }
-
-                        ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); }
+                /// Abstracts type equality for a list of parameter types
+                struct TypeList {
+                        TypeList() : params() {}
+                        TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); }
+                        TypeList( std::list< Type* > &&_params ) : params( _params ) {}
+
+                        TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); }
+                        TypeList( TypeList &&that ) : params( std::move( that.params ) ) {}
 
                         /// Extracts types from a list of TypeExpr*
-                        ConcreteType(AggregateDecl *_base, const std::list< TypeExpr* >& _params) : base(_base), params() {
+                        TypeList( const std::list< TypeExpr* >& _params ) : params() {
                                 for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
                                         params.push_back( (*param)->get_type()->clone() );
@@ -77 +79 @@
                         }
 
-                        ConcreteType& operator= (const ConcreteType& that) {
+                        TypeList& operator= ( const TypeList &that ) {
                                 deleteAll( params );
+
                                 params.clear();
-
-                                base = that.base;
                                 cloneAll( that.params, params );
 
@@ -87 +88 @@
                         }
 
-                        ~ConcreteType() { deleteAll( params ); }
-
-                        bool operator== (const ConcreteType& that) const {
-                                if ( base != that.base ) return false;
+                        TypeList& operator= ( TypeList &&that ) {
+                                deleteAll( params );
+
+                                params = std::move( that.params );
+
+                                return *this;
+                        }
+
+                        ~TypeList() { deleteAll( params ); }
+
+                        bool operator== ( const TypeList& that ) const {
+                                if ( params.size() != that.params.size() ) return false;
 
                                 SymTab::Indexer dummy;
-                                if ( params.size() != that.params.size() ) return false;
                                 for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
                                         if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
@@ -100 +108 @@
                         }
 
-                        AggregateDecl *base;        ///< Base generic type
                         std::list< Type* > params;  ///< Instantiation parameters
                 };
 
-                /// Maps a concrete type to the some value, accounting for scope
-                template< typename Value >
+                /// Maps a key and a TypeList to the some value, accounting for scope
+                template< typename Key, typename Value >
                 class InstantiationMap {
-                        /// Information about a specific instantiation of a generic type
-                        struct Instantiation {
-                                ConcreteType key;  ///< Instantiation parameters for this type
-                                Value *value;      ///< Value for this instantiation
-
-                                Instantiation() : key(), value(0) {}
-                                Instantiation(const ConcreteType &_key, Value *_value) : key(_key), value(_value) {}
-                        };
-                        /// Map of generic types to instantiations of them
-                        typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope;
-
-                        std::vector< Scope > scopes;  ///< list of scopes, from outermost to innermost
+                        /// Wraps value for a specific (Key, TypeList) combination
+                        typedef std::pair< TypeList, Value* > Instantiation;
+                        /// List of TypeLists paired with their appropriate values
+                        typedef std::vector< Instantiation > ValueList;
+                        /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
+                        typedef ScopedMap< Key*, ValueList > InnerMap;
+
+                        InnerMap instantiations;  ///< instantiations
 
                 public:
                         /// Starts a new scope
-                        void beginScope() {
-                                Scope scope;
-                                scopes.push_back(scope);
-                        }
+                        void beginScope() { instantiations.beginScope(); }
 
                         /// Ends a scope
-                        void endScope() {
-                                scopes.pop_back();
-                        }
-
-                        /// Default constructor initializes with one scope
-                        InstantiationMap() { beginScope(); }
-
-//              private:
-                        /// Gets the value for the concrete instantiation of this type, assuming it has already been instantiated in the current scope.
-                        /// Returns NULL on none such.
-                        Value *lookup( AggregateDecl *generic, const std::list< TypeExpr* >& params ) {
-                                ConcreteType key(generic, params);
-                                // scan scopes from innermost out
-                                for ( typename std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) {
-                                        // skip scope if no instantiations of this generic type
-                                        typename Scope::const_iterator insts = scope->find( generic );
-                                        if ( insts == scope->end() ) continue;
-                                        // look through instantiations for matches to concrete type
-                                        for ( typename std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) {
-                                                if ( inst->key == key ) return inst->value;
+                        void endScope() { instantiations.endScope(); }
+
+                        /// Gets the value for the (key, typeList) pair, returns NULL on none such.
+                        Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const {
+                                TypeList typeList( params );
+                                
+                                // scan scopes for matches to the key
+                                for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) {
+                                        for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) {
+                                                if ( inst->first == typeList ) return inst->second;
                                         }
                                 }
-                                // no matching instantiation found
+                                // no matching instantiations found
                                 return 0;
                         }
-                public:
-//                      StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)lookup( inst->get_baseStruct(), typeSubs ); }
-//                      UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)lookup( inst->get_baseUnion(), typeSubs ); }
-
-//              private:
-                        /// Adds a value for a concrete type to the current scope
-                        void insert( AggregateDecl *generic, const std::list< TypeExpr* > &params, Value *value ) {
-                                ConcreteType key(generic, params);
-                                scopes.back()[generic].push_back( Instantiation( key, value ) );
-                        }
-//              public:
-//                      void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { insert( inst->get_baseStruct(), typeSubs, decl ); }
-//                      void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { insert( inst->get_baseUnion(), typeSubs, decl ); }
+
+                        /// Adds a value for a (key, typeList) pair to the current scope
+                        void insert( Key *key, const std::list< TypeExpr* > &params, Value *value ) {
+                                instantiations[ key ].push_back( Instantiation( TypeList( params ), value ) );
+                        }
                 };
 
@@ -197 +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 );
@@ -225 +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;
@@ -233 +214 @@
                 };
 
-                /// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
+                /// * 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:
@@ -244 +227 @@
                         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 );
+                        virtual 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
                 };
 
@@ -253 +251 @@
                 class GenericInstantiator : public DeclMutator {
                         /// Map of (generic type, parameter list) pairs to concrete type instantiations
-                        InstantiationMap< AggregateDecl > instantiations;
+                        InstantiationMap< AggregateDecl, AggregateDecl > instantiations;
                         /// Namer for concrete types
                         UniqueName typeNamer;
@@ -348 +346 @@
                 mutateTranslationUnit/*All*/( translationUnit, pass1 );
                 mutateTranslationUnit/*All*/( translationUnit, pass2 );
-//              instantiateGeneric( translationUnit );
                 instantiator.mutateDeclarationList( translationUnit );
                 mutateTranslationUnit/*All*/( translationUnit, memberFixer );
@@ -653 +650 @@
 
                 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 ) ) {
@@ -743 +740 @@
                 }
 
-                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 );
@@ -782 +752 @@
                                 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->clone() ) );
+                                                        arg++;
+                                                }
                                         } else {
                                                 throw SemanticError( "Cannot pass non-struct type for generic struct" );
@@ -931 +904 @@
                                         return;
                                 } else if ( arg->get_results().front()->get_isLvalue() ) {
-                                        // VariableExpr and MemberExpr are lvalues
-                                        arg = new AddressExpr( arg );
+                                        // VariableExpr and MemberExpr are lvalues; need to check this isn't coming from the second arg of a comma expression though (not an lvalue)
+                                        if ( CommaExpr *commaArg = dynamic_cast< CommaExpr* >( arg ) ) {
+                                                commaArg->set_arg2( new AddressExpr( commaArg->get_arg2() ) );
+                                        } else {
+                                                arg = new AddressExpr( arg );
+                                        }
                                 } else {
                                         // use type computed in unification to declare boxed variables
@@ -1027 +1004 @@
                         } // for
                 }
-
-
 
                 FunctionDecl *Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
@@ -1428 +1403 @@
                                         std::list< TypeDecl* >::const_iterator forallIt = forallParams.begin();
                                         for ( ; tyIt != tyParams.end() && forallIt != forallParams.end(); ++tyIt, ++forallIt ) {
-                                                if ( (*forallIt)->get_kind() != TypeDecl::Any ) continue; // skip types with no assign op (ftype/dtype)
-
-                                                std::list< DeclarationWithType* > &asserts = (*forallIt)->get_assertions();
-                                                assert( ! asserts.empty() && "Type param needs assignment operator assertion" );
-                                                DeclarationWithType *actualDecl = asserts.front();
-                                                TypeInstType *actualType = isTypeInstAssignment( actualDecl );
-                                                assert( actualType && "First assertion of type with assertions should be assignment operator" );
+                                                // Add appropriate mapping to assignment expression environment
                                                 TypeExpr *formalTypeExpr = dynamic_cast< TypeExpr* >( *tyIt );
                                                 assert( formalTypeExpr && "type parameters must be type expressions" );
                                                 Type *formalType = formalTypeExpr->get_type();
-                                                assignExpr->get_env()->add( actualType->get_name(), formalType );
-                                                
+                                                assignExpr->get_env()->add( (*forallIt)->get_name(), formalType );
+
+                                                // skip types with no assign op (ftype/dtype)
+                                                if ( (*forallIt)->get_kind() != TypeDecl::Any ) continue;
+
+                                                // find assignment operator for formal type
                                                 DeclarationWithType *assertAssign = 0;
                                                 if ( TypeInstType *formalTypeInstType = dynamic_cast< TypeInstType* >( formalType ) ) {
@@ -1453 +1426 @@
                                                         }
                                                 }
-                                                
-
+
+                                                // add inferred parameter for field assignment operator to assignment expression
+                                                std::list< DeclarationWithType* > &asserts = (*forallIt)->get_assertions();
+                                                assert( ! asserts.empty() && "Type param needs assignment operator assertion" );
+                                                DeclarationWithType *actualDecl = asserts.front();
                                                 assignExpr->get_inferParams()[ actualDecl->get_uniqueId() ]
                                                         = ParamEntry( assertAssign->get_uniqueId(), assertAssign->get_type()->clone(), actualDecl->get_type()->clone(), wrapFunctionDecl( assertAssign ) );
@@ -1587 +1563 @@
                         ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
                                            new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
-//   ObjectDecl *newFunPtr = new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
                         for ( std::list< TypeDecl *>::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
                                 ObjectDecl *sizeParm, *alignParm;
@@ -1631 +1606 @@
                                         ++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
                                 }
                         }
@@ -1650 +1629 @@
                         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)->clone() ) );
+                                        layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
+                                }
+                        }
+                }
+
+                /// 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 {
+                                        knownOffsets.insert( offsetName );
+                                        
+                                        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();
                 }
 

src/GenPoly/ScopedMap.h

@@ -17 +17 @@
 #define _SCOPEDMAP_H
 
+#include <cassert>
 #include <iterator>
 #include <map>
@@ -164 +165 @@
                 void endScope() {
                         scopes.pop_back();
+                        assert( ! scopes.empty() );
                 }
 
@@ -188 +190 @@
                         return end();
                 }
-                const_iterator find( const Key &key ) const { return const_iterator( find( key ) ); }
+                const_iterator find( const Key &key ) const {
+                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->find( key ) );
+                }
                 
                 /// Finds the given key in the outermost scope inside the given scope where it occurs
@@ -200 +204 @@
                         return end();
                 }
-                const_iterator findNext( const_iterator &it, const Key &key ) const { return const_iterator( findNext( it, key ) ); }
+                const_iterator findNext( const_iterator &it, const Key &key ) const {
+                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->findNext( it, key ) );
+                }
 
                 /// Inserts the given key-value pair into the outermost scope
@@ -208 +214 @@
                 }
                 std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
-                
+
+                Value& operator[] ( const Key &key ) {
+                        iterator slot = find( key );
+                        if ( slot != end() ) return slot->second;
+                        return insert( key, Value() ).first->second;
+                }
         };
 } // namespace GenPoly

src/InitTweak/InitModel.h

@@ -75 +75 @@
                         void visit( UntypedOffsetofExpr * ) { throw 0; }
                         void visit( OffsetofExpr * ) { throw 0; }
+                        void visit( OffsetPackExpr * ) { throw 0; }
                         void visit( AttrExpr * ) { throw 0; }
                         void visit( LogicalExpr * ) { throw 0; }

src/ResolvExpr/AlternativeFinder.cc

@@ -848 +848 @@
         }
 
+        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
+                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
+        }
+
         void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
                 // assume no polymorphism

src/ResolvExpr/AlternativeFinder.h

@@ -59 +59 @@
                 virtual void visit( UntypedOffsetofExpr *offsetofExpr );
                 virtual void visit( OffsetofExpr *offsetofExpr );
+                virtual void visit( OffsetPackExpr *offsetPackExpr );
                 virtual void visit( AttrExpr *attrExpr );
                 virtual void visit( LogicalExpr *logicalExpr );

src/SymTab/Indexer.cc

@@ -344 +344 @@
                 maybeAccept( offsetofExpr->get_type(), *this );
                 maybeAccept( offsetofExpr->get_member(), *this );
+        }
+
+        void Indexer::visit( OffsetPackExpr *offsetPackExpr ) {
+                acceptAllNewScope( offsetPackExpr->get_results(), *this );
+                maybeAccept( offsetPackExpr->get_type(), *this );
         }
 

src/SymTab/Indexer.h

@@ -59 +59 @@
                 virtual void visit( UntypedOffsetofExpr *offsetofExpr );
                 virtual void visit( OffsetofExpr *offsetofExpr );
+                virtual void visit( OffsetPackExpr *offsetPackExpr );
                 virtual void visit( AttrExpr *attrExpr );
                 virtual void visit( LogicalExpr *logicalExpr );

src/SynTree/Expression.cc

@@ -222 +222 @@
 }
 
+OffsetPackExpr::OffsetPackExpr( StructInstType *type_, Expression *aname_ ) : Expression( aname_ ), type( type_ ) {
+        add_result( new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0, false, false ) );
+}
+
+OffsetPackExpr::OffsetPackExpr( const OffsetPackExpr &other ) : Expression( other ), type( maybeClone( other.type ) ) {}
+
+OffsetPackExpr::~OffsetPackExpr() { delete type; }
+
+void OffsetPackExpr::print( std::ostream &os, int indent ) 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 );
+}
+
 AttrExpr::AttrExpr( Expression *attr, Expression *expr_, Expression *_aname ) :
                 Expression( _aname ), attr( attr ), expr(expr_), type(0), isType(false) {

src/SynTree/Expression.h

@@ -362 +362 @@
 };
 
+/// Expression representing a pack of field-offsets for a generic type
+class OffsetPackExpr : public Expression {
+public:
+        OffsetPackExpr( StructInstType *type_, Expression *aname_ = 0 );
+        OffsetPackExpr( const OffsetPackExpr &other );
+        virtual ~OffsetPackExpr();
+
+        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 ) { v.visit( this ); }
+        virtual Expression *acceptMutator( Mutator &m ) { return m.mutate( this ); }
+
+        virtual void print( std::ostream &os, int indent = 0 ) const;
+
+private:
+        StructInstType *type;
+};
+
 /// AttrExpr represents an @attribute expression (like sizeof, but user-defined)
 class AttrExpr : public Expression {

src/SynTree/Mutator.cc

@@ -274 +274 @@
 }
 
+Expression *Mutator::mutate( OffsetPackExpr *offsetPackExpr ) {
+        mutateAll( offsetPackExpr->get_results(), *this );
+        offsetPackExpr->set_type( maybeMutate( offsetPackExpr->get_type(), *this ) );
+        return offsetPackExpr;
+}
+
 Expression *Mutator::mutate( AttrExpr *attrExpr ) {
         mutateAll( attrExpr->get_results(), *this );

src/SynTree/Mutator.h

@@ -67 +67 @@
         virtual Expression* mutate( UntypedOffsetofExpr *offsetofExpr );
         virtual Expression* mutate( OffsetofExpr *offsetofExpr );
+        virtual Expression* mutate( OffsetPackExpr *offsetPackExpr );
         virtual Expression* mutate( AttrExpr *attrExpr );
         virtual Expression* mutate( LogicalExpr *logicalExpr );

src/SynTree/SynTree.h

@@ -72 +72 @@
 class UntypedOffsetofExpr;
 class OffsetofExpr;
+class OffsetPackExpr;
 class AttrExpr;
 class LogicalExpr;

src/SynTree/Visitor.cc

@@ -230 +230 @@
 }
 
+void Visitor::visit( OffsetPackExpr *offsetPackExpr ) {
+        acceptAll( offsetPackExpr->get_results(), *this );
+        maybeAccept( offsetPackExpr->get_type(), *this );
+}
+
 void Visitor::visit( AttrExpr *attrExpr ) {
         acceptAll( attrExpr->get_results(), *this );

src/SynTree/Visitor.h

@@ -67 +67 @@
         virtual void visit( UntypedOffsetofExpr *offsetofExpr );
         virtual void visit( OffsetofExpr *offsetofExpr );
+        virtual void visit( OffsetPackExpr *offsetPackExpr );
         virtual void visit( AttrExpr *attrExpr );
         virtual void visit( LogicalExpr *logicalExpr );

src/Tuples/FlattenTuple.cc

@@ -49 +49 @@
         void FlattenTuple::CollectArgs::visit( UntypedOffsetofExpr *expr )  {  currentArgs.insert( currentArgs.end(), expr );  }
         void FlattenTuple::CollectArgs::visit( OffsetofExpr        *expr )  {  currentArgs.insert( currentArgs.end(), expr );  }
+        void FlattenTuple::CollectArgs::visit( OffsetPackExpr      *expr )  {  currentArgs.insert( currentArgs.end(), expr );  }
         void FlattenTuple::CollectArgs::visit( AttrExpr            *expr )  {  currentArgs.insert( currentArgs.end(), expr );  }
         void FlattenTuple::CollectArgs::visit( LogicalExpr         *expr )  {  currentArgs.insert( currentArgs.end(), expr );  }

src/Tuples/FlattenTuple.h

@@ -45 +45 @@
                         virtual void visit( UntypedOffsetofExpr * );
                         virtual void visit( OffsetofExpr * );
+                        virtual void visit( OffsetPackExpr * );
                         virtual void visit( AttrExpr * );
                         virtual void visit( LogicalExpr * );