Index: src/GenPoly/Box.cpp =================================================================== --- src/GenPoly/Box.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) +++ src/GenPoly/Box.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) @@ -0,0 +1,2270 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Box.cpp -- Implement polymorphic function calls and types. +// +// Author : Andrew Beach +// Created On : Thr Oct 6 13:39:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Oct 2 17:00:00 2023 +// Update Count : 0 +// + +#include "Box.h" + +#include "AST/Decl.hpp" // for Decl, FunctionDecl, ... +#include "AST/Expr.hpp" // for AlignofExpr, ConstantExpr, ... +#include "AST/Init.hpp" // for Init, SingleInit +#include "AST/Inspect.hpp" // for getFunctionName +#include "AST/Pass.hpp" // for Pass, WithDeclsToAdd, ... +#include "AST/Stmt.hpp" // for CompoundStmt, ExprStmt, ... +#include "AST/Vector.hpp" // for vector +#include "AST/GenericSubstitution.hpp" // for genericSubstitution +#include "CodeGen/OperatorTable.h" // for isAssignment +#include "Common/ScopedMap.h" // for ScopedMap +#include "Common/UniqueName.h" // for UniqueName +#include "Common/utility.h" // for toCString, group_iterate +#include "GenPoly/FindFunction.h" // for findFunction +#include "GenPoly/GenPoly.h" // for getFunctionType, ... +#include "GenPoly/Lvalue.h" // for generalizedLvalue +#include "GenPoly/ScopedSet.h" // for ScopedSet +#include "GenPoly/ScrubTyVars.h" // for scrubTypeVars, scrubAllTypeVars +#include "ResolvExpr/Unify.h" // for typesCompatible +#include "SymTab/Mangler.h" // for mangle, mangleType + +namespace GenPoly { + +namespace { + +// -------------------------------------------------------------------------- +/// Adds layout-generation functions to polymorphic types. +struct LayoutFunctionBuilder final : + public ast::WithDeclsToAdd<>, + public ast::WithShortCircuiting, + public ast::WithVisitorRef { + void previsit( ast::StructDecl const * decl ); + void previsit( ast::UnionDecl const * decl ); +}; + +/// Get all sized type declarations; those that affect a layout function. +ast::vector takeSizedParams( + ast::vector const & decls ) { + ast::vector sizedParams; + for ( ast::ptr const & decl : decls ) { + if ( decl->isComplete() ) { + sizedParams.emplace_back( decl ); + } + } + return sizedParams; +} + +ast::BasicType * makeSizeAlignType() { + return new ast::BasicType( ast::BasicType::LongUnsignedInt ); +} + +/// Adds parameters for otype size and alignment to a function type. +void addSTypeParams( + ast::vector & params, + ast::vector const & sizedParams ) { + for ( ast::ptr const & sizedParam : sizedParams ) { + ast::TypeInstType inst( sizedParam ); + std::string paramName = Mangle::mangleType( &inst ); + params.emplace_back( new ast::ObjectDecl( + sizedParam->location, + sizeofName( paramName ), + makeSizeAlignType() + ) ); + params.emplace_back( new ast::ObjectDecl( + sizedParam->location, + alignofName( paramName ), + makeSizeAlignType() + ) ); + } +} + +ast::Type * makeSizeAlignOutType() { + return new ast::PointerType( makeSizeAlignType() ); +} + +struct LayoutData { + ast::FunctionDecl * function; + ast::ObjectDecl * sizeofParam; + ast::ObjectDecl * alignofParam; + ast::ObjectDecl * offsetofParam; +}; + +LayoutData buildLayoutFunction( + CodeLocation const & location, ast::AggregateDecl const * aggr, + ast::vector const & sizedParams, + bool isInFunction, bool isStruct ) { + ast::ObjectDecl * sizeParam = new ast::ObjectDecl( + location, + sizeofName( aggr->name ), + makeSizeAlignOutType() + ); + ast::ObjectDecl * alignParam = new ast::ObjectDecl( + location, + alignofName( aggr->name ), + makeSizeAlignOutType() + ); + ast::ObjectDecl * offsetParam = nullptr; + ast::vector params = { sizeParam, alignParam }; + if ( isStruct ) { + offsetParam = new ast::ObjectDecl( + location, + offsetofName( aggr->name ), + makeSizeAlignOutType() + ); + params.push_back( offsetParam ); + } + addSTypeParams( params, sizedParams ); + + // 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. + ast::FunctionDecl * layoutDecl = new ast::FunctionDecl( + location, + layoutofName( aggr ), + {}, // forall + {}, // assertions + std::move( params ), + {}, // returns + new ast::CompoundStmt( location ), + isInFunction ? ast::Storage::Classes() : ast::Storage::Static, + ast::Linkage::AutoGen, + {}, // attrs + ast::Function::Inline, + ast::FixedArgs + ); + layoutDecl->fixUniqueId(); + return LayoutData{ layoutDecl, sizeParam, alignParam, offsetParam }; +} + +/// Makes a binary operation. +ast::Expr * makeOp( CodeLocation const & location, std::string const & name, + ast::Expr const * lhs, ast::Expr const * rhs ) { + return new ast::UntypedExpr( location, + new ast::NameExpr( location, name ), { lhs, rhs } ); +} + +/// Make a binary operation and wrap it in a statement. +ast::Stmt * makeOpStmt( CodeLocation const & location, std::string const & name, + ast::Expr const * lhs, ast::Expr const * rhs ) { + return new ast::ExprStmt( location, makeOp( location, name, lhs, rhs ) ); +} + +/// Returns the dereference of a local pointer variable. +ast::Expr * derefVar( + CodeLocation const & location, ast::ObjectDecl const * var ) { + return ast::UntypedExpr::createDeref( location, + new ast::VariableExpr( location, var ) ); +} + +/// Makes an if-statement with a single-expression then and no else. +ast::Stmt * makeCond( CodeLocation const & location, + ast::Expr const * cond, ast::Expr const * thenPart ) { + return new ast::IfStmt( location, + cond, new ast::ExprStmt( location, thenPart ), nullptr ); +} + +/// Makes a statement that aligns lhs to rhs (rhs should be an integer +/// power of two). +ast::Stmt * makeAlignTo( CodeLocation const & location, + ast::Expr const * lhs, ast::Expr const * rhs ) { + // Check that the lhs is zeroed out to the level of rhs. + ast::Expr * ifCond = makeOp( location, "?&?", lhs, + makeOp( location, "?-?", rhs, + ast::ConstantExpr::from_ulong( location, 1 ) ) ); + // If not aligned, increment to alignment. + ast::Expr * ifExpr = makeOp( location, "?+=?", ast::deepCopy( lhs ), + makeOp( location, "?-?", ast::deepCopy( rhs ), + ast::deepCopy( ifCond ) ) ); + return makeCond( location, ifCond, ifExpr ); +} + +/// Makes a statement that assigns rhs to lhs if lhs < rhs. +ast::Stmt * makeAssignMax( CodeLocation const & location, + ast::Expr const * lhs, ast::Expr const * rhs ) { + return makeCond( location, + makeOp( location, "?members.empty() ) return; + + // Get parameters that can change layout, exiting early if none. + ast::vector sizedParams = + takeSizedParams( decl->params ); + if ( sizedParams.empty() ) return; + + CodeLocation const & location = decl->location; + + // Build layout function signature. + LayoutData layout = buildLayoutFunction( + location, decl, sizedParams, isInFunction(), true ); + ast::FunctionDecl * layoutDecl = layout.function; + // Also return these or extract them from the parameter list? + ast::ObjectDecl const * sizeofParam = layout.sizeofParam; + ast::ObjectDecl const * alignofParam = layout.alignofParam; + ast::ObjectDecl const * offsetofParam = layout.offsetofParam; + assert( nullptr != layout.offsetofParam ); + + // Calculate structure layout in function body. + // Initialize size and alignment to 0 and 1 + // (Will have at least one member to update size). + auto & kids = layoutDecl->stmts.get_and_mutate()->kids; + kids.emplace_back( makeOpStmt( location, "?=?", + derefVar( location, sizeofParam ), + ast::ConstantExpr::from_ulong( location, 0 ) + ) ); + kids.emplace_back( makeOpStmt( location, "?=?", + derefVar( location, alignofParam ), + ast::ConstantExpr::from_ulong( location, 1 ) + ) ); + // TODO: Polymorphic types will be out of the struct declaration scope. + // Should be removed by PolyGenericCalculator. + for ( auto const & member : enumerate( decl->members ) ) { + auto dwt = member.val.strict_as(); + ast::Type const * memberType = dwt->get_type(); + + if ( 0 < member.idx ) { + // Make sure all later members have padding to align them. + kids.emplace_back( makeAlignTo( location, + derefVar( location, sizeofParam ), + new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) + ) ); + } + + // Place current size in the current offset index. + kids.emplace_back( makeOpStmt( location, "?=?", + makeOp( location, "?[?]", + new ast::VariableExpr( location, offsetofParam ), + ast::ConstantExpr::from_ulong( location, member.idx ) ), + derefVar( location, sizeofParam ) ) ); + + // Add member size to current size. + kids.emplace_back( makeOpStmt( location, "?+=?", + derefVar( location, sizeofParam ), + new ast::SizeofExpr( location, ast::deepCopy( memberType ) ) ) ); + + // Take max of member alignment and global alignment. + // (As align is always 2^n, this will always be a multiple of both.) + kids.emplace_back( makeAssignMax( location, + derefVar( location, alignofParam ), + new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) ) ); + } + // Make sure the type is end-padded to a multiple of its alignment. + kids.emplace_back( makeAlignTo( location, + derefVar( location, sizeofParam ), + derefVar( location, alignofParam ) ) ); + + declsToAddAfter.emplace_back( layoutDecl ); +} + +void LayoutFunctionBuilder::previsit( ast::UnionDecl const * decl ) { + visit_children = false; + // Do not generate layout function for empty tag unions. + if ( decl->members.empty() ) return; + + // Get parameters that can change layout, exiting early if none. + ast::vector sizedParams = + takeSizedParams( decl->params ); + if ( sizedParams.empty() ) return; + + CodeLocation const & location = decl->location; + + // Build layout function signature. + LayoutData layout = buildLayoutFunction( + location, decl, sizedParams, isInFunction(), false ); + ast::FunctionDecl * layoutDecl = layout.function; + // Also return these or extract them from the parameter list? + ast::ObjectDecl const * sizeofParam = layout.sizeofParam; + ast::ObjectDecl const * alignofParam = layout.alignofParam; + assert( nullptr == layout.offsetofParam ); + + // Calculate union layout in function body. + // Both are simply the maximum for union (actually align is always the + // LCM, but with powers of two that is also the maximum). + auto & kids = layoutDecl->stmts.get_and_mutate()->kids; + kids.emplace_back( makeOpStmt( location, + "?=?", derefVar( location, sizeofParam ), + ast::ConstantExpr::from_ulong( location, 1 ) + ) ); + kids.emplace_back( makeOpStmt( location, + "?=?", derefVar( location, alignofParam ), + ast::ConstantExpr::from_ulong( location, 1 ) + ) ); + // TODO: Polymorphic types will be out of the union declaration scope. + for ( auto const & member : decl->members ) { + auto dwt = member.strict_as(); + ast::Type const * memberType = dwt->get_type(); + + // Take max member size and global size. + kids.emplace_back( makeAssignMax( location, + derefVar( location, sizeofParam ), + new ast::SizeofExpr( location, ast::deepCopy( memberType ) ) + ) ); + + // Take max of member alignment and global alignment. + kids.emplace_back( makeAssignMax( location, + derefVar( location, alignofParam ), + new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) + ) ); + } + kids.emplace_back( makeAlignTo( location, + derefVar( location, sizeofParam ), + derefVar( location, alignofParam ) ) ); + + declsToAddAfter.emplace_back( layoutDecl ); +} + +// -------------------------------------------------------------------------- +/// Application expression transformer. +/// * Replaces polymorphic return types with out-parameters. +/// * Replaces call to polymorphic functions with adapter calls which handles +/// dynamic arguments and return values. +/// * Adds appropriate type variables to the function calls. +struct CallAdapter final : + public ast::WithConstTypeSubstitution, + public ast::WithGuards, + public ast::WithShortCircuiting, + public ast::WithStmtsToAdd<>, + public ast::WithVisitorRef { + CallAdapter(); + + void previsit( ast::Decl const * decl ); + ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); + void previsit( ast::TypeDecl const * decl ); + void previsit( ast::CommaExpr const * expr ); + ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); + ast::Expr const * postvisit( ast::UntypedExpr const * expr ); + void previsit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::AddressExpr const * expr ); + ast::ReturnStmt const * previsit( ast::ReturnStmt const * stmt ); + + void beginScope(); + void endScope(); +private: + // Many helpers here use a mutable ApplicationExpr as an in/out parameter + // instead of using the return value, to save on mutates and free up the + // return value. + + /// Passes extra layout arguments for sized polymorphic type parameters. + ast::vector::iterator passTypeVars( + ast::ApplicationExpr * expr, + ast::FunctionType const * funcType ); + /// Wraps a function application with a new temporary for the + /// out-parameter return value. + ast::Expr const * addRetParam( + ast::ApplicationExpr * expr, ast::Type const * retType ); + /// Wraps a function application returning a polymorphic type with a new + /// temporary for the out-parameter return value. + ast::Expr const * addDynRetParam( + ast::ApplicationExpr * expr, ast::Type const * polyType ); + /// Modify a call so it passes the function through the correct adapter. + ast::Expr const * applyAdapter( + ast::ApplicationExpr * expr, + ast::FunctionType const * function ); + /// Convert a single argument into its boxed form to pass the parameter. + void boxParam( ast::ptr & arg, + ast::Type const * formal, TypeVarMap const & exprTyVars ); + /// Box every argument from arg forward, matching the functionType + /// parameter list. arg should point into expr's argument list. + void boxParams( + ast::ApplicationExpr const * expr, + ast::vector::iterator arg, + ast::FunctionType const * function, + const TypeVarMap & typeVars ); + /// Adds the inferred parameters derived from the assertions of the + /// expression to the call. + void addInferredParams( + ast::ApplicationExpr * expr, + ast::vector::iterator arg, + ast::FunctionType const * functionType, + const TypeVarMap & typeVars ); + /// Stores assignment operators from assertion list in + /// local map of assignment operations. + void passAdapters( + ast::ApplicationExpr * expr, + ast::FunctionType const * type, + const TypeVarMap & typeVars ); + /// Create an adapter function based on the type of the adaptee and the + /// real type with the type substitutions applied. + ast::FunctionDecl * makeAdapter( + ast::FunctionType const * adaptee, + ast::FunctionType const * realType, + std::string const & mangleName, + TypeVarMap const & typeVars, + CodeLocation const & location ) const; + /// Replaces intrinsic operator functions with their arithmetic desugaring. + ast::Expr const * handleIntrinsics( ast::ApplicationExpr const * ); + /// Inserts a new temporary variable into the current scope with an + /// auto-generated name. + ast::ObjectDecl * makeTemporary( + CodeLocation const & location, ast::Type const * type ); + + TypeVarMap scopeTypeVars; + ScopedMap< std::string, ast::DeclWithType const * > adapters; + std::map< ast::ApplicationExpr const *, ast::Expr const * > retVals; + ast::DeclWithType const * retval; + UniqueName tmpNamer; +}; + +/// Replaces a polymorphic type with its concrete equivalant under the +/// current environment (returns itself if concrete). +/// If `doClone` is set to false, will not clone interior types +ast::Type const * replaceWithConcrete( + ast::Type const * type, + ast::TypeSubstitution const & typeSubs, + bool doCopy = true ); + +/// Replaces all the type parameters of a generic type with their +/// concrete equivalents under the current environment. +void replaceParametersWithConcrete( + ast::vector & params, + ast::TypeSubstitution const & typeSubs ) { + for ( ast::ptr & paramExpr : params ) { + ast::TypeExpr const * param = paramExpr.as(); + assertf( param, "Aggregate parameters should be type expressions." ); + paramExpr = ast::mutate_field( param, &ast::TypeExpr::type, + replaceWithConcrete( param->type.get(), typeSubs, false ) ); + } +} + +ast::Type const * replaceWithConcrete( + ast::Type const * type, + ast::TypeSubstitution const & typeSubs, + bool doCopy ) { + if ( auto instType = dynamic_cast( type ) ) { + ast::Type const * concrete = typeSubs.lookup( instType ); + return ( nullptr != concrete ) ? concrete : instType; + } else if ( auto structType = + dynamic_cast( type ) ) { + ast::StructInstType * newType = + doCopy ? ast::deepCopy( structType ) : ast::mutate( structType ); + replaceParametersWithConcrete( newType->params, typeSubs ); + return newType; + } else if ( auto unionType = + dynamic_cast( type ) ) { + ast::UnionInstType * newType = + doCopy ? ast::deepCopy( unionType ) : ast::mutate( unionType ); + replaceParametersWithConcrete( newType->params, typeSubs ); + return newType; + } else { + return type; + } +} + +std::string makePolyMonoSuffix( + ast::FunctionType const * function, + TypeVarMap const & typeVars ) { + // If the return type or a parameter type involved polymorphic types, + // then the adapter will need to take those polymorphic types as pointers. + // Therefore, there can be two different functions with the same mangled + // name, so we need to further mangle the names. + std::stringstream name; + for ( auto ret : function->returns ) { + name << ( isPolyType( ret, typeVars ) ? 'P' : 'M' ); + } + name << '_'; + for ( auto arg : function->params ) { + name << ( isPolyType( arg, typeVars ) ? 'P' : 'M' ); + } + return name.str(); +} + +std::string mangleAdapterName( + ast::FunctionType const * function, + TypeVarMap const & typeVars ) { + return Mangle::mangle( function, {} ) + + makePolyMonoSuffix( function, typeVars ); +} + +std::string makeAdapterName( std::string const & mangleName ) { + return "_adapter" + mangleName; +} + +void makeRetParam( ast::FunctionType * type ) { + ast::ptr & retParam = type->returns.front(); + + // Make a new parameter that is a pointer to the type of the old return value. + retParam = new ast::PointerType( retParam.get() ); + type->params.emplace( type->params.begin(), retParam ); + + // We don't need the return value any more. + type->returns.clear(); +} + +ast::FunctionType * makeAdapterType( + ast::FunctionType const * adaptee, + TypeVarMap const & typeVars ) { + ast::FunctionType * adapter = ast::deepCopy( adaptee ); + if ( isDynRet( adapter, typeVars ) ) { + makeRetParam( adapter ); + } + adapter->params.emplace( adapter->params.begin(), + new ast::PointerType( new ast::FunctionType( ast::VariableArgs ) ) + ); + return adapter; +} + +CallAdapter::CallAdapter() : tmpNamer( "_temp" ) {} + +void CallAdapter::previsit( ast::Decl const * ) { + // Prevent type declaration information from leaking out. + GuardScope( scopeTypeVars ); +} + +ast::FunctionDecl const * CallAdapter::previsit( ast::FunctionDecl const * decl ) { + // Prevent type declaration information from leaking out. + GuardScope( scopeTypeVars ); + + if ( nullptr == decl->stmts ) { + return decl; + } + + GuardValue( retval ); + + // Process polymorphic return value. + retval = nullptr; + ast::FunctionType const * type = decl->type; + if ( isDynRet( type ) && decl->linkage != ast::Linkage::C ) { + retval = decl->returns.front(); + + // Give names to unnamed return values. + if ( "" == retval->name ) { + auto mutRet = ast::mutate( retval ); + mutRet->name = "_retparam"; + mutRet->linkage = ast::Linkage::C; + retval = mutRet; + decl = ast::mutate_field_index( decl, + &ast::FunctionDecl::returns, 0, mutRet ); + } + } + + // The formal_usage/expr_id values may be off if we get them from the + // type, trying the declaration instead. + makeTypeVarMap( type, scopeTypeVars ); + + // Get all needed adapters from the call. We will forward them. + ast::vector functions; + for ( ast::ptr const & assertion : type->assertions ) { + auto atype = assertion->result.get(); + findFunction( atype, functions, scopeTypeVars, needsAdapter ); + } + + for ( ast::ptr const & arg : type->params ) { + findFunction( arg, functions, scopeTypeVars, needsAdapter ); + } + + for ( auto funcType : functions ) { + std::string mangleName = mangleAdapterName( funcType, scopeTypeVars ); + if ( adapters.contains( mangleName ) ) continue; + std::string adapterName = makeAdapterName( mangleName ); + // TODO: The forwarding here is problematic because these + // declarations are not rooted anywhere in the translation unit. + adapters.insert( + mangleName, + new ast::ObjectDecl( + decl->location, + adapterName, + new ast::PointerType( + makeAdapterType( funcType, scopeTypeVars ) ), + nullptr, // init + ast::Storage::Classes(), + ast::Linkage::C + ) + ); + } + + return decl; +} + +void CallAdapter::previsit( ast::TypeDecl const * decl ) { + addToTypeVarMap( decl, scopeTypeVars ); +} + +void CallAdapter::previsit( ast::CommaExpr const * expr ) { + // Attempting to find application expressions that were mutated by the + // copy constructor passes to use an explicit return variable, so that + // the variable can be reused as a parameter to the call rather than + // creating a new temporary variable. Previously this step was an + // optimization, but with the introduction of tuples and UniqueExprs, + // it is necessary to ensure that they use the same variable. + // Essentially, looking for pattern: + // (x=f(...), x) + // To compound the issue, the right side can be *x, etc. + // because of lvalue-returning functions + if ( auto assign = expr->arg1.as() ) { + if ( CodeGen::isAssignment( ast::getFunctionName( assign ) ) ) { + assert( 2 == assign->args.size() ); + if ( auto app = assign->args.back().as() ) { + // First argument is assignable, so it must be an lvalue, + // so it should be legal to takes its address. + retVals.insert_or_assign( app, assign->args.front() ); + } + } + } +} + +ast::Expr const * CallAdapter::postvisit( ast::ApplicationExpr const * expr ) { + assert( expr->func->result ); + ast::FunctionType const * function = getFunctionType( expr->func->result ); + assertf( function, "ApplicationExpr has non-function type %s", + toCString( expr->func->result ) ); + + if ( auto newExpr = handleIntrinsics( expr ) ) { + return newExpr; + } + + ast::ApplicationExpr * mutExpr = ast::mutate( expr ); + ast::Expr const * ret = expr; + + // TODO: This entire section should probably be refactored to do less + // pushing to the front/middle of a vector. + ptrdiff_t initArgCount = mutExpr->args.size(); + + TypeVarMap exprTypeVars; + // TODO: Should this take into account the variables already bound in + // scopeTypeVars ([ex] remove them from exprTypeVars)? + makeTypeVarMap( function, exprTypeVars ); + auto dynRetType = isDynRet( function, exprTypeVars ); + + // NOTE: addDynRetParam needs to know the actual (generated) return type + // so it can make a temporary variable, so pass the result type form the + // `expr` `passTypeVars` needs to know the program-text return type ([ex] + // the distinction between _conc_T30 and T3(int)) concRetType may not be + // a good name in one or both of these places. + if ( dynRetType ) { + ast::Type const * result = mutExpr->result; + ast::Type const * concRetType = result->isVoid() ? nullptr : result; + // [Comment from before translation.] + // Used to use dynRetType instead of concRetType. + ret = addDynRetParam( mutExpr, concRetType ); + } else if ( needsAdapter( function, scopeTypeVars ) + && !needsAdapter( function, exprTypeVars ) ) { + // Change the application so it calls the adapter rather than the + // passed function. + ret = applyAdapter( mutExpr, function ); + } + + assert( typeSubs ); + ast::vector::iterator argIt = + passTypeVars( mutExpr, function ); + addInferredParams( mutExpr, argIt, function, exprTypeVars ); + + argIt = mutExpr->args.begin(); + std::advance( argIt, ( mutExpr->args.size() - initArgCount ) ); + + boxParams( mutExpr, argIt, function, exprTypeVars ); + passAdapters( mutExpr, function, exprTypeVars ); + + return ret; +} + +bool isPolyDeref( ast::UntypedExpr const * expr, + TypeVarMap const & typeVars, + ast::TypeSubstitution const * typeSubs ) { + if ( expr->result && isPolyType( expr->result, typeVars, typeSubs ) ) { + if ( auto name = expr->func.as() ) { + if ( "*?" == name->name ) { + return true; + } + } + } + return false; +} + +ast::Expr const * CallAdapter::postvisit( ast::UntypedExpr const * expr ) { + if ( isPolyDeref( expr, scopeTypeVars, typeSubs ) ) { + return expr->args.front(); + } + return expr; +} + +void CallAdapter::previsit( ast::AddressExpr const * ) { + visit_children = false; +} + +ast::Expr const * CallAdapter::postvisit( ast::AddressExpr const * expr ) { + assert( expr->arg->result ); + assert( !expr->arg->result->isVoid() ); + + bool doesNeedAdapter = false; + if ( auto un = expr->arg.as() ) { + if ( isPolyDeref( un, scopeTypeVars, typeSubs ) ) { + if ( auto app = un->args.front().as() ) { + assert( app->func->result ); + auto function = getFunctionType( app->func->result ); + assert( function ); + doesNeedAdapter = needsAdapter( function, scopeTypeVars ); + } + } + } + // isPolyType check needs to happen before mutating expr arg, + // so pull it forward out of the if condition. + expr = ast::mutate_field( expr, &ast::AddressExpr::arg, + expr->arg->accept( *visitor ) ); + // But must happen after mutate, since argument might change + // (ex. intrinsic *?, ?[?]) re-evaluate above comment. + bool polyType = isPolyType( expr->arg->result, scopeTypeVars, typeSubs ); + if ( polyType || doesNeedAdapter ) { + ast::Expr * ret = ast::mutate( expr->arg.get() ); + ret->result = ast::deepCopy( expr->result ); + return ret; + } else { + return expr; + } +} + +ast::ReturnStmt const * CallAdapter::previsit( ast::ReturnStmt const * stmt ) { + // Since retval is set when the return type is dynamic, this function + // should have been converted to void return & out parameter. + if ( retval && stmt->expr ) { + assert( stmt->expr->result ); + assert( !stmt->expr->result->isVoid() ); + return ast::mutate_field( stmt, &ast::ReturnStmt::expr, nullptr ); + } + return stmt; +} + +void CallAdapter::beginScope() { + adapters.beginScope(); +} + +void CallAdapter::endScope() { + adapters.endScope(); +} + +/// Find instances of polymorphic type parameters. +struct PolyFinder { + TypeVarMap const & typeVars; + bool result = false; + PolyFinder( TypeVarMap const & tvs ) : typeVars( tvs ) {} + + void previsit( ast::TypeInstType const * type ) { + if ( isPolyType( type, typeVars ) ) result = true; + } +}; + +/// True if these is an instance of a polymorphic type parameter in the type. +bool hasPolymorphism( ast::Type const * type, TypeVarMap const & typeVars ) { + return ast::Pass::read( type, typeVars ); +} + +ast::vector::iterator CallAdapter::passTypeVars( + ast::ApplicationExpr * expr, + ast::FunctionType const * function ) { + assert( typeSubs ); + ast::vector::iterator arg = expr->args.begin(); + // Pass size/align for type variables. + for ( ast::ptr const & typeVar : function->forall ) { + if ( !typeVar->base->isComplete() ) continue; + ast::Type const * concrete = typeSubs->lookup( typeVar ); + if ( !concrete ) { + // Should this be an assertion? + SemanticError( expr, toString( typeSubs, + "\nunbound type variable: ", typeVar->typeString(), + " in application " ) ); + } + arg = expr->args.insert( arg, + new ast::SizeofExpr( expr->location, ast::deepCopy( concrete ) ) ); + arg++; + arg = expr->args.insert( arg, + new ast::AlignofExpr( expr->location, ast::deepCopy( concrete ) ) ); + arg++; + } + return arg; +} + +ast::Expr const * CallAdapter::addRetParam( + ast::ApplicationExpr * expr, ast::Type const * retType ) { + // Create temporary to hold return value of polymorphic function and + // produce that temporary as a result using a comma expression. + assert( retType ); + + ast::Expr * paramExpr = nullptr; + // Try to use existing return value parameter if it exists, + // otherwise create a new temporary. + if ( retVals.count( expr ) ) { + paramExpr = ast::deepCopy( retVals[ expr ] ); + } else { + auto newObj = makeTemporary( expr->location, ast::deepCopy( retType ) ); + paramExpr = new ast::VariableExpr( expr->location, newObj ); + } + ast::Expr * retExpr = ast::deepCopy( paramExpr ); + + // If the type of the temporary is not polpmorphic, box temporary by + // taking its address; otherwise the temporary is already boxed and can + // be used directly. + if ( !isPolyType( paramExpr->result, scopeTypeVars, typeSubs ) ) { + paramExpr = new ast::AddressExpr( paramExpr->location, paramExpr ); + } + // Add argument to function call. + expr->args.insert( expr->args.begin(), paramExpr ); + // Build a comma expression to call the function and return a value. + ast::CommaExpr * comma = new ast::CommaExpr( + expr->location, expr, retExpr ); + comma->env = expr->env; + expr->env = nullptr; + return comma; +} + +ast::Expr const * CallAdapter::addDynRetParam( + ast::ApplicationExpr * expr, ast::Type const * polyType ) { + assert( typeSubs ); + ast::Type const * concrete = replaceWithConcrete( polyType, *typeSubs ); + // Add out-parameter for return value. + return addRetParam( expr, concrete ); +} + +ast::Expr const * CallAdapter::applyAdapter( + ast::ApplicationExpr * expr, + ast::FunctionType const * function ) { + ast::Expr const * ret = expr; + if ( isDynRet( function, scopeTypeVars ) ) { + ret = addRetParam( expr, function->returns.front() ); + } + std::string mangleName = mangleAdapterName( function, scopeTypeVars ); + std::string adapterName = makeAdapterName( mangleName ); + + // Cast adaptee to `void (*)()`, since it may have any type inside a + // polymorphic function. + ast::Type const * adapteeType = new ast::PointerType( + new ast::FunctionType( ast::VariableArgs ) ); + expr->args.insert( expr->args.begin(), + new ast::CastExpr( expr->location, expr->func, adapteeType ) ); + // The result field is never set on NameExpr. / Now it is. + auto head = new ast::NameExpr( expr->location, adapterName ); + head->result = ast::deepCopy( adapteeType ); + expr->func = head; + + return ret; +} + +/// Cast parameters to polymorphic functions so that types are replaced with +/// `void *` if they are type parameters in the formal type. +/// This gets rid of warnings from gcc. +void addCast( + ast::ptr & actual, + ast::Type const * formal, + TypeVarMap const & typeVars ) { + // Type contains polymorphism, but isn't exactly a polytype, in which + // case it has some real actual type (ex. unsigned int) and casting to + // `void *` is wrong. + if ( hasPolymorphism( formal, typeVars ) + && !isPolyType( formal, typeVars ) ) { + ast::Type const * newType = ast::deepCopy( formal ); + newType = scrubTypeVars( newType, typeVars ); + actual = new ast::CastExpr( actual->location, actual, newType ); + } +} + +void CallAdapter::boxParam( ast::ptr & arg, + ast::Type const * param, TypeVarMap const & exprTypeVars ) { + assertf( arg->result, "arg does not have result: %s", toCString( arg ) ); + addCast( arg, param, exprTypeVars ); + if ( !needsBoxing( param, arg->result, exprTypeVars, typeSubs ) ) { + return; + } + CodeLocation const & location = arg->location; + + if ( arg->get_lvalue() ) { + // The argument expression may be CFA lvalue, but not C lvalue, + // so apply generalizedLvalue transformations. + // if ( auto var = dynamic_cast( arg ) ) { + // if ( dynamic_cast( varExpr->var->get_type() ) ){ + // // temporary hack - don't box arrays, because &arr is not the same as &arr[0] + // return; + // } + // } + arg = generalizedLvalue( new ast::AddressExpr( arg->location, arg ) ); + if ( !ResolvExpr::typesCompatible( param, arg->result ) ) { + // Silence warnings by casting boxed parameters when the actually + // type does not match up with the formal type. + arg = new ast::CastExpr( location, arg, ast::deepCopy( param ) ); + } + } else { + // Use type computed in unification to declare boxed variables. + ast::ptr newType = ast::deepCopy( param ); + if ( typeSubs ) typeSubs->apply( newType ); + ast::ObjectDecl * newObj = makeTemporary( location, newType ); + auto assign = ast::UntypedExpr::createCall( location, "?=?", { + new ast::VariableExpr( location, newObj ), + arg, + } ); + stmtsToAddBefore.push_back( new ast::ExprStmt( location, assign ) ); + arg = new ast::AddressExpr( + new ast::VariableExpr( location, newObj ) ); + } +} + +void CallAdapter::boxParams( + ast::ApplicationExpr const * expr, + ast::vector::iterator arg, + ast::FunctionType const * function, + const TypeVarMap & typeVars ) { + for ( auto param : function->params ) { + assertf( arg != expr->args.end(), + "boxParams: missing argument for param %s to %s in %s", + toCString( param ), toCString( function ), toCString( expr ) ); + boxParam( *arg, param, typeVars ); + ++arg; + } +} + +void CallAdapter::addInferredParams( + ast::ApplicationExpr * expr, + ast::vector::iterator arg, + ast::FunctionType const * functionType, + TypeVarMap const & typeVars ) { + ast::vector::iterator cur = arg; + for ( auto assertion : functionType->assertions ) { + auto inferParam = expr->inferred.inferParams().find( + assertion->var->uniqueId ); + assertf( inferParam != expr->inferred.inferParams().end(), + "addInferredParams missing inferred parameter: %s in: %s", + toCString( assertion ), toCString( expr ) ); + ast::ptr newExpr = ast::deepCopy( inferParam->second.expr ); + boxParam( newExpr, assertion->result, typeVars ); + cur = expr->args.insert( cur, newExpr.release() ); + ++cur; + } +} + +/// Modifies the ApplicationExpr to accept adapter functions for its +/// assertion and parameters, declares the required adapters. +void CallAdapter::passAdapters( + ast::ApplicationExpr * expr, + ast::FunctionType const * type, + const TypeVarMap & exprTypeVars ) { + // Collect a list of function types passed as parameters or implicit + // parameters (assertions). + ast::vector const & paramList = type->params; + ast::vector functions; + + for ( ast::ptr const & assertion : type->assertions ) { + findFunction( assertion->result, functions, exprTypeVars, needsAdapter ); + } + for ( ast::ptr const & arg : paramList ) { + findFunction( arg, functions, exprTypeVars, needsAdapter ); + } + + // Parameter function types for which an appropriate adapter has been + // generated. We cannot use the types after applying substitutions, + // since two different parameter types may be unified to the same type. + std::set adaptersDone; + + CodeLocation const & location = expr->location; + + for ( ast::ptr const & funcType : functions ) { + std::string mangleName = Mangle::mangle( funcType ); + + // Only attempt to create an adapter or pass one as a parameter if we + // haven't already done so for this pre-substitution parameter + // function type. + // The second part of the result if is if the element was inserted. + if ( !adaptersDone.insert( mangleName ).second ) continue; + + // Apply substitution to type variables to figure out what the + // adapter's type should look like. (Copy to make the release safe.) + assert( typeSubs ); + auto result = typeSubs->apply( ast::deepCopy( funcType ) ); + ast::FunctionType * realType = ast::mutate( result.node.release() ); + mangleName = Mangle::mangle( realType ); + mangleName += makePolyMonoSuffix( funcType, exprTypeVars ); + + // Check if the adapter has already been created, or has to be. + using AdapterIter = decltype(adapters)::iterator; + AdapterIter adapter = adapters.find( mangleName ); + if ( adapter == adapters.end() ) { + ast::FunctionDecl * newAdapter = makeAdapter( + funcType, realType, mangleName, exprTypeVars, location ); + std::pair answer = + adapters.insert( mangleName, newAdapter ); + adapter = answer.first; + stmtsToAddBefore.push_back( + new ast::DeclStmt( location, newAdapter ) ); + } + assert( adapter != adapters.end() ); + + // Add the approprate adapter as a parameter. + expr->args.insert( expr->args.begin(), + new ast::VariableExpr( location, adapter->second ) ); + } +} + +// Parameter and argument may be used wrong around here. +ast::Expr * makeAdapterArg( + ast::DeclWithType const * param, + ast::Type const * arg, + ast::Type const * realParam, + TypeVarMap const & typeVars, + CodeLocation const & location ) { + assert( param ); + assert( arg ); + assert( realParam ); + if ( isPolyType( realParam, typeVars ) && !isPolyType( arg ) ) { + ast::UntypedExpr * deref = ast::UntypedExpr::createDeref( + location, + new ast::CastExpr( location, + new ast::VariableExpr( location, param ), + new ast::PointerType( ast::deepCopy( arg ) ) + ) + ); + deref->result = ast::deepCopy( arg ); + return deref; + } + return new ast::VariableExpr( location, param ); +} + +// This seems to be one of the problematic functions. +void addAdapterParams( + ast::ApplicationExpr * adaptee, + ast::vector::const_iterator arg, + ast::vector::iterator param, + ast::vector::iterator paramEnd, + ast::vector::const_iterator realParam, + TypeVarMap const & typeVars, + CodeLocation const & location ) { + UniqueName paramNamer( "_p" ); + for ( ; param != paramEnd ; ++param, ++arg, ++realParam ) { + if ( "" == (*param)->name ) { + auto mutParam = (*param).get_and_mutate(); + mutParam->name = paramNamer.newName(); + mutParam->linkage = ast::Linkage::C; + } + adaptee->args.push_back( + makeAdapterArg( *param, *arg, *realParam, typeVars, location ) ); + } +} + +ast::FunctionDecl * CallAdapter::makeAdapter( + ast::FunctionType const * adaptee, + ast::FunctionType const * realType, + std::string const & mangleName, + TypeVarMap const & typeVars, + CodeLocation const & location ) const { + ast::FunctionType * adapterType = makeAdapterType( adaptee, typeVars ); + adapterType = ast::mutate( scrubTypeVars( adapterType, typeVars ) ); + + // Some of these names will be overwritten, but it gives a default. + UniqueName pNamer( "_param" ); + UniqueName rNamer( "_ret" ); + + bool first = true; + + ast::FunctionDecl * adapterDecl = new ast::FunctionDecl( location, + makeAdapterName( mangleName ), + {}, // forall + {}, // assertions + map_range>( adapterType->params, + [&pNamer, &location, &first]( ast::ptr const & param ) { + // [Trying to make the generated code match exactly more often.] + if ( first ) { + first = false; + return new ast::ObjectDecl( location, "_adaptee", param ); + } + return new ast::ObjectDecl( location, pNamer.newName(), param ); + } ), + map_range>( adapterType->returns, + [&rNamer, &location]( ast::ptr const & retval ) { + return new ast::ObjectDecl( location, rNamer.newName(), retval ); + } ), + nullptr, // stmts + {}, // storage + ast::Linkage::C + ); + + ast::DeclWithType * adapteeDecl = + adapterDecl->params.front().get_and_mutate(); + adapteeDecl->name = "_adaptee"; + + // Do not carry over attributes to real type parameters/return values. + auto mutRealType = ast::mutate( realType ); + for ( ast::ptr & decl : mutRealType->params ) { + if ( decl->attributes.empty() ) continue; + auto mut = ast::mutate( decl.get() ); + mut->attributes.clear(); + decl = mut; + } + for ( ast::ptr & decl : mutRealType->returns ) { + if ( decl->attributes.empty() ) continue; + auto mut = ast::mutate( decl.get() ); + mut->attributes.clear(); + decl = mut; + } + realType = mutRealType; + + ast::ApplicationExpr * adapteeApp = new ast::ApplicationExpr( location, + new ast::CastExpr( location, + new ast::VariableExpr( location, adapteeDecl ), + new ast::PointerType( realType ) + ) + ); + + for ( auto group : group_iterate( realType->assertions, + adapterType->assertions, adaptee->assertions ) ) { + auto assertArg = std::get<0>( group ); + auto assertParam = std::get<1>( group ); + auto assertReal = std::get<2>( group ); + adapteeApp->args.push_back( makeAdapterArg( + assertParam->var, assertArg->var->get_type(), + assertReal->var->get_type(), typeVars, location + ) ); + } + + ast::vector::const_iterator + arg = realType->params.begin(), + param = adapterType->params.begin(), + realParam = adaptee->params.begin(); + ast::vector::iterator + paramDecl = adapterDecl->params.begin(); + // Skip adaptee parameter in the adapter type. + ++param; + ++paramDecl; + + ast::Stmt * bodyStmt; + // Returns void/nothing. + if ( realType->returns.empty() ) { + addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), + realParam, typeVars, location ); + bodyStmt = new ast::ExprStmt( location, adapteeApp ); + // Returns a polymorphic type. + } else if ( isDynType( adaptee->returns.front(), typeVars ) ) { + ast::UntypedExpr * assign = new ast::UntypedExpr( location, + new ast::NameExpr( location, "?=?" ) ); + ast::UntypedExpr * deref = ast::UntypedExpr::createDeref( location, + new ast::CastExpr( location, + new ast::VariableExpr( location, *paramDecl++ ), + new ast::PointerType( + ast::deepCopy( realType->returns.front() ) ) ) ); + assign->args.push_back( deref ); + addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), + realParam, typeVars, location ); + assign->args.push_back( adapteeApp ); + bodyStmt = new ast::ExprStmt( location, assign ); + // Adapter for a function that returns a monomorphic value. + } else { + addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), + realParam, typeVars, location ); + bodyStmt = new ast::ReturnStmt( location, adapteeApp ); + } + + adapterDecl->stmts = new ast::CompoundStmt( location, { bodyStmt } ); + return adapterDecl; +} + +ast::Expr const * makeIncrDecrExpr( + CodeLocation const & location, + ast::ApplicationExpr const * expr, + ast::Type const * polyType, + bool isIncr ) { + ast::NameExpr * opExpr = + new ast::NameExpr( location, isIncr ? "?+=?" : "?-=?" ); + ast::UntypedExpr * addAssign = new ast::UntypedExpr( location, opExpr ); + if ( auto address = expr->args.front().as() ) { + addAssign->args.push_back( address->arg ); + } else { + addAssign->args.push_back( expr->args.front() ); + } + addAssign->args.push_back( new ast::NameExpr( location, + sizeofName( Mangle::mangleType( polyType ) ) ) ); + addAssign->result = ast::deepCopy( expr->result ); + addAssign->env = expr->env ? expr->env : addAssign->env; + return addAssign; +} + +/// Handles intrinsic functions for postvisit ApplicationExpr. +ast::Expr const * CallAdapter::handleIntrinsics( + ast::ApplicationExpr const * expr ) { + auto varExpr = expr->func.as(); + if ( !varExpr || varExpr->var->linkage != ast::Linkage::Intrinsic ) { + return nullptr; + } + std::string const & varName = varExpr->var->name; + + // Index Intrinsic: + if ( "?[?]" == varName ) { + assert( expr->result ); + assert( 2 == expr->args.size() ); + + ast::Type const * baseType1 = + isPolyPtr( expr->args.front()->result, scopeTypeVars, typeSubs ); + ast::Type const * baseType2 = + isPolyPtr( expr->args.back()->result, scopeTypeVars, typeSubs ); + // If neither argument is a polymorphic pointer, do nothing. + if ( !baseType1 && !baseType2 ) { + return expr; + } + // The arguments cannot both be polymorphic pointers. + assert( !baseType1 || !baseType2 ); + // (So exactly one of the arguments is a polymorphic pointer.) + + CodeLocation const & location = expr->location; + CodeLocation const & location1 = expr->args.front()->location; + CodeLocation const & location2 = expr->args.back()->location; + + ast::UntypedExpr * ret = new ast::UntypedExpr( location, + new ast::NameExpr( location, "?+?" ) ); + if ( baseType1 ) { + auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { + expr->args.back(), + new ast::SizeofExpr( location1, deepCopy( baseType1 ) ), + } ); + ret->args.push_back( expr->args.front() ); + ret->args.push_back( multiply ); + } else { + assert( baseType2 ); + auto multiply = ast::UntypedExpr::createCall( location1, "?*?", { + expr->args.front(), + new ast::SizeofExpr( location2, deepCopy( baseType2 ) ), + } ); + ret->args.push_back( multiply ); + ret->args.push_back( expr->args.back() ); + } + ret->result = ast::deepCopy( expr->result ); + ret->env = expr->env ? expr->env : ret->env; + return ret; + // Dereference Intrinsic: + } else if ( "*?" == varName ) { + assert( expr->result ); + assert( 1 == expr->args.size() ); + + // If this isn't for a poly type, then do nothing. + if ( !isPolyType( expr->result, scopeTypeVars, typeSubs ) ) { + return expr; + } + + // Remove dereference from polymorphic types since they are boxed. + ast::Expr * ret = ast::deepCopy( expr->args.front() ); + // Fix expression type to remove pointer. + ret->result = expr->result; + ret->env = expr->env ? expr->env : ret->env; + return ret; + // Post-Increment/Decrement Intrinsics: + } else if ( "?++" == varName || "?--" == varName ) { + assert( expr->result ); + assert( 1 == expr->args.size() ); + + ast::Type const * baseType = + isPolyType( expr->result, scopeTypeVars, typeSubs ); + if ( nullptr == baseType ) { + return expr; + } + ast::Type * tempType = ast::deepCopy( expr->result ); + if ( typeSubs ) { + auto result = typeSubs->apply( tempType ); + tempType = ast::mutate( result.node.release() ); + } + CodeLocation const & location = expr->location; + ast::ObjectDecl * newObj = makeTemporary( location, tempType ); + ast::VariableExpr * tempExpr = + new ast::VariableExpr( location, newObj ); + ast::UntypedExpr * assignExpr = new ast::UntypedExpr( location, + new ast::NameExpr( location, "?=?" ) ); + assignExpr->args.push_back( ast::deepCopy( tempExpr ) ); + if ( auto address = expr->args.front().as() ) { + assignExpr->args.push_back( ast::deepCopy( address->arg ) ); + } else { + assignExpr->args.push_back( ast::deepCopy( expr->args.front() ) ); + } + return new ast::CommaExpr( location, + new ast::CommaExpr( location, + assignExpr, + makeIncrDecrExpr( location, expr, baseType, "?++" == varName ) + ), + tempExpr + ); + // Pre-Increment/Decrement Intrinsics: + } else if ( "++?" == varName || "--?" == varName ) { + assert( expr->result ); + assert( 1 == expr->args.size() ); + + ast::Type const * baseType = + isPolyType( expr->result, scopeTypeVars, typeSubs ); + if ( nullptr == baseType ) { + return expr; + } + return makeIncrDecrExpr( + expr->location, expr, baseType, "++?" == varName ); + // Addition and Subtration Intrinsics: + } else if ( "?+?" == varName || "?-?" == varName ) { + assert( expr->result ); + assert( 2 == expr->args.size() ); + + auto baseType1 = + isPolyPtr( expr->args.front()->result, scopeTypeVars, typeSubs ); + auto baseType2 = + isPolyPtr( expr->args.back()->result, scopeTypeVars, typeSubs ); + + CodeLocation const & location = expr->location; + CodeLocation const & location1 = expr->args.front()->location; + CodeLocation const & location2 = expr->args.back()->location; + // LHS op RHS -> (LHS op RHS) / sizeof(LHS) + if ( baseType1 && baseType2 ) { + auto divide = ast::UntypedExpr::createCall( location, "?/?", { + expr, + new ast::SizeofExpr( location, deepCopy( baseType1 ) ), + } ); + if ( expr->env ) divide->env = expr->env; + return divide; + // LHS op RHS -> LHS op (RHS * sizeof(LHS)) + } else if ( baseType1 ) { + auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { + expr->args.back(), + new ast::SizeofExpr( location1, deepCopy( baseType1 ) ), + } ); + return ast::mutate_field_index( + expr, &ast::ApplicationExpr::args, 1, multiply ); + // LHS op RHS -> (LHS * sizeof(RHS)) op RHS + } else if ( baseType2 ) { + auto multiply = ast::UntypedExpr::createCall( location1, "?*?", { + expr->args.front(), + new ast::SizeofExpr( location2, deepCopy( baseType2 ) ), + } ); + return ast::mutate_field_index( + expr, &ast::ApplicationExpr::args, 0, multiply ); + } + // Addition and Subtration Relative Assignment Intrinsics: + } else if ( "?+=?" == varName || "?-=?" == varName ) { + assert( expr->result ); + assert( 2 == expr->args.size() ); + + CodeLocation const & location1 = expr->args.front()->location; + CodeLocation const & location2 = expr->args.back()->location; + auto baseType = isPolyPtr( expr->result, scopeTypeVars, typeSubs ); + // LHS op RHS -> LHS op (RHS * sizeof(LHS)) + if ( baseType ) { + auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { + expr->args.back(), + new ast::SizeofExpr( location1, deepCopy( baseType ) ), + } ); + return ast::mutate_field_index( + expr, &ast::ApplicationExpr::args, 1, multiply ); + } + } + return expr; +} + +ast::ObjectDecl * CallAdapter::makeTemporary( + CodeLocation const & location, ast::Type const * type ) { + auto newObj = new ast::ObjectDecl( location, tmpNamer.newName(), type ); + stmtsToAddBefore.push_back( new ast::DeclStmt( location, newObj ) ); + return newObj; +} + +// -------------------------------------------------------------------------- +/// Modifies declarations to accept implicit parameters. +/// * Move polymorphic returns in function types to pointer-type parameters. +/// * Adds type size and assertion parameters to parameter lists. +struct DeclAdapter final { + ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); + ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl ); +private: + void addAdapters( ast::FunctionDecl * decl, TypeVarMap & localTypeVars ); +}; + +// size/align/offset parameters may not be used, so add the unused attribute. +ast::ObjectDecl * makeObj( + CodeLocation const & location, std::string const & name ) { + return new ast::ObjectDecl( location, name, + makeSizeAlignType(), + nullptr, ast::Storage::Classes(), ast::Linkage::C, nullptr, + { new ast::Attribute( "unused" ) } ); +} + +ast::FunctionDecl const * DeclAdapter::previsit( ast::FunctionDecl const * decl ) { + TypeVarMap localTypeVars; + makeTypeVarMap( decl, localTypeVars ); + + auto mutDecl = mutate( decl ); + + // Move polymorphic return type to parameter list. + if ( isDynRet( mutDecl->type ) ) { + auto ret = strict_dynamic_cast( + mutDecl->returns.front().get_and_mutate() ); + ret->set_type( new ast::PointerType( ret->type ) ); + mutDecl->params.insert( mutDecl->params.begin(), ret ); + mutDecl->returns.erase( mutDecl->returns.begin() ); + ret->init = nullptr; + } + + // Add size/align and assertions for type parameters to parameter list. + ast::vector inferredParams; + ast::vector layoutParams; + for ( ast::ptr & typeParam : mutDecl->type_params ) { + auto mutParam = mutate( typeParam.get() ); + // Add all size and alignment parameters to parameter list. + if ( mutParam->isComplete() ) { + ast::TypeInstType paramType( mutParam ); + std::string paramName = Mangle::mangleType( ¶mType ); + + auto sizeParam = makeObj( typeParam->location, sizeofName( paramName ) ); + layoutParams.emplace_back( sizeParam ); + + auto alignParam = makeObj( typeParam->location, alignofName( paramName ) ); + layoutParams.emplace_back( alignParam ); + } + // Assertions should be stored in the main list. + assert( mutParam->assertions.empty() ); + typeParam = mutParam; + } + for ( ast::ptr & assert : mutDecl->assertions ) { + // Assertion parameters may not be used in body, + // pass along with unused attribute. + assert.get_and_mutate()->attributes.push_back( + new ast::Attribute( "unused" ) ); + inferredParams.push_back( assert ); + } + mutDecl->assertions.clear(); + + // Prepend each argument group. From last group to first. addAdapters + // does do the same, it just does it itself and see all other parameters. + spliceBegin( mutDecl->params, inferredParams ); + spliceBegin( mutDecl->params, layoutParams ); + addAdapters( mutDecl, localTypeVars ); + + // Now have to update the type to match the declaration. + ast::FunctionType * type = new ast::FunctionType( + mutDecl->type->isVarArgs, mutDecl->type->qualifiers ); + // The forall clauses don't match until Eraser. The assertions are empty. + for ( auto param : mutDecl->params ) { + type->params.emplace_back( param->get_type() ); + } + for ( auto retval : mutDecl->returns ) { + type->returns.emplace_back( retval->get_type() ); + } + mutDecl->type = type; + + return mutDecl; +} + +ast::FunctionDecl const * DeclAdapter::postvisit( + ast::FunctionDecl const * decl ) { + ast::FunctionDecl * mutDecl = mutate( decl ); + if ( !mutDecl->returns.empty() && mutDecl->stmts + // Intrinsic functions won't be using the _retval so no need to + // generate it. + && mutDecl->linkage != ast::Linkage::Intrinsic + // Remove check for prefix once thunks properly use ctor/dtors. + && !isPrefix( mutDecl->name, "_thunk" ) + && !isPrefix( mutDecl->name, "_adapter" ) ) { + assert( 1 == mutDecl->returns.size() ); + ast::DeclWithType const * retval = mutDecl->returns.front(); + if ( "" == retval->name ) { + retval = ast::mutate_field( + retval, &ast::DeclWithType::name, "_retval" ); + mutDecl->returns.front() = retval; + } + auto stmts = mutDecl->stmts.get_and_mutate(); + stmts->kids.push_front( new ast::DeclStmt( retval->location, retval ) ); + ast::DeclWithType * newRet = ast::deepCopy( retval ); + mutDecl->returns.front() = newRet; + } + // Errors should have been caught by this point, remove initializers from + // parameters to allow correct codegen of default arguments. + for ( ast::ptr & param : mutDecl->params ) { + if ( auto obj = param.as() ) { + param = ast::mutate_field( obj, &ast::ObjectDecl::init, nullptr ); + } + } + return mutDecl; +} + +void DeclAdapter::addAdapters( + ast::FunctionDecl * mutDecl, TypeVarMap & localTypeVars ) { + ast::vector functions; + for ( ast::ptr & arg : mutDecl->params ) { + ast::Type const * type = arg->get_type(); + type = findAndReplaceFunction( type, functions, localTypeVars, needsAdapter ); + arg.get_and_mutate()->set_type( type ); + } + std::set adaptersDone; + for ( ast::ptr const & func : functions ) { + std::string mangleName = mangleAdapterName( func, localTypeVars ); + if ( adaptersDone.find( mangleName ) != adaptersDone.end() ) { + continue; + } + std::string adapterName = makeAdapterName( mangleName ); + // The adapter may not actually be used, so make sure it has unused. + mutDecl->params.insert( mutDecl->params.begin(), new ast::ObjectDecl( + mutDecl->location, adapterName, + new ast::PointerType( makeAdapterType( func, localTypeVars ) ), + nullptr, {}, {}, nullptr, + { new ast::Attribute( "unused" ) } ) ); + adaptersDone.insert( adaptersDone.begin(), mangleName ); + } +} + +// -------------------------------------------------------------------------- +// TODO: Ideally, there would be no floating nodes at all. +/// Corrects the floating nodes created in CallAdapter. +struct RewireAdapters final : public ast::WithGuards { + ScopedMap adapters; + void beginScope() { adapters.beginScope(); } + void endScope() { adapters.endScope(); } + void previsit( ast::FunctionDecl const * decl ); + ast::VariableExpr const * previsit( ast::VariableExpr const * expr ); +}; + +void RewireAdapters::previsit( ast::FunctionDecl const * decl ) { + GuardScope( adapters ); + for ( ast::ptr const & param : decl->params ) { + if ( auto objectParam = param.as() ) { + adapters.insert( objectParam->name, objectParam ); + } + } +} + +ast::VariableExpr const * RewireAdapters::previsit( + ast::VariableExpr const * expr ) { + // If the node is not floating, we can skip. + if ( expr->var->isManaged() ) return expr; + auto it = adapters.find( expr->var->name ); + assertf( it != adapters.end(), "Could not correct floating node." ); + return ast::mutate_field( expr, &ast::VariableExpr::var, it->second ); +} + +// -------------------------------------------------------------------------- +/// Inserts code to access polymorphic layout inforation. +/// * Replaces member and size/alignment/offsetof expressions on polymorphic +/// generic types with calculated expressions. +/// * Replaces member expressions for polymorphic types with calculated +/// add-field-offset-and-dereference. +/// * Calculates polymorphic offsetof expressions from offset array. +/// * Inserts dynamic calculation of polymorphic type layouts where needed. +struct PolyGenericCalculator final : + public ast::WithConstTypeSubstitution, + public ast::WithDeclsToAdd<>, + public ast::WithGuards, + public ast::WithStmtsToAdd<>, + public ast::WithVisitorRef { + PolyGenericCalculator(); + + void previsit( ast::FunctionDecl const * decl ); + void previsit( ast::TypedefDecl const * decl ); + void previsit( ast::TypeDecl const * decl ); + ast::Decl const * postvisit( ast::TypeDecl const * decl ); + ast::StructDecl const * previsit( ast::StructDecl const * decl ); + ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); + ast::DeclStmt const * previsit( ast::DeclStmt const * stmt ); + ast::Expr const * postvisit( ast::MemberExpr const * expr ); + void previsit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::SizeofExpr const * expr ); + ast::Expr const * postvisit( ast::AlignofExpr const * expr ); + ast::Expr const * postvisit( ast::OffsetofExpr const * expr ); + ast::Expr const * postvisit( ast::OffsetPackExpr const * expr ); + + void beginScope(); + void endScope(); +private: + /// Makes a new variable in the current scope with the given name, + /// type and optional initializer. + ast::ObjectDecl * makeVar( + CodeLocation const & location, std::string const & name, + ast::Type const * type, ast::Init const * init = nullptr ); + /// 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( CodeLocation const & location, ast::Type const * ); + /// Adds type parameters to the layout call; will generate the + /// appropriate parameters if needed. + void addSTypeParamsToLayoutCall( + ast::UntypedExpr * layoutCall, + const ast::vector & otypeParams ); + /// Change the type of generic aggregate members to char[]. + void mutateMembers( ast::AggregateDecl * aggr ); + /// Returns the calculated sizeof expression for type, or nullptr for use + /// C sizeof(). + ast::Expr const * genSizeof( CodeLocation const &, ast::Type const * ); + /// Enters a new scope for type-variables, + /// adding the type variables from the provided type. + void beginTypeScope( ast::Type const * ); + + /// The type variables and polymorphic parameters currently in scope. + TypeVarMap scopeTypeVars; + /// Set of generic type layouts known in the current scope, + /// indexed by sizeofName. + ScopedSet knownLayouts; + /// Set of non-generic types for which the offset array exists in the + /// current scope, indexed by offsetofName. + ScopedSet knownOffsets; + /// Namer for VLA (variable length array) buffers. + UniqueName bufNamer; + /// If the argument of an AddressExpr is MemberExpr, it is stored here. + ast::MemberExpr const * addrMember = nullptr; +}; + +PolyGenericCalculator::PolyGenericCalculator() : + knownLayouts(), knownOffsets(), bufNamer( "_buf" ) +{} + +/// Converts polymorphic type into a suitable monomorphic representation. +/// Currently: __attribute__((aligned(8) )) char[size_T]; +ast::Type * polyToMonoType( CodeLocation const & location, + ast::Type const * declType ) { + auto charType = new ast::BasicType( ast::BasicType::Char ); + auto size = new ast::NameExpr( location, + sizeofName( Mangle::mangleType( declType ) ) ); + auto aligned = new ast::Attribute( "aligned", + { ast::ConstantExpr::from_int( location, 8 ) } ); + auto ret = new ast::ArrayType( charType, size, + ast::VariableLen, ast::DynamicDim, ast::CV::Qualifiers() ); + ret->attributes.push_back( aligned ); + return ret; +} + +void PolyGenericCalculator::previsit( ast::FunctionDecl const * decl ) { + GuardScope( *this ); + beginTypeScope( decl->type ); +} + +void PolyGenericCalculator::previsit( ast::TypedefDecl const * decl ) { + assertf( false, "All typedef declarations should be removed." ); + beginTypeScope( decl->base ); +} + +void PolyGenericCalculator::previsit( ast::TypeDecl const * decl ) { + addToTypeVarMap( decl, scopeTypeVars ); +} + +ast::Decl const * PolyGenericCalculator::postvisit( + ast::TypeDecl const * decl ) { + ast::Type const * base = decl->base; + if ( nullptr == base ) return decl; + + // Add size/align variables for opaque type declarations. + ast::TypeInstType inst( decl->name, decl ); + std::string typeName = Mangle::mangleType( &inst ); + ast::Type * layoutType = new ast::BasicType( + ast::BasicType::LongUnsignedInt ); + + ast::ObjectDecl * sizeDecl = new ast::ObjectDecl( decl->location, + sizeofName( typeName ), layoutType, + new ast::SingleInit( decl->location, + new ast::SizeofExpr( decl->location, deepCopy( base ) ) + ) + ); + ast::ObjectDecl * alignDecl = new ast::ObjectDecl( decl->location, + alignofName( typeName ), layoutType, + new ast::SingleInit( decl->location, + new ast::AlignofExpr( decl->location, deepCopy( base ) ) + ) + ); + + // Ensure that the initializing sizeof/alignof exprs are properly mutated. + sizeDecl->accept( *visitor ); + alignDecl->accept( *visitor ); + + // A little trick to replace this with two declarations. + // Adding after makes sure that there is no conflict with adding stmts. + declsToAddAfter.push_back( alignDecl ); + return sizeDecl; +} + +ast::StructDecl const * PolyGenericCalculator::previsit( + ast::StructDecl const * decl ) { + auto mutDecl = mutate( decl ); + mutateMembers( mutDecl ); + return mutDecl; +} + +ast::UnionDecl const * PolyGenericCalculator::previsit( + ast::UnionDecl const * decl ) { + auto mutDecl = mutate( decl ); + mutateMembers( mutDecl ); + return mutDecl; +} + +ast::DeclStmt const * PolyGenericCalculator::previsit( ast::DeclStmt const * stmt ) { + ast::ObjectDecl const * decl = stmt->decl.as(); + if ( !decl || !findGeneric( decl->location, decl->type ) ) { + return stmt; + } + + // Change initialization of a polymorphic value object to allocate via a + // variable-length-array (alloca cannot be safely used in loops). + ast::ObjectDecl * newBuf = new ast::ObjectDecl( decl->location, + bufNamer.newName(), + polyToMonoType( decl->location, decl->type ), + nullptr, {}, ast::Linkage::C + ); + stmtsToAddBefore.push_back( new ast::DeclStmt( stmt->location, newBuf ) ); + + // If the object has a cleanup attribute, the clean-up should be on the + // buffer, not the pointer. [Perhaps this should be lifted?] + auto matchAndMove = [newBuf]( ast::ptr & attr ) { + if ( "cleanup" == attr->name ) { + newBuf->attributes.push_back( attr ); + return true; + } + return false; + }; + + auto mutDecl = mutate( decl ); + + // Forally, side effects are not safe in this function. But it works. + erase_if( mutDecl->attributes, matchAndMove ); + + mutDecl->init = new ast::SingleInit( decl->location, + new ast::VariableExpr( decl->location, newBuf ) ); + + return ast::mutate_field( stmt, &ast::DeclStmt::decl, mutDecl ); +} + +/// Checks if memberDecl matches the decl from an aggregate. +bool isMember( ast::DeclWithType const * memberDecl, ast::Decl const * decl ) { + // No matter the field, if the name is different it is not the same. + if ( memberDecl->name != decl->name ) { + return false; + } + + if ( memberDecl->name.empty() ) { + // Plan-9 Field: Match on unique_id. + return ( memberDecl->uniqueId == decl->uniqueId ); + } + + ast::DeclWithType const * declWithType = + strict_dynamic_cast( decl ); + + if ( memberDecl->mangleName.empty() || declWithType->mangleName.empty() ) { + // Tuple-Element Field: Expect neither had mangled name; + // accept match on simple name (like field_2) only. + assert( memberDecl->mangleName.empty() ); + assert( declWithType->mangleName.empty() ); + return true; + } + + // Ordinary Field: Use full name to accommodate overloading. + return ( memberDecl->mangleName == declWithType->mangleName ); +} + +/// Finds the member in the base list that matches the given declaration; +/// returns its index, or -1 if not present. +long findMember( ast::DeclWithType const * memberDecl, + const ast::vector & baseDecls ) { + for ( auto pair : enumerate( baseDecls ) ) { + if ( isMember( memberDecl, pair.val.get() ) ) { + return pair.idx; + } + } + return -1; +} + +/// Returns an index expression into the offset array for a type. +ast::Expr * makeOffsetIndex( CodeLocation const & location, + ast::Type const * objectType, long i ) { + std::string name = offsetofName( Mangle::mangleType( objectType ) ); + return ast::UntypedExpr::createCall( location, "?[?]", { + new ast::NameExpr( location, name ), + ast::ConstantExpr::from_ulong( location, i ), + } ); +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::MemberExpr const * expr ) { + // Only mutate member expressions for polymorphic types. + ast::Type const * objectType = hasPolyBase( + expr->aggregate->result, scopeTypeVars + ); + if ( !objectType ) return expr; + // Ensure layout for this type is available. + // The boolean result is ignored. + findGeneric( expr->location, objectType ); + + // Replace member expression with dynamically-computed layout expression. + ast::Expr * newMemberExpr = nullptr; + if ( auto structType = dynamic_cast( objectType ) ) { + long offsetIndex = findMember( expr->member, structType->base->members ); + if ( -1 == offsetIndex ) return expr; + + // Replace member expression with pointer to struct plus offset. + ast::UntypedExpr * fieldLoc = new ast::UntypedExpr( expr->location, + new ast::NameExpr( expr->location, "?+?" ) ); + ast::Expr * aggr = deepCopy( expr->aggregate ); + aggr->env = nullptr; + fieldLoc->args.push_back( aggr ); + fieldLoc->args.push_back( + makeOffsetIndex( expr->location, objectType, offsetIndex ) ); + fieldLoc->result = deepCopy( expr->result ); + newMemberExpr = fieldLoc; + // Union members are all at offset zero, so just use the aggregate expr. + } else if ( dynamic_cast( objectType ) ) { + ast::Expr * aggr = deepCopy( expr->aggregate ); + aggr->env = nullptr; + aggr->result = deepCopy( expr->result ); + newMemberExpr = aggr; + } else { + return expr; + } + assert( newMemberExpr ); + + // Must apply the generic substitution to the member type to handle cases + // where the member is a generic parameter subsituted by a known concrete + // type. [ex] + // forall( T ) struct Box { T x; } + // forall( T ) void f() { + // Box( T * ) b; b.x; + // } + // TODO: expr->result should be exactly expr->member->get_type() after + // substitution, so it doesn't seem like it should be necessary to apply + // the substitution manually. For some reason this is not currently the + // case. This requires more investigation. + ast::ptr memberType = deepCopy( expr->member->get_type() ); + ast::TypeSubstitution sub = genericSubstitution( objectType ); + sub.apply( memberType ); + + // Not all members of a polymorphic type are themselves of a polymorphic + // type; in this cas the member expression should be wrapped and + // dereferenced to form an lvalue. + if ( !isPolyType( memberType, scopeTypeVars ) ) { + auto ptrCastExpr = new ast::CastExpr( expr->location, newMemberExpr, + new ast::PointerType( memberType ) ); + auto derefExpr = ast::UntypedExpr::createDeref( expr->location, + ptrCastExpr ); + newMemberExpr = derefExpr; + } + + return newMemberExpr; +} + +void PolyGenericCalculator::previsit( ast::AddressExpr const * expr ) { + GuardValue( addrMember ) = expr->arg.as(); +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::AddressExpr const * expr ) { + // arg has to have been a MemberExpr and has been mutated. + if ( nullptr == addrMember || expr->arg == addrMember ) { + return expr; + } + ast::UntypedExpr const * untyped = expr->arg.as(); + if ( !untyped || getFunctionName( untyped ) != "?+?" ) { + return expr; + } + // MemberExpr was converted to pointer + offset; and it is not valid C to + // take the address of an addition, so strip away the address-of. + // It also preserves the env value. + return ast::mutate_field( expr->arg.get(), &ast::Expr::env, expr->env ); +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::SizeofExpr const * expr ) { + ast::Type const * type = expr->type ? expr->type : expr->expr->result; + ast::Expr const * gen = genSizeof( expr->location, type ); + return ( gen ) ? gen : expr; +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::AlignofExpr const * expr ) { + ast::Type const * type = expr->type ? expr->type : expr->expr->result; + if ( findGeneric( expr->location, type ) ) { + return new ast::NameExpr( expr->location, + alignofName( Mangle::mangleType( type ) ) ); + } else { + return expr; + } +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::OffsetofExpr const * expr ) { + ast::Type const * type = expr->type; + if ( !findGeneric( expr->location, type ) ) return expr; + + // Structures replace offsetof expression with an index into offset array. + if ( auto structType = dynamic_cast( type ) ) { + long offsetIndex = findMember( expr->member, structType->base->members ); + if ( -1 == offsetIndex ) return expr; + + return makeOffsetIndex( expr->location, type, offsetIndex ); + // All union members are at offset zero. + } else if ( dynamic_cast( type ) ) { + return ast::ConstantExpr::from_ulong( expr->location, 0 ); + } else { + return expr; + } +} + +ast::Expr const * PolyGenericCalculator::postvisit( + ast::OffsetPackExpr const * expr ) { + ast::StructInstType const * type = expr->type; + + // Pull offset back from generated type information. + if ( findGeneric( expr->location, type ) ) { + return new ast::NameExpr( expr->location, + offsetofName( Mangle::mangleType( type ) ) ); + } + + std::string offsetName = offsetofName( Mangle::mangleType( type ) ); + // Use the already generated offsets for this type. + if ( knownOffsets.contains( offsetName ) ) { + return new ast::NameExpr( expr->location, offsetName ); + } + + knownOffsets.insert( offsetName ); + + auto baseMembers = type->base->members; + ast::Type const * offsetType = new ast::BasicType( + ast::BasicType::LongUnsignedInt ); + + // Build initializer list for offset array. + ast::vector inits; + for ( ast::ptr & member : baseMembers ) { + auto memberDecl = member.as(); + assertf( memberDecl, "Requesting offset of non-DWT member: %s", + toCString( member ) ); + inits.push_back( new ast::SingleInit( expr->location, + new ast::OffsetofExpr( expr->location, + deepCopy( type ), + memberDecl + ) + ) ); + } + + auto offsetArray = makeVar( expr->location, offsetName, + new ast::ArrayType( + offsetType, + ast::ConstantExpr::from_ulong( expr->location, baseMembers.size() ), + ast::FixedLen, + ast::DynamicDim + ), + new ast::ListInit( expr->location, std::move( inits ) ) + ); + + return new ast::VariableExpr( expr->location, offsetArray ); +} + +void PolyGenericCalculator::beginScope() { + knownLayouts.beginScope(); + knownOffsets.beginScope(); +} + +void PolyGenericCalculator::endScope() { + knownOffsets.endScope(); + knownLayouts.endScope(); +} + +ast::ObjectDecl * PolyGenericCalculator::makeVar( + CodeLocation const & location, std::string const & name, + ast::Type const * type, ast::Init const * init ) { + ast::ObjectDecl * ret = new ast::ObjectDecl( location, name, type, init ); + stmtsToAddBefore.push_back( new ast::DeclStmt( location, ret ) ); + return ret; +} + +/// Returns true if any of the otype parameters have a dynamic layout; and +/// puts all otype parameters in the output list. +bool findGenericParams( + ast::vector & out, + ast::vector const & baseParams, + ast::vector const & typeParams ) { + bool hasDynamicLayout = false; + + for ( auto pair : group_iterate( baseParams, typeParams ) ) { + auto baseParam = std::get<0>( pair ); + auto typeParam = std::get<1>( pair ); + if ( !baseParam->isComplete() ) continue; + ast::TypeExpr const * typeExpr = typeParam.as(); + assertf( typeExpr, "All type parameters should be type expressions." ); + + ast::Type const * type = typeExpr->type.get(); + out.push_back( type ); + if ( isPolyType( type ) ) hasDynamicLayout = true; + } + + return hasDynamicLayout; +} + +bool PolyGenericCalculator::findGeneric( + CodeLocation const & location, ast::Type const * type ) { + type = replaceTypeInst( type, typeSubs ); + + if ( auto inst = dynamic_cast( type ) ) { + // Assumes that getting put in the scopeTypeVars includes having the + // layout variables set. + if ( scopeTypeVars.contains( *inst ) ) { + return true; + } + } else if ( auto inst = dynamic_cast( type ) ) { + // Check if this type already has a layout generated for it. + std::string typeName = Mangle::mangleType( type ); + if ( knownLayouts.contains( typeName ) ) return true; + + // Check if any type parameters have dynamic layout; + // If none do, this type is (or will be) monomorphized. + ast::vector sizedParams; + if ( !findGenericParams( sizedParams, + inst->base->params, inst->params ) ) { + return false; + } + + // Insert local variables for layout and generate call to layout + // function. + // Done early so as not to interfere with the later addition of + // parameters to the layout call. + knownLayouts.insert( typeName ); + ast::Type const * layoutType = makeSizeAlignType(); + + int memberCount = inst->base->members.size(); + if ( 0 == memberCount ) { + // All empty structures have the same layout (size 1, align 1). + makeVar( location, + sizeofName( typeName ), layoutType, + new ast::SingleInit( location, + ast::ConstantExpr::from_ulong( location, 1 ) ) ); + makeVar( location, + alignofName( typeName ), ast::deepCopy( layoutType ), + new ast::SingleInit( location, + ast::ConstantExpr::from_ulong( location, 1 ) ) ); + // Since 0-length arrays are forbidden in C, skip the offset array. + } else { + ast::ObjectDecl const * sizeofVar = makeVar( location, + sizeofName( typeName ), deepCopy( layoutType ), nullptr ); + ast::ObjectDecl const * alignofVar = makeVar( location, + alignofName( typeName ), deepCopy( layoutType ), nullptr ); + ast::ObjectDecl const * offsetofVar = makeVar( location, + offsetofName( typeName ), + new ast::ArrayType( + layoutType, + ast::ConstantExpr::from_int( location, memberCount ), + ast::FixedLen, + ast::DynamicDim + ), + nullptr + ); + + // Generate call to layout function. + ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location, + new ast::NameExpr( location, layoutofName( inst->base ) ), + { + new ast::AddressExpr( + new ast::VariableExpr( location, sizeofVar ) ), + new ast::AddressExpr( + new ast::VariableExpr( location, alignofVar ) ), + new ast::VariableExpr( location, offsetofVar ), + } ); + + addSTypeParamsToLayoutCall( layoutCall, sizedParams ); + + stmtsToAddBefore.emplace_back( + new ast::ExprStmt( location, layoutCall ) ); + } + + return true; + } else if ( auto inst = dynamic_cast( type ) ) { + // Check if this type already has a layout generated for it. + std::string typeName = Mangle::mangleType( type ); + if ( knownLayouts.contains( typeName ) ) return true; + + // Check if any type parameters have dynamic layout; + // If none do, this type is (or will be) monomorphized. + ast::vector sizedParams; + if ( !findGenericParams( sizedParams, + inst->base->params, inst->params ) ) { + return false; + } + + // Insert local variables for layout and generate call to layout + // function. + // Done early so as not to interfere with the later addition of + // parameters to the layout call. + knownLayouts.insert( typeName ); + ast::Type const * layoutType = makeSizeAlignType(); + + ast::ObjectDecl * sizeofVar = makeVar( location, + sizeofName( typeName ), layoutType ); + ast::ObjectDecl * alignofVar = makeVar( location, + alignofName( typeName ), ast::deepCopy( layoutType ) ); + + ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location, + new ast::NameExpr( location, layoutofName( inst->base ) ), + { + new ast::AddressExpr( + new ast::VariableExpr( location, sizeofVar ) ), + new ast::AddressExpr( + new ast::VariableExpr( location, alignofVar ) ), + } ); + + addSTypeParamsToLayoutCall( layoutCall, sizedParams ); + + stmtsToAddBefore.emplace_back( + new ast::ExprStmt( location, layoutCall ) ); + + return true; + } + return false; +} + +void PolyGenericCalculator::addSTypeParamsToLayoutCall( + ast::UntypedExpr * layoutCall, + const ast::vector & otypeParams ) { + CodeLocation const & location = layoutCall->location; + ast::vector & args = layoutCall->args; + for ( ast::ptr const & param : otypeParams ) { + if ( findGeneric( location, param ) ) { + // Push size/align vars for a generic parameter back. + std::string paramName = Mangle::mangleType( param ); + args.emplace_back( + new ast::NameExpr( location, sizeofName( paramName ) ) ); + args.emplace_back( + new ast::NameExpr( location, alignofName( paramName ) ) ); + } else { + args.emplace_back( + new ast::SizeofExpr( location, ast::deepCopy( param ) ) ); + args.emplace_back( + new ast::AlignofExpr( location, ast::deepCopy( param ) ) ); + } + } +} + +void PolyGenericCalculator::mutateMembers( ast::AggregateDecl * aggr ) { + std::set genericParams; + for ( ast::ptr const & decl : aggr->params ) { + genericParams.insert( decl->name ); + } + for ( ast::ptr & decl : aggr->members ) { + auto field = decl.as(); + if ( nullptr == field ) continue; + + ast::Type const * type = replaceTypeInst( field->type, typeSubs ); + auto typeInst = dynamic_cast( type ); + if ( nullptr == typeInst ) continue; + + // Do not try to monoporphize generic parameters. + if ( scopeTypeVars.contains( ast::TypeEnvKey( *typeInst ) ) && + !genericParams.count( typeInst->name ) ) { + // Polymorphic aggregate members should be converted into + // monomorphic members. Using char[size_T] here respects + // the expected sizing rules of an aggregate type. + decl = ast::mutate_field( field, &ast::ObjectDecl::type, + polyToMonoType( field->location, field->type ) ); + } + } +} + +ast::Expr const * PolyGenericCalculator::genSizeof( + CodeLocation const & location, ast::Type const * type ) { + if ( auto * array = dynamic_cast( type ) ) { + // Generate calculated size for possibly generic array. + ast::Expr const * sizeofBase = genSizeof( location, array->base ); + if ( nullptr == sizeofBase ) return nullptr; + ast::Expr const * dim = array->dimension; + return makeOp( location, "?*?", sizeofBase, dim ); + } else if ( findGeneric( location, type ) ) { + // Generate calculated size for generic type. + return new ast::NameExpr( location, sizeofName( + Mangle::mangleType( type ) ) ); + } else { + return nullptr; + } +} + +void PolyGenericCalculator::beginTypeScope( ast::Type const * type ) { + GuardScope( scopeTypeVars ); + makeTypeVarMap( type, scopeTypeVars ); +} + +// -------------------------------------------------------------------------- +/// Removes unneeded or incorrect type information. +/// * Replaces initialization of polymorphic values with alloca. +/// * Replaces declaration of dtype/ftype with appropriate void expression. +/// * Replaces sizeof expressions of polymorphic types with a variable. +/// * Strips fields from generic structure declarations. +struct Eraser final : + public ast::WithGuards { + void guardTypeVarMap( ast::Type const * type ) { + GuardScope( scopeTypeVars ); + makeTypeVarMap( type, scopeTypeVars ); + } + + ast::ObjectDecl const * previsit( ast::ObjectDecl const * decl ); + ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); + ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl ); + ast::TypedefDecl const * previsit( ast::TypedefDecl const * decl ); + ast::StructDecl const * previsit( ast::StructDecl const * decl ); + ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); + void previsit( ast::TypeDecl const * decl ); + void previsit( ast::PointerType const * type ); + void previsit( ast::FunctionType const * type ); +public: + TypeVarMap scopeTypeVars; +}; + +ast::ObjectDecl const * Eraser::previsit( ast::ObjectDecl const * decl ) { + guardTypeVarMap( decl->type ); + return scrubAllTypeVars( decl ); +} + +ast::FunctionDecl const * Eraser::previsit( ast::FunctionDecl const * decl ) { + guardTypeVarMap( decl->type ); + return scrubAllTypeVars( decl ); +} + +ast::FunctionDecl const * Eraser::postvisit( ast::FunctionDecl const * decl ) { + if ( decl->type_params.empty() ) return decl; + auto mutDecl = mutate( decl ); + mutDecl->type_params.clear(); + return mutDecl; +} + +ast::TypedefDecl const * Eraser::previsit( ast::TypedefDecl const * decl ) { + guardTypeVarMap( decl->base ); + return scrubAllTypeVars( decl ); +} + +/// Strips the members from a generic aggregate. +template +node_t const * stripGenericMembers( node_t const * decl ) { + if ( decl->params.empty() ) return decl; + auto mutDecl = ast::mutate( decl ); + mutDecl->members.clear(); + return mutDecl; +} + +ast::StructDecl const * Eraser::previsit( ast::StructDecl const * decl ) { + return stripGenericMembers( decl ); +} + +ast::UnionDecl const * Eraser::previsit( ast::UnionDecl const * decl ) { + return stripGenericMembers( decl ); +} + +void Eraser::previsit( ast::TypeDecl const * decl ) { + addToTypeVarMap( decl, scopeTypeVars ); +} + +void Eraser::previsit( ast::PointerType const * type ) { + guardTypeVarMap( type ); +} + +void Eraser::previsit( ast::FunctionType const * type ) { + guardTypeVarMap( type ); +} + +} // namespace + +// -------------------------------------------------------------------------- +void box( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); +} + +} // namespace GenPoly + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/BoxNew.cpp =================================================================== --- src/GenPoly/BoxNew.cpp (revision f48dfcd1acf87e4d711e108cd7119bb80ee701ee) +++ (revision ) @@ -1,2270 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// BoxNew.cpp -- Implement polymorphic function calls and types. -// -// Author : Andrew Beach -// Created On : Thr Oct 6 13:39:00 2022 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Oct 2 17:00:00 2023 -// Update Count : 0 -// - -#include "Box.h" - -#include "AST/Decl.hpp" // for Decl, FunctionDecl, ... -#include "AST/Expr.hpp" // for AlignofExpr, ConstantExpr, ... -#include "AST/Init.hpp" // for Init, SingleInit -#include "AST/Inspect.hpp" // for getFunctionName -#include "AST/Pass.hpp" // for Pass, WithDeclsToAdd, ... -#include "AST/Stmt.hpp" // for CompoundStmt, ExprStmt, ... -#include "AST/Vector.hpp" // for vector -#include "AST/GenericSubstitution.hpp" // for genericSubstitution -#include "CodeGen/OperatorTable.h" // for isAssignment -#include "Common/ScopedMap.h" // for ScopedMap -#include "Common/UniqueName.h" // for UniqueName -#include "Common/utility.h" // for toCString, group_iterate -#include "GenPoly/FindFunction.h" // for findFunction -#include "GenPoly/GenPoly.h" // for getFunctionType, ... -#include "GenPoly/Lvalue.h" // for generalizedLvalue -#include "GenPoly/ScopedSet.h" // for ScopedSet -#include "GenPoly/ScrubTyVars.h" // for scrubTypeVars, scrubAllTypeVars -#include "ResolvExpr/Unify.h" // for typesCompatible -#include "SymTab/Mangler.h" // for mangle, mangleType - -namespace GenPoly { - -namespace { - -// -------------------------------------------------------------------------- -/// Adds layout-generation functions to polymorphic types. -struct LayoutFunctionBuilder final : - public ast::WithDeclsToAdd<>, - public ast::WithShortCircuiting, - public ast::WithVisitorRef { - void previsit( ast::StructDecl const * decl ); - void previsit( ast::UnionDecl const * decl ); -}; - -/// Get all sized type declarations; those that affect a layout function. -ast::vector takeSizedParams( - ast::vector const & decls ) { - ast::vector sizedParams; - for ( ast::ptr const & decl : decls ) { - if ( decl->isComplete() ) { - sizedParams.emplace_back( decl ); - } - } - return sizedParams; -} - -ast::BasicType * makeSizeAlignType() { - return new ast::BasicType( ast::BasicType::LongUnsignedInt ); -} - -/// Adds parameters for otype size and alignment to a function type. -void addSTypeParams( - ast::vector & params, - ast::vector const & sizedParams ) { - for ( ast::ptr const & sizedParam : sizedParams ) { - ast::TypeInstType inst( sizedParam ); - std::string paramName = Mangle::mangleType( &inst ); - params.emplace_back( new ast::ObjectDecl( - sizedParam->location, - sizeofName( paramName ), - makeSizeAlignType() - ) ); - params.emplace_back( new ast::ObjectDecl( - sizedParam->location, - alignofName( paramName ), - makeSizeAlignType() - ) ); - } -} - -ast::Type * makeSizeAlignOutType() { - return new ast::PointerType( makeSizeAlignType() ); -} - -struct LayoutData { - ast::FunctionDecl * function; - ast::ObjectDecl * sizeofParam; - ast::ObjectDecl * alignofParam; - ast::ObjectDecl * offsetofParam; -}; - -LayoutData buildLayoutFunction( - CodeLocation const & location, ast::AggregateDecl const * aggr, - ast::vector const & sizedParams, - bool isInFunction, bool isStruct ) { - ast::ObjectDecl * sizeParam = new ast::ObjectDecl( - location, - sizeofName( aggr->name ), - makeSizeAlignOutType() - ); - ast::ObjectDecl * alignParam = new ast::ObjectDecl( - location, - alignofName( aggr->name ), - makeSizeAlignOutType() - ); - ast::ObjectDecl * offsetParam = nullptr; - ast::vector params = { sizeParam, alignParam }; - if ( isStruct ) { - offsetParam = new ast::ObjectDecl( - location, - offsetofName( aggr->name ), - makeSizeAlignOutType() - ); - params.push_back( offsetParam ); - } - addSTypeParams( params, sizedParams ); - - // 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. - ast::FunctionDecl * layoutDecl = new ast::FunctionDecl( - location, - layoutofName( aggr ), - {}, // forall - {}, // assertions - std::move( params ), - {}, // returns - new ast::CompoundStmt( location ), - isInFunction ? ast::Storage::Classes() : ast::Storage::Static, - ast::Linkage::AutoGen, - {}, // attrs - ast::Function::Inline, - ast::FixedArgs - ); - layoutDecl->fixUniqueId(); - return LayoutData{ layoutDecl, sizeParam, alignParam, offsetParam }; -} - -/// Makes a binary operation. -ast::Expr * makeOp( CodeLocation const & location, std::string const & name, - ast::Expr const * lhs, ast::Expr const * rhs ) { - return new ast::UntypedExpr( location, - new ast::NameExpr( location, name ), { lhs, rhs } ); -} - -/// Make a binary operation and wrap it in a statement. -ast::Stmt * makeOpStmt( CodeLocation const & location, std::string const & name, - ast::Expr const * lhs, ast::Expr const * rhs ) { - return new ast::ExprStmt( location, makeOp( location, name, lhs, rhs ) ); -} - -/// Returns the dereference of a local pointer variable. -ast::Expr * derefVar( - CodeLocation const & location, ast::ObjectDecl const * var ) { - return ast::UntypedExpr::createDeref( location, - new ast::VariableExpr( location, var ) ); -} - -/// Makes an if-statement with a single-expression then and no else. -ast::Stmt * makeCond( CodeLocation const & location, - ast::Expr const * cond, ast::Expr const * thenPart ) { - return new ast::IfStmt( location, - cond, new ast::ExprStmt( location, thenPart ), nullptr ); -} - -/// Makes a statement that aligns lhs to rhs (rhs should be an integer -/// power of two). -ast::Stmt * makeAlignTo( CodeLocation const & location, - ast::Expr const * lhs, ast::Expr const * rhs ) { - // Check that the lhs is zeroed out to the level of rhs. - ast::Expr * ifCond = makeOp( location, "?&?", lhs, - makeOp( location, "?-?", rhs, - ast::ConstantExpr::from_ulong( location, 1 ) ) ); - // If not aligned, increment to alignment. - ast::Expr * ifExpr = makeOp( location, "?+=?", ast::deepCopy( lhs ), - makeOp( location, "?-?", ast::deepCopy( rhs ), - ast::deepCopy( ifCond ) ) ); - return makeCond( location, ifCond, ifExpr ); -} - -/// Makes a statement that assigns rhs to lhs if lhs < rhs. -ast::Stmt * makeAssignMax( CodeLocation const & location, - ast::Expr const * lhs, ast::Expr const * rhs ) { - return makeCond( location, - makeOp( location, "?members.empty() ) return; - - // Get parameters that can change layout, exiting early if none. - ast::vector sizedParams = - takeSizedParams( decl->params ); - if ( sizedParams.empty() ) return; - - CodeLocation const & location = decl->location; - - // Build layout function signature. - LayoutData layout = buildLayoutFunction( - location, decl, sizedParams, isInFunction(), true ); - ast::FunctionDecl * layoutDecl = layout.function; - // Also return these or extract them from the parameter list? - ast::ObjectDecl const * sizeofParam = layout.sizeofParam; - ast::ObjectDecl const * alignofParam = layout.alignofParam; - ast::ObjectDecl const * offsetofParam = layout.offsetofParam; - assert( nullptr != layout.offsetofParam ); - - // Calculate structure layout in function body. - // Initialize size and alignment to 0 and 1 - // (Will have at least one member to update size). - auto & kids = layoutDecl->stmts.get_and_mutate()->kids; - kids.emplace_back( makeOpStmt( location, "?=?", - derefVar( location, sizeofParam ), - ast::ConstantExpr::from_ulong( location, 0 ) - ) ); - kids.emplace_back( makeOpStmt( location, "?=?", - derefVar( location, alignofParam ), - ast::ConstantExpr::from_ulong( location, 1 ) - ) ); - // TODO: Polymorphic types will be out of the struct declaration scope. - // Should be removed by PolyGenericCalculator. - for ( auto const & member : enumerate( decl->members ) ) { - auto dwt = member.val.strict_as(); - ast::Type const * memberType = dwt->get_type(); - - if ( 0 < member.idx ) { - // Make sure all later members have padding to align them. - kids.emplace_back( makeAlignTo( location, - derefVar( location, sizeofParam ), - new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) - ) ); - } - - // Place current size in the current offset index. - kids.emplace_back( makeOpStmt( location, "?=?", - makeOp( location, "?[?]", - new ast::VariableExpr( location, offsetofParam ), - ast::ConstantExpr::from_ulong( location, member.idx ) ), - derefVar( location, sizeofParam ) ) ); - - // Add member size to current size. - kids.emplace_back( makeOpStmt( location, "?+=?", - derefVar( location, sizeofParam ), - new ast::SizeofExpr( location, ast::deepCopy( memberType ) ) ) ); - - // Take max of member alignment and global alignment. - // (As align is always 2^n, this will always be a multiple of both.) - kids.emplace_back( makeAssignMax( location, - derefVar( location, alignofParam ), - new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) ) ); - } - // Make sure the type is end-padded to a multiple of its alignment. - kids.emplace_back( makeAlignTo( location, - derefVar( location, sizeofParam ), - derefVar( location, alignofParam ) ) ); - - declsToAddAfter.emplace_back( layoutDecl ); -} - -void LayoutFunctionBuilder::previsit( ast::UnionDecl const * decl ) { - visit_children = false; - // Do not generate layout function for empty tag unions. - if ( decl->members.empty() ) return; - - // Get parameters that can change layout, exiting early if none. - ast::vector sizedParams = - takeSizedParams( decl->params ); - if ( sizedParams.empty() ) return; - - CodeLocation const & location = decl->location; - - // Build layout function signature. - LayoutData layout = buildLayoutFunction( - location, decl, sizedParams, isInFunction(), false ); - ast::FunctionDecl * layoutDecl = layout.function; - // Also return these or extract them from the parameter list? - ast::ObjectDecl const * sizeofParam = layout.sizeofParam; - ast::ObjectDecl const * alignofParam = layout.alignofParam; - assert( nullptr == layout.offsetofParam ); - - // Calculate union layout in function body. - // Both are simply the maximum for union (actually align is always the - // LCM, but with powers of two that is also the maximum). - auto & kids = layoutDecl->stmts.get_and_mutate()->kids; - kids.emplace_back( makeOpStmt( location, - "?=?", derefVar( location, sizeofParam ), - ast::ConstantExpr::from_ulong( location, 1 ) - ) ); - kids.emplace_back( makeOpStmt( location, - "?=?", derefVar( location, alignofParam ), - ast::ConstantExpr::from_ulong( location, 1 ) - ) ); - // TODO: Polymorphic types will be out of the union declaration scope. - for ( auto const & member : decl->members ) { - auto dwt = member.strict_as(); - ast::Type const * memberType = dwt->get_type(); - - // Take max member size and global size. - kids.emplace_back( makeAssignMax( location, - derefVar( location, sizeofParam ), - new ast::SizeofExpr( location, ast::deepCopy( memberType ) ) - ) ); - - // Take max of member alignment and global alignment. - kids.emplace_back( makeAssignMax( location, - derefVar( location, alignofParam ), - new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) - ) ); - } - kids.emplace_back( makeAlignTo( location, - derefVar( location, sizeofParam ), - derefVar( location, alignofParam ) ) ); - - declsToAddAfter.emplace_back( layoutDecl ); -} - -// -------------------------------------------------------------------------- -/// Application expression transformer. -/// * Replaces polymorphic return types with out-parameters. -/// * Replaces call to polymorphic functions with adapter calls which handles -/// dynamic arguments and return values. -/// * Adds appropriate type variables to the function calls. -struct CallAdapter final : - public ast::WithConstTypeSubstitution, - public ast::WithGuards, - public ast::WithShortCircuiting, - public ast::WithStmtsToAdd<>, - public ast::WithVisitorRef { - CallAdapter(); - - void previsit( ast::Decl const * decl ); - ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); - void previsit( ast::TypeDecl const * decl ); - void previsit( ast::CommaExpr const * expr ); - ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); - ast::Expr const * postvisit( ast::UntypedExpr const * expr ); - void previsit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::AddressExpr const * expr ); - ast::ReturnStmt const * previsit( ast::ReturnStmt const * stmt ); - - void beginScope(); - void endScope(); -private: - // Many helpers here use a mutable ApplicationExpr as an in/out parameter - // instead of using the return value, to save on mutates and free up the - // return value. - - /// Passes extra layout arguments for sized polymorphic type parameters. - ast::vector::iterator passTypeVars( - ast::ApplicationExpr * expr, - ast::FunctionType const * funcType ); - /// Wraps a function application with a new temporary for the - /// out-parameter return value. - ast::Expr const * addRetParam( - ast::ApplicationExpr * expr, ast::Type const * retType ); - /// Wraps a function application returning a polymorphic type with a new - /// temporary for the out-parameter return value. - ast::Expr const * addDynRetParam( - ast::ApplicationExpr * expr, ast::Type const * polyType ); - /// Modify a call so it passes the function through the correct adapter. - ast::Expr const * applyAdapter( - ast::ApplicationExpr * expr, - ast::FunctionType const * function ); - /// Convert a single argument into its boxed form to pass the parameter. - void boxParam( ast::ptr & arg, - ast::Type const * formal, TypeVarMap const & exprTyVars ); - /// Box every argument from arg forward, matching the functionType - /// parameter list. arg should point into expr's argument list. - void boxParams( - ast::ApplicationExpr const * expr, - ast::vector::iterator arg, - ast::FunctionType const * function, - const TypeVarMap & typeVars ); - /// Adds the inferred parameters derived from the assertions of the - /// expression to the call. - void addInferredParams( - ast::ApplicationExpr * expr, - ast::vector::iterator arg, - ast::FunctionType const * functionType, - const TypeVarMap & typeVars ); - /// Stores assignment operators from assertion list in - /// local map of assignment operations. - void passAdapters( - ast::ApplicationExpr * expr, - ast::FunctionType const * type, - const TypeVarMap & typeVars ); - /// Create an adapter function based on the type of the adaptee and the - /// real type with the type substitutions applied. - ast::FunctionDecl * makeAdapter( - ast::FunctionType const * adaptee, - ast::FunctionType const * realType, - std::string const & mangleName, - TypeVarMap const & typeVars, - CodeLocation const & location ) const; - /// Replaces intrinsic operator functions with their arithmetic desugaring. - ast::Expr const * handleIntrinsics( ast::ApplicationExpr const * ); - /// Inserts a new temporary variable into the current scope with an - /// auto-generated name. - ast::ObjectDecl * makeTemporary( - CodeLocation const & location, ast::Type const * type ); - - TypeVarMap scopeTypeVars; - ScopedMap< std::string, ast::DeclWithType const * > adapters; - std::map< ast::ApplicationExpr const *, ast::Expr const * > retVals; - ast::DeclWithType const * retval; - UniqueName tmpNamer; -}; - -/// Replaces a polymorphic type with its concrete equivalant under the -/// current environment (returns itself if concrete). -/// If `doClone` is set to false, will not clone interior types -ast::Type const * replaceWithConcrete( - ast::Type const * type, - ast::TypeSubstitution const & typeSubs, - bool doCopy = true ); - -/// Replaces all the type parameters of a generic type with their -/// concrete equivalents under the current environment. -void replaceParametersWithConcrete( - ast::vector & params, - ast::TypeSubstitution const & typeSubs ) { - for ( ast::ptr & paramExpr : params ) { - ast::TypeExpr const * param = paramExpr.as(); - assertf( param, "Aggregate parameters should be type expressions." ); - paramExpr = ast::mutate_field( param, &ast::TypeExpr::type, - replaceWithConcrete( param->type.get(), typeSubs, false ) ); - } -} - -ast::Type const * replaceWithConcrete( - ast::Type const * type, - ast::TypeSubstitution const & typeSubs, - bool doCopy ) { - if ( auto instType = dynamic_cast( type ) ) { - ast::Type const * concrete = typeSubs.lookup( instType ); - return ( nullptr != concrete ) ? concrete : instType; - } else if ( auto structType = - dynamic_cast( type ) ) { - ast::StructInstType * newType = - doCopy ? ast::deepCopy( structType ) : ast::mutate( structType ); - replaceParametersWithConcrete( newType->params, typeSubs ); - return newType; - } else if ( auto unionType = - dynamic_cast( type ) ) { - ast::UnionInstType * newType = - doCopy ? ast::deepCopy( unionType ) : ast::mutate( unionType ); - replaceParametersWithConcrete( newType->params, typeSubs ); - return newType; - } else { - return type; - } -} - -std::string makePolyMonoSuffix( - ast::FunctionType const * function, - TypeVarMap const & typeVars ) { - // If the return type or a parameter type involved polymorphic types, - // then the adapter will need to take those polymorphic types as pointers. - // Therefore, there can be two different functions with the same mangled - // name, so we need to further mangle the names. - std::stringstream name; - for ( auto ret : function->returns ) { - name << ( isPolyType( ret, typeVars ) ? 'P' : 'M' ); - } - name << '_'; - for ( auto arg : function->params ) { - name << ( isPolyType( arg, typeVars ) ? 'P' : 'M' ); - } - return name.str(); -} - -std::string mangleAdapterName( - ast::FunctionType const * function, - TypeVarMap const & typeVars ) { - return Mangle::mangle( function, {} ) - + makePolyMonoSuffix( function, typeVars ); -} - -std::string makeAdapterName( std::string const & mangleName ) { - return "_adapter" + mangleName; -} - -void makeRetParam( ast::FunctionType * type ) { - ast::ptr & retParam = type->returns.front(); - - // Make a new parameter that is a pointer to the type of the old return value. - retParam = new ast::PointerType( retParam.get() ); - type->params.emplace( type->params.begin(), retParam ); - - // We don't need the return value any more. - type->returns.clear(); -} - -ast::FunctionType * makeAdapterType( - ast::FunctionType const * adaptee, - TypeVarMap const & typeVars ) { - ast::FunctionType * adapter = ast::deepCopy( adaptee ); - if ( isDynRet( adapter, typeVars ) ) { - makeRetParam( adapter ); - } - adapter->params.emplace( adapter->params.begin(), - new ast::PointerType( new ast::FunctionType( ast::VariableArgs ) ) - ); - return adapter; -} - -CallAdapter::CallAdapter() : tmpNamer( "_temp" ) {} - -void CallAdapter::previsit( ast::Decl const * ) { - // Prevent type declaration information from leaking out. - GuardScope( scopeTypeVars ); -} - -ast::FunctionDecl const * CallAdapter::previsit( ast::FunctionDecl const * decl ) { - // Prevent type declaration information from leaking out. - GuardScope( scopeTypeVars ); - - if ( nullptr == decl->stmts ) { - return decl; - } - - GuardValue( retval ); - - // Process polymorphic return value. - retval = nullptr; - ast::FunctionType const * type = decl->type; - if ( isDynRet( type ) && decl->linkage != ast::Linkage::C ) { - retval = decl->returns.front(); - - // Give names to unnamed return values. - if ( "" == retval->name ) { - auto mutRet = ast::mutate( retval ); - mutRet->name = "_retparam"; - mutRet->linkage = ast::Linkage::C; - retval = mutRet; - decl = ast::mutate_field_index( decl, - &ast::FunctionDecl::returns, 0, mutRet ); - } - } - - // The formal_usage/expr_id values may be off if we get them from the - // type, trying the declaration instead. - makeTypeVarMap( type, scopeTypeVars ); - - // Get all needed adapters from the call. We will forward them. - ast::vector functions; - for ( ast::ptr const & assertion : type->assertions ) { - auto atype = assertion->result.get(); - findFunction( atype, functions, scopeTypeVars, needsAdapter ); - } - - for ( ast::ptr const & arg : type->params ) { - findFunction( arg, functions, scopeTypeVars, needsAdapter ); - } - - for ( auto funcType : functions ) { - std::string mangleName = mangleAdapterName( funcType, scopeTypeVars ); - if ( adapters.contains( mangleName ) ) continue; - std::string adapterName = makeAdapterName( mangleName ); - // TODO: The forwarding here is problematic because these - // declarations are not rooted anywhere in the translation unit. - adapters.insert( - mangleName, - new ast::ObjectDecl( - decl->location, - adapterName, - new ast::PointerType( - makeAdapterType( funcType, scopeTypeVars ) ), - nullptr, // init - ast::Storage::Classes(), - ast::Linkage::C - ) - ); - } - - return decl; -} - -void CallAdapter::previsit( ast::TypeDecl const * decl ) { - addToTypeVarMap( decl, scopeTypeVars ); -} - -void CallAdapter::previsit( ast::CommaExpr const * expr ) { - // Attempting to find application expressions that were mutated by the - // copy constructor passes to use an explicit return variable, so that - // the variable can be reused as a parameter to the call rather than - // creating a new temporary variable. Previously this step was an - // optimization, but with the introduction of tuples and UniqueExprs, - // it is necessary to ensure that they use the same variable. - // Essentially, looking for pattern: - // (x=f(...), x) - // To compound the issue, the right side can be *x, etc. - // because of lvalue-returning functions - if ( auto assign = expr->arg1.as() ) { - if ( CodeGen::isAssignment( ast::getFunctionName( assign ) ) ) { - assert( 2 == assign->args.size() ); - if ( auto app = assign->args.back().as() ) { - // First argument is assignable, so it must be an lvalue, - // so it should be legal to takes its address. - retVals.insert_or_assign( app, assign->args.front() ); - } - } - } -} - -ast::Expr const * CallAdapter::postvisit( ast::ApplicationExpr const * expr ) { - assert( expr->func->result ); - ast::FunctionType const * function = getFunctionType( expr->func->result ); - assertf( function, "ApplicationExpr has non-function type %s", - toCString( expr->func->result ) ); - - if ( auto newExpr = handleIntrinsics( expr ) ) { - return newExpr; - } - - ast::ApplicationExpr * mutExpr = ast::mutate( expr ); - ast::Expr const * ret = expr; - - // TODO: This entire section should probably be refactored to do less - // pushing to the front/middle of a vector. - ptrdiff_t initArgCount = mutExpr->args.size(); - - TypeVarMap exprTypeVars; - // TODO: Should this take into account the variables already bound in - // scopeTypeVars ([ex] remove them from exprTypeVars)? - makeTypeVarMap( function, exprTypeVars ); - auto dynRetType = isDynRet( function, exprTypeVars ); - - // NOTE: addDynRetParam needs to know the actual (generated) return type - // so it can make a temporary variable, so pass the result type form the - // `expr` `passTypeVars` needs to know the program-text return type ([ex] - // the distinction between _conc_T30 and T3(int)) concRetType may not be - // a good name in one or both of these places. - if ( dynRetType ) { - ast::Type const * result = mutExpr->result; - ast::Type const * concRetType = result->isVoid() ? nullptr : result; - // [Comment from before translation.] - // Used to use dynRetType instead of concRetType. - ret = addDynRetParam( mutExpr, concRetType ); - } else if ( needsAdapter( function, scopeTypeVars ) - && !needsAdapter( function, exprTypeVars ) ) { - // Change the application so it calls the adapter rather than the - // passed function. - ret = applyAdapter( mutExpr, function ); - } - - assert( typeSubs ); - ast::vector::iterator argIt = - passTypeVars( mutExpr, function ); - addInferredParams( mutExpr, argIt, function, exprTypeVars ); - - argIt = mutExpr->args.begin(); - std::advance( argIt, ( mutExpr->args.size() - initArgCount ) ); - - boxParams( mutExpr, argIt, function, exprTypeVars ); - passAdapters( mutExpr, function, exprTypeVars ); - - return ret; -} - -bool isPolyDeref( ast::UntypedExpr const * expr, - TypeVarMap const & typeVars, - ast::TypeSubstitution const * typeSubs ) { - if ( expr->result && isPolyType( expr->result, typeVars, typeSubs ) ) { - if ( auto name = expr->func.as() ) { - if ( "*?" == name->name ) { - return true; - } - } - } - return false; -} - -ast::Expr const * CallAdapter::postvisit( ast::UntypedExpr const * expr ) { - if ( isPolyDeref( expr, scopeTypeVars, typeSubs ) ) { - return expr->args.front(); - } - return expr; -} - -void CallAdapter::previsit( ast::AddressExpr const * ) { - visit_children = false; -} - -ast::Expr const * CallAdapter::postvisit( ast::AddressExpr const * expr ) { - assert( expr->arg->result ); - assert( !expr->arg->result->isVoid() ); - - bool doesNeedAdapter = false; - if ( auto un = expr->arg.as() ) { - if ( isPolyDeref( un, scopeTypeVars, typeSubs ) ) { - if ( auto app = un->args.front().as() ) { - assert( app->func->result ); - auto function = getFunctionType( app->func->result ); - assert( function ); - doesNeedAdapter = needsAdapter( function, scopeTypeVars ); - } - } - } - // isPolyType check needs to happen before mutating expr arg, - // so pull it forward out of the if condition. - expr = ast::mutate_field( expr, &ast::AddressExpr::arg, - expr->arg->accept( *visitor ) ); - // But must happen after mutate, since argument might change - // (ex. intrinsic *?, ?[?]) re-evaluate above comment. - bool polyType = isPolyType( expr->arg->result, scopeTypeVars, typeSubs ); - if ( polyType || doesNeedAdapter ) { - ast::Expr * ret = ast::mutate( expr->arg.get() ); - ret->result = ast::deepCopy( expr->result ); - return ret; - } else { - return expr; - } -} - -ast::ReturnStmt const * CallAdapter::previsit( ast::ReturnStmt const * stmt ) { - // Since retval is set when the return type is dynamic, this function - // should have been converted to void return & out parameter. - if ( retval && stmt->expr ) { - assert( stmt->expr->result ); - assert( !stmt->expr->result->isVoid() ); - return ast::mutate_field( stmt, &ast::ReturnStmt::expr, nullptr ); - } - return stmt; -} - -void CallAdapter::beginScope() { - adapters.beginScope(); -} - -void CallAdapter::endScope() { - adapters.endScope(); -} - -/// Find instances of polymorphic type parameters. -struct PolyFinder { - TypeVarMap const & typeVars; - bool result = false; - PolyFinder( TypeVarMap const & tvs ) : typeVars( tvs ) {} - - void previsit( ast::TypeInstType const * type ) { - if ( isPolyType( type, typeVars ) ) result = true; - } -}; - -/// True if these is an instance of a polymorphic type parameter in the type. -bool hasPolymorphism( ast::Type const * type, TypeVarMap const & typeVars ) { - return ast::Pass::read( type, typeVars ); -} - -ast::vector::iterator CallAdapter::passTypeVars( - ast::ApplicationExpr * expr, - ast::FunctionType const * function ) { - assert( typeSubs ); - ast::vector::iterator arg = expr->args.begin(); - // Pass size/align for type variables. - for ( ast::ptr const & typeVar : function->forall ) { - if ( !typeVar->base->isComplete() ) continue; - ast::Type const * concrete = typeSubs->lookup( typeVar ); - if ( !concrete ) { - // Should this be an assertion? - SemanticError( expr, toString( typeSubs, - "\nunbound type variable: ", typeVar->typeString(), - " in application " ) ); - } - arg = expr->args.insert( arg, - new ast::SizeofExpr( expr->location, ast::deepCopy( concrete ) ) ); - arg++; - arg = expr->args.insert( arg, - new ast::AlignofExpr( expr->location, ast::deepCopy( concrete ) ) ); - arg++; - } - return arg; -} - -ast::Expr const * CallAdapter::addRetParam( - ast::ApplicationExpr * expr, ast::Type const * retType ) { - // Create temporary to hold return value of polymorphic function and - // produce that temporary as a result using a comma expression. - assert( retType ); - - ast::Expr * paramExpr = nullptr; - // Try to use existing return value parameter if it exists, - // otherwise create a new temporary. - if ( retVals.count( expr ) ) { - paramExpr = ast::deepCopy( retVals[ expr ] ); - } else { - auto newObj = makeTemporary( expr->location, ast::deepCopy( retType ) ); - paramExpr = new ast::VariableExpr( expr->location, newObj ); - } - ast::Expr * retExpr = ast::deepCopy( paramExpr ); - - // If the type of the temporary is not polpmorphic, box temporary by - // taking its address; otherwise the temporary is already boxed and can - // be used directly. - if ( !isPolyType( paramExpr->result, scopeTypeVars, typeSubs ) ) { - paramExpr = new ast::AddressExpr( paramExpr->location, paramExpr ); - } - // Add argument to function call. - expr->args.insert( expr->args.begin(), paramExpr ); - // Build a comma expression to call the function and return a value. - ast::CommaExpr * comma = new ast::CommaExpr( - expr->location, expr, retExpr ); - comma->env = expr->env; - expr->env = nullptr; - return comma; -} - -ast::Expr const * CallAdapter::addDynRetParam( - ast::ApplicationExpr * expr, ast::Type const * polyType ) { - assert( typeSubs ); - ast::Type const * concrete = replaceWithConcrete( polyType, *typeSubs ); - // Add out-parameter for return value. - return addRetParam( expr, concrete ); -} - -ast::Expr const * CallAdapter::applyAdapter( - ast::ApplicationExpr * expr, - ast::FunctionType const * function ) { - ast::Expr const * ret = expr; - if ( isDynRet( function, scopeTypeVars ) ) { - ret = addRetParam( expr, function->returns.front() ); - } - std::string mangleName = mangleAdapterName( function, scopeTypeVars ); - std::string adapterName = makeAdapterName( mangleName ); - - // Cast adaptee to `void (*)()`, since it may have any type inside a - // polymorphic function. - ast::Type const * adapteeType = new ast::PointerType( - new ast::FunctionType( ast::VariableArgs ) ); - expr->args.insert( expr->args.begin(), - new ast::CastExpr( expr->location, expr->func, adapteeType ) ); - // The result field is never set on NameExpr. / Now it is. - auto head = new ast::NameExpr( expr->location, adapterName ); - head->result = ast::deepCopy( adapteeType ); - expr->func = head; - - return ret; -} - -/// Cast parameters to polymorphic functions so that types are replaced with -/// `void *` if they are type parameters in the formal type. -/// This gets rid of warnings from gcc. -void addCast( - ast::ptr & actual, - ast::Type const * formal, - TypeVarMap const & typeVars ) { - // Type contains polymorphism, but isn't exactly a polytype, in which - // case it has some real actual type (ex. unsigned int) and casting to - // `void *` is wrong. - if ( hasPolymorphism( formal, typeVars ) - && !isPolyType( formal, typeVars ) ) { - ast::Type const * newType = ast::deepCopy( formal ); - newType = scrubTypeVars( newType, typeVars ); - actual = new ast::CastExpr( actual->location, actual, newType ); - } -} - -void CallAdapter::boxParam( ast::ptr & arg, - ast::Type const * param, TypeVarMap const & exprTypeVars ) { - assertf( arg->result, "arg does not have result: %s", toCString( arg ) ); - addCast( arg, param, exprTypeVars ); - if ( !needsBoxing( param, arg->result, exprTypeVars, typeSubs ) ) { - return; - } - CodeLocation const & location = arg->location; - - if ( arg->get_lvalue() ) { - // The argument expression may be CFA lvalue, but not C lvalue, - // so apply generalizedLvalue transformations. - // if ( auto var = dynamic_cast( arg ) ) { - // if ( dynamic_cast( varExpr->var->get_type() ) ){ - // // temporary hack - don't box arrays, because &arr is not the same as &arr[0] - // return; - // } - // } - arg = generalizedLvalue( new ast::AddressExpr( arg->location, arg ) ); - if ( !ResolvExpr::typesCompatible( param, arg->result ) ) { - // Silence warnings by casting boxed parameters when the actually - // type does not match up with the formal type. - arg = new ast::CastExpr( location, arg, ast::deepCopy( param ) ); - } - } else { - // Use type computed in unification to declare boxed variables. - ast::ptr newType = ast::deepCopy( param ); - if ( typeSubs ) typeSubs->apply( newType ); - ast::ObjectDecl * newObj = makeTemporary( location, newType ); - auto assign = ast::UntypedExpr::createCall( location, "?=?", { - new ast::VariableExpr( location, newObj ), - arg, - } ); - stmtsToAddBefore.push_back( new ast::ExprStmt( location, assign ) ); - arg = new ast::AddressExpr( - new ast::VariableExpr( location, newObj ) ); - } -} - -void CallAdapter::boxParams( - ast::ApplicationExpr const * expr, - ast::vector::iterator arg, - ast::FunctionType const * function, - const TypeVarMap & typeVars ) { - for ( auto param : function->params ) { - assertf( arg != expr->args.end(), - "boxParams: missing argument for param %s to %s in %s", - toCString( param ), toCString( function ), toCString( expr ) ); - boxParam( *arg, param, typeVars ); - ++arg; - } -} - -void CallAdapter::addInferredParams( - ast::ApplicationExpr * expr, - ast::vector::iterator arg, - ast::FunctionType const * functionType, - TypeVarMap const & typeVars ) { - ast::vector::iterator cur = arg; - for ( auto assertion : functionType->assertions ) { - auto inferParam = expr->inferred.inferParams().find( - assertion->var->uniqueId ); - assertf( inferParam != expr->inferred.inferParams().end(), - "addInferredParams missing inferred parameter: %s in: %s", - toCString( assertion ), toCString( expr ) ); - ast::ptr newExpr = ast::deepCopy( inferParam->second.expr ); - boxParam( newExpr, assertion->result, typeVars ); - cur = expr->args.insert( cur, newExpr.release() ); - ++cur; - } -} - -/// Modifies the ApplicationExpr to accept adapter functions for its -/// assertion and parameters, declares the required adapters. -void CallAdapter::passAdapters( - ast::ApplicationExpr * expr, - ast::FunctionType const * type, - const TypeVarMap & exprTypeVars ) { - // Collect a list of function types passed as parameters or implicit - // parameters (assertions). - ast::vector const & paramList = type->params; - ast::vector functions; - - for ( ast::ptr const & assertion : type->assertions ) { - findFunction( assertion->result, functions, exprTypeVars, needsAdapter ); - } - for ( ast::ptr const & arg : paramList ) { - findFunction( arg, functions, exprTypeVars, needsAdapter ); - } - - // Parameter function types for which an appropriate adapter has been - // generated. We cannot use the types after applying substitutions, - // since two different parameter types may be unified to the same type. - std::set adaptersDone; - - CodeLocation const & location = expr->location; - - for ( ast::ptr const & funcType : functions ) { - std::string mangleName = Mangle::mangle( funcType ); - - // Only attempt to create an adapter or pass one as a parameter if we - // haven't already done so for this pre-substitution parameter - // function type. - // The second part of the result if is if the element was inserted. - if ( !adaptersDone.insert( mangleName ).second ) continue; - - // Apply substitution to type variables to figure out what the - // adapter's type should look like. (Copy to make the release safe.) - assert( typeSubs ); - auto result = typeSubs->apply( ast::deepCopy( funcType ) ); - ast::FunctionType * realType = ast::mutate( result.node.release() ); - mangleName = Mangle::mangle( realType ); - mangleName += makePolyMonoSuffix( funcType, exprTypeVars ); - - // Check if the adapter has already been created, or has to be. - using AdapterIter = decltype(adapters)::iterator; - AdapterIter adapter = adapters.find( mangleName ); - if ( adapter == adapters.end() ) { - ast::FunctionDecl * newAdapter = makeAdapter( - funcType, realType, mangleName, exprTypeVars, location ); - std::pair answer = - adapters.insert( mangleName, newAdapter ); - adapter = answer.first; - stmtsToAddBefore.push_back( - new ast::DeclStmt( location, newAdapter ) ); - } - assert( adapter != adapters.end() ); - - // Add the approprate adapter as a parameter. - expr->args.insert( expr->args.begin(), - new ast::VariableExpr( location, adapter->second ) ); - } -} - -// Parameter and argument may be used wrong around here. -ast::Expr * makeAdapterArg( - ast::DeclWithType const * param, - ast::Type const * arg, - ast::Type const * realParam, - TypeVarMap const & typeVars, - CodeLocation const & location ) { - assert( param ); - assert( arg ); - assert( realParam ); - if ( isPolyType( realParam, typeVars ) && !isPolyType( arg ) ) { - ast::UntypedExpr * deref = ast::UntypedExpr::createDeref( - location, - new ast::CastExpr( location, - new ast::VariableExpr( location, param ), - new ast::PointerType( ast::deepCopy( arg ) ) - ) - ); - deref->result = ast::deepCopy( arg ); - return deref; - } - return new ast::VariableExpr( location, param ); -} - -// This seems to be one of the problematic functions. -void addAdapterParams( - ast::ApplicationExpr * adaptee, - ast::vector::const_iterator arg, - ast::vector::iterator param, - ast::vector::iterator paramEnd, - ast::vector::const_iterator realParam, - TypeVarMap const & typeVars, - CodeLocation const & location ) { - UniqueName paramNamer( "_p" ); - for ( ; param != paramEnd ; ++param, ++arg, ++realParam ) { - if ( "" == (*param)->name ) { - auto mutParam = (*param).get_and_mutate(); - mutParam->name = paramNamer.newName(); - mutParam->linkage = ast::Linkage::C; - } - adaptee->args.push_back( - makeAdapterArg( *param, *arg, *realParam, typeVars, location ) ); - } -} - -ast::FunctionDecl * CallAdapter::makeAdapter( - ast::FunctionType const * adaptee, - ast::FunctionType const * realType, - std::string const & mangleName, - TypeVarMap const & typeVars, - CodeLocation const & location ) const { - ast::FunctionType * adapterType = makeAdapterType( adaptee, typeVars ); - adapterType = ast::mutate( scrubTypeVars( adapterType, typeVars ) ); - - // Some of these names will be overwritten, but it gives a default. - UniqueName pNamer( "_param" ); - UniqueName rNamer( "_ret" ); - - bool first = true; - - ast::FunctionDecl * adapterDecl = new ast::FunctionDecl( location, - makeAdapterName( mangleName ), - {}, // forall - {}, // assertions - map_range>( adapterType->params, - [&pNamer, &location, &first]( ast::ptr const & param ) { - // [Trying to make the generated code match exactly more often.] - if ( first ) { - first = false; - return new ast::ObjectDecl( location, "_adaptee", param ); - } - return new ast::ObjectDecl( location, pNamer.newName(), param ); - } ), - map_range>( adapterType->returns, - [&rNamer, &location]( ast::ptr const & retval ) { - return new ast::ObjectDecl( location, rNamer.newName(), retval ); - } ), - nullptr, // stmts - {}, // storage - ast::Linkage::C - ); - - ast::DeclWithType * adapteeDecl = - adapterDecl->params.front().get_and_mutate(); - adapteeDecl->name = "_adaptee"; - - // Do not carry over attributes to real type parameters/return values. - auto mutRealType = ast::mutate( realType ); - for ( ast::ptr & decl : mutRealType->params ) { - if ( decl->attributes.empty() ) continue; - auto mut = ast::mutate( decl.get() ); - mut->attributes.clear(); - decl = mut; - } - for ( ast::ptr & decl : mutRealType->returns ) { - if ( decl->attributes.empty() ) continue; - auto mut = ast::mutate( decl.get() ); - mut->attributes.clear(); - decl = mut; - } - realType = mutRealType; - - ast::ApplicationExpr * adapteeApp = new ast::ApplicationExpr( location, - new ast::CastExpr( location, - new ast::VariableExpr( location, adapteeDecl ), - new ast::PointerType( realType ) - ) - ); - - for ( auto group : group_iterate( realType->assertions, - adapterType->assertions, adaptee->assertions ) ) { - auto assertArg = std::get<0>( group ); - auto assertParam = std::get<1>( group ); - auto assertReal = std::get<2>( group ); - adapteeApp->args.push_back( makeAdapterArg( - assertParam->var, assertArg->var->get_type(), - assertReal->var->get_type(), typeVars, location - ) ); - } - - ast::vector::const_iterator - arg = realType->params.begin(), - param = adapterType->params.begin(), - realParam = adaptee->params.begin(); - ast::vector::iterator - paramDecl = adapterDecl->params.begin(); - // Skip adaptee parameter in the adapter type. - ++param; - ++paramDecl; - - ast::Stmt * bodyStmt; - // Returns void/nothing. - if ( realType->returns.empty() ) { - addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), - realParam, typeVars, location ); - bodyStmt = new ast::ExprStmt( location, adapteeApp ); - // Returns a polymorphic type. - } else if ( isDynType( adaptee->returns.front(), typeVars ) ) { - ast::UntypedExpr * assign = new ast::UntypedExpr( location, - new ast::NameExpr( location, "?=?" ) ); - ast::UntypedExpr * deref = ast::UntypedExpr::createDeref( location, - new ast::CastExpr( location, - new ast::VariableExpr( location, *paramDecl++ ), - new ast::PointerType( - ast::deepCopy( realType->returns.front() ) ) ) ); - assign->args.push_back( deref ); - addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), - realParam, typeVars, location ); - assign->args.push_back( adapteeApp ); - bodyStmt = new ast::ExprStmt( location, assign ); - // Adapter for a function that returns a monomorphic value. - } else { - addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(), - realParam, typeVars, location ); - bodyStmt = new ast::ReturnStmt( location, adapteeApp ); - } - - adapterDecl->stmts = new ast::CompoundStmt( location, { bodyStmt } ); - return adapterDecl; -} - -ast::Expr const * makeIncrDecrExpr( - CodeLocation const & location, - ast::ApplicationExpr const * expr, - ast::Type const * polyType, - bool isIncr ) { - ast::NameExpr * opExpr = - new ast::NameExpr( location, isIncr ? "?+=?" : "?-=?" ); - ast::UntypedExpr * addAssign = new ast::UntypedExpr( location, opExpr ); - if ( auto address = expr->args.front().as() ) { - addAssign->args.push_back( address->arg ); - } else { - addAssign->args.push_back( expr->args.front() ); - } - addAssign->args.push_back( new ast::NameExpr( location, - sizeofName( Mangle::mangleType( polyType ) ) ) ); - addAssign->result = ast::deepCopy( expr->result ); - addAssign->env = expr->env ? expr->env : addAssign->env; - return addAssign; -} - -/// Handles intrinsic functions for postvisit ApplicationExpr. -ast::Expr const * CallAdapter::handleIntrinsics( - ast::ApplicationExpr const * expr ) { - auto varExpr = expr->func.as(); - if ( !varExpr || varExpr->var->linkage != ast::Linkage::Intrinsic ) { - return nullptr; - } - std::string const & varName = varExpr->var->name; - - // Index Intrinsic: - if ( "?[?]" == varName ) { - assert( expr->result ); - assert( 2 == expr->args.size() ); - - ast::Type const * baseType1 = - isPolyPtr( expr->args.front()->result, scopeTypeVars, typeSubs ); - ast::Type const * baseType2 = - isPolyPtr( expr->args.back()->result, scopeTypeVars, typeSubs ); - // If neither argument is a polymorphic pointer, do nothing. - if ( !baseType1 && !baseType2 ) { - return expr; - } - // The arguments cannot both be polymorphic pointers. - assert( !baseType1 || !baseType2 ); - // (So exactly one of the arguments is a polymorphic pointer.) - - CodeLocation const & location = expr->location; - CodeLocation const & location1 = expr->args.front()->location; - CodeLocation const & location2 = expr->args.back()->location; - - ast::UntypedExpr * ret = new ast::UntypedExpr( location, - new ast::NameExpr( location, "?+?" ) ); - if ( baseType1 ) { - auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { - expr->args.back(), - new ast::SizeofExpr( location1, deepCopy( baseType1 ) ), - } ); - ret->args.push_back( expr->args.front() ); - ret->args.push_back( multiply ); - } else { - assert( baseType2 ); - auto multiply = ast::UntypedExpr::createCall( location1, "?*?", { - expr->args.front(), - new ast::SizeofExpr( location2, deepCopy( baseType2 ) ), - } ); - ret->args.push_back( multiply ); - ret->args.push_back( expr->args.back() ); - } - ret->result = ast::deepCopy( expr->result ); - ret->env = expr->env ? expr->env : ret->env; - return ret; - // Dereference Intrinsic: - } else if ( "*?" == varName ) { - assert( expr->result ); - assert( 1 == expr->args.size() ); - - // If this isn't for a poly type, then do nothing. - if ( !isPolyType( expr->result, scopeTypeVars, typeSubs ) ) { - return expr; - } - - // Remove dereference from polymorphic types since they are boxed. - ast::Expr * ret = ast::deepCopy( expr->args.front() ); - // Fix expression type to remove pointer. - ret->result = expr->result; - ret->env = expr->env ? expr->env : ret->env; - return ret; - // Post-Increment/Decrement Intrinsics: - } else if ( "?++" == varName || "?--" == varName ) { - assert( expr->result ); - assert( 1 == expr->args.size() ); - - ast::Type const * baseType = - isPolyType( expr->result, scopeTypeVars, typeSubs ); - if ( nullptr == baseType ) { - return expr; - } - ast::Type * tempType = ast::deepCopy( expr->result ); - if ( typeSubs ) { - auto result = typeSubs->apply( tempType ); - tempType = ast::mutate( result.node.release() ); - } - CodeLocation const & location = expr->location; - ast::ObjectDecl * newObj = makeTemporary( location, tempType ); - ast::VariableExpr * tempExpr = - new ast::VariableExpr( location, newObj ); - ast::UntypedExpr * assignExpr = new ast::UntypedExpr( location, - new ast::NameExpr( location, "?=?" ) ); - assignExpr->args.push_back( ast::deepCopy( tempExpr ) ); - if ( auto address = expr->args.front().as() ) { - assignExpr->args.push_back( ast::deepCopy( address->arg ) ); - } else { - assignExpr->args.push_back( ast::deepCopy( expr->args.front() ) ); - } - return new ast::CommaExpr( location, - new ast::CommaExpr( location, - assignExpr, - makeIncrDecrExpr( location, expr, baseType, "?++" == varName ) - ), - tempExpr - ); - // Pre-Increment/Decrement Intrinsics: - } else if ( "++?" == varName || "--?" == varName ) { - assert( expr->result ); - assert( 1 == expr->args.size() ); - - ast::Type const * baseType = - isPolyType( expr->result, scopeTypeVars, typeSubs ); - if ( nullptr == baseType ) { - return expr; - } - return makeIncrDecrExpr( - expr->location, expr, baseType, "++?" == varName ); - // Addition and Subtration Intrinsics: - } else if ( "?+?" == varName || "?-?" == varName ) { - assert( expr->result ); - assert( 2 == expr->args.size() ); - - auto baseType1 = - isPolyPtr( expr->args.front()->result, scopeTypeVars, typeSubs ); - auto baseType2 = - isPolyPtr( expr->args.back()->result, scopeTypeVars, typeSubs ); - - CodeLocation const & location = expr->location; - CodeLocation const & location1 = expr->args.front()->location; - CodeLocation const & location2 = expr->args.back()->location; - // LHS op RHS -> (LHS op RHS) / sizeof(LHS) - if ( baseType1 && baseType2 ) { - auto divide = ast::UntypedExpr::createCall( location, "?/?", { - expr, - new ast::SizeofExpr( location, deepCopy( baseType1 ) ), - } ); - if ( expr->env ) divide->env = expr->env; - return divide; - // LHS op RHS -> LHS op (RHS * sizeof(LHS)) - } else if ( baseType1 ) { - auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { - expr->args.back(), - new ast::SizeofExpr( location1, deepCopy( baseType1 ) ), - } ); - return ast::mutate_field_index( - expr, &ast::ApplicationExpr::args, 1, multiply ); - // LHS op RHS -> (LHS * sizeof(RHS)) op RHS - } else if ( baseType2 ) { - auto multiply = ast::UntypedExpr::createCall( location1, "?*?", { - expr->args.front(), - new ast::SizeofExpr( location2, deepCopy( baseType2 ) ), - } ); - return ast::mutate_field_index( - expr, &ast::ApplicationExpr::args, 0, multiply ); - } - // Addition and Subtration Relative Assignment Intrinsics: - } else if ( "?+=?" == varName || "?-=?" == varName ) { - assert( expr->result ); - assert( 2 == expr->args.size() ); - - CodeLocation const & location1 = expr->args.front()->location; - CodeLocation const & location2 = expr->args.back()->location; - auto baseType = isPolyPtr( expr->result, scopeTypeVars, typeSubs ); - // LHS op RHS -> LHS op (RHS * sizeof(LHS)) - if ( baseType ) { - auto multiply = ast::UntypedExpr::createCall( location2, "?*?", { - expr->args.back(), - new ast::SizeofExpr( location1, deepCopy( baseType ) ), - } ); - return ast::mutate_field_index( - expr, &ast::ApplicationExpr::args, 1, multiply ); - } - } - return expr; -} - -ast::ObjectDecl * CallAdapter::makeTemporary( - CodeLocation const & location, ast::Type const * type ) { - auto newObj = new ast::ObjectDecl( location, tmpNamer.newName(), type ); - stmtsToAddBefore.push_back( new ast::DeclStmt( location, newObj ) ); - return newObj; -} - -// -------------------------------------------------------------------------- -/// Modifies declarations to accept implicit parameters. -/// * Move polymorphic returns in function types to pointer-type parameters. -/// * Adds type size and assertion parameters to parameter lists. -struct DeclAdapter final { - ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); - ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl ); -private: - void addAdapters( ast::FunctionDecl * decl, TypeVarMap & localTypeVars ); -}; - -// size/align/offset parameters may not be used, so add the unused attribute. -ast::ObjectDecl * makeObj( - CodeLocation const & location, std::string const & name ) { - return new ast::ObjectDecl( location, name, - makeSizeAlignType(), - nullptr, ast::Storage::Classes(), ast::Linkage::C, nullptr, - { new ast::Attribute( "unused" ) } ); -} - -ast::FunctionDecl const * DeclAdapter::previsit( ast::FunctionDecl const * decl ) { - TypeVarMap localTypeVars; - makeTypeVarMap( decl, localTypeVars ); - - auto mutDecl = mutate( decl ); - - // Move polymorphic return type to parameter list. - if ( isDynRet( mutDecl->type ) ) { - auto ret = strict_dynamic_cast( - mutDecl->returns.front().get_and_mutate() ); - ret->set_type( new ast::PointerType( ret->type ) ); - mutDecl->params.insert( mutDecl->params.begin(), ret ); - mutDecl->returns.erase( mutDecl->returns.begin() ); - ret->init = nullptr; - } - - // Add size/align and assertions for type parameters to parameter list. - ast::vector inferredParams; - ast::vector layoutParams; - for ( ast::ptr & typeParam : mutDecl->type_params ) { - auto mutParam = mutate( typeParam.get() ); - // Add all size and alignment parameters to parameter list. - if ( mutParam->isComplete() ) { - ast::TypeInstType paramType( mutParam ); - std::string paramName = Mangle::mangleType( ¶mType ); - - auto sizeParam = makeObj( typeParam->location, sizeofName( paramName ) ); - layoutParams.emplace_back( sizeParam ); - - auto alignParam = makeObj( typeParam->location, alignofName( paramName ) ); - layoutParams.emplace_back( alignParam ); - } - // Assertions should be stored in the main list. - assert( mutParam->assertions.empty() ); - typeParam = mutParam; - } - for ( ast::ptr & assert : mutDecl->assertions ) { - // Assertion parameters may not be used in body, - // pass along with unused attribute. - assert.get_and_mutate()->attributes.push_back( - new ast::Attribute( "unused" ) ); - inferredParams.push_back( assert ); - } - mutDecl->assertions.clear(); - - // Prepend each argument group. From last group to first. addAdapters - // does do the same, it just does it itself and see all other parameters. - spliceBegin( mutDecl->params, inferredParams ); - spliceBegin( mutDecl->params, layoutParams ); - addAdapters( mutDecl, localTypeVars ); - - // Now have to update the type to match the declaration. - ast::FunctionType * type = new ast::FunctionType( - mutDecl->type->isVarArgs, mutDecl->type->qualifiers ); - // The forall clauses don't match until Eraser. The assertions are empty. - for ( auto param : mutDecl->params ) { - type->params.emplace_back( param->get_type() ); - } - for ( auto retval : mutDecl->returns ) { - type->returns.emplace_back( retval->get_type() ); - } - mutDecl->type = type; - - return mutDecl; -} - -ast::FunctionDecl const * DeclAdapter::postvisit( - ast::FunctionDecl const * decl ) { - ast::FunctionDecl * mutDecl = mutate( decl ); - if ( !mutDecl->returns.empty() && mutDecl->stmts - // Intrinsic functions won't be using the _retval so no need to - // generate it. - && mutDecl->linkage != ast::Linkage::Intrinsic - // Remove check for prefix once thunks properly use ctor/dtors. - && !isPrefix( mutDecl->name, "_thunk" ) - && !isPrefix( mutDecl->name, "_adapter" ) ) { - assert( 1 == mutDecl->returns.size() ); - ast::DeclWithType const * retval = mutDecl->returns.front(); - if ( "" == retval->name ) { - retval = ast::mutate_field( - retval, &ast::DeclWithType::name, "_retval" ); - mutDecl->returns.front() = retval; - } - auto stmts = mutDecl->stmts.get_and_mutate(); - stmts->kids.push_front( new ast::DeclStmt( retval->location, retval ) ); - ast::DeclWithType * newRet = ast::deepCopy( retval ); - mutDecl->returns.front() = newRet; - } - // Errors should have been caught by this point, remove initializers from - // parameters to allow correct codegen of default arguments. - for ( ast::ptr & param : mutDecl->params ) { - if ( auto obj = param.as() ) { - param = ast::mutate_field( obj, &ast::ObjectDecl::init, nullptr ); - } - } - return mutDecl; -} - -void DeclAdapter::addAdapters( - ast::FunctionDecl * mutDecl, TypeVarMap & localTypeVars ) { - ast::vector functions; - for ( ast::ptr & arg : mutDecl->params ) { - ast::Type const * type = arg->get_type(); - type = findAndReplaceFunction( type, functions, localTypeVars, needsAdapter ); - arg.get_and_mutate()->set_type( type ); - } - std::set adaptersDone; - for ( ast::ptr const & func : functions ) { - std::string mangleName = mangleAdapterName( func, localTypeVars ); - if ( adaptersDone.find( mangleName ) != adaptersDone.end() ) { - continue; - } - std::string adapterName = makeAdapterName( mangleName ); - // The adapter may not actually be used, so make sure it has unused. - mutDecl->params.insert( mutDecl->params.begin(), new ast::ObjectDecl( - mutDecl->location, adapterName, - new ast::PointerType( makeAdapterType( func, localTypeVars ) ), - nullptr, {}, {}, nullptr, - { new ast::Attribute( "unused" ) } ) ); - adaptersDone.insert( adaptersDone.begin(), mangleName ); - } -} - -// -------------------------------------------------------------------------- -// TODO: Ideally, there would be no floating nodes at all. -/// Corrects the floating nodes created in CallAdapter. -struct RewireAdapters final : public ast::WithGuards { - ScopedMap adapters; - void beginScope() { adapters.beginScope(); } - void endScope() { adapters.endScope(); } - void previsit( ast::FunctionDecl const * decl ); - ast::VariableExpr const * previsit( ast::VariableExpr const * expr ); -}; - -void RewireAdapters::previsit( ast::FunctionDecl const * decl ) { - GuardScope( adapters ); - for ( ast::ptr const & param : decl->params ) { - if ( auto objectParam = param.as() ) { - adapters.insert( objectParam->name, objectParam ); - } - } -} - -ast::VariableExpr const * RewireAdapters::previsit( - ast::VariableExpr const * expr ) { - // If the node is not floating, we can skip. - if ( expr->var->isManaged() ) return expr; - auto it = adapters.find( expr->var->name ); - assertf( it != adapters.end(), "Could not correct floating node." ); - return ast::mutate_field( expr, &ast::VariableExpr::var, it->second ); -} - -// -------------------------------------------------------------------------- -/// Inserts code to access polymorphic layout inforation. -/// * Replaces member and size/alignment/offsetof expressions on polymorphic -/// generic types with calculated expressions. -/// * Replaces member expressions for polymorphic types with calculated -/// add-field-offset-and-dereference. -/// * Calculates polymorphic offsetof expressions from offset array. -/// * Inserts dynamic calculation of polymorphic type layouts where needed. -struct PolyGenericCalculator final : - public ast::WithConstTypeSubstitution, - public ast::WithDeclsToAdd<>, - public ast::WithGuards, - public ast::WithStmtsToAdd<>, - public ast::WithVisitorRef { - PolyGenericCalculator(); - - void previsit( ast::FunctionDecl const * decl ); - void previsit( ast::TypedefDecl const * decl ); - void previsit( ast::TypeDecl const * decl ); - ast::Decl const * postvisit( ast::TypeDecl const * decl ); - ast::StructDecl const * previsit( ast::StructDecl const * decl ); - ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); - ast::DeclStmt const * previsit( ast::DeclStmt const * stmt ); - ast::Expr const * postvisit( ast::MemberExpr const * expr ); - void previsit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::SizeofExpr const * expr ); - ast::Expr const * postvisit( ast::AlignofExpr const * expr ); - ast::Expr const * postvisit( ast::OffsetofExpr const * expr ); - ast::Expr const * postvisit( ast::OffsetPackExpr const * expr ); - - void beginScope(); - void endScope(); -private: - /// Makes a new variable in the current scope with the given name, - /// type and optional initializer. - ast::ObjectDecl * makeVar( - CodeLocation const & location, std::string const & name, - ast::Type const * type, ast::Init const * init = nullptr ); - /// 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( CodeLocation const & location, ast::Type const * ); - /// Adds type parameters to the layout call; will generate the - /// appropriate parameters if needed. - void addSTypeParamsToLayoutCall( - ast::UntypedExpr * layoutCall, - const ast::vector & otypeParams ); - /// Change the type of generic aggregate members to char[]. - void mutateMembers( ast::AggregateDecl * aggr ); - /// Returns the calculated sizeof expression for type, or nullptr for use - /// C sizeof(). - ast::Expr const * genSizeof( CodeLocation const &, ast::Type const * ); - /// Enters a new scope for type-variables, - /// adding the type variables from the provided type. - void beginTypeScope( ast::Type const * ); - - /// The type variables and polymorphic parameters currently in scope. - TypeVarMap scopeTypeVars; - /// Set of generic type layouts known in the current scope, - /// indexed by sizeofName. - ScopedSet knownLayouts; - /// Set of non-generic types for which the offset array exists in the - /// current scope, indexed by offsetofName. - ScopedSet knownOffsets; - /// Namer for VLA (variable length array) buffers. - UniqueName bufNamer; - /// If the argument of an AddressExpr is MemberExpr, it is stored here. - ast::MemberExpr const * addrMember = nullptr; -}; - -PolyGenericCalculator::PolyGenericCalculator() : - knownLayouts(), knownOffsets(), bufNamer( "_buf" ) -{} - -/// Converts polymorphic type into a suitable monomorphic representation. -/// Currently: __attribute__((aligned(8) )) char[size_T]; -ast::Type * polyToMonoType( CodeLocation const & location, - ast::Type const * declType ) { - auto charType = new ast::BasicType( ast::BasicType::Char ); - auto size = new ast::NameExpr( location, - sizeofName( Mangle::mangleType( declType ) ) ); - auto aligned = new ast::Attribute( "aligned", - { ast::ConstantExpr::from_int( location, 8 ) } ); - auto ret = new ast::ArrayType( charType, size, - ast::VariableLen, ast::DynamicDim, ast::CV::Qualifiers() ); - ret->attributes.push_back( aligned ); - return ret; -} - -void PolyGenericCalculator::previsit( ast::FunctionDecl const * decl ) { - GuardScope( *this ); - beginTypeScope( decl->type ); -} - -void PolyGenericCalculator::previsit( ast::TypedefDecl const * decl ) { - assertf( false, "All typedef declarations should be removed." ); - beginTypeScope( decl->base ); -} - -void PolyGenericCalculator::previsit( ast::TypeDecl const * decl ) { - addToTypeVarMap( decl, scopeTypeVars ); -} - -ast::Decl const * PolyGenericCalculator::postvisit( - ast::TypeDecl const * decl ) { - ast::Type const * base = decl->base; - if ( nullptr == base ) return decl; - - // Add size/align variables for opaque type declarations. - ast::TypeInstType inst( decl->name, decl ); - std::string typeName = Mangle::mangleType( &inst ); - ast::Type * layoutType = new ast::BasicType( - ast::BasicType::LongUnsignedInt ); - - ast::ObjectDecl * sizeDecl = new ast::ObjectDecl( decl->location, - sizeofName( typeName ), layoutType, - new ast::SingleInit( decl->location, - new ast::SizeofExpr( decl->location, deepCopy( base ) ) - ) - ); - ast::ObjectDecl * alignDecl = new ast::ObjectDecl( decl->location, - alignofName( typeName ), layoutType, - new ast::SingleInit( decl->location, - new ast::AlignofExpr( decl->location, deepCopy( base ) ) - ) - ); - - // Ensure that the initializing sizeof/alignof exprs are properly mutated. - sizeDecl->accept( *visitor ); - alignDecl->accept( *visitor ); - - // A little trick to replace this with two declarations. - // Adding after makes sure that there is no conflict with adding stmts. - declsToAddAfter.push_back( alignDecl ); - return sizeDecl; -} - -ast::StructDecl const * PolyGenericCalculator::previsit( - ast::StructDecl const * decl ) { - auto mutDecl = mutate( decl ); - mutateMembers( mutDecl ); - return mutDecl; -} - -ast::UnionDecl const * PolyGenericCalculator::previsit( - ast::UnionDecl const * decl ) { - auto mutDecl = mutate( decl ); - mutateMembers( mutDecl ); - return mutDecl; -} - -ast::DeclStmt const * PolyGenericCalculator::previsit( ast::DeclStmt const * stmt ) { - ast::ObjectDecl const * decl = stmt->decl.as(); - if ( !decl || !findGeneric( decl->location, decl->type ) ) { - return stmt; - } - - // Change initialization of a polymorphic value object to allocate via a - // variable-length-array (alloca cannot be safely used in loops). - ast::ObjectDecl * newBuf = new ast::ObjectDecl( decl->location, - bufNamer.newName(), - polyToMonoType( decl->location, decl->type ), - nullptr, {}, ast::Linkage::C - ); - stmtsToAddBefore.push_back( new ast::DeclStmt( stmt->location, newBuf ) ); - - // If the object has a cleanup attribute, the clean-up should be on the - // buffer, not the pointer. [Perhaps this should be lifted?] - auto matchAndMove = [newBuf]( ast::ptr & attr ) { - if ( "cleanup" == attr->name ) { - newBuf->attributes.push_back( attr ); - return true; - } - return false; - }; - - auto mutDecl = mutate( decl ); - - // Forally, side effects are not safe in this function. But it works. - erase_if( mutDecl->attributes, matchAndMove ); - - mutDecl->init = new ast::SingleInit( decl->location, - new ast::VariableExpr( decl->location, newBuf ) ); - - return ast::mutate_field( stmt, &ast::DeclStmt::decl, mutDecl ); -} - -/// Checks if memberDecl matches the decl from an aggregate. -bool isMember( ast::DeclWithType const * memberDecl, ast::Decl const * decl ) { - // No matter the field, if the name is different it is not the same. - if ( memberDecl->name != decl->name ) { - return false; - } - - if ( memberDecl->name.empty() ) { - // Plan-9 Field: Match on unique_id. - return ( memberDecl->uniqueId == decl->uniqueId ); - } - - ast::DeclWithType const * declWithType = - strict_dynamic_cast( decl ); - - if ( memberDecl->mangleName.empty() || declWithType->mangleName.empty() ) { - // Tuple-Element Field: Expect neither had mangled name; - // accept match on simple name (like field_2) only. - assert( memberDecl->mangleName.empty() ); - assert( declWithType->mangleName.empty() ); - return true; - } - - // Ordinary Field: Use full name to accommodate overloading. - return ( memberDecl->mangleName == declWithType->mangleName ); -} - -/// Finds the member in the base list that matches the given declaration; -/// returns its index, or -1 if not present. -long findMember( ast::DeclWithType const * memberDecl, - const ast::vector & baseDecls ) { - for ( auto pair : enumerate( baseDecls ) ) { - if ( isMember( memberDecl, pair.val.get() ) ) { - return pair.idx; - } - } - return -1; -} - -/// Returns an index expression into the offset array for a type. -ast::Expr * makeOffsetIndex( CodeLocation const & location, - ast::Type const * objectType, long i ) { - std::string name = offsetofName( Mangle::mangleType( objectType ) ); - return ast::UntypedExpr::createCall( location, "?[?]", { - new ast::NameExpr( location, name ), - ast::ConstantExpr::from_ulong( location, i ), - } ); -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::MemberExpr const * expr ) { - // Only mutate member expressions for polymorphic types. - ast::Type const * objectType = hasPolyBase( - expr->aggregate->result, scopeTypeVars - ); - if ( !objectType ) return expr; - // Ensure layout for this type is available. - // The boolean result is ignored. - findGeneric( expr->location, objectType ); - - // Replace member expression with dynamically-computed layout expression. - ast::Expr * newMemberExpr = nullptr; - if ( auto structType = dynamic_cast( objectType ) ) { - long offsetIndex = findMember( expr->member, structType->base->members ); - if ( -1 == offsetIndex ) return expr; - - // Replace member expression with pointer to struct plus offset. - ast::UntypedExpr * fieldLoc = new ast::UntypedExpr( expr->location, - new ast::NameExpr( expr->location, "?+?" ) ); - ast::Expr * aggr = deepCopy( expr->aggregate ); - aggr->env = nullptr; - fieldLoc->args.push_back( aggr ); - fieldLoc->args.push_back( - makeOffsetIndex( expr->location, objectType, offsetIndex ) ); - fieldLoc->result = deepCopy( expr->result ); - newMemberExpr = fieldLoc; - // Union members are all at offset zero, so just use the aggregate expr. - } else if ( dynamic_cast( objectType ) ) { - ast::Expr * aggr = deepCopy( expr->aggregate ); - aggr->env = nullptr; - aggr->result = deepCopy( expr->result ); - newMemberExpr = aggr; - } else { - return expr; - } - assert( newMemberExpr ); - - // Must apply the generic substitution to the member type to handle cases - // where the member is a generic parameter subsituted by a known concrete - // type. [ex] - // forall( T ) struct Box { T x; } - // forall( T ) void f() { - // Box( T * ) b; b.x; - // } - // TODO: expr->result should be exactly expr->member->get_type() after - // substitution, so it doesn't seem like it should be necessary to apply - // the substitution manually. For some reason this is not currently the - // case. This requires more investigation. - ast::ptr memberType = deepCopy( expr->member->get_type() ); - ast::TypeSubstitution sub = genericSubstitution( objectType ); - sub.apply( memberType ); - - // Not all members of a polymorphic type are themselves of a polymorphic - // type; in this cas the member expression should be wrapped and - // dereferenced to form an lvalue. - if ( !isPolyType( memberType, scopeTypeVars ) ) { - auto ptrCastExpr = new ast::CastExpr( expr->location, newMemberExpr, - new ast::PointerType( memberType ) ); - auto derefExpr = ast::UntypedExpr::createDeref( expr->location, - ptrCastExpr ); - newMemberExpr = derefExpr; - } - - return newMemberExpr; -} - -void PolyGenericCalculator::previsit( ast::AddressExpr const * expr ) { - GuardValue( addrMember ) = expr->arg.as(); -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::AddressExpr const * expr ) { - // arg has to have been a MemberExpr and has been mutated. - if ( nullptr == addrMember || expr->arg == addrMember ) { - return expr; - } - ast::UntypedExpr const * untyped = expr->arg.as(); - if ( !untyped || getFunctionName( untyped ) != "?+?" ) { - return expr; - } - // MemberExpr was converted to pointer + offset; and it is not valid C to - // take the address of an addition, so strip away the address-of. - // It also preserves the env value. - return ast::mutate_field( expr->arg.get(), &ast::Expr::env, expr->env ); -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::SizeofExpr const * expr ) { - ast::Type const * type = expr->type ? expr->type : expr->expr->result; - ast::Expr const * gen = genSizeof( expr->location, type ); - return ( gen ) ? gen : expr; -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::AlignofExpr const * expr ) { - ast::Type const * type = expr->type ? expr->type : expr->expr->result; - if ( findGeneric( expr->location, type ) ) { - return new ast::NameExpr( expr->location, - alignofName( Mangle::mangleType( type ) ) ); - } else { - return expr; - } -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::OffsetofExpr const * expr ) { - ast::Type const * type = expr->type; - if ( !findGeneric( expr->location, type ) ) return expr; - - // Structures replace offsetof expression with an index into offset array. - if ( auto structType = dynamic_cast( type ) ) { - long offsetIndex = findMember( expr->member, structType->base->members ); - if ( -1 == offsetIndex ) return expr; - - return makeOffsetIndex( expr->location, type, offsetIndex ); - // All union members are at offset zero. - } else if ( dynamic_cast( type ) ) { - return ast::ConstantExpr::from_ulong( expr->location, 0 ); - } else { - return expr; - } -} - -ast::Expr const * PolyGenericCalculator::postvisit( - ast::OffsetPackExpr const * expr ) { - ast::StructInstType const * type = expr->type; - - // Pull offset back from generated type information. - if ( findGeneric( expr->location, type ) ) { - return new ast::NameExpr( expr->location, - offsetofName( Mangle::mangleType( type ) ) ); - } - - std::string offsetName = offsetofName( Mangle::mangleType( type ) ); - // Use the already generated offsets for this type. - if ( knownOffsets.contains( offsetName ) ) { - return new ast::NameExpr( expr->location, offsetName ); - } - - knownOffsets.insert( offsetName ); - - auto baseMembers = type->base->members; - ast::Type const * offsetType = new ast::BasicType( - ast::BasicType::LongUnsignedInt ); - - // Build initializer list for offset array. - ast::vector inits; - for ( ast::ptr & member : baseMembers ) { - auto memberDecl = member.as(); - assertf( memberDecl, "Requesting offset of non-DWT member: %s", - toCString( member ) ); - inits.push_back( new ast::SingleInit( expr->location, - new ast::OffsetofExpr( expr->location, - deepCopy( type ), - memberDecl - ) - ) ); - } - - auto offsetArray = makeVar( expr->location, offsetName, - new ast::ArrayType( - offsetType, - ast::ConstantExpr::from_ulong( expr->location, baseMembers.size() ), - ast::FixedLen, - ast::DynamicDim - ), - new ast::ListInit( expr->location, std::move( inits ) ) - ); - - return new ast::VariableExpr( expr->location, offsetArray ); -} - -void PolyGenericCalculator::beginScope() { - knownLayouts.beginScope(); - knownOffsets.beginScope(); -} - -void PolyGenericCalculator::endScope() { - knownOffsets.endScope(); - knownLayouts.endScope(); -} - -ast::ObjectDecl * PolyGenericCalculator::makeVar( - CodeLocation const & location, std::string const & name, - ast::Type const * type, ast::Init const * init ) { - ast::ObjectDecl * ret = new ast::ObjectDecl( location, name, type, init ); - stmtsToAddBefore.push_back( new ast::DeclStmt( location, ret ) ); - return ret; -} - -/// Returns true if any of the otype parameters have a dynamic layout; and -/// puts all otype parameters in the output list. -bool findGenericParams( - ast::vector & out, - ast::vector const & baseParams, - ast::vector const & typeParams ) { - bool hasDynamicLayout = false; - - for ( auto pair : group_iterate( baseParams, typeParams ) ) { - auto baseParam = std::get<0>( pair ); - auto typeParam = std::get<1>( pair ); - if ( !baseParam->isComplete() ) continue; - ast::TypeExpr const * typeExpr = typeParam.as(); - assertf( typeExpr, "All type parameters should be type expressions." ); - - ast::Type const * type = typeExpr->type.get(); - out.push_back( type ); - if ( isPolyType( type ) ) hasDynamicLayout = true; - } - - return hasDynamicLayout; -} - -bool PolyGenericCalculator::findGeneric( - CodeLocation const & location, ast::Type const * type ) { - type = replaceTypeInst( type, typeSubs ); - - if ( auto inst = dynamic_cast( type ) ) { - // Assumes that getting put in the scopeTypeVars includes having the - // layout variables set. - if ( scopeTypeVars.contains( *inst ) ) { - return true; - } - } else if ( auto inst = dynamic_cast( type ) ) { - // Check if this type already has a layout generated for it. - std::string typeName = Mangle::mangleType( type ); - if ( knownLayouts.contains( typeName ) ) return true; - - // Check if any type parameters have dynamic layout; - // If none do, this type is (or will be) monomorphized. - ast::vector sizedParams; - if ( !findGenericParams( sizedParams, - inst->base->params, inst->params ) ) { - return false; - } - - // Insert local variables for layout and generate call to layout - // function. - // Done early so as not to interfere with the later addition of - // parameters to the layout call. - knownLayouts.insert( typeName ); - ast::Type const * layoutType = makeSizeAlignType(); - - int memberCount = inst->base->members.size(); - if ( 0 == memberCount ) { - // All empty structures have the same layout (size 1, align 1). - makeVar( location, - sizeofName( typeName ), layoutType, - new ast::SingleInit( location, - ast::ConstantExpr::from_ulong( location, 1 ) ) ); - makeVar( location, - alignofName( typeName ), ast::deepCopy( layoutType ), - new ast::SingleInit( location, - ast::ConstantExpr::from_ulong( location, 1 ) ) ); - // Since 0-length arrays are forbidden in C, skip the offset array. - } else { - ast::ObjectDecl const * sizeofVar = makeVar( location, - sizeofName( typeName ), deepCopy( layoutType ), nullptr ); - ast::ObjectDecl const * alignofVar = makeVar( location, - alignofName( typeName ), deepCopy( layoutType ), nullptr ); - ast::ObjectDecl const * offsetofVar = makeVar( location, - offsetofName( typeName ), - new ast::ArrayType( - layoutType, - ast::ConstantExpr::from_int( location, memberCount ), - ast::FixedLen, - ast::DynamicDim - ), - nullptr - ); - - // Generate call to layout function. - ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location, - new ast::NameExpr( location, layoutofName( inst->base ) ), - { - new ast::AddressExpr( - new ast::VariableExpr( location, sizeofVar ) ), - new ast::AddressExpr( - new ast::VariableExpr( location, alignofVar ) ), - new ast::VariableExpr( location, offsetofVar ), - } ); - - addSTypeParamsToLayoutCall( layoutCall, sizedParams ); - - stmtsToAddBefore.emplace_back( - new ast::ExprStmt( location, layoutCall ) ); - } - - return true; - } else if ( auto inst = dynamic_cast( type ) ) { - // Check if this type already has a layout generated for it. - std::string typeName = Mangle::mangleType( type ); - if ( knownLayouts.contains( typeName ) ) return true; - - // Check if any type parameters have dynamic layout; - // If none do, this type is (or will be) monomorphized. - ast::vector sizedParams; - if ( !findGenericParams( sizedParams, - inst->base->params, inst->params ) ) { - return false; - } - - // Insert local variables for layout and generate call to layout - // function. - // Done early so as not to interfere with the later addition of - // parameters to the layout call. - knownLayouts.insert( typeName ); - ast::Type const * layoutType = makeSizeAlignType(); - - ast::ObjectDecl * sizeofVar = makeVar( location, - sizeofName( typeName ), layoutType ); - ast::ObjectDecl * alignofVar = makeVar( location, - alignofName( typeName ), ast::deepCopy( layoutType ) ); - - ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location, - new ast::NameExpr( location, layoutofName( inst->base ) ), - { - new ast::AddressExpr( - new ast::VariableExpr( location, sizeofVar ) ), - new ast::AddressExpr( - new ast::VariableExpr( location, alignofVar ) ), - } ); - - addSTypeParamsToLayoutCall( layoutCall, sizedParams ); - - stmtsToAddBefore.emplace_back( - new ast::ExprStmt( location, layoutCall ) ); - - return true; - } - return false; -} - -void PolyGenericCalculator::addSTypeParamsToLayoutCall( - ast::UntypedExpr * layoutCall, - const ast::vector & otypeParams ) { - CodeLocation const & location = layoutCall->location; - ast::vector & args = layoutCall->args; - for ( ast::ptr const & param : otypeParams ) { - if ( findGeneric( location, param ) ) { - // Push size/align vars for a generic parameter back. - std::string paramName = Mangle::mangleType( param ); - args.emplace_back( - new ast::NameExpr( location, sizeofName( paramName ) ) ); - args.emplace_back( - new ast::NameExpr( location, alignofName( paramName ) ) ); - } else { - args.emplace_back( - new ast::SizeofExpr( location, ast::deepCopy( param ) ) ); - args.emplace_back( - new ast::AlignofExpr( location, ast::deepCopy( param ) ) ); - } - } -} - -void PolyGenericCalculator::mutateMembers( ast::AggregateDecl * aggr ) { - std::set genericParams; - for ( ast::ptr const & decl : aggr->params ) { - genericParams.insert( decl->name ); - } - for ( ast::ptr & decl : aggr->members ) { - auto field = decl.as(); - if ( nullptr == field ) continue; - - ast::Type const * type = replaceTypeInst( field->type, typeSubs ); - auto typeInst = dynamic_cast( type ); - if ( nullptr == typeInst ) continue; - - // Do not try to monoporphize generic parameters. - if ( scopeTypeVars.contains( ast::TypeEnvKey( *typeInst ) ) && - !genericParams.count( typeInst->name ) ) { - // Polymorphic aggregate members should be converted into - // monomorphic members. Using char[size_T] here respects - // the expected sizing rules of an aggregate type. - decl = ast::mutate_field( field, &ast::ObjectDecl::type, - polyToMonoType( field->location, field->type ) ); - } - } -} - -ast::Expr const * PolyGenericCalculator::genSizeof( - CodeLocation const & location, ast::Type const * type ) { - if ( auto * array = dynamic_cast( type ) ) { - // Generate calculated size for possibly generic array. - ast::Expr const * sizeofBase = genSizeof( location, array->base ); - if ( nullptr == sizeofBase ) return nullptr; - ast::Expr const * dim = array->dimension; - return makeOp( location, "?*?", sizeofBase, dim ); - } else if ( findGeneric( location, type ) ) { - // Generate calculated size for generic type. - return new ast::NameExpr( location, sizeofName( - Mangle::mangleType( type ) ) ); - } else { - return nullptr; - } -} - -void PolyGenericCalculator::beginTypeScope( ast::Type const * type ) { - GuardScope( scopeTypeVars ); - makeTypeVarMap( type, scopeTypeVars ); -} - -// -------------------------------------------------------------------------- -/// Removes unneeded or incorrect type information. -/// * Replaces initialization of polymorphic values with alloca. -/// * Replaces declaration of dtype/ftype with appropriate void expression. -/// * Replaces sizeof expressions of polymorphic types with a variable. -/// * Strips fields from generic structure declarations. -struct Eraser final : - public ast::WithGuards { - void guardTypeVarMap( ast::Type const * type ) { - GuardScope( scopeTypeVars ); - makeTypeVarMap( type, scopeTypeVars ); - } - - ast::ObjectDecl const * previsit( ast::ObjectDecl const * decl ); - ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl ); - ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl ); - ast::TypedefDecl const * previsit( ast::TypedefDecl const * decl ); - ast::StructDecl const * previsit( ast::StructDecl const * decl ); - ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); - void previsit( ast::TypeDecl const * decl ); - void previsit( ast::PointerType const * type ); - void previsit( ast::FunctionType const * type ); -public: - TypeVarMap scopeTypeVars; -}; - -ast::ObjectDecl const * Eraser::previsit( ast::ObjectDecl const * decl ) { - guardTypeVarMap( decl->type ); - return scrubAllTypeVars( decl ); -} - -ast::FunctionDecl const * Eraser::previsit( ast::FunctionDecl const * decl ) { - guardTypeVarMap( decl->type ); - return scrubAllTypeVars( decl ); -} - -ast::FunctionDecl const * Eraser::postvisit( ast::FunctionDecl const * decl ) { - if ( decl->type_params.empty() ) return decl; - auto mutDecl = mutate( decl ); - mutDecl->type_params.clear(); - return mutDecl; -} - -ast::TypedefDecl const * Eraser::previsit( ast::TypedefDecl const * decl ) { - guardTypeVarMap( decl->base ); - return scrubAllTypeVars( decl ); -} - -/// Strips the members from a generic aggregate. -template -node_t const * stripGenericMembers( node_t const * decl ) { - if ( decl->params.empty() ) return decl; - auto mutDecl = ast::mutate( decl ); - mutDecl->members.clear(); - return mutDecl; -} - -ast::StructDecl const * Eraser::previsit( ast::StructDecl const * decl ) { - return stripGenericMembers( decl ); -} - -ast::UnionDecl const * Eraser::previsit( ast::UnionDecl const * decl ) { - return stripGenericMembers( decl ); -} - -void Eraser::previsit( ast::TypeDecl const * decl ) { - addToTypeVarMap( decl, scopeTypeVars ); -} - -void Eraser::previsit( ast::PointerType const * type ) { - guardTypeVarMap( type ); -} - -void Eraser::previsit( ast::FunctionType const * type ) { - guardTypeVarMap( type ); -} - -} // namespace - -// -------------------------------------------------------------------------- -void box( ast::TranslationUnit & translationUnit ) { - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); -} - -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/InstantiateGeneric.cpp =================================================================== --- src/GenPoly/InstantiateGeneric.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) +++ src/GenPoly/InstantiateGeneric.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) @@ -0,0 +1,735 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// InstantiateGeneric.cpp -- Create concrete instances of generic types. +// +// Author : Andrew Beach +// Created On : Tue Aug 16 10:51:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Oct 31 16:48:00 2022 +// Update Count : 1 +// + +#include "InstantiateGeneric.h" + +#include // for assertf, assert +#include // for set +#include // for move, pair +#include // for vector + +#include "AST/Copy.hpp" // for deepCopy +#include "AST/Create.hpp" // for asForward +#include "AST/Inspect.hpp" // for getFunction +#include "AST/Pass.hpp" // for Pass, WithGuard, WithShortCi... +#include "AST/TranslationUnit.hpp" // for TranslationUnit +#include "AST/Vector.hpp" // for vector +#include "CodeGen/OperatorTable.h" // for isAssignment +#include "Common/ScopedMap.h" // for ScopedMap +#include "Common/UniqueName.h" // for UniqueName +#include "GenPoly/GenPoly.h" // for isPolyType, typesPolyCompatible +#include "GenPoly/ScrubTyVars.h" // for scrubAll +#include "ResolvExpr/AdjustExprType.hpp" // for adjustExprType +#include "ResolvExpr/Unify.h" // for typesCompatible + +namespace GenPoly { + +namespace { + +// Utilities: + +using type_vector = ast::vector< ast::TypeExpr >; + +/// Abstracts type equality for a list of parameter types. +struct TypeList { + TypeList() : params() {} + TypeList( ast::vector< ast::Type > const & params ) : + params( params ) {} + TypeList( ast::vector< ast::Type > && params ) : + params( std::move( params ) ) {} + TypeList( TypeList const & that ) : params( that.params ) {} + TypeList( TypeList && that ) : params( std::move( that.params ) ) {} + + TypeList( ast::vector< ast::TypeExpr > const & exprs ) : + params() { + for ( auto expr : exprs ) { + params.emplace_back( ast::deepCopy( expr->type ) ); + } + } + + TypeList & operator=( TypeList const & that ) { + params = that.params; + return *this; + } + + TypeList & operator=( TypeList && that ) { + params = std::move( that.params ); + return *this; + } + + bool operator==( TypeList const & that ) const { + if ( params.size() != that.params.size() ) { + return false; + } + + for ( auto it = params.begin(), jt = that.params.begin() ; + it != params.end() ; ++it, ++jt ) { + if ( !typesPolyCompatible( it->get(), jt->get() ) ) { + return false; + } + } + return true; + } + + ast::vector params; +}; + +/// Maps a key and a TypeList to a valuue. Also supports scoping. +class InstantiationMap final { + /// Wraps value for a specific (AggregateDecl, TypeList) combination. + using Instantiation = std::pair>; + /// List of TypeLists paired with the appropriate values. + using ValueList = std::vector; + /// Underlying map type; maps keys to a linear list of corresponding + /// TypeLists and values. + using InnerMap = ScopedMap, ValueList>; + + InnerMap data; +public: + void beginScope() { data.beginScope(); } + void endScope() { data.endScope(); } + + /// Gets the value for the (declaration, type list) pair, + /// returns null if no such value exists. + ast::AggregateDecl const * lookup( + ast::AggregateDecl const * key, + type_vector const & params ) const { + // This type repackaging is used for the helpers. + ast::ptr ptr = key; + TypeList typeList( params ); + + // Scan scopes for matches to the key. + for ( auto insts = data.find( key ) ; + insts != data.end() ; insts = data.findNext( insts, ptr )) { + for ( auto inst = insts->second.rbegin() ; + inst != insts->second.rend() ; ++inst ) { + if ( inst->first == typeList ) { + return inst->second; + } + } + } + return nullptr; + } + + /// Adds a value for a (key, type list) pair to the current scope. + void insert( ast::AggregateDecl const * key, type_vector const & params, + ast::AggregateDecl const * value ) { + auto it = data.findAt( data.currentScope(), key ); + if ( it == data.end() ) { + data.insert( key, ValueList( 1, + Instantiation( TypeList( params ), value ) ) ); + } else { + it->second.emplace_back( + Instantiation( TypeList( params ), value ) ); + } + } +}; + +/// Possible options for a given specialization of a generic type. +enum class GenericType { + /// Concrete instatiation based solely on {d,f}type-to-void conversions. + dtypeStatic, + /// Concrete instatiation requiring at least one parameters type. + concrete, + /// No concrete instantiation. + dynamic +}; + +GenericType & operator|=( GenericType & gt, const GenericType & ht ) { + if ( gt < ht ) gt = ht; + return gt; +} + +bool isDtypeStatic( ast::vector const & baseParams ) { + return std::all_of( baseParams.begin(), baseParams.end(), + []( ast::TypeDecl const * td ){ return !td->isComplete(); } + ); +} + +/// Makes substitutions of params into baseParams; returns dtypeStatic if +/// there is a concrete instantiation based only on {d,f}type-to-void +/// conversions, concrete if there is a concrete instantiation requiring at +/// least one parameter type, and dynamic if there is no concrete instantiation. +GenericType makeSubstitutions( + ast::vector & out, + ast::vector const & baseParams, + ast::vector const & params ) { + GenericType gt = GenericType::dtypeStatic; + + // Substitute concrete types for given parameters, + // using incomplete types for placeholders. + auto baseParam = baseParams.begin(); + auto param = params.begin(); + for ( ; baseParam != baseParams.end() && param != params.end() ; + ++baseParam, ++param ) { + ast::TypeExpr const * paramExpr = param->as(); + assertf( paramExpr, "Aggregate parameters should be type expressions." ); + + if ( (*baseParam)->isComplete() ) { + // Substitute parameter for complete (otype or sized dtype) type. + if ( isPolyType( paramExpr->type ) ) { + // Substitute polymorphic parameter type in to generic type. + out.push_back( ast::deepCopy( paramExpr ) ); + gt = GenericType::dynamic; + } else { + // Normalize possibly dtype-static parameter type. + out.emplace_back( new ast::TypeExpr( paramExpr->location, + scrubAllTypeVars( ast::deepCopy( paramExpr->type ) ) ) ); + gt |= GenericType::concrete; + } + } else switch ( (*baseParam)->kind ) { + case ast::TypeDecl::Dtype: + // Here, pretend that any incomplete dtype is `void`. + out.emplace_back( new ast::TypeExpr( paramExpr->location, + new ast::VoidType() ) ); + break; + case ast::TypeDecl::Ftype: + // Here, pretend that any ftype is `void (*)(void)`. + out.emplace_back( new ast::TypeExpr( paramExpr->location, + new ast::FunctionType() ) ); + break; + case ast::TypeDecl::Ttype: + assertf( false, "Ttype parameters are not currently allowed as parameters to generic types." ); + break; + default: + assertf( false, "Unhandled type parameter kind" ); + break; + } + } + + assertf( baseParam == baseParams.end(), "Base Parameters not exausted." ); + assertf( param == params.end(), "Type parameters not exausted." ); + return gt; +} + +/// Substitutes types of members according to baseParams => typeSubs, +/// returning the result in a new vector. +ast::vector substituteMembers( + ast::vector const & members, + ast::vector const & baseParams, + ast::vector const & typeSubs ) { + ast::vector out; + ast::TypeSubstitution subs( baseParams, typeSubs ); + for ( ast::ptr const & member : members ) { + // Create a manual copy to avoid in-place mutation. + // If being a PureVisitor is decided to be part of apply's interface, + // then we can actually skip this step as it will never mutate in- + // place. (Then we don't need the extra guard to free temp value.) + ast::ptr copy = ast::deepCopy( member.get() ); + auto result = subs.apply( copy.get() ); + out.emplace_back( result.node ); + } + return out; +} + +/// Substitutes types of members according to baseParams => typeSubs, +/// modifying them in-place. +void substituteMembersHere( + ast::vector & members, + ast::vector const & baseParams, + ast::vector const & typeSubs ) { + ast::TypeSubstitution subs( baseParams, typeSubs ); + for ( ast::ptr & member : members ) { + // The member must be mutated in place to avoid breaking + assert( member->unique() ); + + auto field = member.strict_as(); + auto result = subs.apply( field->type.get() ); + auto copy = ast::mutate_field( + field, &ast::ObjectDecl::type, result.node ); + + // I'm not kidding, it is very important. + assert( copy == member.get() ); + } +} + +/// Strips the instances' type parameters. +void stripInstParams( ast::BaseInstType * inst ) { + inst->params.clear(); +} + +bool isGenericType( ast::Type const * type ) { + if ( auto inst = dynamic_cast( type ) ) { + return !inst->params.empty(); + } else if ( auto inst = dynamic_cast( type ) ) { + return !inst->params.empty(); + } else { + return false; + } +} + +// The Passes: + +struct FixDtypeStatic final : + public ast::WithGuards, + public ast::WithVisitorRef, + public ast::WithShortCircuiting, + public ast::WithStmtsToAdd<> { + ast::ApplicationExpr const * previsit( ast::ApplicationExpr const * expr ); + void previsit( ast::AddressExpr const * expr ); + + ast::Expr const * postvisit( ast::MemberExpr const * expr ); +private: + template + ast::Expr const * fixMemberExpr( + Aggr const * inst, ast::MemberExpr const * memberExpr ); + + ast::Expr const * fixMemberExpr( + ast::vector const & baseParams, + ast::MemberExpr const * memberExpr ); + + bool isLValueArg = false; +}; + +ast::ApplicationExpr const * FixDtypeStatic::previsit( + ast::ApplicationExpr const * expr ) { + GuardValue( isLValueArg ) = false; + ast::Decl const * function = ast::getFunction( expr ); + if ( ast::Linkage::Intrinsic != function->linkage + || !CodeGen::isAssignment( function->name ) ) { + return expr; + } + + // Explicity visit children because only the first element must be a + // C lvalue (normally, it can only send info to both or neither). + visit_children = false; + expr = mutate_field( expr, &ast::ApplicationExpr::env, + maybe_accept( expr->env.get(), *visitor ) ); + expr = mutate_field( expr, &ast::ApplicationExpr::result, + maybe_accept( expr->result.get(), *visitor ) ); + expr = mutate_field( expr, &ast::ApplicationExpr::func, + maybe_accept( expr->func.get(), *visitor ) ); + isLValueArg = true; + for ( unsigned i = 0; i < expr->args.size(); ++i ) { + ast::Expr const * newExpr = expr->args[i]->accept( *visitor ); + // This is declared here for lifetime reasons. + ast::ptr cast; + if ( newExpr != expr->args[i].get() && + (cast = dynamic_cast( newExpr )) ) { + newExpr = cast->arg.get(); + } + expr = mutate_field_index( expr, &ast::ApplicationExpr::args, + i, newExpr ); + isLValueArg = false; + } + return expr; +} + +void FixDtypeStatic::previsit( ast::AddressExpr const * ) { + // The argument of an address expression (`&`) must be a C lvalue. + GuardValue( isLValueArg ) = true; +} + +ast::Expr const * FixDtypeStatic::postvisit( ast::MemberExpr const * expr ) { + ast::ptr const & type = expr->aggregate->result; + if ( auto inst = type.as() ) { + if ( !inst->params.empty() ) return fixMemberExpr( inst, expr ); + } else if ( auto inst = type.as() ) { + if ( !inst->params.empty() ) return fixMemberExpr( inst, expr ); + } + return expr; +} + +template +ast::Expr const * FixDtypeStatic::fixMemberExpr( + Aggr const * inst, ast::MemberExpr const * memberExpr ) { + return fixMemberExpr( inst->base->params, memberExpr ); +} + +ast::Expr const * FixDtypeStatic::fixMemberExpr( + ast::vector const & baseParams, + ast::MemberExpr const * memberExpr ) { + // Need to cast dtype-static member expressions to their actual type + // before the actual type type is erased. + // NOTE: The casts here have the third argument (isGenerated) set to + // ExplicitCast so that they casts persist until Box, where they are needed. + + if ( !isDtypeStatic( baseParams ) || + ResolvExpr::typesCompatible( + memberExpr->result, + memberExpr->member->get_type() ) ) { + return memberExpr; + } + + // Type of member and type of expression differ. + ast::Type const * concType = ast::deepCopy( memberExpr->result ); + CodeLocation const & location = memberExpr->location; + if ( isLValueArg ) { + // The result must be a C lvalue expression. So make a new reference + // variable with the correct actual type to replace the + // member expression. + // forall(T &) + // struct Ptr { + // T * x; + // }; + // Ptr(int) p; + // int i; + // The original expression: + // p.x = &i; + // Becomes the expression/declaration: + // int *& _dtype_static_member_0; + // (_dtype_static_member_0 = (int**)&p.x, + // _dtype_static_member_0) = &i; + + // The declaration is simple: + static UniqueName tmpNamer( "_dtype_static_member_" ); + ast::ObjectDecl * tmp = new ast::ObjectDecl( location, + tmpNamer.newName(), + new ast::ReferenceType( concType ), + nullptr, + ast::Storage::Classes(), + ast::Linkage::C + ); + stmtsToAddBefore.push_back( new ast::DeclStmt( location, tmp ) ); + + // The expression is more complex, uses references and reference / + // pointer parity. But breaking it up risks reordering. + return new ast::CommaExpr( location, + ast::UntypedExpr::createAssign( location, + new ast::VariableExpr( location, tmp ), + new ast::CastExpr( location, + new ast::AddressExpr( location, memberExpr ), + new ast::PointerType( ast::deepCopy( concType ) ), + ast::ExplicitCast + ) + ), + new ast::VariableExpr( location, tmp ) + ); + } else { + // Here, it can simply add a cast to actual types. + return new ast::CastExpr( location, + memberExpr, + concType, + ast::ExplicitCast + ); + } +} + +struct GenericInstantiator final : + public ast::WithCodeLocation, + public ast::WithConstTypeSubstitution, + public ast::WithDeclsToAdd<>, + public ast::WithGuards, + public ast::WithVisitorRef +{ + /// Map of (generic type, parameter list) pairs + /// to concrete type instantiations. + InstantiationMap instantiations; + /// Set of types which are dtype-only generic + /// (and therefore have static layout). + std::set dtypeStatics; + /// Namer for concrete types. + UniqueName typeNamer; + /// Should not make use of type environment to replace types of function + /// parameter and return values. + bool inFunctionType = false; + /// Index of current member, used to recreate MemberExprs with the + /// member from an instantiation. + int memberIndex = -1; + + GenericInstantiator() : + instantiations(), dtypeStatics(), typeNamer("_conc_") {} + + ast::Type const * postvisit( ast::StructInstType const * inst ); + ast::Type const * postvisit( ast::UnionInstType const * inst ); + + void previsit( ast::MemberExpr const * expr ); + ast::Expr const * postvisit( ast::MemberExpr const * expr ); + ast::Expr const * postvisit( ast::Expr const * expr ); + ast::Designation const * postvisit( ast::Designation const * ); + + void previsit( ast::ParseNode const * node ) { + GuardValue( location ) = &node->location; + } + void previsit( ast::FunctionType const * ) { + GuardValue( inFunctionType ) = true; + } + void beginScope() { + instantiations.beginScope(); + } + void endScope() { + instantiations.endScope(); + } +private: + /// Wrap instantiation lookup for structures. + ast::StructDecl const * lookup( + ast::StructInstType const * inst, type_vector const & typeSubs ) const; + /// Wrap instantiation lookup for unions. + ast::UnionDecl const * lookup( + ast::UnionInstType const * inst, type_vector const & typeSubs ) const; + /// Wrap instantiation insertion for structures. + void insert( ast::StructInstType const * inst, + type_vector const & typeSubs, ast::StructDecl const * decl ); + /// Wrap instantiation insertion for unions. + void insert( ast::UnionInstType const * inst, + type_vector const & typeSubs, ast::UnionDecl const * decl ); + + void replaceParametersWithConcrete( ast::vector & params ); + ast::Type const * replaceWithConcrete( ast::Type const * type, bool doClone ); + + template + ast::Type const * fixInstType( ast::SueInstType const * inst ); + + /// Strips a dtype-static aggregate decl of its type parameters, + /// marks it as stripped. + void stripDtypeParams( ast::AggregateDecl * base, + ast::vector & baseParams, + ast::vector const & typeSubs ); +}; + +ast::Type const * GenericInstantiator::postvisit( + ast::StructInstType const * inst ) { + return fixInstType( inst ); +} + +ast::Type const * GenericInstantiator::postvisit( + ast::UnionInstType const * inst ) { + return fixInstType( inst ); +} + +template +ast::Type const * GenericInstantiator::fixInstType( + ast::SueInstType const * inst ) { + assert( location ); + + // There is nothing to mutate if the params are empty. + if ( inst->params.empty() ) return inst; + + // Need to replace type variables to ensure that generic types are + // instantiated for the return values of polymorphic functions (in + // particular, for thunks, because they are not [currently] copy + // constructed). + // (This used to be run only on structures, but I believe both need it.) + inst = strict_dynamic_cast const *>( + replaceWithConcrete( inst, false ) ); + + // Check for an already-instantiatiated dtype-static type. + if ( dtypeStatics.find( inst->base ) != dtypeStatics.end() ) { + auto mutInst = ast::mutate( inst ); + stripInstParams( mutInst ); + return mutInst; + } + + // Check if the type can be concretely instantiated; + // and put substitutions in typeSubs. + assertf( inst->base, "Base data-type has parameters." ); + ast::vector typeSubs; + GenericType gt = makeSubstitutions( typeSubs, inst->base->params, inst->params ); + switch ( gt ) { + case GenericType::dtypeStatic: + { + auto mutInst = ast::mutate( inst ); + assert( mutInst->base->unique() ); + auto mutBase = mutInst->base.get_and_mutate(); + stripDtypeParams( mutBase, mutBase->params, typeSubs ); + stripInstParams( mutInst ); + return mutInst; + } + case GenericType::concrete: + { + // Make concrete instantiation of generic type. + AggrDecl const * concDecl = lookup( inst, typeSubs ); + if ( !concDecl ) { + // Set concDecl to new type, insert type declaration + // into statements to add. + AggrDecl * newDecl = new AggrDecl( *location, + typeNamer.newName( inst->name ) + ); + newDecl->body = inst->base->body; + newDecl->members = substituteMembers( + inst->base->members, + inst->base->params, + typeSubs + ); + + // Forward declare before recursion. (TODO: Only when needed, #199.) + insert( inst, typeSubs, newDecl ); + if ( AggrDecl const * forwardDecl = ast::asForward( newDecl ) ) { + declsToAddBefore.push_back( forwardDecl ); + } + // Recursively instantiate members: + concDecl = strict_dynamic_cast( + newDecl->accept( *visitor ) ); + // Must occur before declaration is added so + // that member instantiation appear first. + declsToAddBefore.push_back( concDecl ); + } + return new ast::SueInstType( concDecl, inst->qualifiers ); + } + case GenericType::dynamic: + // Do nothing. + default: + // Should never happen. + return inst; + } +} + +void GenericInstantiator::previsit( ast::MemberExpr const * expr ) { + GuardValue( location ) = &expr->location; + GuardValue( memberIndex ) = -1; + // Only run on expressions where the field being accessed is generic. + if ( isGenericType( expr->aggregate->result ) ) { + // Find the location of the member: + ast::AggregateDecl const * aggr = + expr->aggregate->result.strict_as()->aggr(); + ast::vector const & members = aggr->members; + auto it = std::find( members.begin(), members.end(), expr->member ); + memberIndex = std::distance( members.begin(), it ); + assertf( memberIndex < (int)members.size(), "Could not find member %s in generic type %s.", toString( expr->member ).c_str(), toString( expr->aggregate ).c_str() ); + } +} + +ast::Expr const * GenericInstantiator::postvisit( + ast::MemberExpr const * expr ) { + if ( memberIndex == -1 ) { + return expr; + } + + // Using the location from the generic type, find the member + // in the instantiation and rebuild the member expression. + ast::AggregateDecl const * aggr = + expr->aggregate->result.strict_as()->aggr(); + assertf( memberIndex < (int)aggr->members.size(), "Instantiation somehow has fewer members than the generic type." ); + ast::Decl const * member = *std::next( aggr->members.begin(), memberIndex ); + assertf( member->name == expr->member->name, "Instantiation has different member order than the generic type. %s / %s", toString( member ).c_str(), toString( expr->member ).c_str() ); + auto field = strict_dynamic_cast< ast::DeclWithType const * >( member ); + ast::MemberExpr * ret = new ast::MemberExpr( expr->location, + field, + ast::deepCopy( expr->aggregate ) + ); + // For pointer decay: + ret->result = ResolvExpr::adjustExprType( + ret->result, + ast::TypeEnvironment(), + ast::SymbolTable() + ); + ret->env = expr->env; + return ret; +} + +ast::Expr const * GenericInstantiator::postvisit( ast::Expr const * expr ) { + // We are not modifying env on MemberExpr, but that seems to work. + if ( expr->env ) { + auto newEnv = expr->env->accept( *visitor ); + expr = ast::mutate_field( expr, &ast::Expr::env, newEnv ); + } + return expr; +} + +// This attempts to figure out what the final name of the field will be. +// Pretty printing can cause this to become incorrect. +std::string getPrintName( ast::DeclWithType const * decl ) { + return ( decl->linkage.is_mangled ) + ? decl->scopedMangleName() : decl->name; +} + +ast::Designation const * GenericInstantiator::postvisit( + ast::Designation const * designation ) { + // Disconnect designator names from their fields. + // It is now incorrect to point at the generic definition where the used + // type now is replaced with a concrete instance. Ideally, new variable + // expressions would point at fields in the concrete instances, but that + // is work and that information should not be needed this late in + // compilation. + + // Modify all designations, even if not needed. + auto mutNode = mutate( designation ); + for ( ast::ptr & designator : mutNode->designators ) { + if ( auto var = designator.as() ) { + designator = new ast::NameExpr( + var->location, getPrintName( var->var ) ); + } + } + return mutNode; +} + +ast::StructDecl const * GenericInstantiator::lookup( + ast::StructInstType const * inst, + type_vector const & typeSubs ) const { + auto ret = instantiations.lookup( inst->base, typeSubs ); + return strict_dynamic_cast( ret ); +} + +ast::UnionDecl const * GenericInstantiator::lookup( + ast::UnionInstType const * inst, + type_vector const & typeSubs ) const { + auto ret = instantiations.lookup( inst->base, typeSubs ); + return strict_dynamic_cast( ret ); +} + +void GenericInstantiator::insert( ast::StructInstType const * inst, + type_vector const & typeSubs, ast::StructDecl const * decl ) { + instantiations.insert( inst->base, typeSubs, decl ); +} + +void GenericInstantiator::insert( ast::UnionInstType const * inst, + type_vector const & typeSubs, ast::UnionDecl const * decl ) { + instantiations.insert( inst->base, typeSubs, decl ); +} + +void GenericInstantiator::replaceParametersWithConcrete( + ast::vector & params ) { + for ( ast::ptr & param : params ) { + auto paramType = param.as(); + assertf( paramType, "Aggregate parameters should be type expressions." ); + auto type = replaceWithConcrete( paramType->type, false ); + param = ast::mutate_field( paramType, &ast::TypeExpr::type, type ); + } +} + +ast::Type const * GenericInstantiator::replaceWithConcrete( + ast::Type const * type, bool doClone ) { + if ( auto inst = dynamic_cast( type ) ) { + if ( typeSubs && !inFunctionType ) { + ast::Type const * concType = typeSubs->lookup( inst ); + return ast::deepCopy( ( concType ) ? concType : inst ); + } + } else if ( auto inst = dynamic_cast( type ) ) { + auto mut = ( doClone ) ? ast::deepCopy( inst ) : ast::mutate( inst ); + replaceParametersWithConcrete( mut->params ); + return mut; + } else if ( auto inst = dynamic_cast( type ) ) { + auto mut = ( doClone ) ? ast::deepCopy( inst ) : ast::mutate( inst ); + replaceParametersWithConcrete( mut->params ); + return mut; + } + return type; +} + +void GenericInstantiator::stripDtypeParams( + ast::AggregateDecl * base, + ast::vector & baseParams, + ast::vector const & typeSubs ) { + substituteMembersHere( base->members, baseParams, typeSubs ); + + baseParams.clear(); + + dtypeStatics.insert( base ); +} + +} // namespace + +void instantiateGeneric( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); +} + +} // namespace GenPoly + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/InstantiateGenericNew.cpp =================================================================== --- src/GenPoly/InstantiateGenericNew.cpp (revision f48dfcd1acf87e4d711e108cd7119bb80ee701ee) +++ (revision ) @@ -1,735 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// InstantiateGenericNew.cpp -- Create concrete instances of generic types. -// -// Author : Andrew Beach -// Created On : Tue Aug 16 10:51:00 2022 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Oct 31 16:48:00 2022 -// Update Count : 1 -// - -#include "InstantiateGeneric.h" - -#include // for assertf, assert -#include // for set -#include // for move, pair -#include // for vector - -#include "AST/Copy.hpp" // for deepCopy -#include "AST/Create.hpp" // for asForward -#include "AST/Inspect.hpp" // for getFunction -#include "AST/Pass.hpp" // for Pass, WithGuard, WithShortCi... -#include "AST/TranslationUnit.hpp" // for TranslationUnit -#include "AST/Vector.hpp" // for vector -#include "CodeGen/OperatorTable.h" // for isAssignment -#include "Common/ScopedMap.h" // for ScopedMap -#include "Common/UniqueName.h" // for UniqueName -#include "GenPoly/GenPoly.h" // for isPolyType, typesPolyCompatible -#include "GenPoly/ScrubTyVars.h" // for scrubAll -#include "ResolvExpr/AdjustExprType.hpp" // for adjustExprType -#include "ResolvExpr/Unify.h" // for typesCompatible - -namespace GenPoly { - -namespace { - -// Utilities: - -using type_vector = ast::vector< ast::TypeExpr >; - -/// Abstracts type equality for a list of parameter types. -struct TypeList { - TypeList() : params() {} - TypeList( ast::vector< ast::Type > const & params ) : - params( params ) {} - TypeList( ast::vector< ast::Type > && params ) : - params( std::move( params ) ) {} - TypeList( TypeList const & that ) : params( that.params ) {} - TypeList( TypeList && that ) : params( std::move( that.params ) ) {} - - TypeList( ast::vector< ast::TypeExpr > const & exprs ) : - params() { - for ( auto expr : exprs ) { - params.emplace_back( ast::deepCopy( expr->type ) ); - } - } - - TypeList & operator=( TypeList const & that ) { - params = that.params; - return *this; - } - - TypeList & operator=( TypeList && that ) { - params = std::move( that.params ); - return *this; - } - - bool operator==( TypeList const & that ) const { - if ( params.size() != that.params.size() ) { - return false; - } - - for ( auto it = params.begin(), jt = that.params.begin() ; - it != params.end() ; ++it, ++jt ) { - if ( !typesPolyCompatible( it->get(), jt->get() ) ) { - return false; - } - } - return true; - } - - ast::vector params; -}; - -/// Maps a key and a TypeList to a valuue. Also supports scoping. -class InstantiationMap final { - /// Wraps value for a specific (AggregateDecl, TypeList) combination. - using Instantiation = std::pair>; - /// List of TypeLists paired with the appropriate values. - using ValueList = std::vector; - /// Underlying map type; maps keys to a linear list of corresponding - /// TypeLists and values. - using InnerMap = ScopedMap, ValueList>; - - InnerMap data; -public: - void beginScope() { data.beginScope(); } - void endScope() { data.endScope(); } - - /// Gets the value for the (declaration, type list) pair, - /// returns null if no such value exists. - ast::AggregateDecl const * lookup( - ast::AggregateDecl const * key, - type_vector const & params ) const { - // This type repackaging is used for the helpers. - ast::ptr ptr = key; - TypeList typeList( params ); - - // Scan scopes for matches to the key. - for ( auto insts = data.find( key ) ; - insts != data.end() ; insts = data.findNext( insts, ptr )) { - for ( auto inst = insts->second.rbegin() ; - inst != insts->second.rend() ; ++inst ) { - if ( inst->first == typeList ) { - return inst->second; - } - } - } - return nullptr; - } - - /// Adds a value for a (key, type list) pair to the current scope. - void insert( ast::AggregateDecl const * key, type_vector const & params, - ast::AggregateDecl const * value ) { - auto it = data.findAt( data.currentScope(), key ); - if ( it == data.end() ) { - data.insert( key, ValueList( 1, - Instantiation( TypeList( params ), value ) ) ); - } else { - it->second.emplace_back( - Instantiation( TypeList( params ), value ) ); - } - } -}; - -/// Possible options for a given specialization of a generic type. -enum class GenericType { - /// Concrete instatiation based solely on {d,f}type-to-void conversions. - dtypeStatic, - /// Concrete instatiation requiring at least one parameters type. - concrete, - /// No concrete instantiation. - dynamic -}; - -GenericType & operator|=( GenericType & gt, const GenericType & ht ) { - if ( gt < ht ) gt = ht; - return gt; -} - -bool isDtypeStatic( ast::vector const & baseParams ) { - return std::all_of( baseParams.begin(), baseParams.end(), - []( ast::TypeDecl const * td ){ return !td->isComplete(); } - ); -} - -/// Makes substitutions of params into baseParams; returns dtypeStatic if -/// there is a concrete instantiation based only on {d,f}type-to-void -/// conversions, concrete if there is a concrete instantiation requiring at -/// least one parameter type, and dynamic if there is no concrete instantiation. -GenericType makeSubstitutions( - ast::vector & out, - ast::vector const & baseParams, - ast::vector const & params ) { - GenericType gt = GenericType::dtypeStatic; - - // Substitute concrete types for given parameters, - // using incomplete types for placeholders. - auto baseParam = baseParams.begin(); - auto param = params.begin(); - for ( ; baseParam != baseParams.end() && param != params.end() ; - ++baseParam, ++param ) { - ast::TypeExpr const * paramExpr = param->as(); - assertf( paramExpr, "Aggregate parameters should be type expressions." ); - - if ( (*baseParam)->isComplete() ) { - // Substitute parameter for complete (otype or sized dtype) type. - if ( isPolyType( paramExpr->type ) ) { - // Substitute polymorphic parameter type in to generic type. - out.push_back( ast::deepCopy( paramExpr ) ); - gt = GenericType::dynamic; - } else { - // Normalize possibly dtype-static parameter type. - out.emplace_back( new ast::TypeExpr( paramExpr->location, - scrubAllTypeVars( ast::deepCopy( paramExpr->type ) ) ) ); - gt |= GenericType::concrete; - } - } else switch ( (*baseParam)->kind ) { - case ast::TypeDecl::Dtype: - // Here, pretend that any incomplete dtype is `void`. - out.emplace_back( new ast::TypeExpr( paramExpr->location, - new ast::VoidType() ) ); - break; - case ast::TypeDecl::Ftype: - // Here, pretend that any ftype is `void (*)(void)`. - out.emplace_back( new ast::TypeExpr( paramExpr->location, - new ast::FunctionType() ) ); - break; - case ast::TypeDecl::Ttype: - assertf( false, "Ttype parameters are not currently allowed as parameters to generic types." ); - break; - default: - assertf( false, "Unhandled type parameter kind" ); - break; - } - } - - assertf( baseParam == baseParams.end(), "Base Parameters not exausted." ); - assertf( param == params.end(), "Type parameters not exausted." ); - return gt; -} - -/// Substitutes types of members according to baseParams => typeSubs, -/// returning the result in a new vector. -ast::vector substituteMembers( - ast::vector const & members, - ast::vector const & baseParams, - ast::vector const & typeSubs ) { - ast::vector out; - ast::TypeSubstitution subs( baseParams, typeSubs ); - for ( ast::ptr const & member : members ) { - // Create a manual copy to avoid in-place mutation. - // If being a PureVisitor is decided to be part of apply's interface, - // then we can actually skip this step as it will never mutate in- - // place. (Then we don't need the extra guard to free temp value.) - ast::ptr copy = ast::deepCopy( member.get() ); - auto result = subs.apply( copy.get() ); - out.emplace_back( result.node ); - } - return out; -} - -/// Substitutes types of members according to baseParams => typeSubs, -/// modifying them in-place. -void substituteMembersHere( - ast::vector & members, - ast::vector const & baseParams, - ast::vector const & typeSubs ) { - ast::TypeSubstitution subs( baseParams, typeSubs ); - for ( ast::ptr & member : members ) { - // The member must be mutated in place to avoid breaking - assert( member->unique() ); - - auto field = member.strict_as(); - auto result = subs.apply( field->type.get() ); - auto copy = ast::mutate_field( - field, &ast::ObjectDecl::type, result.node ); - - // I'm not kidding, it is very important. - assert( copy == member.get() ); - } -} - -/// Strips the instances' type parameters. -void stripInstParams( ast::BaseInstType * inst ) { - inst->params.clear(); -} - -bool isGenericType( ast::Type const * type ) { - if ( auto inst = dynamic_cast( type ) ) { - return !inst->params.empty(); - } else if ( auto inst = dynamic_cast( type ) ) { - return !inst->params.empty(); - } else { - return false; - } -} - -// The Passes: - -struct FixDtypeStatic final : - public ast::WithGuards, - public ast::WithVisitorRef, - public ast::WithShortCircuiting, - public ast::WithStmtsToAdd<> { - ast::ApplicationExpr const * previsit( ast::ApplicationExpr const * expr ); - void previsit( ast::AddressExpr const * expr ); - - ast::Expr const * postvisit( ast::MemberExpr const * expr ); -private: - template - ast::Expr const * fixMemberExpr( - Aggr const * inst, ast::MemberExpr const * memberExpr ); - - ast::Expr const * fixMemberExpr( - ast::vector const & baseParams, - ast::MemberExpr const * memberExpr ); - - bool isLValueArg = false; -}; - -ast::ApplicationExpr const * FixDtypeStatic::previsit( - ast::ApplicationExpr const * expr ) { - GuardValue( isLValueArg ) = false; - ast::Decl const * function = ast::getFunction( expr ); - if ( ast::Linkage::Intrinsic != function->linkage - || !CodeGen::isAssignment( function->name ) ) { - return expr; - } - - // Explicity visit children because only the first element must be a - // C lvalue (normally, it can only send info to both or neither). - visit_children = false; - expr = mutate_field( expr, &ast::ApplicationExpr::env, - maybe_accept( expr->env.get(), *visitor ) ); - expr = mutate_field( expr, &ast::ApplicationExpr::result, - maybe_accept( expr->result.get(), *visitor ) ); - expr = mutate_field( expr, &ast::ApplicationExpr::func, - maybe_accept( expr->func.get(), *visitor ) ); - isLValueArg = true; - for ( unsigned i = 0; i < expr->args.size(); ++i ) { - ast::Expr const * newExpr = expr->args[i]->accept( *visitor ); - // This is declared here for lifetime reasons. - ast::ptr cast; - if ( newExpr != expr->args[i].get() && - (cast = dynamic_cast( newExpr )) ) { - newExpr = cast->arg.get(); - } - expr = mutate_field_index( expr, &ast::ApplicationExpr::args, - i, newExpr ); - isLValueArg = false; - } - return expr; -} - -void FixDtypeStatic::previsit( ast::AddressExpr const * ) { - // The argument of an address expression (`&`) must be a C lvalue. - GuardValue( isLValueArg ) = true; -} - -ast::Expr const * FixDtypeStatic::postvisit( ast::MemberExpr const * expr ) { - ast::ptr const & type = expr->aggregate->result; - if ( auto inst = type.as() ) { - if ( !inst->params.empty() ) return fixMemberExpr( inst, expr ); - } else if ( auto inst = type.as() ) { - if ( !inst->params.empty() ) return fixMemberExpr( inst, expr ); - } - return expr; -} - -template -ast::Expr const * FixDtypeStatic::fixMemberExpr( - Aggr const * inst, ast::MemberExpr const * memberExpr ) { - return fixMemberExpr( inst->base->params, memberExpr ); -} - -ast::Expr const * FixDtypeStatic::fixMemberExpr( - ast::vector const & baseParams, - ast::MemberExpr const * memberExpr ) { - // Need to cast dtype-static member expressions to their actual type - // before the actual type type is erased. - // NOTE: The casts here have the third argument (isGenerated) set to - // ExplicitCast so that they casts persist until Box, where they are needed. - - if ( !isDtypeStatic( baseParams ) || - ResolvExpr::typesCompatible( - memberExpr->result, - memberExpr->member->get_type() ) ) { - return memberExpr; - } - - // Type of member and type of expression differ. - ast::Type const * concType = ast::deepCopy( memberExpr->result ); - CodeLocation const & location = memberExpr->location; - if ( isLValueArg ) { - // The result must be a C lvalue expression. So make a new reference - // variable with the correct actual type to replace the - // member expression. - // forall(T &) - // struct Ptr { - // T * x; - // }; - // Ptr(int) p; - // int i; - // The original expression: - // p.x = &i; - // Becomes the expression/declaration: - // int *& _dtype_static_member_0; - // (_dtype_static_member_0 = (int**)&p.x, - // _dtype_static_member_0) = &i; - - // The declaration is simple: - static UniqueName tmpNamer( "_dtype_static_member_" ); - ast::ObjectDecl * tmp = new ast::ObjectDecl( location, - tmpNamer.newName(), - new ast::ReferenceType( concType ), - nullptr, - ast::Storage::Classes(), - ast::Linkage::C - ); - stmtsToAddBefore.push_back( new ast::DeclStmt( location, tmp ) ); - - // The expression is more complex, uses references and reference / - // pointer parity. But breaking it up risks reordering. - return new ast::CommaExpr( location, - ast::UntypedExpr::createAssign( location, - new ast::VariableExpr( location, tmp ), - new ast::CastExpr( location, - new ast::AddressExpr( location, memberExpr ), - new ast::PointerType( ast::deepCopy( concType ) ), - ast::ExplicitCast - ) - ), - new ast::VariableExpr( location, tmp ) - ); - } else { - // Here, it can simply add a cast to actual types. - return new ast::CastExpr( location, - memberExpr, - concType, - ast::ExplicitCast - ); - } -} - -struct GenericInstantiator final : - public ast::WithCodeLocation, - public ast::WithConstTypeSubstitution, - public ast::WithDeclsToAdd<>, - public ast::WithGuards, - public ast::WithVisitorRef -{ - /// Map of (generic type, parameter list) pairs - /// to concrete type instantiations. - InstantiationMap instantiations; - /// Set of types which are dtype-only generic - /// (and therefore have static layout). - std::set dtypeStatics; - /// Namer for concrete types. - UniqueName typeNamer; - /// Should not make use of type environment to replace types of function - /// parameter and return values. - bool inFunctionType = false; - /// Index of current member, used to recreate MemberExprs with the - /// member from an instantiation. - int memberIndex = -1; - - GenericInstantiator() : - instantiations(), dtypeStatics(), typeNamer("_conc_") {} - - ast::Type const * postvisit( ast::StructInstType const * inst ); - ast::Type const * postvisit( ast::UnionInstType const * inst ); - - void previsit( ast::MemberExpr const * expr ); - ast::Expr const * postvisit( ast::MemberExpr const * expr ); - ast::Expr const * postvisit( ast::Expr const * expr ); - ast::Designation const * postvisit( ast::Designation const * ); - - void previsit( ast::ParseNode const * node ) { - GuardValue( location ) = &node->location; - } - void previsit( ast::FunctionType const * ) { - GuardValue( inFunctionType ) = true; - } - void beginScope() { - instantiations.beginScope(); - } - void endScope() { - instantiations.endScope(); - } -private: - /// Wrap instantiation lookup for structures. - ast::StructDecl const * lookup( - ast::StructInstType const * inst, type_vector const & typeSubs ) const; - /// Wrap instantiation lookup for unions. - ast::UnionDecl const * lookup( - ast::UnionInstType const * inst, type_vector const & typeSubs ) const; - /// Wrap instantiation insertion for structures. - void insert( ast::StructInstType const * inst, - type_vector const & typeSubs, ast::StructDecl const * decl ); - /// Wrap instantiation insertion for unions. - void insert( ast::UnionInstType const * inst, - type_vector const & typeSubs, ast::UnionDecl const * decl ); - - void replaceParametersWithConcrete( ast::vector & params ); - ast::Type const * replaceWithConcrete( ast::Type const * type, bool doClone ); - - template - ast::Type const * fixInstType( ast::SueInstType const * inst ); - - /// Strips a dtype-static aggregate decl of its type parameters, - /// marks it as stripped. - void stripDtypeParams( ast::AggregateDecl * base, - ast::vector & baseParams, - ast::vector const & typeSubs ); -}; - -ast::Type const * GenericInstantiator::postvisit( - ast::StructInstType const * inst ) { - return fixInstType( inst ); -} - -ast::Type const * GenericInstantiator::postvisit( - ast::UnionInstType const * inst ) { - return fixInstType( inst ); -} - -template -ast::Type const * GenericInstantiator::fixInstType( - ast::SueInstType const * inst ) { - assert( location ); - - // There is nothing to mutate if the params are empty. - if ( inst->params.empty() ) return inst; - - // Need to replace type variables to ensure that generic types are - // instantiated for the return values of polymorphic functions (in - // particular, for thunks, because they are not [currently] copy - // constructed). - // (This used to be run only on structures, but I believe both need it.) - inst = strict_dynamic_cast const *>( - replaceWithConcrete( inst, false ) ); - - // Check for an already-instantiatiated dtype-static type. - if ( dtypeStatics.find( inst->base ) != dtypeStatics.end() ) { - auto mutInst = ast::mutate( inst ); - stripInstParams( mutInst ); - return mutInst; - } - - // Check if the type can be concretely instantiated; - // and put substitutions in typeSubs. - assertf( inst->base, "Base data-type has parameters." ); - ast::vector typeSubs; - GenericType gt = makeSubstitutions( typeSubs, inst->base->params, inst->params ); - switch ( gt ) { - case GenericType::dtypeStatic: - { - auto mutInst = ast::mutate( inst ); - assert( mutInst->base->unique() ); - auto mutBase = mutInst->base.get_and_mutate(); - stripDtypeParams( mutBase, mutBase->params, typeSubs ); - stripInstParams( mutInst ); - return mutInst; - } - case GenericType::concrete: - { - // Make concrete instantiation of generic type. - AggrDecl const * concDecl = lookup( inst, typeSubs ); - if ( !concDecl ) { - // Set concDecl to new type, insert type declaration - // into statements to add. - AggrDecl * newDecl = new AggrDecl( *location, - typeNamer.newName( inst->name ) - ); - newDecl->body = inst->base->body; - newDecl->members = substituteMembers( - inst->base->members, - inst->base->params, - typeSubs - ); - - // Forward declare before recursion. (TODO: Only when needed, #199.) - insert( inst, typeSubs, newDecl ); - if ( AggrDecl const * forwardDecl = ast::asForward( newDecl ) ) { - declsToAddBefore.push_back( forwardDecl ); - } - // Recursively instantiate members: - concDecl = strict_dynamic_cast( - newDecl->accept( *visitor ) ); - // Must occur before declaration is added so - // that member instantiation appear first. - declsToAddBefore.push_back( concDecl ); - } - return new ast::SueInstType( concDecl, inst->qualifiers ); - } - case GenericType::dynamic: - // Do nothing. - default: - // Should never happen. - return inst; - } -} - -void GenericInstantiator::previsit( ast::MemberExpr const * expr ) { - GuardValue( location ) = &expr->location; - GuardValue( memberIndex ) = -1; - // Only run on expressions where the field being accessed is generic. - if ( isGenericType( expr->aggregate->result ) ) { - // Find the location of the member: - ast::AggregateDecl const * aggr = - expr->aggregate->result.strict_as()->aggr(); - ast::vector const & members = aggr->members; - auto it = std::find( members.begin(), members.end(), expr->member ); - memberIndex = std::distance( members.begin(), it ); - assertf( memberIndex < (int)members.size(), "Could not find member %s in generic type %s.", toString( expr->member ).c_str(), toString( expr->aggregate ).c_str() ); - } -} - -ast::Expr const * GenericInstantiator::postvisit( - ast::MemberExpr const * expr ) { - if ( memberIndex == -1 ) { - return expr; - } - - // Using the location from the generic type, find the member - // in the instantiation and rebuild the member expression. - ast::AggregateDecl const * aggr = - expr->aggregate->result.strict_as()->aggr(); - assertf( memberIndex < (int)aggr->members.size(), "Instantiation somehow has fewer members than the generic type." ); - ast::Decl const * member = *std::next( aggr->members.begin(), memberIndex ); - assertf( member->name == expr->member->name, "Instantiation has different member order than the generic type. %s / %s", toString( member ).c_str(), toString( expr->member ).c_str() ); - auto field = strict_dynamic_cast< ast::DeclWithType const * >( member ); - ast::MemberExpr * ret = new ast::MemberExpr( expr->location, - field, - ast::deepCopy( expr->aggregate ) - ); - // For pointer decay: - ret->result = ResolvExpr::adjustExprType( - ret->result, - ast::TypeEnvironment(), - ast::SymbolTable() - ); - ret->env = expr->env; - return ret; -} - -ast::Expr const * GenericInstantiator::postvisit( ast::Expr const * expr ) { - // We are not modifying env on MemberExpr, but that seems to work. - if ( expr->env ) { - auto newEnv = expr->env->accept( *visitor ); - expr = ast::mutate_field( expr, &ast::Expr::env, newEnv ); - } - return expr; -} - -// This attempts to figure out what the final name of the field will be. -// Pretty printing can cause this to become incorrect. -std::string getPrintName( ast::DeclWithType const * decl ) { - return ( decl->linkage.is_mangled ) - ? decl->scopedMangleName() : decl->name; -} - -ast::Designation const * GenericInstantiator::postvisit( - ast::Designation const * designation ) { - // Disconnect designator names from their fields. - // It is now incorrect to point at the generic definition where the used - // type now is replaced with a concrete instance. Ideally, new variable - // expressions would point at fields in the concrete instances, but that - // is work and that information should not be needed this late in - // compilation. - - // Modify all designations, even if not needed. - auto mutNode = mutate( designation ); - for ( ast::ptr & designator : mutNode->designators ) { - if ( auto var = designator.as() ) { - designator = new ast::NameExpr( - var->location, getPrintName( var->var ) ); - } - } - return mutNode; -} - -ast::StructDecl const * GenericInstantiator::lookup( - ast::StructInstType const * inst, - type_vector const & typeSubs ) const { - auto ret = instantiations.lookup( inst->base, typeSubs ); - return strict_dynamic_cast( ret ); -} - -ast::UnionDecl const * GenericInstantiator::lookup( - ast::UnionInstType const * inst, - type_vector const & typeSubs ) const { - auto ret = instantiations.lookup( inst->base, typeSubs ); - return strict_dynamic_cast( ret ); -} - -void GenericInstantiator::insert( ast::StructInstType const * inst, - type_vector const & typeSubs, ast::StructDecl const * decl ) { - instantiations.insert( inst->base, typeSubs, decl ); -} - -void GenericInstantiator::insert( ast::UnionInstType const * inst, - type_vector const & typeSubs, ast::UnionDecl const * decl ) { - instantiations.insert( inst->base, typeSubs, decl ); -} - -void GenericInstantiator::replaceParametersWithConcrete( - ast::vector & params ) { - for ( ast::ptr & param : params ) { - auto paramType = param.as(); - assertf( paramType, "Aggregate parameters should be type expressions." ); - auto type = replaceWithConcrete( paramType->type, false ); - param = ast::mutate_field( paramType, &ast::TypeExpr::type, type ); - } -} - -ast::Type const * GenericInstantiator::replaceWithConcrete( - ast::Type const * type, bool doClone ) { - if ( auto inst = dynamic_cast( type ) ) { - if ( typeSubs && !inFunctionType ) { - ast::Type const * concType = typeSubs->lookup( inst ); - return ast::deepCopy( ( concType ) ? concType : inst ); - } - } else if ( auto inst = dynamic_cast( type ) ) { - auto mut = ( doClone ) ? ast::deepCopy( inst ) : ast::mutate( inst ); - replaceParametersWithConcrete( mut->params ); - return mut; - } else if ( auto inst = dynamic_cast( type ) ) { - auto mut = ( doClone ) ? ast::deepCopy( inst ) : ast::mutate( inst ); - replaceParametersWithConcrete( mut->params ); - return mut; - } - return type; -} - -void GenericInstantiator::stripDtypeParams( - ast::AggregateDecl * base, - ast::vector & baseParams, - ast::vector const & typeSubs ) { - substituteMembersHere( base->members, baseParams, typeSubs ); - - baseParams.clear(); - - dtypeStatics.insert( base ); -} - -} // namespace - -void instantiateGeneric( ast::TranslationUnit & translationUnit ) { - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); -} - -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/Lvalue.cpp =================================================================== --- src/GenPoly/Lvalue.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) +++ src/GenPoly/Lvalue.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) @@ -0,0 +1,631 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Lvalue.cpp -- Clean up lvalues and remove references. +// +// Author : Andrew Beach +// Created On : Thu Sep 15 14:08:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Wed Oct 6 9:59:00 2022 +// Update Count : 0 +// + +#include "Lvalue.h" + +#include +#include + +#include "AST/Copy.hpp" // for deepCopy +#include "AST/Expr.hpp" +#include "AST/Inspect.hpp" +#include "AST/LinkageSpec.hpp" // for Linkage +#include "AST/Pass.hpp" +#include "Common/SemanticError.h" // for SemanticWarning +#include "Common/ToString.hpp" // for toCString +#include "Common/UniqueName.h" // for UniqueName +#include "GenPoly/GenPoly.h" // for genFunctionType +#include "ResolvExpr/typeops.h" // for typesCompatible +#include "ResolvExpr/Unify.h" // for unify + +#if 0 +#define PRINT(x) x +#else +#define PRINT(x) +#endif + +namespace GenPoly { + +namespace { + +/// Intrinsic functions that return references now instead return lvalues. +struct FixIntrinsicResults final : public ast::WithGuards { + enum { + NoSkip, + Skip, + SkipInProgress, + } skip = NoSkip; + + void previsit( ast::AsmExpr const * ) { + GuardValue( skip ) = Skip; + } + void previsit( ast::ApplicationExpr const * ) { + GuardValue( skip ) = (skip == Skip) ? SkipInProgress : NoSkip; + } + + ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); + void previsit( ast::FunctionDecl const * decl ); + bool inIntrinsic = false; +}; + +/// Add de-references around address-of operations on reference types. +struct AddressRef final : + public ast::WithConstTranslationUnit, + public ast::WithGuards, + public ast::WithShortCircuiting, + public ast::WithVisitorRef { + void previsit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::AddressExpr const * expr ); + void previsit( ast::Expr const * expr ); + ast::ApplicationExpr const * previsit( ast::ApplicationExpr const * expr ); + void previsit( ast::SingleInit const * init ); + + void handleNonAddr( ast::Expr const * expr ); + + bool first = true; + bool current = false; + bool addCast = false; + int refDepth = 0; +}; + +/// Handles casts between references and pointers, +/// creating temporaries for the conversion. +struct ReferenceConversions final : + public ast::WithConstTranslationUnit, + public ast::WithGuards, public ast::WithStmtsToAdd<> { + ast::Expr const * postvisit( ast::CastExpr const * expr ); + ast::Expr const * postvisit( ast::AddressExpr const * expr ); +}; + +/// Intrinsic functions that take reference parameters don't actually do. +/// Their reference arguments must be implicity dereferenced. +/// TODO Also appears to contain redundent code with AddressRef +struct FixIntrinsicArgs final : + public ast::WithConstTranslationUnit { + ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); +}; + +/// Removes redundant &* / *& patterns that may be generated. +struct CollapseAddressDeref final { + ast::Expr const * postvisit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); +}; + +/// GCC-like Generalized Lvalues (which have since been removed from GCC). +/// https://gcc.gnu.org/onlinedocs/gcc-3.4.6/gcc/Lvalues.html#Lvalues +/// Replaces &(a,b) with (a, &b), &(a ? b : c) with (a ? &b : &c) +struct GeneralizedLvalue final : + public ast::WithVisitorRef { + ast::Expr const * postvisit( ast::AddressExpr const * expr ); + ast::Expr const * postvisit( ast::MemberExpr const * expr ); + + template + ast::Expr const * applyTransformation( + Node const * expr, ast::ptr Node::*field, Func mkExpr ); +}; + +/// Replace all reference types with pointer types. +struct ReferenceTypeElimination final { + ast::Type const * postvisit( ast::ReferenceType const * type ); +}; + +/// True for intrinsic function calls that return an lvalue in C. +bool isIntrinsicReference( ast::Expr const * expr ) { + // The known intrinsic-reference prelude functions. + static std::set const lvalueFunctions = { "*?", "?[?]" }; + if ( auto untyped = dynamic_cast( expr ) ) { + std::string fname = ast::getFunctionName( untyped ); + return lvalueFunctions.count( fname ); + } else if ( auto app = dynamic_cast( expr ) ) { + if ( auto func = ast::getFunction( app ) ) { + return func->linkage == ast::Linkage::Intrinsic + && lvalueFunctions.count( func->name ); + } + } + return false; +} + +// A maybe typed variant of the createDeref function (only UntypedExpr). +ast::Expr * mkDeref( + ast::TranslationGlobal const & global, ast::Expr const * arg ) { + if ( global.dereference ) { + // Note: Reference depth can be arbitrarily deep here, + // so peel off the outermost pointer/reference, not just + // pointer because they are effecitvely equivalent in this pass + ast::VariableExpr * deref = new ast::VariableExpr( + arg->location, global.dereference ); + deref->result = new ast::PointerType( deref->result ); + ast::Type const * base = ast::getPointerBase( arg->result ); + assertf( base, "expected pointer type in dereference (type was %s)", toString( arg->result ).c_str() ); + ast::ApplicationExpr * ret = + new ast::ApplicationExpr( arg->location, deref, { arg } ); + ret->result = ast::deepCopy( base ); + return ret; + } else { + return ast::UntypedExpr::createDeref( arg->location, arg ); + } +} + +ast::Expr const * FixIntrinsicResults::postvisit( + ast::ApplicationExpr const * expr ) { + if ( skip == SkipInProgress || !isIntrinsicReference( expr ) ) { + return expr; + } + // Eliminate reference types from intrinsic applications + // now they return lvalues. + ast::ptr result = + expr->result.strict_as(); + expr = ast::mutate_field( expr, &ast::ApplicationExpr::result, + ast::deepCopy( result->base ) ); + if ( inIntrinsic ) { + return expr; + } + // When not in an intrinsic function, add a cast to don't add cast when + // in an intrinsic function, since they already have the cast. + auto * ret = new ast::CastExpr( expr->location, expr, result.get() ); + ret->env = expr->env; + return ret; +} + +void FixIntrinsicResults::previsit( ast::FunctionDecl const * decl ) { + GuardValue( inIntrinsic ) = decl->linkage == ast::Linkage::Intrinsic; +} + +void AddressRef::previsit( ast::AddressExpr const * ) { + // Is this the first address-of in the chain? + GuardValue( current ) = first; + // Later references will not be for next address-of to be first in chain. + GuardValue( first ) = false; + // If is the outermost address-of in a chain: + if ( current ) { + // Set depth to 0 so that postvisit can + // find the innermost address-of easily. + GuardValue( refDepth ) = 0; + } +} + +ast::Expr const * AddressRef::postvisit( ast::AddressExpr const * expr ) { + PRINT( std::cerr << "addr ref at " << expr << std::endl; ) + if ( 0 == refDepth ) { + PRINT( std::cerr << "depth 0, get new depth..." << std::endl; ) + // Is this the innermost address-of in a chain? record depth D. + if ( isIntrinsicReference( expr->arg ) ) { + assertf( false, "AddrRef : address-of should not have intrinsic reference argument: %s", toCString( expr->arg ) ); + } else { + // try to avoid ?[?] + // TODO is this condition still necessary? intrinsicReferences + // should have a cast around them at this point, so I don't think + // this condition ever fires. + refDepth = expr->arg->result->referenceDepth(); + PRINT( std::cerr << "arg not intrinsic reference, new depth is: " << refDepth << std::endl; ) + } + } + if ( current ) { + PRINT( std::cerr << "current, depth is: " << refDepth << std::endl; ) + ast::Expr const * ret = expr; + while ( refDepth ) { + // Add one dereference for each address-of in the chain. + ret = mkDeref( transUnit().global, ret ); + --refDepth; + } + + // if addrExpr depth is 0, then the result is a pointer because the + // arg was depth 1 and not lvalue. This means the dereference result + // is not a reference, is lvalue, and one less pointer depth than the + // addrExpr. Thus the cast is meaningless. + // TODO: One thing to double check is whether it is possible for the + // types to differ outside of the single pointer level (i.e. can the + // base type of addrExpr differ from the type of addrExpr-arg?). If + // so then the cast might need to be added, conditional on a more + // sophisticated check. + if ( addCast && 0 != expr->result->referenceDepth() ) { + PRINT( std::cerr << "adding cast to " << expr->result << std::endl; ) + return new ast::CastExpr( expr->location, + ret, ast::deepCopy( expr->result ) ); + } + return ret; + } + PRINT( std::cerr << "not current..." << std::endl; ) + return expr; +} + +void AddressRef::previsit( ast::Expr const * expr ) { + handleNonAddr( expr ); + GuardValue( addCast ) = false; +} + +// So we want to skip traversing to the head? +ast::ApplicationExpr const * AddressRef::previsit( + ast::ApplicationExpr const * expr ) { + visit_children = false; + GuardValue( addCast ); + handleNonAddr( expr ); + auto mutExpr = ast::mutate( expr ); + for ( ast::ptr & arg : mutExpr->args ) { + addCast = true; + arg = arg->accept( *visitor ); + } + return mutExpr; +} + +void AddressRef::previsit( ast::SingleInit const * ) { + // Each initialization context with address-of requires a cast. + GuardValue( addCast ) = true; +} + +// idea: &&&E: get outer &, inner & +// at inner &, record depth D of reference type of argument of &. +// at auter &, add D derefs. +void AddressRef::handleNonAddr( ast::Expr const * ) { + // non-address-of: reset status variables: + // * current expr is NOT the first address-of expr in an address-of chain. + // * next seen address-of expr IS the first in the chain. + GuardValue( current ) = false; + GuardValue( first ) = true; +} + +ast::Expr const * ReferenceConversions::postvisit( + ast::CastExpr const * expr ) { + // TODO: Is it possible to convert directly between reference types with + // a different base. e.g. + // int x; + // (double&)x; + // At the moment, I (who?) am working off of the assumption that this is + // illegal, thus the cast becomes redundant after this pass, so trash the + // cast altogether. If that changes, care must be taken to insert the + // correct pointer casts in the right places. + + // Note: reference depth difference is the determining factor in what + // code is run, rather than whether something is reference type or not, + // since conversion still needs to occur when both types are references + // that differ in depth. + ast::Type const * dstType = expr->result.get(); + ast::Type const * srcType = expr->arg->result.get(); + assertf( dstType, "Cast to no type in: %s", toCString( expr ) ); + assertf( srcType, "Cast from no type in: %s", toCString( expr ) ); + int dstDepth = dstType->referenceDepth(); + int srcDepth = srcType->referenceDepth(); + int diff = dstDepth - srcDepth; + + if ( 0 < diff && !expr->arg->get_lvalue() ) { + // rvalue to reference conversion -- introduce temporary + // know that reference depth of cast argument is 0 + // (int &&&)3; + // becomes + // int __ref_tmp_0 = 3; + // int & __ref_tmp_1 = &__ref_tmp_0; + // int && __ref_tmp_2 = &__ref_tmp_1; + // &__ref_tmp_2; + // The last & comes from the remaining reference conversion code. + SemanticWarning( expr->arg->location, + Warning::RvalueToReferenceConversion, toCString( expr->arg ) ); + + static UniqueName tmpNamer( "__ref_tmp_" ); + ast::ObjectDecl * tmp = new ast::ObjectDecl( expr->arg->location, + tmpNamer.newName(), + ast::deepCopy( expr->arg->result ), + new ast::SingleInit( expr->arg->location, expr->arg ) ); + PRINT( std::cerr << "make tmp: " << tmp << std::endl; ) + stmtsToAddBefore.push_back( new ast::DeclStmt( tmp->location, tmp ) ); + for ( int i = 0 ; i < dstDepth - 1 ; ++i ) { + ast::ObjectDecl * newTmp = new ast::ObjectDecl( tmp->location, + tmpNamer.newName(), + new ast::ReferenceType( ast::deepCopy( tmp->type ) ), + new ast::SingleInit( tmp->location, + new ast::AddressExpr( tmp->location, + new ast::VariableExpr( tmp->location, tmp ) ) ) ); + PRINT( std::cerr << "make tmp: " << i << ": " << newTmp << std::endl; ) + stmtsToAddBefore.push_back( + new ast::DeclStmt( newTmp->location, newTmp ) ); + tmp = newTmp; + } + // Update diff so that remaining code works out correctly. + expr = ast::mutate_field( expr, &ast::CastExpr::arg, + new ast::VariableExpr( tmp->location, tmp ) ); + PRINT( std::cerr << "update cast to: " << expr << std::endl; ) + srcType = expr->arg->result; + srcDepth = srcType->referenceDepth(); + diff = dstDepth - srcDepth; + assert( 1 == diff ); + } + + // Handle conversion between different depths. + PRINT( + if ( dstDepth || srcDepth ) { + std::cerr << "dstType: " << dstType << " / srcType: " << srcType << '\n'; + std::cerr << "depth: " << dstDepth << " / " << srcDepth << std::endl; + } + ) + // Conversion to type with more depth/more references. + // Add address-of for each level of difference. + if ( 0 < diff ) { + ast::Expr * ret = ast::mutate( expr->arg.get() ); + for ( int i = 0 ; i < diff ; ++i ) { + ret = new ast::AddressExpr( ret->location, ret ); + } + if ( expr->arg->get_lvalue() && + !ResolvExpr::typesCompatible( + srcType, + strict_dynamic_cast( dstType )->base ) ) { + // Must keep cast if cast-to type is different from the actual type. + return ast::mutate_field( expr, &ast::CastExpr::arg, ret ); + } + ret->env = expr->env; + ret->result = expr->result; + return ret; + // Conversion to type with less depth/fewer references. + // Add dereferences for each level of difference. + } else if ( diff < 0 ) { + ast::Expr * ret = ast::mutate( expr->arg.get() ); + for ( int i = 0 ; i < -diff ; ++i ) { + ret = mkDeref( transUnit().global, ret ); + } + // Must keep cast if types are different. + if ( !ResolvExpr::typesCompatibleIgnoreQualifiers( + dstType->stripReferences(), + srcType->stripReferences() ) ) { + return ast::mutate_field( expr, &ast::CastExpr::arg, ret ); + } + ret->env = expr->env; + ret->result = expr->result; + // The result must be an lvalue. + assert( ret->get_lvalue() ); + return ret; + // Conversion with the same depth. + } else { + assert( 0 == diff ); + // Remove useless generated casts. + if ( expr->isGenerated && + ResolvExpr::typesCompatible( + expr->result, + expr->arg->result ) ) { + PRINT( + std::cerr << "types are compatible, removing cast: " << expr << '\n'; + std::cerr << "-- " << expr->result << '\n'; + std::cerr << "-- " << expr->arg->result << std::endl; + ) + return ast::mutate_field( expr->arg.get(), + &ast::Expr::env, expr->env.get() ); + } + return expr; + } +} + +ast::Expr const * ReferenceConversions::postvisit( + ast::AddressExpr const * expr ) { + // Inner expression may have been lvalue to reference conversion, which + // becomes an address expression. In this case, remove the outer address + // expression and return the argument. + // TODO: It's possible that this might catch too much and require a more + // sophisticated check. TODO What check are we talking about here? + return expr; +} + +ast::Expr const * FixIntrinsicArgs::postvisit( + ast::ApplicationExpr const * expr ) { + // Intrinsic functions don't really take reference-typed parameters, + // so they require an implicit dereference on their arguments. + auto function = ast::getFunction( expr ); + if ( function == nullptr ) { + return expr; + } + + ast::FunctionType const * ftype = GenPoly::getFunctionType( function->get_type() ); + assertf( ftype, "Function declaration does not have function type." ); + // Can be of different lengths only when function is variadic. + assertf( ftype->params.size() == expr->args.size() || ftype->isVarArgs, + "ApplicationExpr args do not match formal parameter type." ); + assertf( ftype->params.size() <= expr->args.size(), + "Cannot have more parameters than arguments." ); + + unsigned int i = 0; + unsigned int const end = ftype->params.size(); + + // This is used to make sure we get a zip on shortests. + if ( end == i ) return expr; + + // This mutate could be redundent, but it is simpler this way. + auto mutExpr = ast::mutate( expr ); + + for ( auto pair : unsafe_group_iterate( mutExpr->args, ftype->params ) ) { + ast::ptr & arg = std::get<0>( pair ); + ast::ptr const & formal = std::get<1>( pair ); + PRINT( + std::cerr << "pair<0>: " << arg.get() << std::endl; + std::cerr << " -- " << arg->result << std::endl; + std::cerr << "pair<1>: " << formal << std::endl; + ) + //if ( dynamic_cast( formal.get() ) ) { + if ( formal.as() ) { + PRINT( std::cerr << "===formal is reference" << std::endl; ) + // TODO: It's likely that the second condition should be + // `... && ! isIntrinsicReference( arg )`, but this requires + // investigation. + + if ( ast::Linkage::Intrinsic != function->linkage + && isIntrinsicReference( arg ) ) { + // Needed for definition of prelude functions, etc. + // If argument is dereference or array subscript, the result + // isn't REALLY a reference, but non-intrinsic functions + // expect a reference: take address + + // TODO: OK, so this should be cut?! + // NODE: Previously, this condition fixed + // void f(int *&); + // int & x = ...; + // f(&x); + // But now this is taken care of by a reference cast added by + // AddressRef. Need to find a new example or remove this + // branch. + PRINT( + std::cerr << "===is intrinsic arg in non-intrinsic call - adding address" << std::endl; + ) + arg = new ast::AddressExpr( arg->location, arg ); + } else if ( ast::Linkage::Intrinsic == function->linkage + && arg->result->referenceDepth() != 0 ) { + // Argument is a 'real' reference, but function expects a C + // lvalue: Add a dereference to the reference-typed argument. + PRINT( + std::cerr << "===is non-intrinsic arg in intrinsic call - adding deref to arg" << std::endl; + ) + ast::Type const * base = ast::getPointerBase( arg->result ); + assertf( base, "parameter is reference, arg must be pointer or reference: %s", toString( arg->result ).c_str() ); + ast::PointerType * ptr = new ast::PointerType( ast::deepCopy( base ) ); + arg = ast::mutate_field( arg.get(), + &ast::ApplicationExpr::result, ptr ); + arg = mkDeref( transUnit().global, arg ); + } + } + ++i; + if ( end == i ) break; + } + return mutExpr; +} + +ast::Expr const * CollapseAddressDeref::postvisit( + ast::AddressExpr const * expr ) { + ast::Expr const * arg = expr->arg; + if ( isIntrinsicReference( arg ) ) { + std::string fname = ast::getFunctionName( arg ); + if ( fname == "*?" ) { + ast::Expr const * arg0 = ast::getCallArg( arg, 0 ); + ast::Expr * ret = ast::mutate( arg0 ); + ret->env = expr->env; + return ret; + } + } else if ( auto cast = dynamic_cast( arg ) ) { + // Need to move cast to pointer type out a level since address of + // pointer is not valid C code (can be introduced in prior passes, + // e.g., InstantiateGeneric) + if ( ast::getPointerBase( cast->result ) ) { + auto mutExpr = ast::mutate( expr ); + auto mutCast = strict_dynamic_cast( + ast::mutate( mutExpr->arg.release() ) ); + mutExpr->arg = mutCast->arg; + mutCast->arg = mutExpr; + mutCast->result = new ast::PointerType( mutCast->result ); + return mutCast; + } + } + return expr; +} + +ast::Expr const * CollapseAddressDeref::postvisit( + ast::ApplicationExpr const * expr ) { + if ( isIntrinsicReference( expr ) ) { + std::string fname = ast::getFunctionName( expr ); + if ( fname == "*?" ) { + assert( 1 == expr->args.size() ); + ast::Expr const * arg = ast::getCallArg( expr, 0 ); + // xxx - this isn't right, because it can remove casts that + // should be there... + // while ( auto cast = dynamic_cast< ast::CastExpr const * >( arg ) ) { + // arg = cast->arg; + // } + if ( auto addr = dynamic_cast( arg ) ) { + return ast::mutate_field( addr->arg.get(), + &ast::Expr::env, expr->env.get() ); + } + } + } + return expr; +} + +ast::Expr const * GeneralizedLvalue::postvisit( + ast::AddressExpr const * expr ) { + return applyTransformation( expr, &ast::AddressExpr::arg, + []( ast::Expr const * arg ) { + return new ast::AddressExpr( arg->location, arg ); + } + ); +} + +ast::Expr const * GeneralizedLvalue::postvisit( + ast::MemberExpr const * expr ) { + return applyTransformation( expr, &ast::MemberExpr::aggregate, + [expr]( ast::Expr const * aggr ) { + return new ast::MemberExpr( aggr->location, expr->member, aggr ); + } + ); +} + +template +ast::Expr const * GeneralizedLvalue::applyTransformation( + Node const * expr, ast::ptr Node::*field, Func mkExpr ) { + ast::ptr const & arg = expr->*field; + if ( auto commaArg = arg.as() ) { + ast::Expr const * arg1 = ast::deepCopy( commaArg->arg1 ); + ast::Expr const * arg2 = ast::deepCopy( commaArg->arg2 ); + ast::Expr const * ret = new ast::CommaExpr( + commaArg->location, arg1, mkExpr( arg2 )->accept( *visitor ) ); + return ret; + } else if ( auto condArg = arg.as() ) { + ast::Expr const * arg1 = ast::deepCopy( condArg->arg1 ); + ast::Expr const * arg2 = ast::deepCopy( condArg->arg2 ); + ast::Expr const * arg3 = ast::deepCopy( condArg->arg3 ); + ast::ConditionalExpr * ret = new ast::ConditionalExpr( + condArg->location, arg1, mkExpr( arg2 )->accept( *visitor ), + mkExpr( arg3 )->accept( *visitor ) ); + + // Conditional expr type may not be either of the arguments, + // so unify to get the result. + // TODO: Maybe I could create a wrapper for this. + ast::ptr common = nullptr; + ast::TypeEnvironment newEnv; + ast::AssertionSet needAssertions, haveAssertions; + ast::OpenVarSet openVars; + ResolvExpr::unify( ret->arg2->result, ret->arg3->result, newEnv, + needAssertions, haveAssertions, openVars, common ); + ret->result = common ? common : ast::deepCopy( ret->arg2->result ); + return ret; + } + return expr; +} + +ast::Type const * ReferenceTypeElimination::postvisit( + ast::ReferenceType const * type ) { + return new ast::PointerType( type->base, type->qualifiers ); +} + +} // namespace + +// Stored elsewhere (Lvalue2, initially false): +extern bool referencesEliminated; + +void convertLvalue( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + ast::Pass::run( translationUnit ); + // Last because other passes need reference types to work. + ast::Pass::run( translationUnit ); + // From this point forward, nothing should create reference types. + referencesEliminated = true; +} + +ast::Expr const * generalizedLvalue( ast::Expr const * expr ) { + ast::Pass visitor; + return expr->accept( visitor ); +} + +} // namespace GenPoly + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/LvalueNew.cpp =================================================================== --- src/GenPoly/LvalueNew.cpp (revision f48dfcd1acf87e4d711e108cd7119bb80ee701ee) +++ (revision ) @@ -1,631 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// LvalueNew.cpp -- Clean up lvalues and remove references. -// -// Author : Andrew Beach -// Created On : Thu Sep 15 14:08:00 2022 -// Last Modified By : Andrew Beach -// Last Modified On : Wed Oct 6 9:59:00 2022 -// Update Count : 0 -// - -#include "Lvalue.h" - -#include -#include - -#include "AST/Copy.hpp" // for deepCopy -#include "AST/Expr.hpp" -#include "AST/Inspect.hpp" -#include "AST/LinkageSpec.hpp" // for Linkage -#include "AST/Pass.hpp" -#include "Common/SemanticError.h" // for SemanticWarning -#include "Common/ToString.hpp" // for toCString -#include "Common/UniqueName.h" // for UniqueName -#include "GenPoly/GenPoly.h" // for genFunctionType -#include "ResolvExpr/typeops.h" // for typesCompatible -#include "ResolvExpr/Unify.h" // for unify - -#if 0 -#define PRINT(x) x -#else -#define PRINT(x) -#endif - -namespace GenPoly { - -namespace { - -/// Intrinsic functions that return references now instead return lvalues. -struct FixIntrinsicResults final : public ast::WithGuards { - enum { - NoSkip, - Skip, - SkipInProgress, - } skip = NoSkip; - - void previsit( ast::AsmExpr const * ) { - GuardValue( skip ) = Skip; - } - void previsit( ast::ApplicationExpr const * ) { - GuardValue( skip ) = (skip == Skip) ? SkipInProgress : NoSkip; - } - - ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); - void previsit( ast::FunctionDecl const * decl ); - bool inIntrinsic = false; -}; - -/// Add de-references around address-of operations on reference types. -struct AddressRef final : - public ast::WithConstTranslationUnit, - public ast::WithGuards, - public ast::WithShortCircuiting, - public ast::WithVisitorRef { - void previsit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::AddressExpr const * expr ); - void previsit( ast::Expr const * expr ); - ast::ApplicationExpr const * previsit( ast::ApplicationExpr const * expr ); - void previsit( ast::SingleInit const * init ); - - void handleNonAddr( ast::Expr const * expr ); - - bool first = true; - bool current = false; - bool addCast = false; - int refDepth = 0; -}; - -/// Handles casts between references and pointers, -/// creating temporaries for the conversion. -struct ReferenceConversions final : - public ast::WithConstTranslationUnit, - public ast::WithGuards, public ast::WithStmtsToAdd<> { - ast::Expr const * postvisit( ast::CastExpr const * expr ); - ast::Expr const * postvisit( ast::AddressExpr const * expr ); -}; - -/// Intrinsic functions that take reference parameters don't actually do. -/// Their reference arguments must be implicity dereferenced. -/// TODO Also appears to contain redundent code with AddressRef -struct FixIntrinsicArgs final : - public ast::WithConstTranslationUnit { - ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); -}; - -/// Removes redundant &* / *& patterns that may be generated. -struct CollapseAddressDeref final { - ast::Expr const * postvisit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::ApplicationExpr const * expr ); -}; - -/// GCC-like Generalized Lvalues (which have since been removed from GCC). -/// https://gcc.gnu.org/onlinedocs/gcc-3.4.6/gcc/Lvalues.html#Lvalues -/// Replaces &(a,b) with (a, &b), &(a ? b : c) with (a ? &b : &c) -struct GeneralizedLvalue final : - public ast::WithVisitorRef { - ast::Expr const * postvisit( ast::AddressExpr const * expr ); - ast::Expr const * postvisit( ast::MemberExpr const * expr ); - - template - ast::Expr const * applyTransformation( - Node const * expr, ast::ptr Node::*field, Func mkExpr ); -}; - -/// Replace all reference types with pointer types. -struct ReferenceTypeElimination final { - ast::Type const * postvisit( ast::ReferenceType const * type ); -}; - -/// True for intrinsic function calls that return an lvalue in C. -bool isIntrinsicReference( ast::Expr const * expr ) { - // The known intrinsic-reference prelude functions. - static std::set const lvalueFunctions = { "*?", "?[?]" }; - if ( auto untyped = dynamic_cast( expr ) ) { - std::string fname = ast::getFunctionName( untyped ); - return lvalueFunctions.count( fname ); - } else if ( auto app = dynamic_cast( expr ) ) { - if ( auto func = ast::getFunction( app ) ) { - return func->linkage == ast::Linkage::Intrinsic - && lvalueFunctions.count( func->name ); - } - } - return false; -} - -// A maybe typed variant of the createDeref function (only UntypedExpr). -ast::Expr * mkDeref( - ast::TranslationGlobal const & global, ast::Expr const * arg ) { - if ( global.dereference ) { - // Note: Reference depth can be arbitrarily deep here, - // so peel off the outermost pointer/reference, not just - // pointer because they are effecitvely equivalent in this pass - ast::VariableExpr * deref = new ast::VariableExpr( - arg->location, global.dereference ); - deref->result = new ast::PointerType( deref->result ); - ast::Type const * base = ast::getPointerBase( arg->result ); - assertf( base, "expected pointer type in dereference (type was %s)", toString( arg->result ).c_str() ); - ast::ApplicationExpr * ret = - new ast::ApplicationExpr( arg->location, deref, { arg } ); - ret->result = ast::deepCopy( base ); - return ret; - } else { - return ast::UntypedExpr::createDeref( arg->location, arg ); - } -} - -ast::Expr const * FixIntrinsicResults::postvisit( - ast::ApplicationExpr const * expr ) { - if ( skip == SkipInProgress || !isIntrinsicReference( expr ) ) { - return expr; - } - // Eliminate reference types from intrinsic applications - // now they return lvalues. - ast::ptr result = - expr->result.strict_as(); - expr = ast::mutate_field( expr, &ast::ApplicationExpr::result, - ast::deepCopy( result->base ) ); - if ( inIntrinsic ) { - return expr; - } - // When not in an intrinsic function, add a cast to don't add cast when - // in an intrinsic function, since they already have the cast. - auto * ret = new ast::CastExpr( expr->location, expr, result.get() ); - ret->env = expr->env; - return ret; -} - -void FixIntrinsicResults::previsit( ast::FunctionDecl const * decl ) { - GuardValue( inIntrinsic ) = decl->linkage == ast::Linkage::Intrinsic; -} - -void AddressRef::previsit( ast::AddressExpr const * ) { - // Is this the first address-of in the chain? - GuardValue( current ) = first; - // Later references will not be for next address-of to be first in chain. - GuardValue( first ) = false; - // If is the outermost address-of in a chain: - if ( current ) { - // Set depth to 0 so that postvisit can - // find the innermost address-of easily. - GuardValue( refDepth ) = 0; - } -} - -ast::Expr const * AddressRef::postvisit( ast::AddressExpr const * expr ) { - PRINT( std::cerr << "addr ref at " << expr << std::endl; ) - if ( 0 == refDepth ) { - PRINT( std::cerr << "depth 0, get new depth..." << std::endl; ) - // Is this the innermost address-of in a chain? record depth D. - if ( isIntrinsicReference( expr->arg ) ) { - assertf( false, "AddrRef : address-of should not have intrinsic reference argument: %s", toCString( expr->arg ) ); - } else { - // try to avoid ?[?] - // TODO is this condition still necessary? intrinsicReferences - // should have a cast around them at this point, so I don't think - // this condition ever fires. - refDepth = expr->arg->result->referenceDepth(); - PRINT( std::cerr << "arg not intrinsic reference, new depth is: " << refDepth << std::endl; ) - } - } - if ( current ) { - PRINT( std::cerr << "current, depth is: " << refDepth << std::endl; ) - ast::Expr const * ret = expr; - while ( refDepth ) { - // Add one dereference for each address-of in the chain. - ret = mkDeref( transUnit().global, ret ); - --refDepth; - } - - // if addrExpr depth is 0, then the result is a pointer because the - // arg was depth 1 and not lvalue. This means the dereference result - // is not a reference, is lvalue, and one less pointer depth than the - // addrExpr. Thus the cast is meaningless. - // TODO: One thing to double check is whether it is possible for the - // types to differ outside of the single pointer level (i.e. can the - // base type of addrExpr differ from the type of addrExpr-arg?). If - // so then the cast might need to be added, conditional on a more - // sophisticated check. - if ( addCast && 0 != expr->result->referenceDepth() ) { - PRINT( std::cerr << "adding cast to " << expr->result << std::endl; ) - return new ast::CastExpr( expr->location, - ret, ast::deepCopy( expr->result ) ); - } - return ret; - } - PRINT( std::cerr << "not current..." << std::endl; ) - return expr; -} - -void AddressRef::previsit( ast::Expr const * expr ) { - handleNonAddr( expr ); - GuardValue( addCast ) = false; -} - -// So we want to skip traversing to the head? -ast::ApplicationExpr const * AddressRef::previsit( - ast::ApplicationExpr const * expr ) { - visit_children = false; - GuardValue( addCast ); - handleNonAddr( expr ); - auto mutExpr = ast::mutate( expr ); - for ( ast::ptr & arg : mutExpr->args ) { - addCast = true; - arg = arg->accept( *visitor ); - } - return mutExpr; -} - -void AddressRef::previsit( ast::SingleInit const * ) { - // Each initialization context with address-of requires a cast. - GuardValue( addCast ) = true; -} - -// idea: &&&E: get outer &, inner & -// at inner &, record depth D of reference type of argument of &. -// at auter &, add D derefs. -void AddressRef::handleNonAddr( ast::Expr const * ) { - // non-address-of: reset status variables: - // * current expr is NOT the first address-of expr in an address-of chain. - // * next seen address-of expr IS the first in the chain. - GuardValue( current ) = false; - GuardValue( first ) = true; -} - -ast::Expr const * ReferenceConversions::postvisit( - ast::CastExpr const * expr ) { - // TODO: Is it possible to convert directly between reference types with - // a different base. e.g. - // int x; - // (double&)x; - // At the moment, I (who?) am working off of the assumption that this is - // illegal, thus the cast becomes redundant after this pass, so trash the - // cast altogether. If that changes, care must be taken to insert the - // correct pointer casts in the right places. - - // Note: reference depth difference is the determining factor in what - // code is run, rather than whether something is reference type or not, - // since conversion still needs to occur when both types are references - // that differ in depth. - ast::Type const * dstType = expr->result.get(); - ast::Type const * srcType = expr->arg->result.get(); - assertf( dstType, "Cast to no type in: %s", toCString( expr ) ); - assertf( srcType, "Cast from no type in: %s", toCString( expr ) ); - int dstDepth = dstType->referenceDepth(); - int srcDepth = srcType->referenceDepth(); - int diff = dstDepth - srcDepth; - - if ( 0 < diff && !expr->arg->get_lvalue() ) { - // rvalue to reference conversion -- introduce temporary - // know that reference depth of cast argument is 0 - // (int &&&)3; - // becomes - // int __ref_tmp_0 = 3; - // int & __ref_tmp_1 = &__ref_tmp_0; - // int && __ref_tmp_2 = &__ref_tmp_1; - // &__ref_tmp_2; - // The last & comes from the remaining reference conversion code. - SemanticWarning( expr->arg->location, - Warning::RvalueToReferenceConversion, toCString( expr->arg ) ); - - static UniqueName tmpNamer( "__ref_tmp_" ); - ast::ObjectDecl * tmp = new ast::ObjectDecl( expr->arg->location, - tmpNamer.newName(), - ast::deepCopy( expr->arg->result ), - new ast::SingleInit( expr->arg->location, expr->arg ) ); - PRINT( std::cerr << "make tmp: " << tmp << std::endl; ) - stmtsToAddBefore.push_back( new ast::DeclStmt( tmp->location, tmp ) ); - for ( int i = 0 ; i < dstDepth - 1 ; ++i ) { - ast::ObjectDecl * newTmp = new ast::ObjectDecl( tmp->location, - tmpNamer.newName(), - new ast::ReferenceType( ast::deepCopy( tmp->type ) ), - new ast::SingleInit( tmp->location, - new ast::AddressExpr( tmp->location, - new ast::VariableExpr( tmp->location, tmp ) ) ) ); - PRINT( std::cerr << "make tmp: " << i << ": " << newTmp << std::endl; ) - stmtsToAddBefore.push_back( - new ast::DeclStmt( newTmp->location, newTmp ) ); - tmp = newTmp; - } - // Update diff so that remaining code works out correctly. - expr = ast::mutate_field( expr, &ast::CastExpr::arg, - new ast::VariableExpr( tmp->location, tmp ) ); - PRINT( std::cerr << "update cast to: " << expr << std::endl; ) - srcType = expr->arg->result; - srcDepth = srcType->referenceDepth(); - diff = dstDepth - srcDepth; - assert( 1 == diff ); - } - - // Handle conversion between different depths. - PRINT( - if ( dstDepth || srcDepth ) { - std::cerr << "dstType: " << dstType << " / srcType: " << srcType << '\n'; - std::cerr << "depth: " << dstDepth << " / " << srcDepth << std::endl; - } - ) - // Conversion to type with more depth/more references. - // Add address-of for each level of difference. - if ( 0 < diff ) { - ast::Expr * ret = ast::mutate( expr->arg.get() ); - for ( int i = 0 ; i < diff ; ++i ) { - ret = new ast::AddressExpr( ret->location, ret ); - } - if ( expr->arg->get_lvalue() && - !ResolvExpr::typesCompatible( - srcType, - strict_dynamic_cast( dstType )->base ) ) { - // Must keep cast if cast-to type is different from the actual type. - return ast::mutate_field( expr, &ast::CastExpr::arg, ret ); - } - ret->env = expr->env; - ret->result = expr->result; - return ret; - // Conversion to type with less depth/fewer references. - // Add dereferences for each level of difference. - } else if ( diff < 0 ) { - ast::Expr * ret = ast::mutate( expr->arg.get() ); - for ( int i = 0 ; i < -diff ; ++i ) { - ret = mkDeref( transUnit().global, ret ); - } - // Must keep cast if types are different. - if ( !ResolvExpr::typesCompatibleIgnoreQualifiers( - dstType->stripReferences(), - srcType->stripReferences() ) ) { - return ast::mutate_field( expr, &ast::CastExpr::arg, ret ); - } - ret->env = expr->env; - ret->result = expr->result; - // The result must be an lvalue. - assert( ret->get_lvalue() ); - return ret; - // Conversion with the same depth. - } else { - assert( 0 == diff ); - // Remove useless generated casts. - if ( expr->isGenerated && - ResolvExpr::typesCompatible( - expr->result, - expr->arg->result ) ) { - PRINT( - std::cerr << "types are compatible, removing cast: " << expr << '\n'; - std::cerr << "-- " << expr->result << '\n'; - std::cerr << "-- " << expr->arg->result << std::endl; - ) - return ast::mutate_field( expr->arg.get(), - &ast::Expr::env, expr->env.get() ); - } - return expr; - } -} - -ast::Expr const * ReferenceConversions::postvisit( - ast::AddressExpr const * expr ) { - // Inner expression may have been lvalue to reference conversion, which - // becomes an address expression. In this case, remove the outer address - // expression and return the argument. - // TODO: It's possible that this might catch too much and require a more - // sophisticated check. TODO What check are we talking about here? - return expr; -} - -ast::Expr const * FixIntrinsicArgs::postvisit( - ast::ApplicationExpr const * expr ) { - // Intrinsic functions don't really take reference-typed parameters, - // so they require an implicit dereference on their arguments. - auto function = ast::getFunction( expr ); - if ( function == nullptr ) { - return expr; - } - - ast::FunctionType const * ftype = GenPoly::getFunctionType( function->get_type() ); - assertf( ftype, "Function declaration does not have function type." ); - // Can be of different lengths only when function is variadic. - assertf( ftype->params.size() == expr->args.size() || ftype->isVarArgs, - "ApplicationExpr args do not match formal parameter type." ); - assertf( ftype->params.size() <= expr->args.size(), - "Cannot have more parameters than arguments." ); - - unsigned int i = 0; - unsigned int const end = ftype->params.size(); - - // This is used to make sure we get a zip on shortests. - if ( end == i ) return expr; - - // This mutate could be redundent, but it is simpler this way. - auto mutExpr = ast::mutate( expr ); - - for ( auto pair : unsafe_group_iterate( mutExpr->args, ftype->params ) ) { - ast::ptr & arg = std::get<0>( pair ); - ast::ptr const & formal = std::get<1>( pair ); - PRINT( - std::cerr << "pair<0>: " << arg.get() << std::endl; - std::cerr << " -- " << arg->result << std::endl; - std::cerr << "pair<1>: " << formal << std::endl; - ) - //if ( dynamic_cast( formal.get() ) ) { - if ( formal.as() ) { - PRINT( std::cerr << "===formal is reference" << std::endl; ) - // TODO: It's likely that the second condition should be - // `... && ! isIntrinsicReference( arg )`, but this requires - // investigation. - - if ( ast::Linkage::Intrinsic != function->linkage - && isIntrinsicReference( arg ) ) { - // Needed for definition of prelude functions, etc. - // If argument is dereference or array subscript, the result - // isn't REALLY a reference, but non-intrinsic functions - // expect a reference: take address - - // TODO: OK, so this should be cut?! - // NODE: Previously, this condition fixed - // void f(int *&); - // int & x = ...; - // f(&x); - // But now this is taken care of by a reference cast added by - // AddressRef. Need to find a new example or remove this - // branch. - PRINT( - std::cerr << "===is intrinsic arg in non-intrinsic call - adding address" << std::endl; - ) - arg = new ast::AddressExpr( arg->location, arg ); - } else if ( ast::Linkage::Intrinsic == function->linkage - && arg->result->referenceDepth() != 0 ) { - // Argument is a 'real' reference, but function expects a C - // lvalue: Add a dereference to the reference-typed argument. - PRINT( - std::cerr << "===is non-intrinsic arg in intrinsic call - adding deref to arg" << std::endl; - ) - ast::Type const * base = ast::getPointerBase( arg->result ); - assertf( base, "parameter is reference, arg must be pointer or reference: %s", toString( arg->result ).c_str() ); - ast::PointerType * ptr = new ast::PointerType( ast::deepCopy( base ) ); - arg = ast::mutate_field( arg.get(), - &ast::ApplicationExpr::result, ptr ); - arg = mkDeref( transUnit().global, arg ); - } - } - ++i; - if ( end == i ) break; - } - return mutExpr; -} - -ast::Expr const * CollapseAddressDeref::postvisit( - ast::AddressExpr const * expr ) { - ast::Expr const * arg = expr->arg; - if ( isIntrinsicReference( arg ) ) { - std::string fname = ast::getFunctionName( arg ); - if ( fname == "*?" ) { - ast::Expr const * arg0 = ast::getCallArg( arg, 0 ); - ast::Expr * ret = ast::mutate( arg0 ); - ret->env = expr->env; - return ret; - } - } else if ( auto cast = dynamic_cast( arg ) ) { - // Need to move cast to pointer type out a level since address of - // pointer is not valid C code (can be introduced in prior passes, - // e.g., InstantiateGeneric) - if ( ast::getPointerBase( cast->result ) ) { - auto mutExpr = ast::mutate( expr ); - auto mutCast = strict_dynamic_cast( - ast::mutate( mutExpr->arg.release() ) ); - mutExpr->arg = mutCast->arg; - mutCast->arg = mutExpr; - mutCast->result = new ast::PointerType( mutCast->result ); - return mutCast; - } - } - return expr; -} - -ast::Expr const * CollapseAddressDeref::postvisit( - ast::ApplicationExpr const * expr ) { - if ( isIntrinsicReference( expr ) ) { - std::string fname = ast::getFunctionName( expr ); - if ( fname == "*?" ) { - assert( 1 == expr->args.size() ); - ast::Expr const * arg = ast::getCallArg( expr, 0 ); - // xxx - this isn't right, because it can remove casts that - // should be there... - // while ( auto cast = dynamic_cast< ast::CastExpr const * >( arg ) ) { - // arg = cast->arg; - // } - if ( auto addr = dynamic_cast( arg ) ) { - return ast::mutate_field( addr->arg.get(), - &ast::Expr::env, expr->env.get() ); - } - } - } - return expr; -} - -ast::Expr const * GeneralizedLvalue::postvisit( - ast::AddressExpr const * expr ) { - return applyTransformation( expr, &ast::AddressExpr::arg, - []( ast::Expr const * arg ) { - return new ast::AddressExpr( arg->location, arg ); - } - ); -} - -ast::Expr const * GeneralizedLvalue::postvisit( - ast::MemberExpr const * expr ) { - return applyTransformation( expr, &ast::MemberExpr::aggregate, - [expr]( ast::Expr const * aggr ) { - return new ast::MemberExpr( aggr->location, expr->member, aggr ); - } - ); -} - -template -ast::Expr const * GeneralizedLvalue::applyTransformation( - Node const * expr, ast::ptr Node::*field, Func mkExpr ) { - ast::ptr const & arg = expr->*field; - if ( auto commaArg = arg.as() ) { - ast::Expr const * arg1 = ast::deepCopy( commaArg->arg1 ); - ast::Expr const * arg2 = ast::deepCopy( commaArg->arg2 ); - ast::Expr const * ret = new ast::CommaExpr( - commaArg->location, arg1, mkExpr( arg2 )->accept( *visitor ) ); - return ret; - } else if ( auto condArg = arg.as() ) { - ast::Expr const * arg1 = ast::deepCopy( condArg->arg1 ); - ast::Expr const * arg2 = ast::deepCopy( condArg->arg2 ); - ast::Expr const * arg3 = ast::deepCopy( condArg->arg3 ); - ast::ConditionalExpr * ret = new ast::ConditionalExpr( - condArg->location, arg1, mkExpr( arg2 )->accept( *visitor ), - mkExpr( arg3 )->accept( *visitor ) ); - - // Conditional expr type may not be either of the arguments, - // so unify to get the result. - // TODO: Maybe I could create a wrapper for this. - ast::ptr common = nullptr; - ast::TypeEnvironment newEnv; - ast::AssertionSet needAssertions, haveAssertions; - ast::OpenVarSet openVars; - ResolvExpr::unify( ret->arg2->result, ret->arg3->result, newEnv, - needAssertions, haveAssertions, openVars, common ); - ret->result = common ? common : ast::deepCopy( ret->arg2->result ); - return ret; - } - return expr; -} - -ast::Type const * ReferenceTypeElimination::postvisit( - ast::ReferenceType const * type ) { - return new ast::PointerType( type->base, type->qualifiers ); -} - -} // namespace - -// Stored elsewhere (Lvalue2, initially false): -extern bool referencesEliminated; - -void convertLvalue( ast::TranslationUnit & translationUnit ) { - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - ast::Pass::run( translationUnit ); - // Last because other passes need reference types to work. - ast::Pass::run( translationUnit ); - // From this point forward, nothing should create reference types. - referencesEliminated = true; -} - -ast::Expr const * generalizedLvalue( ast::Expr const * expr ) { - ast::Pass visitor; - return expr->accept( visitor ); -} - -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/Specialize.cpp =================================================================== --- src/GenPoly/Specialize.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) +++ src/GenPoly/Specialize.cpp (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) @@ -0,0 +1,478 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Specialize.cpp -- Generate thunks to specialize polymorphic functions. +// +// Author : Andrew Beach +// Created On : Tue Jun 7 13:37:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Tue Jun 7 13:37:00 2022 +// Update Count : 0 +// + +#include "Specialize.h" + +#include "AST/Copy.hpp" // for deepCopy +#include "AST/Inspect.hpp" // for isIntrinsicCallExpr +#include "AST/Pass.hpp" // for Pass +#include "AST/TypeEnvironment.hpp" // for OpenVarSet, AssertionSet +#include "Common/UniqueName.h" // for UniqueName +#include "GenPoly/GenPoly.h" // for getFunctionType +#include "ResolvExpr/FindOpenVars.h" // for findOpenVars + +namespace GenPoly { + +namespace { + +struct SpecializeCore final : + public ast::WithConstTypeSubstitution, + public ast::WithDeclsToAdd<>, + public ast::WithVisitorRef { + std::string paramPrefix = "_p"; + + ast::ApplicationExpr * handleExplicitParams( + const ast::ApplicationExpr * expr ); + const ast::Expr * createThunkFunction( + const CodeLocation & location, + const ast::FunctionType * funType, + const ast::Expr * actual, + const ast::InferredParams * inferParams ); + const ast::Expr * doSpecialization( + const CodeLocation & location, + const ast::Type * formalType, + const ast::Expr * actual, + const ast::InferredParams * inferParams ); + + const ast::Expr * postvisit( const ast::ApplicationExpr * expr ); + const ast::Expr * postvisit( const ast::CastExpr * expr ); +}; + +const ast::InferredParams * getInferredParams( const ast::Expr * expr ) { + const ast::Expr::InferUnion & inferred = expr->inferred; + if ( inferred.hasParams() ) { + return &inferred.inferParams(); + } else { + return nullptr; + } +} + +// Check if both types have the same structure. The leaf (non-tuple) types +// don't have to match but the tuples must match. +bool isTupleStructureMatching( const ast::Type * t0, const ast::Type * t1 ) { + const ast::TupleType * tt0 = dynamic_cast( t0 ); + const ast::TupleType * tt1 = dynamic_cast( t1 ); + if ( tt0 && tt1 ) { + if ( tt0->size() != tt1->size() ) { + return false; + } + for ( auto types : group_iterate( tt0->types, tt1->types ) ) { + if ( !isTupleStructureMatching( + std::get<0>( types ), std::get<1>( types ) ) ) { + return false; + } + } + return true; + } + return (!tt0 && !tt1); +} + +// The number of elements in a list, if all tuples had been flattened. +size_t flatTypeListSize( const std::vector> & types ) { + size_t sum = 0; + for ( const ast::ptr & type : types ) { + if ( const ast::TupleType * tuple = type.as() ) { + sum += flatTypeListSize( tuple->types ); + } else { + sum += 1; + } + } + return sum; +} + +// Find the total number of components in a parameter list. +size_t functionParameterSize( const ast::FunctionType * type ) { + return flatTypeListSize( type->params ); +} + +bool needsPolySpecialization( + const ast::Type * /*formalType*/, + const ast::Type * actualType, + const ast::TypeSubstitution * subs ) { + if ( !subs ) { + return false; + } + + using namespace ResolvExpr; + ast::OpenVarSet openVars, closedVars; + ast::AssertionSet need, have; // unused + ast::TypeEnvironment env; // unused + // findOpenVars( formalType, openVars, closedVars, need, have, FirstClosed ); + findOpenVars( actualType, openVars, closedVars, need, have, env, FirstOpen ); + for ( const ast::OpenVarSet::value_type & openVar : openVars ) { + const ast::Type * boundType = subs->lookup( openVar.first ); + // If the variable is not bound, move onto the next variable. + if ( !boundType ) continue; + + // Is the variable cound to another type variable? + if ( auto inst = dynamic_cast( boundType ) ) { + if ( closedVars.find( *inst ) == closedVars.end() ) { + return true; + } else { + assertf(false, "closed: %s", inst->name.c_str()); + } + // Otherwise, the variable is bound to a concrete type. + } else { + return true; + } + } + // None of the type variables are bound. + return false; +} + +bool needsTupleSpecialization( + const ast::Type * formalType, const ast::Type * actualType ) { + // Needs tuple specialization if the structure of the formal type and + // actual type do not match. + + // This is the case if the formal type has ttype polymorphism, or if the structure of tuple types + // between the function do not match exactly. + if ( const ast::FunctionType * ftype = getFunctionType( formalType ) ) { + // A pack in the parameter or return type requires specialization. + if ( ftype->isTtype() ) { + return true; + } + // Conversion of 0 to a function type does not require specialization. + if ( dynamic_cast( actualType ) ) { + return false; + } + const ast::FunctionType * atype = + getFunctionType( actualType->stripReferences() ); + assertf( atype, + "formal type is a function type, but actual type is not: %s", + toString( actualType ).c_str() ); + // Can't tuple specialize if parameter sizes deeply-differ. + if ( functionParameterSize( ftype ) != functionParameterSize( atype ) ) { + return false; + } + // If tuple parameter size matches but actual parameter sizes differ + // then there needs to be specialization. + if ( ftype->params.size() != atype->params.size() ) { + return true; + } + // Total parameter size can be the same, while individual parameters + // can have different structure. + for ( auto pairs : group_iterate( ftype->params, atype->params ) ) { + if ( !isTupleStructureMatching( + std::get<0>( pairs ), std::get<1>( pairs ) ) ) { + return true; + } + } + } + return false; +} + +bool needsSpecialization( + const ast::Type * formalType, const ast::Type * actualType, + const ast::TypeSubstitution * subs ) { + return needsPolySpecialization( formalType, actualType, subs ) + || needsTupleSpecialization( formalType, actualType ); +} + +ast::ApplicationExpr * SpecializeCore::handleExplicitParams( + const ast::ApplicationExpr * expr ) { + assert( expr->func->result ); + const ast::FunctionType * func = getFunctionType( expr->func->result ); + assert( func ); + + ast::ApplicationExpr * mut = ast::mutate( expr ); + + std::vector>::const_iterator formal; + std::vector>::iterator actual; + for ( formal = func->params.begin(), actual = mut->args.begin() ; + formal != func->params.end() && actual != mut->args.end() ; + ++formal, ++actual ) { + *actual = doSpecialization( (*actual)->location, + *formal, *actual, getInferredParams( expr ) ); + } + return mut; +} + +// Explode assuming simple cases: either type is pure tuple (but not tuple +// expr) or type is non-tuple. +template +void explodeSimple( const CodeLocation & location, + const ast::Expr * expr, OutputIterator out ) { + // Recurse on tuple types using index expressions on each component. + if ( auto tuple = expr->result.as() ) { + ast::ptr cleanup = expr; + for ( unsigned int i = 0 ; i < tuple->size() ; ++i ) { + explodeSimple( location, + new ast::TupleIndexExpr( location, expr, i ), out ); + } + // For a non-tuple type, output a clone of the expression. + } else { + *out++ = expr; + } +} + +// Restructures arguments to match the structure of the formal parameters +// of the actual function. Returns the next structured argument. +template +const ast::Expr * structureArg( + const CodeLocation& location, const ast::ptr & type, + Iterator & begin, const Iterator & end ) { + if ( auto tuple = type.as() ) { + std::vector> exprs; + for ( const ast::ptr & t : *tuple ) { + exprs.push_back( structureArg( location, t, begin, end ) ); + } + return new ast::TupleExpr( location, std::move( exprs ) ); + } else { + assertf( begin != end, "reached the end of the arguments while structuring" ); + return *begin++; + } +} + +struct TypeInstFixer final : public ast::WithShortCircuiting { + std::map> typeMap; + + void previsit(const ast::TypeDecl *) { visit_children = false; } + const ast::TypeInstType * postvisit(const ast::TypeInstType * typeInst) { + if (typeMap.count(typeInst->base)) { + ast::TypeInstType * newInst = mutate(typeInst); + auto const & pair = typeMap[typeInst->base]; + newInst->expr_id = pair.first; + newInst->formal_usage = pair.second; + return newInst; + } + return typeInst; + } +}; + +const ast::Expr * SpecializeCore::createThunkFunction( + const CodeLocation & location, + const ast::FunctionType * funType, + const ast::Expr * actual, + const ast::InferredParams * inferParams ) { + // One set of unique names per program. + static UniqueName thunkNamer("_thunk"); + + const ast::FunctionType * newType = ast::deepCopy( funType ); + if ( typeSubs ) { + // Must replace only occurrences of type variables + // that occure free in the thunk's type. + auto result = typeSubs->applyFree( newType ); + newType = result.node.release(); + } + + using DWTVector = std::vector>; + using DeclVector = std::vector>; + + UniqueName paramNamer( paramPrefix ); + + // Create new thunk with same signature as formal type. + ast::Pass fixer; + for (const auto & kv : newType->forall) { + if (fixer.core.typeMap.count(kv->base)) { + std::cerr << location << ' ' << kv->base->name + << ' ' << kv->expr_id << '_' << kv->formal_usage + << ',' << fixer.core.typeMap[kv->base].first + << '_' << fixer.core.typeMap[kv->base].second << std::endl; + assertf(false, "multiple formals in specialize"); + } + else { + fixer.core.typeMap[kv->base] = std::make_pair(kv->expr_id, kv->formal_usage); + } + } + + ast::CompoundStmt * thunkBody = new ast::CompoundStmt( location ); + ast::FunctionDecl * thunkFunc = new ast::FunctionDecl( + location, + thunkNamer.newName(), + map_range( newType->forall, []( const ast::TypeInstType * inst ) { + return ast::deepCopy( inst->base ); + } ), + map_range( newType->assertions, []( const ast::VariableExpr * expr ) { + return ast::deepCopy( expr->var ); + } ), + map_range( newType->params, [&location, ¶mNamer]( const ast::Type * type ) { + return new ast::ObjectDecl( location, paramNamer.newName(), ast::deepCopy( type ) ); + } ), + map_range( newType->returns, [&location, ¶mNamer]( const ast::Type * type ) { + return new ast::ObjectDecl( location, paramNamer.newName(), ast::deepCopy( type ) ); + } ), + thunkBody, + ast::Storage::Classes(), + ast::Linkage::C + ); + + thunkFunc->fixUniqueId(); + + // Thunks may be generated and not used, avoid them. + thunkFunc->attributes.push_back( new ast::Attribute( "unused" ) ); + + // Global thunks must be static to avoid collitions. + // Nested thunks must not be unique and hence, not static. + thunkFunc->storage.is_static = !isInFunction(); + + // Weave thunk parameters into call to actual function, + // naming thunk parameters as we go. + ast::ApplicationExpr * app = new ast::ApplicationExpr( location, actual ); + + const ast::FunctionType * actualType = ast::deepCopy( getFunctionType( actual->result ) ); + if ( typeSubs ) { + // Need to apply the environment to the actual function's type, + // since it may itself be polymorphic. + auto result = typeSubs->apply( actualType ); + actualType = result.node.release(); + } + + ast::ptr actualTypeManager = actualType; + + std::vector> args; + for ( ast::ptr & param : thunkFunc->params ) { + // Name each thunk parameter and explode it. + // These are then threaded back into the actual function call. + ast::DeclWithType * mutParam = ast::mutate( param.get() ); + explodeSimple( location, new ast::VariableExpr( location, mutParam ), + std::back_inserter( args ) ); + } + + // Walk parameters to the actual function alongside the exploded thunk + // parameters and restructure the arguments to match the actual parameters. + std::vector>::iterator + argBegin = args.begin(), argEnd = args.end(); + for ( const auto & actualArg : actualType->params ) { + app->args.push_back( + structureArg( location, actualArg.get(), argBegin, argEnd ) ); + } + assertf( argBegin == argEnd, "Did not structure all arguments." ); + + app->accept(fixer); // this should modify in place + + app->env = ast::TypeSubstitution::newFromExpr( app, typeSubs ); + if ( inferParams ) { + app->inferred.inferParams() = *inferParams; + } + + // Handle any specializations that may still be present. + { + std::string oldParamPrefix = paramPrefix; + paramPrefix += "p"; + std::list> oldDecls; + oldDecls.splice( oldDecls.end(), declsToAddBefore ); + + app->accept( *visitor ); + // Write recursive specializations into the thunk body. + for ( const ast::ptr & decl : declsToAddBefore ) { + thunkBody->push_back( new ast::DeclStmt( decl->location, decl ) ); + } + + declsToAddBefore = std::move( oldDecls ); + paramPrefix = std::move( oldParamPrefix ); + } + + // Add return (or valueless expression) to the thunk. + ast::Stmt * appStmt; + if ( funType->returns.empty() ) { + appStmt = new ast::ExprStmt( app->location, app ); + } else { + appStmt = new ast::ReturnStmt( app->location, app ); + } + thunkBody->push_back( appStmt ); + + // Add the thunk definition: + declsToAddBefore.push_back( thunkFunc ); + + // Return address of thunk function as replacement expression. + return new ast::AddressExpr( location, + new ast::VariableExpr( location, thunkFunc ) ); +} + +const ast::Expr * SpecializeCore::doSpecialization( + const CodeLocation & location, + const ast::Type * formalType, + const ast::Expr * actual, + const ast::InferredParams * inferParams ) { + assertf( actual->result, "attempting to specialize an untyped expression" ); + if ( needsSpecialization( formalType, actual->result, typeSubs ) ) { + if ( const ast::FunctionType * type = getFunctionType( formalType ) ) { + if ( const ast::ApplicationExpr * expr = + dynamic_cast( actual ) ) { + return createThunkFunction( location, type, expr->func, inferParams ); + } else if ( auto expr = + dynamic_cast( actual ) ) { + return createThunkFunction( location, type, expr, inferParams ); + } else { + // (I don't even know what that comment means.) + // This likely won't work, as anything that could build an ApplicationExpr probably hit one of the previous two branches + return createThunkFunction( location, type, actual, inferParams ); + } + } else { + return actual; + } + } else { + return actual; + } +} + +const ast::Expr * SpecializeCore::postvisit( + const ast::ApplicationExpr * expr ) { + if ( ast::isIntrinsicCallExpr( expr ) ) { + return expr; + } + + // Create thunks for the inferred parameters. + // This is not needed for intrinsic calls, because they aren't + // actually passed to the function. It needs to handle explicit params + // before inferred params so that explicit params do not recieve a + // changed set of inferParams (and change them again). + // Alternatively, if order starts to matter then copy expr's inferParams + // and pass them to handleExplicitParams. + ast::ApplicationExpr * mut = handleExplicitParams( expr ); + if ( !mut->inferred.hasParams() ) { + return mut; + } + ast::InferredParams & inferParams = mut->inferred.inferParams(); + for ( ast::InferredParams::value_type & inferParam : inferParams ) { + inferParam.second.expr = doSpecialization( + inferParam.second.expr->location, + inferParam.second.formalType, + inferParam.second.expr, + getInferredParams( inferParam.second.expr ) + ); + } + return mut; +} + +const ast::Expr * SpecializeCore::postvisit( const ast::CastExpr * expr ) { + if ( expr->result->isVoid() ) { + // No specialization if there is no return value. + return expr; + } + const ast::Expr * specialized = doSpecialization( + expr->location, expr->result, expr->arg, getInferredParams( expr ) ); + if ( specialized != expr->arg ) { + // Assume that the specialization incorporates the cast. + return specialized; + } else { + return expr; + } +} + +} // namespace + +void convertSpecializations( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); +} + +} // namespace GenPoly + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/SpecializeNew.cpp =================================================================== --- src/GenPoly/SpecializeNew.cpp (revision f48dfcd1acf87e4d711e108cd7119bb80ee701ee) +++ (revision ) @@ -1,478 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// SpecializeNew.cpp -- Generate thunks to specialize polymorphic functions. -// -// Author : Andrew Beach -// Created On : Tue Jun 7 13:37:00 2022 -// Last Modified By : Andrew Beach -// Last Modified On : Tue Jun 7 13:37:00 2022 -// Update Count : 0 -// - -#include "Specialize.h" - -#include "AST/Copy.hpp" // for deepCopy -#include "AST/Inspect.hpp" // for isIntrinsicCallExpr -#include "AST/Pass.hpp" // for Pass -#include "AST/TypeEnvironment.hpp" // for OpenVarSet, AssertionSet -#include "Common/UniqueName.h" // for UniqueName -#include "GenPoly/GenPoly.h" // for getFunctionType -#include "ResolvExpr/FindOpenVars.h" // for findOpenVars - -namespace GenPoly { - -namespace { - -struct SpecializeCore final : - public ast::WithConstTypeSubstitution, - public ast::WithDeclsToAdd<>, - public ast::WithVisitorRef { - std::string paramPrefix = "_p"; - - ast::ApplicationExpr * handleExplicitParams( - const ast::ApplicationExpr * expr ); - const ast::Expr * createThunkFunction( - const CodeLocation & location, - const ast::FunctionType * funType, - const ast::Expr * actual, - const ast::InferredParams * inferParams ); - const ast::Expr * doSpecialization( - const CodeLocation & location, - const ast::Type * formalType, - const ast::Expr * actual, - const ast::InferredParams * inferParams ); - - const ast::Expr * postvisit( const ast::ApplicationExpr * expr ); - const ast::Expr * postvisit( const ast::CastExpr * expr ); -}; - -const ast::InferredParams * getInferredParams( const ast::Expr * expr ) { - const ast::Expr::InferUnion & inferred = expr->inferred; - if ( inferred.hasParams() ) { - return &inferred.inferParams(); - } else { - return nullptr; - } -} - -// Check if both types have the same structure. The leaf (non-tuple) types -// don't have to match but the tuples must match. -bool isTupleStructureMatching( const ast::Type * t0, const ast::Type * t1 ) { - const ast::TupleType * tt0 = dynamic_cast( t0 ); - const ast::TupleType * tt1 = dynamic_cast( t1 ); - if ( tt0 && tt1 ) { - if ( tt0->size() != tt1->size() ) { - return false; - } - for ( auto types : group_iterate( tt0->types, tt1->types ) ) { - if ( !isTupleStructureMatching( - std::get<0>( types ), std::get<1>( types ) ) ) { - return false; - } - } - return true; - } - return (!tt0 && !tt1); -} - -// The number of elements in a list, if all tuples had been flattened. -size_t flatTypeListSize( const std::vector> & types ) { - size_t sum = 0; - for ( const ast::ptr & type : types ) { - if ( const ast::TupleType * tuple = type.as() ) { - sum += flatTypeListSize( tuple->types ); - } else { - sum += 1; - } - } - return sum; -} - -// Find the total number of components in a parameter list. -size_t functionParameterSize( const ast::FunctionType * type ) { - return flatTypeListSize( type->params ); -} - -bool needsPolySpecialization( - const ast::Type * /*formalType*/, - const ast::Type * actualType, - const ast::TypeSubstitution * subs ) { - if ( !subs ) { - return false; - } - - using namespace ResolvExpr; - ast::OpenVarSet openVars, closedVars; - ast::AssertionSet need, have; // unused - ast::TypeEnvironment env; // unused - // findOpenVars( formalType, openVars, closedVars, need, have, FirstClosed ); - findOpenVars( actualType, openVars, closedVars, need, have, env, FirstOpen ); - for ( const ast::OpenVarSet::value_type & openVar : openVars ) { - const ast::Type * boundType = subs->lookup( openVar.first ); - // If the variable is not bound, move onto the next variable. - if ( !boundType ) continue; - - // Is the variable cound to another type variable? - if ( auto inst = dynamic_cast( boundType ) ) { - if ( closedVars.find( *inst ) == closedVars.end() ) { - return true; - } else { - assertf(false, "closed: %s", inst->name.c_str()); - } - // Otherwise, the variable is bound to a concrete type. - } else { - return true; - } - } - // None of the type variables are bound. - return false; -} - -bool needsTupleSpecialization( - const ast::Type * formalType, const ast::Type * actualType ) { - // Needs tuple specialization if the structure of the formal type and - // actual type do not match. - - // This is the case if the formal type has ttype polymorphism, or if the structure of tuple types - // between the function do not match exactly. - if ( const ast::FunctionType * ftype = getFunctionType( formalType ) ) { - // A pack in the parameter or return type requires specialization. - if ( ftype->isTtype() ) { - return true; - } - // Conversion of 0 to a function type does not require specialization. - if ( dynamic_cast( actualType ) ) { - return false; - } - const ast::FunctionType * atype = - getFunctionType( actualType->stripReferences() ); - assertf( atype, - "formal type is a function type, but actual type is not: %s", - toString( actualType ).c_str() ); - // Can't tuple specialize if parameter sizes deeply-differ. - if ( functionParameterSize( ftype ) != functionParameterSize( atype ) ) { - return false; - } - // If tuple parameter size matches but actual parameter sizes differ - // then there needs to be specialization. - if ( ftype->params.size() != atype->params.size() ) { - return true; - } - // Total parameter size can be the same, while individual parameters - // can have different structure. - for ( auto pairs : group_iterate( ftype->params, atype->params ) ) { - if ( !isTupleStructureMatching( - std::get<0>( pairs ), std::get<1>( pairs ) ) ) { - return true; - } - } - } - return false; -} - -bool needsSpecialization( - const ast::Type * formalType, const ast::Type * actualType, - const ast::TypeSubstitution * subs ) { - return needsPolySpecialization( formalType, actualType, subs ) - || needsTupleSpecialization( formalType, actualType ); -} - -ast::ApplicationExpr * SpecializeCore::handleExplicitParams( - const ast::ApplicationExpr * expr ) { - assert( expr->func->result ); - const ast::FunctionType * func = getFunctionType( expr->func->result ); - assert( func ); - - ast::ApplicationExpr * mut = ast::mutate( expr ); - - std::vector>::const_iterator formal; - std::vector>::iterator actual; - for ( formal = func->params.begin(), actual = mut->args.begin() ; - formal != func->params.end() && actual != mut->args.end() ; - ++formal, ++actual ) { - *actual = doSpecialization( (*actual)->location, - *formal, *actual, getInferredParams( expr ) ); - } - return mut; -} - -// Explode assuming simple cases: either type is pure tuple (but not tuple -// expr) or type is non-tuple. -template -void explodeSimple( const CodeLocation & location, - const ast::Expr * expr, OutputIterator out ) { - // Recurse on tuple types using index expressions on each component. - if ( auto tuple = expr->result.as() ) { - ast::ptr cleanup = expr; - for ( unsigned int i = 0 ; i < tuple->size() ; ++i ) { - explodeSimple( location, - new ast::TupleIndexExpr( location, expr, i ), out ); - } - // For a non-tuple type, output a clone of the expression. - } else { - *out++ = expr; - } -} - -// Restructures arguments to match the structure of the formal parameters -// of the actual function. Returns the next structured argument. -template -const ast::Expr * structureArg( - const CodeLocation& location, const ast::ptr & type, - Iterator & begin, const Iterator & end ) { - if ( auto tuple = type.as() ) { - std::vector> exprs; - for ( const ast::ptr & t : *tuple ) { - exprs.push_back( structureArg( location, t, begin, end ) ); - } - return new ast::TupleExpr( location, std::move( exprs ) ); - } else { - assertf( begin != end, "reached the end of the arguments while structuring" ); - return *begin++; - } -} - -struct TypeInstFixer final : public ast::WithShortCircuiting { - std::map> typeMap; - - void previsit(const ast::TypeDecl *) { visit_children = false; } - const ast::TypeInstType * postvisit(const ast::TypeInstType * typeInst) { - if (typeMap.count(typeInst->base)) { - ast::TypeInstType * newInst = mutate(typeInst); - auto const & pair = typeMap[typeInst->base]; - newInst->expr_id = pair.first; - newInst->formal_usage = pair.second; - return newInst; - } - return typeInst; - } -}; - -const ast::Expr * SpecializeCore::createThunkFunction( - const CodeLocation & location, - const ast::FunctionType * funType, - const ast::Expr * actual, - const ast::InferredParams * inferParams ) { - // One set of unique names per program. - static UniqueName thunkNamer("_thunk"); - - const ast::FunctionType * newType = ast::deepCopy( funType ); - if ( typeSubs ) { - // Must replace only occurrences of type variables - // that occure free in the thunk's type. - auto result = typeSubs->applyFree( newType ); - newType = result.node.release(); - } - - using DWTVector = std::vector>; - using DeclVector = std::vector>; - - UniqueName paramNamer( paramPrefix ); - - // Create new thunk with same signature as formal type. - ast::Pass fixer; - for (const auto & kv : newType->forall) { - if (fixer.core.typeMap.count(kv->base)) { - std::cerr << location << ' ' << kv->base->name - << ' ' << kv->expr_id << '_' << kv->formal_usage - << ',' << fixer.core.typeMap[kv->base].first - << '_' << fixer.core.typeMap[kv->base].second << std::endl; - assertf(false, "multiple formals in specialize"); - } - else { - fixer.core.typeMap[kv->base] = std::make_pair(kv->expr_id, kv->formal_usage); - } - } - - ast::CompoundStmt * thunkBody = new ast::CompoundStmt( location ); - ast::FunctionDecl * thunkFunc = new ast::FunctionDecl( - location, - thunkNamer.newName(), - map_range( newType->forall, []( const ast::TypeInstType * inst ) { - return ast::deepCopy( inst->base ); - } ), - map_range( newType->assertions, []( const ast::VariableExpr * expr ) { - return ast::deepCopy( expr->var ); - } ), - map_range( newType->params, [&location, ¶mNamer]( const ast::Type * type ) { - return new ast::ObjectDecl( location, paramNamer.newName(), ast::deepCopy( type ) ); - } ), - map_range( newType->returns, [&location, ¶mNamer]( const ast::Type * type ) { - return new ast::ObjectDecl( location, paramNamer.newName(), ast::deepCopy( type ) ); - } ), - thunkBody, - ast::Storage::Classes(), - ast::Linkage::C - ); - - thunkFunc->fixUniqueId(); - - // Thunks may be generated and not used, avoid them. - thunkFunc->attributes.push_back( new ast::Attribute( "unused" ) ); - - // Global thunks must be static to avoid collitions. - // Nested thunks must not be unique and hence, not static. - thunkFunc->storage.is_static = !isInFunction(); - - // Weave thunk parameters into call to actual function, - // naming thunk parameters as we go. - ast::ApplicationExpr * app = new ast::ApplicationExpr( location, actual ); - - const ast::FunctionType * actualType = ast::deepCopy( getFunctionType( actual->result ) ); - if ( typeSubs ) { - // Need to apply the environment to the actual function's type, - // since it may itself be polymorphic. - auto result = typeSubs->apply( actualType ); - actualType = result.node.release(); - } - - ast::ptr actualTypeManager = actualType; - - std::vector> args; - for ( ast::ptr & param : thunkFunc->params ) { - // Name each thunk parameter and explode it. - // These are then threaded back into the actual function call. - ast::DeclWithType * mutParam = ast::mutate( param.get() ); - explodeSimple( location, new ast::VariableExpr( location, mutParam ), - std::back_inserter( args ) ); - } - - // Walk parameters to the actual function alongside the exploded thunk - // parameters and restructure the arguments to match the actual parameters. - std::vector>::iterator - argBegin = args.begin(), argEnd = args.end(); - for ( const auto & actualArg : actualType->params ) { - app->args.push_back( - structureArg( location, actualArg.get(), argBegin, argEnd ) ); - } - assertf( argBegin == argEnd, "Did not structure all arguments." ); - - app->accept(fixer); // this should modify in place - - app->env = ast::TypeSubstitution::newFromExpr( app, typeSubs ); - if ( inferParams ) { - app->inferred.inferParams() = *inferParams; - } - - // Handle any specializations that may still be present. - { - std::string oldParamPrefix = paramPrefix; - paramPrefix += "p"; - std::list> oldDecls; - oldDecls.splice( oldDecls.end(), declsToAddBefore ); - - app->accept( *visitor ); - // Write recursive specializations into the thunk body. - for ( const ast::ptr & decl : declsToAddBefore ) { - thunkBody->push_back( new ast::DeclStmt( decl->location, decl ) ); - } - - declsToAddBefore = std::move( oldDecls ); - paramPrefix = std::move( oldParamPrefix ); - } - - // Add return (or valueless expression) to the thunk. - ast::Stmt * appStmt; - if ( funType->returns.empty() ) { - appStmt = new ast::ExprStmt( app->location, app ); - } else { - appStmt = new ast::ReturnStmt( app->location, app ); - } - thunkBody->push_back( appStmt ); - - // Add the thunk definition: - declsToAddBefore.push_back( thunkFunc ); - - // Return address of thunk function as replacement expression. - return new ast::AddressExpr( location, - new ast::VariableExpr( location, thunkFunc ) ); -} - -const ast::Expr * SpecializeCore::doSpecialization( - const CodeLocation & location, - const ast::Type * formalType, - const ast::Expr * actual, - const ast::InferredParams * inferParams ) { - assertf( actual->result, "attempting to specialize an untyped expression" ); - if ( needsSpecialization( formalType, actual->result, typeSubs ) ) { - if ( const ast::FunctionType * type = getFunctionType( formalType ) ) { - if ( const ast::ApplicationExpr * expr = - dynamic_cast( actual ) ) { - return createThunkFunction( location, type, expr->func, inferParams ); - } else if ( auto expr = - dynamic_cast( actual ) ) { - return createThunkFunction( location, type, expr, inferParams ); - } else { - // (I don't even know what that comment means.) - // This likely won't work, as anything that could build an ApplicationExpr probably hit one of the previous two branches - return createThunkFunction( location, type, actual, inferParams ); - } - } else { - return actual; - } - } else { - return actual; - } -} - -const ast::Expr * SpecializeCore::postvisit( - const ast::ApplicationExpr * expr ) { - if ( ast::isIntrinsicCallExpr( expr ) ) { - return expr; - } - - // Create thunks for the inferred parameters. - // This is not needed for intrinsic calls, because they aren't - // actually passed to the function. It needs to handle explicit params - // before inferred params so that explicit params do not recieve a - // changed set of inferParams (and change them again). - // Alternatively, if order starts to matter then copy expr's inferParams - // and pass them to handleExplicitParams. - ast::ApplicationExpr * mut = handleExplicitParams( expr ); - if ( !mut->inferred.hasParams() ) { - return mut; - } - ast::InferredParams & inferParams = mut->inferred.inferParams(); - for ( ast::InferredParams::value_type & inferParam : inferParams ) { - inferParam.second.expr = doSpecialization( - inferParam.second.expr->location, - inferParam.second.formalType, - inferParam.second.expr, - getInferredParams( inferParam.second.expr ) - ); - } - return mut; -} - -const ast::Expr * SpecializeCore::postvisit( const ast::CastExpr * expr ) { - if ( expr->result->isVoid() ) { - // No specialization if there is no return value. - return expr; - } - const ast::Expr * specialized = doSpecialization( - expr->location, expr->result, expr->arg, getInferredParams( expr ) ); - if ( specialized != expr->arg ) { - // Assume that the specialization incorporates the cast. - return specialized; - } else { - return expr; - } -} - -} // namespace - -void convertSpecializations( ast::TranslationUnit & translationUnit ) { - ast::Pass::run( translationUnit ); -} - -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/module.mk =================================================================== --- src/GenPoly/module.mk (revision f48dfcd1acf87e4d711e108cd7119bb80ee701ee) +++ src/GenPoly/module.mk (revision 83fd57dbde2b629bbcc22cdd6694eccab69dd48e) @@ -22,16 +22,16 @@ SRC += $(SRC_GENPOLY) \ - GenPoly/BoxNew.cpp \ + GenPoly/Box.cpp \ GenPoly/Box.h \ GenPoly/ErasableScopedMap.h \ GenPoly/FindFunction.cc \ GenPoly/FindFunction.h \ - GenPoly/InstantiateGenericNew.cpp \ + GenPoly/InstantiateGeneric.cpp \ GenPoly/InstantiateGeneric.h \ - GenPoly/LvalueNew.cpp \ + GenPoly/Lvalue.cpp \ GenPoly/ScopedSet.h \ GenPoly/ScrubTyVars.cc \ GenPoly/ScrubTyVars.h \ - GenPoly/SpecializeNew.cpp \ + GenPoly/Specialize.cpp \ GenPoly/Specialize.h