Index: src/GenPoly/Box.cc
===================================================================
--- src/GenPoly/Box.cc	(revision dbd8652cebff1e6ac5f417592f678108e89c3503)
+++ src/GenPoly/Box.cc	(revision 9d7b3ea1ccb5d1eccef1e7382c27f22177146c1a)
@@ -22,4 +22,5 @@
 
 #include "Box.h"
+#include "DeclMutator.h"
 #include "InstantiateGeneric.h"
 #include "PolyMutator.h"
@@ -54,4 +55,15 @@
 		FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
 
+		/// Adds layout-generation functions to polymorphic types
+		class LayoutFunctionBuilder : public DeclMutator {
+			unsigned int functionNesting;  // current level of nested functions
+		public:
+			LayoutFunctionBuilder() : functionNesting( 0 ) {}
+
+			virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
+			virtual Declaration *mutate( StructDecl *structDecl );
+			virtual Declaration *mutate( UnionDecl *unionDecl );
+		};
+		
 		/// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
 		class Pass1 : public PolyMutator {
@@ -159,13 +171,4 @@
 	} // anonymous namespace
 
-	void printAllNotBuiltin( const std::list< Declaration *>& translationUnit, std::ostream &os ) {
-		for ( std::list< Declaration *>::const_iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
-			if ( ! LinkageSpec::isBuiltin( (*i)->get_linkage() ) ) {
-				(*i)->print( os );
-				os << std::endl;
-			} // if
-		} // for
-	}
-
 	/// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
 	template< typename MutatorType >
@@ -195,8 +198,10 @@
 
 	void box( std::list< Declaration *>& translationUnit ) {
+		LayoutFunctionBuilder layoutBuilder;
 		Pass1 pass1;
 		Pass2 pass2;
 		MemberExprFixer memberFixer;
 		Pass3 pass3;
+		layoutBuilder.mutateDeclarationList( translationUnit );
 		mutateTranslationUnit/*All*/( translationUnit, pass1 );
 		mutateTranslationUnit/*All*/( translationUnit, pass2 );
@@ -206,4 +211,198 @@
 	}
 
+	////////////////////////////////// LayoutFunctionBuilder ////////////////////////////////////////////
+
+	DeclarationWithType *LayoutFunctionBuilder::mutate( FunctionDecl *functionDecl ) {
+		functionDecl->set_functionType( maybeMutate( functionDecl->get_functionType(), *this ) );
+		mutateAll( functionDecl->get_oldDecls(), *this );
+		++functionNesting;
+		functionDecl->set_statements( maybeMutate( functionDecl->get_statements(), *this ) );
+		--functionNesting;
+		return functionDecl;
+	}
+	
+	/// Get a list of type declarations that will affect a layout function
+	std::list< TypeDecl* > takeOtypeOnly( std::list< TypeDecl* > &decls ) {
+		std::list< TypeDecl * > otypeDecls;
+
+		for ( std::list< TypeDecl* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
+			if ( decl->get_kind() == TypeDecl::Any ) {
+				otypeDecls.push_back( *decl );
+			}
+		}
+		
+		return otypeDecls;
+	}
+
+	/// Adds parameters for otype layout to a function type
+	void addOtypeParams( FunctionType *layoutFnType, std::list< TypeDecl* > &otypeParams ) {
+		BasicType sizeAlignType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+		
+		for ( std::list< TypeDecl* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
+			layoutFnType->get_parameters().push_back( new ObjectDecl( sizeofName( (*param)->get_base() ), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
+		}
+	}
+
+	/// Builds a layout function declaration
+	FunctionDecl *buildLayoutFunctionDecl( const std::string &typeName, unsigned int functionNesting, FunctionType *layoutFnType ) {
+		// Routines at global scope marked "static" to prevent multiple definitions is separate translation units
+		// because each unit generates copies of the default routines for each aggregate.
+		FunctionDecl *layoutDecl = new FunctionDecl(
+			"__layoutof_" + typeName, functionNesting > 0 ? DeclarationNode::NoStorageClass : DeclarationNode::Static, LinkageSpec::AutoGen, layoutFnType, new CompoundStmt( noLabels ), true, false );
+		layoutDecl->fixUniqueId();
+		return layoutDecl;
+	}
+
+	/// Makes a unary operation
+	Expression *makeOp( const std::string &name, Expression *arg ) {
+		UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
+		expr->get_args().push_back( arg );
+		return expr;
+	}
+
+	/// Makes a binary operation
+	Expression *makeOp( const std::string &name, Expression *lhs, Expression *rhs ) {
+		UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
+		expr->get_args().push_back( lhs );
+		expr->get_args().push_back( rhs );
+		return expr;
+	}
+
+	/// Returns the dereference of a local pointer variable
+	Expression *derefVar( ObjectDecl *var ) {
+		return makeOp( "*?", new VariableExpr( var ) );
+	}
+
+	/// makes an if-statement with a single-expression if-block and no then block
+	Statement *makeCond( Expression *cond, Expression *ifPart ) {
+		return new IfStmt( noLabels, cond, new ExprStmt( ifPart ), 0 );
+	}
+
+	/// makes a statement that assigns rhs to lhs if lhs < rhs
+	Statement *makeAssignMax( Expression *lhs, Expression *rhs ) {
+		return makeCond( makeOp( "?<?", lhs, rhs ), makeOp( "?=?", lhs->clone(), rhs->clone() ) );
+	}
+
+	/// makes a statement that aligns lhs to rhs (rhs should be an integer power of two)
+	Statement *makeAlignTo( Expression *lhs, Expression *rhs ) {
+		// check that the lhs is zeroed out to the level of rhs
+		Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), "1" ) ) ) );
+		// if not aligned, increment to alignment
+		Expression *ifExpr = makeOp( "?+=?", lhs->clone(), makeOp( "?-?", rhs->clone(), ifCond->clone() ) );
+		return makeCond( ifCond, ifExpr );
+	}
+	
+	/// adds an expression to a compound statement
+	void addExpr( CompoundStmt *stmts, Expression *expr ) {
+		stmts->get_kids().push_back( new ExprStmt( noLabels, expr ) );
+	}
+
+	/// adds a statement to a compound statement
+	void addStmt( CompoundStmt *stmts, Statement *stmt ) {
+		stmts->get_kids().push_back( stmt );
+	}
+	
+	virtual Declaration *LayoutFunctionBuilder::mutate( StructDecl *structDecl ) {
+		// do not generate layout function for "empty" tag structs
+		if ( structDecl->get_members().empty() ) return structDecl;
+
+		// get parameters that can change layout, exiting early if none
+		std::list< TypeDecl* > otypeParams = takeOtypeOnly( structDecl->get_parameters() );
+		if ( otypeParams.empty() ) return structDecl;
+
+		// build layout function signature
+		FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
+		BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+		PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
+		
+		ObjectDecl *sizeParam = new ObjectDecl( "__sizeof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
+		layoutFnType->get_parameters().push_back( sizeParam );
+		ObjectDecl *alignParam = new ObjectDecl( "__alignof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
+		layoutFnType->get_parameters().push_back( alignParam );
+		ObjectDecl *offsetParam = new ObjectDecl( "__offsetof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
+		layoutFnType->get_parameters().push_back( offsetParam );
+		addOtypeParams( layoutFnType, otypeParams );
+
+		// build function decl
+		FunctionDecl *layoutDecl = buildLayoutFunctionDecl( structDecl->get_name(), functionNesting, layoutFnType );
+
+		// calculate struct layout in function body
+
+		// initialize size and alignment to 0 and 1 (will have at least one member to re-edit size
+		addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) );
+		addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
+		unsigned long n_members = 0;
+		bool firstMember = true;
+		for ( std::list< Declaration* >::const_iterator member = structDecl->get_members().begin(); member != structDecl->get_members().end(); ++member ) {
+			DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
+			assert( dwt );
+
+			if ( firstMember ) {
+				firstMember = false;
+			} else {
+				// make sure all members after the first (automatically aligned at 0) are properly padded for alignment
+				addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), new AlignofExpr( dwt->get_type() ) ) );
+			}
+			
+			// place current size in the current offset index
+			addExpr( layoutDecl->get_statements(), makeOp( "?=?", makeOp( "?[?]", new VariableExpr( offsetParam ), new ConstantExpr( Constant::from( n_members ) ) ),
+			                                                      derefVar( sizeParam ) ) );
+			++n_members;
+
+			// add member size to current size
+			addExpr( layoutDecl->get_statements(), makeOp( "?+=?", derefVar( sizeParam ), new SizeofExpr( dwt->get_type() ) ) );
+			
+			// take max of member alignment and global alignment
+			addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( dwt->get_type() ) ) );
+		}
+		// make sure the type is end-padded to a multiple of its alignment
+		addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
+
+		addDeclarationAfter( layoutDecl );
+		return structDecl;
+	}
+	
+	virtual Declaration *LayoutFunctionBuilder::mutate( UnionDecl *unionDecl ) {
+		// do not generate layout function for "empty" tag unions
+		if ( unionDecl->get_members().empty() ) return unionDecl;
+		
+		// get parameters that can change layout, exiting early if none
+		std::list< TypeDecl* > otypeParams = takeOtypeOnly( unionDecl->get_parameters() );
+		if ( otypeParams.empty() ) return unionDecl;
+
+		// build layout function signature
+		FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
+		BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
+		PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
+		
+		ObjectDecl *sizeParam = new ObjectDecl( "__sizeof_" + unionDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
+		layoutFnType->get_parameters().push_back( sizeParam );
+		ObjectDecl *alignParam = new ObjectDecl( "__alignof_" + unionDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
+		layoutFnType->get_parameters().push_back( alignParam );
+		addOtypeParams( layoutFnType, otypeParams );
+
+		// build function decl
+		FunctionDecl *layoutDecl = buildLayoutFunctionDecl( unionDecl->get_name(), functionNesting, layoutFnType );
+
+		// calculate union layout in function body
+		addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
+		addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
+		for ( std::list< Declaration* >::const_iterator member = unionDecl->get_members().begin(); member != unionDecl->get_members().end(); ++member ) {
+			DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
+			assert( dwt );
+			
+			// take max member size and global size
+			addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( sizeParam ), new SizeofExpr( dwt->get_type() ) ) );
+			
+			// take max of member alignment and global alignment
+			addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( dwt->get_type() ) ) );
+		}
+		// make sure the type is end-padded to a multiple of its alignment
+		addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
+
+		addDeclarationAfter( layoutDecl );
+		return unionDecl;
+	}
+	
 	////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////