Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ (revision ) @@ -1,1910 +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. -// -// Box.cc -- -// -// Author : Richard C. Bilson -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Dec 19 16:36:00 2022 -// Update Count : 348 -// - -#include "Box.h" - -#include // for mismatch -#include // for assert, strict_dynamic_cast -#include // for operator<<, stringstream -#include // for list, list<>::iterator, _Lis... -#include // for _Rb_tree_const_iterator, map -#include // for auto_ptr -#include // for set -#include // for string, allocator, basic_string -#include // for pair - -#include "CodeGen/OperatorTable.h" -#include "Common/PassVisitor.h" // for PassVisitor -#include "Common/ScopedMap.h" // for ScopedMap, ScopedMap<>::iter... -#include "Common/SemanticError.h" // for SemanticError -#include "Common/UniqueName.h" // for UniqueName -#include "Common/ToString.hpp" // for toCString -#include "FindFunction.h" // for findFunction, findAndReplace... -#include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_i... -#include "GenPoly/GenPoly.h" // for TyVarMap, isPolyType, mangle... -#include "InitTweak/InitTweak.h" // for getFunctionName, isAssignment -#include "Lvalue.h" // for generalizedLvalue -#include "ResolvExpr/Unify.h" // for typesCompatible -#include "ScopedSet.h" // for ScopedSet, ScopedSet<>::iter... -#include "ScrubTyVars.h" // for ScrubTyVars -#include "SymTab/Indexer.h" // for Indexer -#include "SymTab/Mangler.h" // for Mangler -#include "SynTree/LinkageSpec.h" // for C, Spec, Cforall, Intrinsic -#include "SynTree/Attribute.h" // for Attribute -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Declaration.h" // for DeclarationWithType, ObjectDecl -#include "SynTree/Expression.h" // for ApplicationExpr, UntypedExpr -#include "SynTree/Initializer.h" // for SingleInit, Initializer, Lis... -#include "SynTree/Label.h" // for Label -#include "SynTree/Mutator.h" // for maybeMutate, Mutator, mutateAll -#include "SynTree/Statement.h" // for ExprStmt, DeclStmt, ReturnStmt -#include "SynTree/SynTree.h" // for UniqueId -#include "SynTree/Type.h" // for Type, FunctionType, PointerType -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution, operator<< - -namespace GenPoly { - namespace { - FunctionType *makeAdapterType( FunctionType const *adaptee, const TyVarMap &tyVars ); - - class BoxPass { - protected: - BoxPass() : scopeTyVars( TypeDecl::Data{} ) {} - TyVarMap scopeTyVars; - }; - - /// Adds layout-generation functions to polymorphic types. - class LayoutFunctionBuilder final : public WithDeclsToAdd, public WithVisitorRef, public WithShortCircuiting { - public: - void previsit( StructDecl *structDecl ); - void previsit( UnionDecl *unionDecl ); - }; - - /// Updates the call sites of polymorphic functions. - /// Replaces polymorphic return types with out-parameters, - /// replaces calls to polymorphic functions with adapter calls, - /// and adds appropriate type variables to the function call. - class CallAdapter final : public BoxPass, public WithConstTypeSubstitution, public WithStmtsToAdd, public WithGuards, public WithVisitorRef, public WithShortCircuiting { - public: - CallAdapter(); - - void premutate( Declaration * declaration ); - void premutate( FunctionDecl * functionDecl ); - void premutate( TypeDecl * typeDecl ); - void premutate( CommaExpr * commaExpr ); - Expression * postmutate( ApplicationExpr * appExpr ); - Expression * postmutate( UntypedExpr *expr ); - void premutate( AddressExpr * addrExpr ); - Expression * postmutate( AddressExpr * addrExpr ); - void premutate( ReturnStmt * returnStmt ); - void premutate( PointerType * pointerType ); - void premutate( FunctionType * functionType ); - - void beginScope(); - void endScope(); - private: - /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application - /// Will insert 0, 2 or 3 more arguments. - std::list< Expression *>::iterator passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ); - /// passes extra type parameters into a polymorphic function application - /// Returns an iterator to the first argument after the added - /// arguments, which are added at the beginning. - std::list< Expression *>::iterator passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, const TyVarMap &exprTyVars ); - /// wraps a function application with a new temporary for the out-parameter return value - /// The new out-parameter is the new first parameter. - Expression *addRetParam( ApplicationExpr *appExpr, Type *retType ); - /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value - Expression *addDynRetParam( ApplicationExpr *appExpr, Type *polyType ); - /// Converts a function call into a call of the adapter with the - /// original function as the first argument (all other arguments - /// are pushed back). May adjust return value. - Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function ); - /// Modifies the `arg`, replacing it with a boxed expression - /// that matches `formal` under the current TyVarMap. - void boxParam( Expression *&arg, Type *formal, const TyVarMap &exprTyVars ); - /// Box an argument of `appExpr` for each parameter in `function` - /// starting at `arg`. - /// `exprTyVars` is the function's type variables. - void boxParams( ApplicationExpr *appExpr, std::list< Expression *>::iterator arg, FunctionType *function, const TyVarMap &exprTyVars ); - /// Boxes each assertion and inserts them into `appExpr` at - /// `arg`. `exprTyVars` is the function's type variables. - void addInferredParams( ApplicationExpr *appExpr, std::list< Expression *>::iterator arg, FunctionType *functionType, const TyVarMap &tyVars ); - /// Stores assignment operators from assertion list in local map of assignment operations - void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars ); - /// Creates an adapter definition from `adaptee` to `realType`, using - /// `mangleName` as the base name for the adapter. `tyVars` is the map of - /// type variables for the function type of the adapted expression. - FunctionDecl *makeAdapter( FunctionType const *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ); - /// Replaces intrinsic operator functions with their arithmetic desugaring - Expression *handleIntrinsics( ApplicationExpr *appExpr ); - /// Inserts a new temporary variable into the current scope with an auto-generated name - ObjectDecl *makeTemporary( Type *type ); - - ScopedMap< std::string, DeclarationWithType* > adapters; ///< Set of adapter functions in the current scope - - std::map< ApplicationExpr *, Expression * > retVals; - - DeclarationWithType *retval; - UniqueName tempNamer; - }; - - /// Updates declarations (and types) that require adapters. - /// * Moves polymorphic returns in function types to pointer-type parameters - /// * adds type size and assertion parameters to parameter lists - struct DeclAdapter final : public BoxPass, public WithGuards { - void handleAggDecl(); - - DeclarationWithType * postmutate( FunctionDecl *functionDecl ); - void premutate( StructDecl *structDecl ); - void premutate( UnionDecl *unionDecl ); - void premutate( TraitDecl *unionDecl ); - void premutate( TypeDecl *typeDecl ); - void premutate( PointerType *pointerType ); - void premutate( FunctionType *funcType ); - - private: - void addAdapters( FunctionType *functionType ); - - std::map< UniqueId, std::string > adapterName; - }; - - /// * Replaces member and size/align/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 - class PolyGenericCalculator final : public BoxPass, public WithGuards, public WithVisitorRef, public WithStmtsToAdd, public WithDeclsToAdd, public WithConstTypeSubstitution { - public: - PolyGenericCalculator(); - - void premutate( ObjectDecl *objectDecl ); - void premutate( FunctionDecl *functionDecl ); - void premutate( TypedefDecl *objectDecl ); - void premutate( TypeDecl *objectDecl ); - Declaration * postmutate( TypeDecl *TraitDecl ); - void premutate( PointerType *pointerType ); - void premutate( FunctionType *funcType ); - void premutate( DeclStmt *declStmt ); - Expression *postmutate( MemberExpr *memberExpr ); - void premutate( AddressExpr *addrExpr ); - Expression *postmutate( AddressExpr *addrExpr ); - Expression *postmutate( SizeofExpr *sizeofExpr ); - Expression *postmutate( AlignofExpr *alignofExpr ); - Expression *postmutate( OffsetofExpr *offsetofExpr ); - Expression *postmutate( OffsetPackExpr *offsetPackExpr ); - void premutate( StructDecl * ); - void premutate( UnionDecl * ); - - void beginScope(); - void endScope(); - - private: - /// Makes a new variable in the current scope with the given name, type & optional initializer - ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 ); - /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns - bool findGeneric( Type const *ty ); - /// adds type parameters to the layout call; will generate the appropriate parameters if needed - void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ); - /// change the type of generic aggregate members to char[] - void mutateMembers( AggregateDecl * aggrDecl ); - /// returns the calculated sizeof expression for ty, or nullptr for use C sizeof() - Expression* genSizeof( Type* ty ); - - /// Enters a new scope for type-variables, adding the type variables from ty - void beginTypeScope( Type *ty ); - /// Enters a new scope for knowLayouts and knownOffsets and queues exit calls - void beginGenericScope(); - - ScopedSet< std::string > knownLayouts; ///< Set of generic type layouts known in the current scope, indexed by sizeofName - ScopedSet< std::string > knownOffsets; ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName - UniqueName bufNamer; ///< Namer for VLA buffers - Expression * addrMember = nullptr; ///< AddressExpr argument is MemberExpr? - bool expect_func_type = false; ///< used to avoid recursing too deep in type decls - }; - - /// Erases unneeded/unwanted polymorphic information. - /// Replaces initialization of polymorphic values with alloca, - /// declaration of dtype/ftype with appropriate void expression, - /// sizeof expressions of polymorphic types with the proper variable, - /// and strips fields from generic struct declarations. - struct Eraser final { - void premutate( ObjectDecl * objectDecl ); - void premutate( FunctionDecl * functionDecl ); - void premutate( TypedefDecl * typedefDecl ); - void premutate( StructDecl * structDecl ); - void premutate( UnionDecl * unionDecl ); - }; - } // anonymous namespace - - void box( std::list< Declaration *>& translationUnit ) { - PassVisitor layoutBuilder; - PassVisitor callAdapter; - PassVisitor declAdapter; - PassVisitor polyCalculator; - PassVisitor eraser; - - acceptAll( translationUnit, layoutBuilder ); - mutateAll( translationUnit, callAdapter ); - mutateAll( translationUnit, declAdapter ); - mutateAll( translationUnit, polyCalculator ); - mutateAll( translationUnit, eraser ); - } - -////////////////////////////////// LayoutFunctionBuilder //////////////////////////////////////// - - /// Get a list of type declarations that will affect a layout function - std::list< TypeDecl* > takeOtypeOnly( std::list< TypeDecl* > &decls ) { - std::list< TypeDecl * > otypeDecls; - - for ( TypeDecl * const decl : decls ) { - if ( decl->isComplete() ) { - otypeDecls.push_back( decl ); - } - } - - return otypeDecls; - } - - /// Adds parameters for otype layout to a function type - void addOtypeParams( FunctionType *layoutFnType, std::list< TypeDecl* > &otypeParams ) { - BasicType sizeAlignType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - - for ( TypeDecl * const param : otypeParams ) { - TypeInstType paramType( Type::Qualifiers(), param->get_name(), param ); - std::string paramName = mangleType( ¶mType ); - layoutFnType->get_parameters().push_back( new ObjectDecl( sizeofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) ); - layoutFnType->get_parameters().push_back( new ObjectDecl( alignofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) ); - } - } - - /// Builds a layout function declaration - FunctionDecl *buildLayoutFunctionDecl( AggregateDecl *typeDecl, bool isInFunction, FunctionType *layoutFnType ) { - // Routines at global scope marked "static" to prevent multiple definitions is separate translation units - // because each unit generates copies of the default routines for each aggregate. - FunctionDecl *layoutDecl = new FunctionDecl( layoutofName( typeDecl ), - isInFunction ? Type::StorageClasses() : Type::StorageClasses( Type::Static ), - LinkageSpec::AutoGen, layoutFnType, new CompoundStmt(), - std::list< Attribute * >(), Type::FuncSpecifiers( Type::Inline ) ); - layoutDecl->fixUniqueId(); - return layoutDecl; - } - - /// Makes a binary operation - Expression *makeOp( const std::string &name, Expression *lhs, Expression *rhs ) { - UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) ); - expr->args.push_back( lhs ); - expr->args.push_back( rhs ); - return expr; - } - - /// Returns the dereference of a local pointer variable - Expression *derefVar( ObjectDecl *var ) { - return UntypedExpr::createDeref( new VariableExpr( var ) ); - } - - /// makes an if-statement with a single-expression if-block and no then block - Statement *makeCond( Expression *cond, Expression *ifPart ) { - return new IfStmt( cond, new ExprStmt( ifPart ), 0 ); - } - - /// makes a statement that assigns rhs to lhs if lhs < rhs - Statement *makeAssignMax( Expression *lhs, Expression *rhs ) { - return makeCond( makeOp( "?clone(), rhs->clone() ) ); - } - - /// makes a statement that aligns lhs to rhs (rhs should be an integer power of two) - Statement *makeAlignTo( Expression *lhs, Expression *rhs ) { - // check that the lhs is zeroed out to the level of rhs - Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant::from_ulong( 1 ) ) ) ); - // if not aligned, increment to alignment - Expression *ifExpr = makeOp( "?+=?", lhs->clone(), makeOp( "?-?", rhs->clone(), ifCond->clone() ) ); - return makeCond( ifCond, ifExpr ); - } - - /// adds an expression to a compound statement - void addExpr( CompoundStmt *stmts, Expression *expr ) { - stmts->get_kids().push_back( new ExprStmt( expr ) ); - } - - /// adds a statement to a compound statement - void addStmt( CompoundStmt *stmts, Statement *stmt ) { - stmts->get_kids().push_back( stmt ); - } - - void LayoutFunctionBuilder::previsit( StructDecl *structDecl ) { - // do not generate layout function for "empty" tag structs - visit_children = false; - if ( structDecl->get_members().empty() ) return; - - // get parameters that can change layout, exiting early if none - std::list< TypeDecl* > otypeParams = takeOtypeOnly( structDecl->get_parameters() ); - if ( otypeParams.empty() ) return; - - // build layout function signature - FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false ); - BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType ); - - ObjectDecl *sizeParam = new ObjectDecl( sizeofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 ); - layoutFnType->get_parameters().push_back( sizeParam ); - ObjectDecl *alignParam = new ObjectDecl( alignofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 ); - layoutFnType->get_parameters().push_back( alignParam ); - ObjectDecl *offsetParam = new ObjectDecl( offsetofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 ); - layoutFnType->get_parameters().push_back( offsetParam ); - addOtypeParams( layoutFnType, otypeParams ); - - // build function decl - FunctionDecl *layoutDecl = buildLayoutFunctionDecl( structDecl, isInFunction(), layoutFnType ); - - // calculate struct layout in function body - - // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size) - addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 0 ) ) ) ); - addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) ); - for ( auto index_member : enumerate( structDecl->members ) ) { - DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( index_member.val ); - assert( dwt ); - Type *memberType = dwt->get_type(); - - if ( 0 < index_member.idx ) { - // make sure all members after the first (automatically aligned at 0) are properly padded for alignment - addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), new AlignofExpr( memberType->clone() ) ) ); - } - - // place current size in the current offset index - addExpr( layoutDecl->get_statements(), makeOp( "?=?", makeOp( "?[?]", new VariableExpr( offsetParam ), new ConstantExpr( Constant::from_ulong( index_member.idx ) ) ), - derefVar( sizeParam ) ) ); - - // add member size to current size - addExpr( layoutDecl->get_statements(), makeOp( "?+=?", derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) ); - - // take max of member alignment and global alignment - addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) ); - } - // make sure the type is end-padded to a multiple of its alignment - addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) ); - - declsToAddAfter.push_back( layoutDecl ); - } - - void LayoutFunctionBuilder::previsit( UnionDecl *unionDecl ) { - // do not generate layout function for "empty" tag unions - visit_children = false; - if ( unionDecl->get_members().empty() ) return; - - // get parameters that can change layout, exiting early if none - std::list< TypeDecl* > otypeParams = takeOtypeOnly( unionDecl->get_parameters() ); - if ( otypeParams.empty() ) return; - - // build layout function signature - FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false ); - BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType ); - - ObjectDecl *sizeParam = new ObjectDecl( sizeofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 ); - layoutFnType->get_parameters().push_back( sizeParam ); - ObjectDecl *alignParam = new ObjectDecl( alignofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 ); - layoutFnType->get_parameters().push_back( alignParam ); - addOtypeParams( layoutFnType, otypeParams ); - - // build function decl - FunctionDecl *layoutDecl = buildLayoutFunctionDecl( unionDecl, isInFunction(), layoutFnType ); - - // calculate union layout in function body - addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) ); - addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) ); - for ( Declaration * const member : unionDecl->members ) { - DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( member ); - assert( dwt ); - Type *memberType = dwt->get_type(); - - // take max member size and global size - addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) ); - - // take max of member alignment and global alignment - addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) ); - } - // make sure the type is end-padded to a multiple of its alignment - addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) ); - - declsToAddAfter.push_back( layoutDecl ); - } - -////////////////////////////////////////////// CallAdapter ////////////////////////////////////// - - namespace { - std::string makePolyMonoSuffix( FunctionType const * function, const TyVarMap &tyVars ) { - // NOTE: this function previously used isPolyObj, which failed to produce - // the correct thing in some situations. It's not clear to me why this wasn't working. - - // 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 ( DeclarationWithType const * const ret : function->returnVals ) { - name << ( isPolyType( ret->get_type(), tyVars ) ? 'P' : 'M' ); - } - name << '_'; - for ( DeclarationWithType const * const arg : function->parameters ) { - name << ( isPolyType( arg->get_type(), tyVars ) ? 'P' : 'M' ); - } - return name.str(); - } - - std::string mangleAdapterName( FunctionType const * function, const TyVarMap &tyVars ) { - return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars ); - } - - std::string makeAdapterName( const std::string &mangleName ) { - return "_adapter" + mangleName; - } - - /// 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 - Type *replaceWithConcrete( Type *type, TypeSubstitution const * env, bool doClone = true ); - - CallAdapter::CallAdapter() : tempNamer( "_temp" ) {} - - void CallAdapter::premutate( Declaration * ) { - // Prevent type declaration information from leaking out. - GuardScope( scopeTyVars ); - } - - void CallAdapter::premutate( FunctionDecl *functionDecl ) { - if ( functionDecl->get_statements() ) { // empty routine body ? - // std::cerr << "mutating function: " << functionDecl->get_mangleName() << std::endl; - GuardScope( scopeTyVars ); - GuardValue( retval ); - - // process polymorphic return value - retval = nullptr; - FunctionType *functionType = functionDecl->type; - if ( isDynRet( functionType ) && functionDecl->linkage != LinkageSpec::C ) { - retval = functionType->returnVals.front(); - - // give names to unnamed return values - if ( retval->name == "" ) { - retval->name = "_retparm"; - retval->linkage = LinkageSpec::C; - } // if - } // if - - makeTyVarMap( functionType, scopeTyVars ); - - std::list< FunctionType const *> functions; - for ( TypeDecl * const tyVar : functionType->forall ) { - for ( DeclarationWithType * const assert : tyVar->assertions ) { - findFunction( assert->get_type(), functions, scopeTyVars, needsAdapter ); - } // for - } // for - for ( DeclarationWithType * const arg : functionType->parameters ) { - findFunction( arg->get_type(), functions, scopeTyVars, needsAdapter ); - } // for - - for ( FunctionType const * const funType : functions ) { - std::string mangleName = mangleAdapterName( funType, scopeTyVars ); - if ( !adapters.contains( mangleName ) ) { - std::string adapterName = makeAdapterName( mangleName ); - adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, nullptr, new PointerType( Type::Qualifiers(), makeAdapterType( funType, scopeTyVars ) ), nullptr ) ) ); - } // if - } // for - // std::cerr << "end function: " << functionDecl->get_mangleName() << std::endl; - } // if - } - - void CallAdapter::premutate( TypeDecl *typeDecl ) { - addToTyVarMap( typeDecl, scopeTyVars ); - } - - void CallAdapter::premutate( CommaExpr *commaExpr ) { - // 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 temp 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 ( UntypedExpr * assign = dynamic_cast< UntypedExpr * >( commaExpr->get_arg1() ) ) { - if ( CodeGen::isAssignment( InitTweak::getFunctionName( assign ) ) ) { - assert( assign->get_args().size() == 2 ); - if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * > ( assign->get_args().back() ) ) { - // first argument is assignable, so it must be an lvalue, so it should be legal to take its address. - retVals[appExpr] = assign->get_args().front(); - } - } - } - } - - std::list< Expression *>::iterator CallAdapter::passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) { - Type *polyType = isPolyType( parmType, exprTyVars ); - if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) { - std::string typeName = mangleType( polyType ); - if ( seenTypes.count( typeName ) ) return arg; - - arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) ); - arg++; - arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) ); - arg++; - if ( dynamic_cast< StructInstType* >( polyType ) ) { - if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) { - // zero-length arrays are forbidden by C, so don't pass offset for empty struct - if ( ! argBaseStructType->get_baseStruct()->get_members().empty() ) { - arg = appExpr->get_args().insert( arg, new OffsetPackExpr( argBaseStructType->clone() ) ); - arg++; - } - } else { - SemanticError( argBaseType, "Cannot pass non-struct type for generic struct: " ); - } - } - - seenTypes.insert( typeName ); - } - return arg; - } - - std::list< Expression *>::iterator CallAdapter::passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, const TyVarMap &exprTyVars ) { - assert( env ); - std::list< Expression *>::iterator arg = appExpr->args.begin(); - // pass size/align for type variables - // NOTE: This is iterating over a map. This means the sorting - // order of the keys changes behaviour, as the iteration order - // is visible outside the loop. - The order matches the orignal - // order because the vars have been renamed with numbers that, - // even when converted to strings, sort in the original order. - // (At least, that is the best explination I have.) - for ( std::pair const & tyParam : exprTyVars ) { - if ( !tyParam.second.isComplete ) continue; - Type *concrete = env->lookup( tyParam.first ); - // If there is an unbound type variable, it should have detected already. - assertf( concrete, "Unbound type variable: %s in: %s", - toCString( tyParam.first ), toCString( *env ) ); - - arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) ); - arg++; - arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) ); - arg++; - } // for - - // add size/align for generic types to parameter list - if ( ! appExpr->get_function()->result ) return arg; - FunctionType *funcType = getFunctionType( appExpr->get_function()->get_result() ); - assert( funcType ); - - // Iterator over the original function arguments. - std::list< Expression* >::const_iterator fnArg; - // Names for generic types we've seen. - std::set< std::string > seenTypes; - - // a polymorphic return type may need to be added to the argument list - if ( polyRetType ) { - Type *concRetType = replaceWithConcrete( polyRetType, env ); - arg = passArgTypeVars( appExpr, polyRetType, concRetType, arg, exprTyVars, seenTypes ); - // Skip the return parameter in the argument list. - fnArg = arg + 1; - } else { - fnArg = arg; - } - - // add type information args for presently unseen types in parameter list - std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); - for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) { - Type * argType = (*fnArg)->get_result(); - if ( ! argType ) continue; - arg = passArgTypeVars( appExpr, (*fnParm)->get_type(), argType, arg, exprTyVars, seenTypes ); - } - return arg; - } - - ObjectDecl *CallAdapter::makeTemporary( Type *type ) { - ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0, type, 0 ); - stmtsToAddBefore.push_back( new DeclStmt( newObj ) ); - return newObj; - } - - Expression *CallAdapter::addRetParam( ApplicationExpr *appExpr, Type *retType ) { - // Create temporary to hold return value of polymorphic function and produce that temporary as a result - // using a comma expression. - assert( retType ); - - Expression * paramExpr = nullptr; - // try to use existing return value parameter if it exists, otherwise create a new temporary - if ( retVals.count( appExpr ) ) { - paramExpr = retVals[appExpr]->clone(); - } else { - ObjectDecl *newObj = makeTemporary( retType->clone() ); - paramExpr = new VariableExpr( newObj ); - } - Expression * retExpr = paramExpr->clone(); - - // If the type of the temporary is not polymorphic, box temporary by taking its address; - // otherwise the temporary is already boxed and can be used directly. - if ( ! isPolyType( paramExpr->get_result(), scopeTyVars, env ) ) { - paramExpr = new AddressExpr( paramExpr ); - } // if - // Add argument to function call. - appExpr->args.push_front( paramExpr ); - // Build a comma expression to call the function and emulate a normal return. - CommaExpr *commaExpr = new CommaExpr( appExpr, retExpr ); - commaExpr->env = appExpr->env; - appExpr->env = nullptr; - return commaExpr; - } - - /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment - void replaceParametersWithConcrete( std::list< Expression* >& params, TypeSubstitution const * env ) { - for ( Expression * const param : params ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - paramType->set_type( replaceWithConcrete( paramType->get_type(), env, false ) ); - } - } - - // See forward definition. - Type *replaceWithConcrete( Type *type, TypeSubstitution const * env, bool doClone ) { - assert( env ); - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) { - Type *concrete = env->lookup( typeInst->get_name() ); - if ( concrete == 0 ) { - return typeInst; - } // if - return concrete; - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( doClone ) { - structType = structType->clone(); - } - replaceParametersWithConcrete( structType->get_parameters(), env ); - return structType; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( doClone ) { - unionType = unionType->clone(); - } - replaceParametersWithConcrete( unionType->get_parameters(), env ); - return unionType; - } - return type; - } - - Expression *CallAdapter::addDynRetParam( ApplicationExpr *appExpr, Type *dynType ) { - Type *concrete = replaceWithConcrete( dynType, env ); - // add out-parameter for return value - return addRetParam( appExpr, concrete ); - } - - Expression *CallAdapter::applyAdapter( ApplicationExpr *appExpr, FunctionType *function ) { - Expression *ret = appExpr; - if ( isDynRet( function, scopeTyVars ) ) { - ret = addRetParam( appExpr, function->returnVals.front()->get_type() ); - } // if - std::string mangleName = mangleAdapterName( function, scopeTyVars ); - std::string adapterName = makeAdapterName( mangleName ); - - // cast adaptee to void (*)(), since it may have any type inside a polymorphic function - Type * adapteeType = new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ); - appExpr->get_args().push_front( new CastExpr( appExpr->function, adapteeType ) ); - appExpr->set_function( new NameExpr( adapterName ) ); // xxx - result is never set on NameExpr - - return ret; - } - - // find instances of polymorphic type parameters - struct PolyFinder { - const TyVarMap * tyVars = nullptr; - bool found = false; - - void previsit( TypeInstType * t ) { - if ( isPolyType( t, *tyVars ) ) { - found = true; - } - } - }; - - // true if there is an instance of a polymorphic type parameter in t - bool hasPolymorphism( Type * t, const TyVarMap &tyVars ) { - PassVisitor finder; - finder.pass.tyVars = &tyVars; - maybeAccept( t, finder ); - return finder.pass.found; - } - - /// 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( Expression *&actual, Type *formal, const TyVarMap &tyVars ) { - // type contains polymorphism, but isn't exactly a polytype, in which case it - // has some real actual type (e.g. unsigned int) and casting to void * is wrong - if ( hasPolymorphism( formal, tyVars ) && ! isPolyType( formal, tyVars ) ) { - Type * newType = formal->clone(); - newType = ScrubTyVars::scrub( newType, tyVars ); - actual = new CastExpr( actual, newType ); - } // if - } - - void CallAdapter::boxParam( Expression *&arg, Type *param, const TyVarMap &exprTyVars ) { - assertf( arg->result, "arg does not have result: %s", toString( arg ).c_str() ); - addCast( arg, param, exprTyVars ); - if ( ! needsBoxing( param, arg->result, exprTyVars, env ) ) return; - - if ( arg->get_lvalue() ) { - // argument expression may be CFA lvalue, but not C lvalue -- apply generalizedLvalue transformations. - // if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( 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 AddressExpr( arg ) ); - if ( ! ResolvExpr::typesCompatible( param, arg->get_result(), SymTab::Indexer() ) ) { - // silence warnings by casting boxed parameters when the actual type does not match up with the formal type. - arg = new CastExpr( arg, param->clone() ); - } - } else { - // use type computed in unification to declare boxed variables - Type * newType = param->clone(); - if ( env ) env->apply( newType ); - ObjectDecl *newObj = makeTemporary( newType ); - // TODO: is this right??? (Why wouldn't it be?) - newObj->get_type()->get_qualifiers() = Type::Qualifiers(); - // TODO: why doesn't this just use initialization syntax? - // (Possibly to ensure code is run at the right time.) - UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) ); - assign->get_args().push_back( new VariableExpr( newObj ) ); - assign->get_args().push_back( arg ); - stmtsToAddBefore.push_back( new ExprStmt( assign ) ); - arg = new AddressExpr( new VariableExpr( newObj ) ); - } // if - } - - void CallAdapter::boxParams( ApplicationExpr *appExpr, std::list< Expression *>::iterator arg, FunctionType *function, const TyVarMap &exprTyVars ) { - for ( DeclarationWithType * param : function->parameters ) { - assertf( arg != appExpr->args.end(), "boxParams: missing argument for param %s to %s in %s", toString( param ).c_str(), toString( function ).c_str(), toString( appExpr ).c_str() ); - boxParam( *arg, param->get_type(), exprTyVars ); - ++arg; - } // for - } - - void CallAdapter::addInferredParams( ApplicationExpr *appExpr, std::list< Expression *>::iterator arg, FunctionType *functionType, const TyVarMap &tyVars ) { - for ( TypeDecl * const tyVar : functionType->forall ) { - for ( DeclarationWithType * const assert : tyVar->assertions ) { - InferredParams::const_iterator inferParam = appExpr->inferParams.find( assert->get_uniqueId() ); - assertf( inferParam != appExpr->inferParams.end(), "addInferredParams missing inferred parameter: %s in: %s", toString( assert ).c_str(), toString( appExpr ).c_str() ); - Expression *newExpr = inferParam->second.expr->clone(); - boxParam( newExpr, assert->get_type(), tyVars ); - arg = appExpr->get_args().insert( arg, newExpr ); - ++arg; - } // for - } // for - } - - void makeRetParm( FunctionType *funcType ) { - DeclarationWithType *retParm = funcType->returnVals.front(); - - // make a new parameter that is a pointer to the type of the old return value - retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) ); - funcType->get_parameters().push_front( retParm ); - - // we don't need the return value any more - funcType->get_returnVals().clear(); - } - - FunctionType *makeAdapterType( FunctionType const *adaptee, const TyVarMap &tyVars ) { - // actually make the adapter type - FunctionType *adapter = adaptee->clone(); - if ( isDynRet( adapter, tyVars ) ) { - makeRetParm( adapter ); - } // if - adapter->get_parameters().push_front( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) ); - return adapter; - } - - Expression *makeAdapterArg( - DeclarationWithType *param, - DeclarationWithType const *arg, - DeclarationWithType const *realParam, - const TyVarMap &tyVars ) { - assert( param ); - assert( arg ); - if ( isPolyType( realParam->get_type(), tyVars ) - && ! isPolyType( arg->get_type() ) ) { - UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) ); - deref->args.push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) ); - deref->result = arg->get_type()->clone(); - return deref; - } // if - return new VariableExpr( param ); - } - - void addAdapterParams( - ApplicationExpr *adapteeApp, - std::list< DeclarationWithType *>::const_iterator arg, - std::list< DeclarationWithType *>::const_iterator param, - std::list< DeclarationWithType *>::const_iterator paramEnd, - std::list< DeclarationWithType *>::const_iterator realParam, - const TyVarMap &tyVars ) { - UniqueName paramNamer( "_p" ); - for ( ; param != paramEnd; ++param, ++arg, ++realParam ) { - if ( (*param)->get_name() == "" ) { - (*param)->set_name( paramNamer.newName() ); - (*param)->set_linkage( LinkageSpec::C ); - } // if - adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) ); - } // for - } - - FunctionDecl *CallAdapter::makeAdapter( FunctionType const *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) { - FunctionType *adapterType = makeAdapterType( adaptee, tyVars ); - adapterType = ScrubTyVars::scrub( adapterType, tyVars ); - DeclarationWithType *adapteeDecl = adapterType->get_parameters().front(); - adapteeDecl->set_name( "_adaptee" ); - // do not carry over attributes to real type parameters/return values - for ( DeclarationWithType * dwt : realType->parameters ) { - deleteAll( dwt->get_type()->attributes ); - dwt->get_type()->attributes.clear(); - } - for ( DeclarationWithType * dwt : realType->returnVals ) { - deleteAll( dwt->get_type()->attributes ); - dwt->get_type()->attributes.clear(); - } - ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) ); - Statement *bodyStmt; - - for ( auto tys : group_iterate( realType->forall, adapterType->forall, adaptee->forall ) ) { - TypeDecl * tyArg = std::get<0>( tys ); - TypeDecl * tyParam = std::get<1>( tys ); - TypeDecl * realTyParam = std::get<2>( tys ); - for ( auto asserts : group_iterate( tyArg->assertions, tyParam->assertions, realTyParam->assertions ) ) { - DeclarationWithType * assertArg = std::get<0>( asserts ); - DeclarationWithType * assertParam = std::get<1>( asserts ); - DeclarationWithType * realAssertParam = std::get<2>( asserts ); - adapteeApp->args.push_back( makeAdapterArg( assertParam, assertArg, realAssertParam, tyVars ) ); - } // for - } // for - - std::list< DeclarationWithType *>::const_iterator arg = realType->parameters.begin(); - std::list< DeclarationWithType *>::const_iterator param = adapterType->parameters.begin(); - std::list< DeclarationWithType *>::const_iterator realParam = adaptee->parameters.begin(); - param++; // skip adaptee parameter in the adapter type - if ( realType->get_returnVals().empty() ) { - // void return - addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars ); - bodyStmt = new ExprStmt( adapteeApp ); - } else if ( isDynType( adaptee->returnVals.front()->get_type(), tyVars ) ) { - // return type T - if ( (*param)->get_name() == "" ) { - (*param)->set_name( "_ret" ); - (*param)->set_linkage( LinkageSpec::C ); - } // if - UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) ); - UntypedExpr *deref = UntypedExpr::createDeref( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) ); - assign->get_args().push_back( deref ); - addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars ); - assign->get_args().push_back( adapteeApp ); - bodyStmt = new ExprStmt( assign ); - } else { - // adapter for a function that returns a monomorphic value - addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars ); - bodyStmt = new ReturnStmt( adapteeApp ); - } // if - CompoundStmt *adapterBody = new CompoundStmt(); - adapterBody->get_kids().push_back( bodyStmt ); - std::string adapterName = makeAdapterName( mangleName ); - return new FunctionDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, adapterType, adapterBody ); - } - - void CallAdapter::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) { - // collect a list of function types passed as parameters or implicit parameters (assertions) - std::list functions; - for ( TypeDecl * const tyVar : functionType->get_forall() ) { - for ( DeclarationWithType * const assert : tyVar->get_assertions() ) { - findFunction( assert->get_type(), functions, exprTyVars, needsAdapter ); - } // for - } // for - for ( DeclarationWithType * const arg : functionType->get_parameters() ) { - findFunction( arg->get_type(), functions, exprTyVars, needsAdapter ); - } // for - - // 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< std::string > adaptersDone; - - for ( FunctionType const * const funType : functions ) { - std::string mangleName = SymTab::Mangler::mangle( funType ); - - // 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 insert result is "is the value new". - if ( !adaptersDone.insert( mangleName ).second ) continue; - - // Apply substitution to type variables to figure out what the adapter's type should look like. - assert( env ); - FunctionType *realType = funType->clone(); - env->apply( realType ); - mangleName = SymTab::Mangler::mangle( realType ); - mangleName += makePolyMonoSuffix( funType, exprTyVars ); - - typedef ScopedMap< std::string, DeclarationWithType* >::iterator AdapterIter; - AdapterIter adapter = adapters.find( mangleName ); - if ( adapter == adapters.end() ) { - // Adapter has not been created yet in the current scope, so define it. - FunctionDecl *newAdapter = makeAdapter( funType, realType, mangleName, exprTyVars ); - std::pair< AdapterIter, bool > answer = adapters.insert( mangleName, newAdapter ); - adapter = answer.first; - stmtsToAddBefore.push_back( new DeclStmt( newAdapter ) ); - } // if - assert( adapter != adapters.end() ); - - // Add the appropriate adapter as a parameter. - appExpr->args.push_front( new VariableExpr( adapter->second ) ); - } // for - } // passAdapters - - Expression *makeIncrDecrExpr( ApplicationExpr *appExpr, Type *polyType, bool isIncr ) { - NameExpr *opExpr = new NameExpr( ( isIncr ) ? "?+=?" : "?-=?" ); - UntypedExpr *addAssign = new UntypedExpr( opExpr ); - if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) { - addAssign->get_args().push_back( address->get_arg() ); - } else { - addAssign->get_args().push_back( appExpr->get_args().front() ); - } // if - addAssign->get_args().push_back( new NameExpr( sizeofName( mangleType( polyType ) ) ) ); - addAssign->set_result( appExpr->get_result()->clone() ); - if ( appExpr->get_env() ) { - addAssign->set_env( appExpr->get_env() ); - appExpr->set_env( 0 ); - } // if - appExpr->get_args().clear(); - delete appExpr; - return addAssign; - } - - Expression *CallAdapter::handleIntrinsics( ApplicationExpr *appExpr ) { - if ( VariableExpr *varExpr = dynamic_cast< VariableExpr *>( appExpr->function ) ) { - if ( varExpr->var->linkage == LinkageSpec::Intrinsic ) { - if ( varExpr->var->name == "?[?]" ) { - assert( appExpr->result ); - assert( appExpr->get_args().size() == 2 ); - Type *baseType1 = isPolyPtr( appExpr->args.front()->result, scopeTyVars, env ); - Type *baseType2 = isPolyPtr( appExpr->args.back()->result, scopeTyVars, env ); - assert( ! baseType1 || ! baseType2 ); // the arguments cannot both be polymorphic pointers - UntypedExpr *ret = 0; - if ( baseType1 || baseType2 ) { // one of the arguments is a polymorphic pointer - ret = new UntypedExpr( new NameExpr( "?+?" ) ); - } // if - if ( baseType1 ) { - UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) ); - multiply->get_args().push_back( appExpr->get_args().back() ); - multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) ); - ret->get_args().push_back( appExpr->get_args().front() ); - ret->get_args().push_back( multiply ); - } else if ( baseType2 ) { - UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) ); - multiply->get_args().push_back( appExpr->get_args().front() ); - multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) ); - ret->get_args().push_back( multiply ); - ret->get_args().push_back( appExpr->get_args().back() ); - } // if - if ( baseType1 || baseType2 ) { - delete ret->get_result(); - ret->set_result( appExpr->get_result()->clone() ); - if ( appExpr->get_env() ) { - ret->set_env( appExpr->get_env() ); - appExpr->set_env( 0 ); - } // if - appExpr->get_args().clear(); - delete appExpr; - return ret; - } // if - } else if ( varExpr->get_var()->get_name() == "*?" ) { - assert( appExpr->result ); - assert( ! appExpr->get_args().empty() ); - if ( isPolyType( appExpr->get_result(), scopeTyVars, env ) ) { - // remove dereference from polymorphic types since they are boxed. - Expression *ret = appExpr->get_args().front(); - // fix expr type to remove pointer - delete ret->get_result(); - ret->set_result( appExpr->get_result()->clone() ); - if ( appExpr->get_env() ) { - ret->set_env( appExpr->get_env() ); - appExpr->set_env( 0 ); - } // if - appExpr->get_args().clear(); - delete appExpr; - return ret; - } // if - } else if ( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) { - assert( appExpr->result ); - assert( appExpr->get_args().size() == 1 ); - if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) { - Type *tempType = appExpr->get_result()->clone(); - if ( env ) { - env->apply( tempType ); - } // if - ObjectDecl *newObj = makeTemporary( tempType ); - VariableExpr *tempExpr = new VariableExpr( newObj ); - UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) ); - assignExpr->get_args().push_back( tempExpr->clone() ); - if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) { - assignExpr->get_args().push_back( address->get_arg()->clone() ); - } else { - assignExpr->get_args().push_back( appExpr->get_args().front()->clone() ); - } // if - CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) ); - return new CommaExpr( firstComma, tempExpr ); - } // if - } else if ( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) { - assert( appExpr->result ); - assert( appExpr->get_args().size() == 1 ); - if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) { - return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" ); - } // if - } else if ( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) { - assert( appExpr->result ); - assert( appExpr->get_args().size() == 2 ); - Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env ); - Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env ); - if ( baseType1 && baseType2 ) { - UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) ); - divide->get_args().push_back( appExpr ); - divide->get_args().push_back( new SizeofExpr( baseType1->clone() ) ); - divide->set_result( appExpr->get_result()->clone() ); - if ( appExpr->get_env() ) { - divide->set_env( appExpr->get_env() ); - appExpr->set_env( 0 ); - } // if - return divide; - } else if ( baseType1 ) { - UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) ); - multiply->get_args().push_back( appExpr->get_args().back() ); - multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) ); - appExpr->get_args().back() = multiply; - } else if ( baseType2 ) { - UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) ); - multiply->get_args().push_back( appExpr->get_args().front() ); - multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) ); - appExpr->get_args().front() = multiply; - } // if - } else if ( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) { - assert( appExpr->result ); - assert( appExpr->get_args().size() == 2 ); - Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ); - if ( baseType ) { - UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) ); - multiply->get_args().push_back( appExpr->get_args().back() ); - multiply->get_args().push_back( new SizeofExpr( baseType->clone() ) ); - appExpr->get_args().back() = multiply; - } // if - } // if - return appExpr; - } // if - } // if - return 0; - } - - Expression *CallAdapter::postmutate( ApplicationExpr *appExpr ) { - // std::cerr << "mutate appExpr: " << InitTweak::getFunctionName( appExpr ) << std::endl; - // for ( auto tyVar : scopeTyVars ) { - // std::cerr << tyVar.first << " "; - // } - // std::cerr << "\n"; - - assert( appExpr->function->result ); - FunctionType * function = getFunctionType( appExpr->function->result ); - assertf( function, "ApplicationExpr has non-function type: %s", toString( appExpr->function->result ).c_str() ); - - if ( Expression *newExpr = handleIntrinsics( appExpr ) ) { - return newExpr; - } // if - - Expression *ret = appExpr; - // Save iterator to the first original parameter (works with lists). - std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin(); - - TyVarMap exprTyVars( TypeDecl::Data{} ); - makeTyVarMap( function, exprTyVars ); // xxx - should this take into account the variables already bound in scopeTyVars (i.e. remove them from exprTyVars?) - ReferenceToType *dynRetType = isDynRet( function, exprTyVars ); - - // std::cerr << function << std::endl; - // std::cerr << "scopeTyVars: "; - // printTyVarMap( std::cerr, scopeTyVars ); - // std::cerr << "exprTyVars: "; - // printTyVarMap( std::cerr, exprTyVars ); - // std::cerr << "env: " << *env << std::endl; - // std::cerr << needsAdapter( function, scopeTyVars ) << ! needsAdapter( function, exprTyVars) << std::endl; - - // NOTE: addDynRetParam needs to know the actual (generated) return type so it can make a temp variable, so pass the result type from the appExpr - // passTypeVars needs to know the program-text return type (i.e. the distinction between _conc_T30 and T3(int)) - // concRetType may not be a good name in one or both of these places. A more appropriate name change is welcome. - if ( dynRetType ) { - // std::cerr << "dynRetType: " << dynRetType << std::endl; - Type *concRetType = appExpr->get_result()->isVoid() ? nullptr : appExpr->get_result(); - ret = addDynRetParam( appExpr, concRetType ); // xxx - used to use dynRetType instead of concRetType - } else if ( needsAdapter( function, scopeTyVars ) && ! needsAdapter( function, exprTyVars) ) { // xxx - exprTyVars is used above...? - // xxx - the ! needsAdapter check may be incorrect. It seems there is some situation where an adapter is applied where it shouldn't be, and this fixes it for some cases. More investigation is needed. - - // std::cerr << "needs adapter: "; - // printTyVarMap( std::cerr, scopeTyVars ); - // std::cerr << *env << std::endl; - // change the application so it calls the adapter rather than the passed function - ret = applyAdapter( appExpr, function ); - } // if - - Type *concRetType = replaceWithConcrete( dynRetType, env ); - std::list< Expression *>::iterator arg = - passTypeVars( appExpr, concRetType, exprTyVars ); // xxx - used to use dynRetType instead of concRetType; this changed so that the correct type paramaters are passed for return types (it should be the concrete type's parameters, not the formal type's) - addInferredParams( appExpr, arg, function, exprTyVars ); - - // This needs to point at the original first argument. - boxParams( appExpr, paramBegin, function, exprTyVars ); - - passAdapters( appExpr, function, exprTyVars ); - - return ret; - } - - bool isPolyDeref( UntypedExpr const * expr, TyVarMap const & scopeTyVars, TypeSubstitution const * env ) { - if ( expr->result && isPolyType( expr->result, scopeTyVars, env ) ) { - if ( auto name = dynamic_cast( expr->function ) ) { - if ( name->name == "*?" ) { - return true; - } // if - } // if - } // if - return false; - } - - Expression * CallAdapter::postmutate( UntypedExpr *expr ) { - if ( isPolyDeref( expr, scopeTyVars, env ) ) { - Expression *ret = expr->args.front(); - expr->args.clear(); - delete expr; - return ret; - } - return expr; - } - - void CallAdapter::premutate( AddressExpr * ) { visit_children = false; } - - Expression * CallAdapter::postmutate( AddressExpr * addrExpr ) { - assert( addrExpr->arg->result && ! addrExpr->arg->result->isVoid() ); - - bool needs = false; - if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->arg ) ) { - if ( isPolyDeref( expr, scopeTyVars, env ) ) { - if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->args.front() ) ) { - assert( appExpr->function->result ); - FunctionType *function = getFunctionType( appExpr->function->result ); - assert( function ); - needs = needsAdapter( function, scopeTyVars ); - } // if - } // if - } // if - // isPolyType check needs to happen before mutating addrExpr arg, so pull it forward - // out of the if condition. - addrExpr->arg = addrExpr->arg->acceptMutator( *visitor ); - // ... but must happen after mutate, since argument might change (e.g. intrinsic *?, ?[?]) - re-evaluate above comment - bool polytype = isPolyType( addrExpr->arg->result, scopeTyVars, env ); - if ( polytype || needs ) { - Expression *ret = addrExpr->arg; - delete ret->result; - ret->result = addrExpr->result->clone(); - addrExpr->arg = nullptr; - delete addrExpr; - return ret; - } else { - return addrExpr; - } // if - } - - void CallAdapter::premutate( ReturnStmt *returnStmt ) { - if ( retval && returnStmt->expr ) { - assert( returnStmt->expr->result && ! returnStmt->expr->result->isVoid() ); - delete returnStmt->expr; - returnStmt->expr = nullptr; - } // if - } - - void CallAdapter::premutate( PointerType *pointerType ) { - GuardScope( scopeTyVars ); - makeTyVarMap( pointerType, scopeTyVars ); - } - - void CallAdapter::premutate( FunctionType *functionType ) { - GuardScope( scopeTyVars ); - makeTyVarMap( functionType, scopeTyVars ); - } - - void CallAdapter::beginScope() { - adapters.beginScope(); - } - - void CallAdapter::endScope() { - adapters.endScope(); - } - -////////////////////////////////////////// DeclAdapter ////////////////////////////////////////// - - void DeclAdapter::addAdapters( FunctionType *functionType ) { - std::list< FunctionType const *> functions; - for ( DeclarationWithType * const arg : functionType->parameters ) { - Type *orig = arg->get_type(); - findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter ); - arg->set_type( orig ); - } - std::set< std::string > adaptersDone; - for ( FunctionType const * const funType : functions ) { - std::string mangleName = mangleAdapterName( funType, scopeTyVars ); - if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) { - std::string adapterName = makeAdapterName( mangleName ); - // adapter may not be used in body, pass along with unused attribute. - functionType->parameters.push_front( - new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( funType, scopeTyVars ) ), 0, { new Attribute( "unused" ) } ) ); - adaptersDone.insert( adaptersDone.begin(), mangleName ); - } - } - } - - DeclarationWithType * DeclAdapter::postmutate( FunctionDecl *functionDecl ) { - FunctionType * ftype = functionDecl->type; - if ( ! ftype->returnVals.empty() && functionDecl->statements ) { - // intrinsic functions won't be using the _retval so no need to generate it. - if ( functionDecl->linkage != LinkageSpec::Intrinsic && !isPrefix( functionDecl->name, "_thunk" ) && ! isPrefix( functionDecl->name, "_adapter" ) ) { // xxx - remove check for prefix once thunks properly use ctor/dtors - assert( ftype->returnVals.size() == 1 ); - DeclarationWithType * retval = ftype->returnVals.front(); - if ( retval->name == "" ) { - retval->name = "_retval"; - } - functionDecl->statements->kids.push_front( new DeclStmt( retval ) ); - DeclarationWithType * newRet = retval->clone(); // for ownership purposes - ftype->returnVals.front() = newRet; - } - } - // errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments - for ( Declaration * param : functionDecl->type->parameters ) { - if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) { - delete obj->init; - obj->init = nullptr; - } - } - return functionDecl; - } - - void DeclAdapter::premutate( StructDecl * ) { - // prevent tyVars from leaking into containing scope - GuardScope( scopeTyVars ); - } - - void DeclAdapter::premutate( UnionDecl * ) { - // prevent tyVars from leaking into containing scope - GuardScope( scopeTyVars ); - } - - void DeclAdapter::premutate( TraitDecl * ) { - // prevent tyVars from leaking into containing scope - GuardScope( scopeTyVars ); - } - - void DeclAdapter::premutate( TypeDecl *typeDecl ) { - addToTyVarMap( typeDecl, scopeTyVars ); - } - - void DeclAdapter::premutate( PointerType *pointerType ) { - GuardScope( scopeTyVars ); - makeTyVarMap( pointerType, scopeTyVars ); - } - - void DeclAdapter::premutate( FunctionType *funcType ) { - GuardScope( scopeTyVars ); - makeTyVarMap( funcType, scopeTyVars ); - - // move polymorphic return type to parameter list - if ( isDynRet( funcType ) ) { - ObjectDecl *ret = strict_dynamic_cast< ObjectDecl* >( funcType->get_returnVals().front() ); - ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) ); - funcType->get_parameters().push_front( ret ); - funcType->get_returnVals().pop_front(); - ret->set_init( nullptr ); // xxx - memory leak? - } - - // add size/align and assertions for type parameters to parameter list - std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin(); - std::list< DeclarationWithType *> inferredParams; - // size/align/offset parameters may not be used in body, pass along with unused attribute. - ObjectDecl newObj( "", Type::StorageClasses(), LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0, - { new Attribute( "unused" ) } ); - ObjectDecl newPtr( "", Type::StorageClasses(), LinkageSpec::C, 0, - new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 ); - for ( TypeDecl * const tyParam : funcType->get_forall() ) { - ObjectDecl *sizeParm, *alignParm; - // add all size and alignment parameters to parameter list - if ( tyParam->isComplete() ) { - TypeInstType parmType( Type::Qualifiers(), tyParam->get_name(), tyParam ); - std::string parmName = mangleType( &parmType ); - - sizeParm = newObj.clone(); - sizeParm->set_name( sizeofName( parmName ) ); - last = funcType->get_parameters().insert( last, sizeParm ); - ++last; - - alignParm = newObj.clone(); - alignParm->set_name( alignofName( parmName ) ); - last = funcType->get_parameters().insert( last, alignParm ); - ++last; - } - // move all assertions into parameter list - for ( DeclarationWithType * const assert : tyParam->get_assertions() ) { - // assertion parameters may not be used in body, pass along with unused attribute. - assert->get_attributes().push_back( new Attribute( "unused" ) ); - inferredParams.push_back( assert ); - } - tyParam->get_assertions().clear(); - } - - // add size/align for generic parameter types to parameter list - std::set< std::string > seenTypes; // sizeofName for generic types we've seen - for ( DeclarationWithType * const fnParam : funcType->get_parameters() ) { - Type *polyType = isPolyType( fnParam->get_type(), scopeTyVars ); - if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) { - std::string typeName = mangleType( polyType ); - if ( seenTypes.count( typeName ) ) continue; - - ObjectDecl *sizeParm, *alignParm, *offsetParm; - sizeParm = newObj.clone(); - sizeParm->set_name( sizeofName( typeName ) ); - last = funcType->get_parameters().insert( last, sizeParm ); - ++last; - - alignParm = newObj.clone(); - alignParm->set_name( alignofName( typeName ) ); - last = funcType->get_parameters().insert( last, alignParm ); - ++last; - - if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyType ) ) { - // NOTE zero-length arrays are illegal in C, so empty structs have no offset array - if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) { - offsetParm = newPtr.clone(); - offsetParm->set_name( offsetofName( typeName ) ); - last = funcType->get_parameters().insert( last, offsetParm ); - ++last; - } - } - seenTypes.insert( typeName ); - } - } - - // splice assertion parameters into parameter list - funcType->get_parameters().splice( last, inferredParams ); - addAdapters( funcType ); - } - -////////////////////////////////////////// PolyGenericCalculator //////////////////////////////// - - PolyGenericCalculator::PolyGenericCalculator() - : knownLayouts(), knownOffsets(), bufNamer( "_buf" ) {} - - void PolyGenericCalculator::beginTypeScope( Type *ty ) { - GuardScope( scopeTyVars ); - makeTyVarMap( ty, scopeTyVars ); - } - - void PolyGenericCalculator::beginGenericScope() { - GuardScope( *this ); - // We expect the first function type see to be the type relating to this scope - // but any further type is probably some unrelated function pointer - // keep track of which is the first - GuardValue( expect_func_type ); - expect_func_type = true; - } - - void PolyGenericCalculator::premutate( ObjectDecl *objectDecl ) { - beginTypeScope( objectDecl->get_type() ); - } - - void PolyGenericCalculator::premutate( FunctionDecl *functionDecl ) { - beginGenericScope(); - - beginTypeScope( functionDecl->get_functionType() ); - } - - void PolyGenericCalculator::premutate( TypedefDecl *typedefDecl ) { - assert(false); - beginTypeScope( typedefDecl->get_base() ); - } - - void PolyGenericCalculator::premutate( TypeDecl * typeDecl ) { - addToTyVarMap( typeDecl, scopeTyVars ); - } - - Declaration * PolyGenericCalculator::postmutate( TypeDecl *typeDecl ) { - if ( Type * base = typeDecl->base ) { - // add size/align variables for opaque type declarations - TypeInstType inst( Type::Qualifiers(), typeDecl->name, typeDecl ); - std::string typeName = mangleType( &inst ); - Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - - ObjectDecl * sizeDecl = ObjectDecl::newObject( sizeofName( typeName ), layoutType, new SingleInit( new SizeofExpr( base->clone() ) ) ); - ObjectDecl * alignDecl = ObjectDecl::newObject( alignofName( typeName ), layoutType->clone(), new SingleInit( new AlignofExpr( base->clone() ) ) ); - - // ensure that the initializing sizeof/alignof exprs are properly mutated - sizeDecl->acceptMutator( *visitor ); - alignDecl->acceptMutator( *visitor ); - - // can't use makeVar, because it inserts into stmtsToAdd and TypeDecls can occur at global scope - declsToAddAfter.push_back( alignDecl ); - // replace with sizeDecl - return sizeDecl; - } - return typeDecl; - } - - void PolyGenericCalculator::premutate( PointerType *pointerType ) { - beginTypeScope( pointerType ); - } - - void PolyGenericCalculator::premutate( FunctionType *funcType ) { - beginTypeScope( funcType ); - - GuardValue( expect_func_type ); - - if(!expect_func_type) { - // If this is the first function type we see - // Then it's the type of the declaration and we care about it - GuardScope( *this ); - } - - // The other functions type we will see in this scope are probably functions parameters - // they don't help us with the layout and offsets so don't mark them as known in this scope - expect_func_type = false; - - // make sure that any type information passed into the function is accounted for - for ( DeclarationWithType * const fnParam : funcType->get_parameters() ) { - // condition here duplicates that in DeclAdapter::mutate( FunctionType* ) - Type *polyType = isPolyType( fnParam->get_type(), scopeTyVars ); - if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) { - knownLayouts.insert( mangleType( polyType ) ); - } - } - } - - /// converts polymorphic type T into a suitable monomorphic representation, currently: __attribute__((aligned(8)) char[size_T] - Type * polyToMonoType( Type const * declType ) { - Type * charType = new BasicType( Type::Qualifiers(), BasicType::Kind::Char); - Expression * size = new NameExpr( sizeofName( mangleType(declType) ) ); - Attribute * aligned = new Attribute( "aligned", std::list{ new ConstantExpr( Constant::from_int(8) ) } ); - return new ArrayType( Type::Qualifiers(), charType, size, - true, false, std::list{ aligned } ); - } - - void PolyGenericCalculator::mutateMembers( AggregateDecl * aggrDecl ) { - std::set< std::string > genericParams; - for ( TypeDecl * td : aggrDecl->parameters ) { - genericParams.insert( td->name ); - } - for ( Declaration * decl : aggrDecl->members ) { - if ( ObjectDecl * field = dynamic_cast< ObjectDecl * >( decl ) ) { - Type * ty = replaceTypeInst( field->type, env ); - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) { - // do not try to monomorphize generic parameters - if ( scopeTyVars.contains( typeInst->get_name() ) && ! 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. - Type * newType = polyToMonoType( field->type ); - delete field->type; - field->type = newType; - } - } - } - } - } - - void PolyGenericCalculator::premutate( StructDecl * structDecl ) { - mutateMembers( structDecl ); - } - - void PolyGenericCalculator::premutate( UnionDecl * unionDecl ) { - mutateMembers( unionDecl ); - } - - void PolyGenericCalculator::premutate( DeclStmt *declStmt ) { - if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) { - if ( findGeneric( objectDecl->get_type() ) ) { - // change initialization of a polymorphic value object to allocate via a VLA - // (alloca was previously used, but can't be safely used in loops) - ObjectDecl *newBuf = ObjectDecl::newObject( bufNamer.newName(), polyToMonoType( objectDecl->type ), nullptr ); - stmtsToAddBefore.push_back( new DeclStmt( newBuf ) ); - - // if the object has a cleanup attribute, the cleanup should be on the buffer, not the pointer - auto matchAndMove = [newBuf](Attribute * attr){ - if(attr->name == "cleanup") { - newBuf->attributes.push_back(attr); - return true; - } - return false; - }; - - objectDecl->attributes.remove_if(matchAndMove); - - delete objectDecl->get_init(); - objectDecl->set_init( new SingleInit( new VariableExpr( newBuf ) ) ); - } - } - } - - /// Checks if memberDecl matches the decl from an aggregate. - bool isMember( DeclarationWithType *memberDecl, Declaration * decl ) { - if ( memberDecl->get_name() != decl->get_name() ) - return false; - - if ( memberDecl->get_name().empty() ) { - // Plan-9 Field: match on unique_id. - return ( memberDecl->get_uniqueId() == decl->get_uniqueId() ); - } - - DeclarationWithType *declWithType = strict_dynamic_cast< DeclarationWithType* >( decl ); - - if ( memberDecl->get_mangleName().empty() || declWithType->get_mangleName().empty() ) { - // Tuple-Element Field: expect neither had mangled name; accept match on simple name (like field_2) only. - assert( memberDecl->get_mangleName().empty() && declWithType->get_mangleName().empty() ); - return true; - } - - // Ordinary Field: Use full name to accommodate overloading. - return ( memberDecl->get_mangleName() == declWithType->get_mangleName() ); - } - - /// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present - long findMember( DeclarationWithType *memberDecl, std::list< Declaration* > &baseDecls ) { - for ( auto pair : enumerate( baseDecls ) ) { - if ( isMember( memberDecl, pair.val ) ) { - return pair.idx; - } - } - return -1; - } - - /// Returns an index expression into the offset array for a type - Expression *makeOffsetIndex( Type const *objectType, long i ) { - ConstantExpr *fieldIndex = new ConstantExpr( Constant::from_ulong( i ) ); - UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) ); - fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) ); - fieldOffset->get_args().push_back( fieldIndex ); - return fieldOffset; - } - - Expression *PolyGenericCalculator::postmutate( MemberExpr *memberExpr ) { - // only mutate member expressions for polymorphic types - int tyDepth; - Type *objectType = hasPolyBase( memberExpr->aggregate->result, scopeTyVars, &tyDepth ); - if ( ! objectType ) return memberExpr; - findGeneric( objectType ); // ensure layout for this type is available - - // replace member expression with dynamically-computed layout expression - Expression *newMemberExpr = nullptr; - if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) { - // look up offset index - long i = findMember( memberExpr->member, structType->baseStruct->members ); - if ( i == -1 ) return memberExpr; - - // replace member expression with pointer to base plus offset - UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) ); - Expression * aggr = memberExpr->aggregate->clone(); - delete aggr->env; // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it - aggr->env = nullptr; - fieldLoc->get_args().push_back( aggr ); - fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) ); - fieldLoc->set_result( memberExpr->result->clone() ); - newMemberExpr = fieldLoc; - } else if ( dynamic_cast< UnionInstType* >( objectType ) ) { - // union members are all at offset zero, so just use the aggregate expr - Expression * aggr = memberExpr->aggregate->clone(); - delete aggr->env; // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it - aggr->env= nullptr; - newMemberExpr = aggr; - newMemberExpr->result = memberExpr->result->clone(); - } else return memberExpr; - assert( newMemberExpr ); - - // Must apply the generic substitution to the member type to handle cases where the member is a generic parameter substituted by a known concrete type, e.g. - // forall(otype T) struct Box { T x; } - // forall(otype T) f() { - // Box(T *) b; b.x; - // } - // TODO: memberExpr->result should be exactly memberExpr->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. - Type *memberType = memberExpr->member->get_type()->clone(); - TypeSubstitution sub = objectType->genericSubstitution(); - sub.apply( memberType ); - if ( ! isPolyType( memberType, scopeTyVars ) ) { - // Not all members of a polymorphic type are themselves of polymorphic type; in this case the member expression should be wrapped and dereferenced to form an lvalue - CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) ); - UntypedExpr *derefExpr = UntypedExpr::createDeref( ptrCastExpr ); - newMemberExpr = derefExpr; - } - - delete memberType; - delete memberExpr; - return newMemberExpr; - } - - void PolyGenericCalculator::premutate( AddressExpr * addrExpr ) { - GuardValue( addrMember ); - // is the argument a MemberExpr before mutating? - addrMember = dynamic_cast< MemberExpr * >( addrExpr->arg ); - } - - Expression * PolyGenericCalculator::postmutate( AddressExpr * addrExpr ) { - if ( addrMember && addrMember != addrExpr->arg ) { - // arg was a MemberExpr and has been mutated - if ( UntypedExpr * untyped = dynamic_cast< UntypedExpr * >( addrExpr->arg ) ) { - if ( InitTweak::getFunctionName( untyped ) == "?+?" ) { - // MemberExpr was converted to pointer+offset, and it is not valid C to take the address of an addition, so strip the address-of - // TODO: should addrExpr->arg->result be changed to addrExpr->result? - Expression * ret = addrExpr->arg; - addrExpr->arg = nullptr; - std::swap( addrExpr->env, ret->env ); - delete addrExpr; - return ret; - } - } - } - return addrExpr; - } - - ObjectDecl *PolyGenericCalculator::makeVar( const std::string &name, Type *type, Initializer *init ) { - ObjectDecl *newObj = new ObjectDecl( name, Type::StorageClasses(), LinkageSpec::C, nullptr, type, init ); - stmtsToAddBefore.push_back( new DeclStmt( newObj ) ); - return newObj; - } - - void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) { - for ( Type * const param : otypeParams ) { - if ( findGeneric( param ) ) { - // push size/align vars for a generic parameter back - std::string paramName = mangleType( param ); - layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) ); - layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) ); - } else { - layoutCall->get_args().push_back( new SizeofExpr( param->clone() ) ); - layoutCall->get_args().push_back( new AlignofExpr( param->clone() ) ); - } - } - } - - /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list - bool findGenericParams( std::list< TypeDecl* > const &baseParams, std::list< Expression* > const &typeParams, std::list< Type* > &out ) { - bool hasDynamicLayout = false; - - for ( auto paramPair : group_iterate( baseParams, typeParams ) ) { - TypeDecl * baseParam = std::get<0>( paramPair ); - Expression * typeParam = std::get<1>( paramPair ); - // skip non-otype parameters - if ( ! baseParam->isComplete() ) continue; - TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( typeParam ); - assert( typeExpr && "all otype parameters should be type expressions" ); - - Type *type = typeExpr->get_type(); - out.push_back( type ); - if ( isPolyType( type ) ) hasDynamicLayout = true; - } - - return hasDynamicLayout; - } - - bool PolyGenericCalculator::findGeneric( Type const *ty ) { - ty = replaceTypeInst( ty, env ); - - if ( auto typeInst = dynamic_cast< TypeInstType const * >( ty ) ) { - if ( scopeTyVars.contains( typeInst->get_name() ) ) { - // NOTE assumes here that getting put in the scopeTyVars included having the layout variables set - return true; - } - return false; - } else if ( auto structTy = dynamic_cast< StructInstType const * >( ty ) ) { - // check if this type already has a layout generated for it - std::string typeName = mangleType( ty ); - if ( knownLayouts.contains( typeName ) ) return true; - - // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized - std::list< Type* > otypeParams; - if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->parameters, otypeParams ) ) return false; - - // insert local variables for layout and generate call to layout function - knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call - Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - - int n_members = structTy->get_baseStruct()->get_members().size(); - if ( n_members == 0 ) { - // all empty structs have the same layout - size 1, align 1 - makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) ); - makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) ); - // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array - } else { - ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType ); - ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() ); - ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) ); - - // generate call to layout function - UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) ); - layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) ); - layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) ); - layoutCall->get_args().push_back( new VariableExpr( offsetVar ) ); - addOtypeParamsToLayoutCall( layoutCall, otypeParams ); - - stmtsToAddBefore.push_back( new ExprStmt( layoutCall ) ); - } - - // std::cout << "TRUE 2" << std::endl; - - return true; - } else if ( auto unionTy = dynamic_cast< UnionInstType const * >( ty ) ) { - // check if this type already has a layout generated for it - std::string typeName = mangleType( ty ); - if ( knownLayouts.contains( typeName ) ) return true; - - // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized - std::list< Type* > otypeParams; - if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->parameters, otypeParams ) ) return false; - - // insert local variables for layout and generate call to layout function - knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call - Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - - ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType ); - ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() ); - - // generate call to layout function - UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) ); - layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) ); - layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) ); - addOtypeParamsToLayoutCall( layoutCall, otypeParams ); - - stmtsToAddBefore.push_back( new ExprStmt( layoutCall ) ); - - return true; - } - - return false; - } - - Expression * PolyGenericCalculator::genSizeof( Type* ty ) { - if ( ArrayType * aty = dynamic_cast(ty) ) { - // generate calculated size for possibly generic array - Expression * sizeofBase = genSizeof( aty->get_base() ); - if ( ! sizeofBase ) return nullptr; - Expression * dim = aty->get_dimension(); - aty->set_dimension( nullptr ); - return makeOp( "?*?", sizeofBase, dim ); - } else if ( findGeneric( ty ) ) { - // generate calculated size for generic type - return new NameExpr( sizeofName( mangleType( ty ) ) ); - } else return nullptr; - } - - Expression *PolyGenericCalculator::postmutate( SizeofExpr *sizeofExpr ) { - Type *ty = sizeofExpr->get_isType() ? - sizeofExpr->get_type() : sizeofExpr->get_expr()->get_result(); - - Expression * gen = genSizeof( ty ); - if ( gen ) { - delete sizeofExpr; - return gen; - } else return sizeofExpr; - } - - Expression *PolyGenericCalculator::postmutate( AlignofExpr *alignofExpr ) { - Type *ty = alignofExpr->get_isType() ? alignofExpr->get_type() : alignofExpr->get_expr()->get_result(); - if ( findGeneric( ty ) ) { - Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) ); - delete alignofExpr; - return ret; - } - return alignofExpr; - } - - Expression *PolyGenericCalculator::postmutate( OffsetofExpr *offsetofExpr ) { - // only mutate expressions for polymorphic structs/unions - Type *ty = offsetofExpr->get_type(); - if ( ! findGeneric( ty ) ) return offsetofExpr; - - if ( StructInstType *structType = dynamic_cast< StructInstType* >( ty ) ) { - // replace offsetof expression by index into offset array - long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() ); - if ( i == -1 ) return offsetofExpr; - - Expression *offsetInd = makeOffsetIndex( ty, i ); - delete offsetofExpr; - return offsetInd; - } else if ( dynamic_cast< UnionInstType* >( ty ) ) { - // all union members are at offset zero - delete offsetofExpr; - return new ConstantExpr( Constant::from_ulong( 0 ) ); - } else return offsetofExpr; - } - - Expression *PolyGenericCalculator::postmutate( OffsetPackExpr *offsetPackExpr ) { - StructInstType *ty = offsetPackExpr->get_type(); - - Expression *ret = 0; - if ( findGeneric( ty ) ) { - // pull offset back from generated type information - ret = new NameExpr( offsetofName( mangleType( ty ) ) ); - } else { - std::string offsetName = offsetofName( mangleType( ty ) ); - if ( knownOffsets.contains( offsetName ) ) { - // use the already-generated offsets for this type - ret = new NameExpr( offsetName ); - } else { - knownOffsets.insert( offsetName ); - - std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members(); - Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ); - - // build initializer list for offset array - std::list< Initializer* > inits; - for ( Declaration * const member : baseMembers ) { - DeclarationWithType *memberDecl = dynamic_cast< DeclarationWithType* >( member ); - assertf( memberDecl, "Requesting offset of Non-DWT member: %s", toString( member ).c_str() ); - inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) ); - } - - // build the offset array and replace the pack with a reference to it - ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ), - new ListInit( inits ) ); - ret = new VariableExpr( offsetArray ); - } - } - - delete offsetPackExpr; - return ret; - } - - void PolyGenericCalculator::beginScope() { - knownLayouts.beginScope(); - knownOffsets.beginScope(); - } - - void PolyGenericCalculator::endScope() { - knownLayouts.endScope(); - knownOffsets.endScope(); - } - -////////////////////////////////////////// Eraser /////////////////////////////////////////////// - - void Eraser::premutate( ObjectDecl * objectDecl ) { - ScrubTyVars::scrubAll( objectDecl ); - } - - void Eraser::premutate( FunctionDecl * functionDecl ) { - ScrubTyVars::scrubAll( functionDecl ); - } - - void Eraser::premutate( TypedefDecl * typedefDecl ) { - ScrubTyVars::scrubAll( typedefDecl ); - } - - /// Strips the members from a generic aggregate - static void stripGenericMembers( AggregateDecl * decl ) { - if ( ! decl->parameters.empty() ) decl->members.clear(); - } - - void Eraser::premutate( StructDecl * structDecl ) { - stripGenericMembers( structDecl ); - } - - void Eraser::premutate( UnionDecl * unionDecl ) { - stripGenericMembers( unionDecl ); - } - } // anonymous namespace -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/FindFunction.cc =================================================================== --- src/GenPoly/FindFunction.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/FindFunction.cc (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -20,75 +20,9 @@ #include "AST/Pass.hpp" // for Pass #include "AST/Type.hpp" -#include "Common/PassVisitor.h" // for PassVisitor #include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::iterator #include "GenPoly/GenPoly.h" // for TyVarMap #include "ScrubTyVars.h" // for ScrubTyVars -#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl -#include "SynTree/Mutator.h" // for Mutator, mutateAll -#include "SynTree/Type.h" // for FunctionType, Type, Type::For... namespace GenPoly { - class FindFunction : public WithGuards, public WithVisitorRef, public WithShortCircuiting { - public: - FindFunction( std::list< FunctionType const* > &functions, const TyVarMap &tyVars, bool replaceMode, FindFunctionPredicate predicate ); - - void premutate( FunctionType * functionType ); - Type * postmutate( FunctionType * functionType ); - void premutate( PointerType * pointerType ); - private: - void handleForall( const Type::ForallList &forall ); - - std::list< FunctionType const * > & functions; - TyVarMap tyVars; - bool replaceMode; - FindFunctionPredicate predicate; - }; - - void findFunction( Type *type, std::list< FunctionType const * > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate ) { - PassVisitor finder( functions, tyVars, false, predicate ); - type->acceptMutator( finder ); - } - - void findAndReplaceFunction( Type *&type, std::list< FunctionType const * > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate ) { - PassVisitor finder( functions, tyVars, true, predicate ); - type = type->acceptMutator( finder ); - } - - FindFunction::FindFunction( std::list< FunctionType const * > &functions, const TyVarMap &tyVars, bool replaceMode, FindFunctionPredicate predicate ) - : functions( functions ), tyVars( tyVars ), replaceMode( replaceMode ), predicate( predicate ) { - } - - void FindFunction::handleForall( const Type::ForallList &forall ) { - for ( const Declaration * td : forall ) { - TyVarMap::iterator var = tyVars.find( td->name ); - if ( var != tyVars.end() ) { - tyVars.erase( var->first ); - } // if - } // for - } - - void FindFunction::premutate( FunctionType * functionType ) { - visit_children = false; - GuardScope( tyVars ); - handleForall( functionType->get_forall() ); - mutateAll( functionType->get_returnVals(), *visitor ); - } - - Type * FindFunction::postmutate( FunctionType * functionType ) { - Type *ret = functionType; - if ( predicate( functionType, tyVars ) ) { - functions.push_back( functionType ); - if ( replaceMode ) { - // replace type parameters in function type with void* - ret = ScrubTyVars::scrub( functionType->clone(), tyVars ); - } // if - } // if - return ret; - } - - void FindFunction::premutate( PointerType * pointerType ) { - GuardScope( tyVars ); - handleForall( pointerType->get_forall() ); - } namespace { @@ -154,5 +88,4 @@ void FindFunctionCore::previsit( ast::PointerType const * /*type*/ ) { GuardScope( typeVars ); - //handleForall( type->forall ); } @@ -164,8 +97,4 @@ ast::Pass pass( functions, typeVars, predicate, false ); type->accept( pass ); - //(void)type; - //(void)functions; - //(void)typeVars; - //(void)predicate; } @@ -175,8 +104,4 @@ ast::Pass pass( functions, typeVars, predicate, true ); return type->accept( pass ); - //(void)functions; - //(void)typeVars; - //(void)predicate; - //return type; } Index: src/GenPoly/FindFunction.h =================================================================== --- src/GenPoly/FindFunction.h (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/FindFunction.h (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -16,18 +16,7 @@ #pragma once -#include // for list - #include "GenPoly.h" // for TyVarMap -class FunctionType; -class Type; - namespace GenPoly { - typedef bool (*FindFunctionPredicate)( FunctionType*, const TyVarMap& ); - - /// recursively walk `type`, placing all functions that match `predicate` under `tyVars` into `functions` - void findFunction( Type *type, std::list< FunctionType const * > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate ); - /// like `findFunction`, but also replaces the function type with void ()(void) - void findAndReplaceFunction( Type *&type, std::list< FunctionType const * > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate ); typedef bool (*FindFunctionPred)( const ast::FunctionType *, const TypeVarMap & ); Index: src/GenPoly/GenPoly.cc =================================================================== --- src/GenPoly/GenPoly.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/GenPoly.cc (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -29,8 +29,4 @@ #include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it... #include "ResolvExpr/typeops.h" // for flatten -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Expression.h" // for Expression, TypeExpr, Constan... -#include "SynTree/Type.h" // for Type, StructInstType, UnionIn... -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution using namespace std; @@ -39,13 +35,4 @@ namespace { /// Checks a parameter list for polymorphic parameters; will substitute according to env if present - bool hasPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - if ( isPolyType( paramType->get_type(), env ) ) return true; - } - return false; - } - bool hasPolyParams( const std::vector> & params, const ast::TypeSubstitution * env ) { for ( auto ¶m : params ) { @@ -58,13 +45,4 @@ /// Checks a parameter list for polymorphic parameters from tyVars; will substitute according to env if present - bool hasPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true; - } - return false; - } - bool hasPolyParams( const std::vector> & params, const TypeVarMap & typeVars, const ast::TypeSubstitution * env ) { for ( auto & param : params ) { @@ -77,13 +55,4 @@ /// Checks a parameter list for dynamic-layout parameters from tyVars; will substitute according to env if present - bool hasDynParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - if ( isDynType( paramType->get_type(), tyVars, env ) ) return true; - } - return false; - } - bool hasDynParams( const std::vector> & params, @@ -99,42 +68,4 @@ return false; } - - /// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present - bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - if ( includesPolyType( paramType->get_type(), env ) ) return true; - } - return false; - } - - /// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present - bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true; - } - return false; - } - } - - Type* replaceTypeInst( Type* type, const TypeSubstitution* env ) { - if ( ! env ) return type; - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { - Type *newType = env->lookup( typeInst->get_name() ); - if ( newType ) return newType; - } - return type; - } - - const Type* replaceTypeInst( const Type* type, const TypeSubstitution* env ) { - if ( ! env ) return type; - if ( auto typeInst = dynamic_cast< const TypeInstType* >( type ) ) { - Type *newType = env->lookup( typeInst->get_name() ); - if ( newType ) return newType; - } - return type; } @@ -146,19 +77,4 @@ } return type; - } - - Type *isPolyType( Type *type, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( dynamic_cast< TypeInstType * >( type ) ) { - return type; - } else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) { - return isPolyType( arrayType->base, env ); - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( hasPolyParams( structType->get_parameters(), env ) ) return type; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( hasPolyParams( unionType->get_parameters(), env ) ) return type; - } - return 0; } @@ -178,21 +94,4 @@ } - Type *isPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) { - if ( tyVars.contains( typeInst->get_name() ) ) { - return type; - } - } else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) { - return isPolyType( arrayType->base, tyVars, env ); - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( hasPolyParams( structType->get_parameters(), tyVars, env ) ) return type; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( hasPolyParams( unionType->get_parameters(), tyVars, env ) ) return type; - } - return 0; - } - const ast::Type * isPolyType( const ast::Type * type, const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) { @@ -211,20 +110,4 @@ } - ReferenceToType *isDynType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) { - auto var = tyVars.find( typeInst->get_name() ); - if ( var != tyVars.end() && var->second.isComplete ) { - return typeInst; - } - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( hasDynParams( structType->get_parameters(), tyVars, env ) ) return structType; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( hasDynParams( unionType->get_parameters(), tyVars, env ) ) return unionType; - } - return 0; - } - const ast::BaseInstType * isDynType( const ast::Type * type, const TypeVarMap & typeVars, @@ -249,10 +132,4 @@ } - ReferenceToType *isDynRet( FunctionType *function, const TyVarMap &forallTypes ) { - if ( function->get_returnVals().empty() ) return 0; - - return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes ); - } - const ast::BaseInstType *isDynRet( const ast::FunctionType * type, const TypeVarMap & typeVars ) { @@ -262,12 +139,4 @@ } - ReferenceToType *isDynRet( FunctionType *function ) { - if ( function->get_returnVals().empty() ) return 0; - - TyVarMap forallTypes( TypeDecl::Data{} ); - makeTyVarMap( function, forallTypes ); - return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes ); - } - const ast::BaseInstType *isDynRet( const ast::FunctionType * func ) { if ( func->returns.empty() ) return nullptr; @@ -278,19 +147,4 @@ } - bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars ) { -// if ( ! adaptee->get_returnVals().empty() && isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) { -// return true; -// } // if - if ( isDynRet( adaptee, tyVars ) ) return true; - - for ( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); innerArg != adaptee->get_parameters().end(); ++innerArg ) { -// if ( isPolyType( (*innerArg)->get_type(), tyVars ) ) { - if ( isDynType( (*innerArg)->get_type(), tyVars ) ) { - return true; - } // if - } // for - return false; - } - bool needsAdapter( ast::FunctionType const * adaptee, const TypeVarMap & typeVars ) { @@ -304,22 +158,4 @@ return false; } - - Type *isPolyPtr( Type *type, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( PointerType *ptr = dynamic_cast< PointerType *>( type ) ) { - return isPolyType( ptr->get_base(), env ); - } - return 0; - } - - Type *isPolyPtr( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( PointerType *ptr = dynamic_cast< PointerType *>( type ) ) { - return isPolyType( ptr->get_base(), tyVars, env ); - } - return 0; - } const ast::Type * isPolyPtr( @@ -333,38 +169,4 @@ return nullptr; } - - Type * hasPolyBase( Type *type, int *levels, const TypeSubstitution *env ) { - int dummy; - if ( ! levels ) { levels = &dummy; } - *levels = 0; - - while ( true ) { - type = replaceTypeInst( type, env ); - - if ( PointerType *ptr = dynamic_cast< PointerType *>( type ) ) { - type = ptr->get_base(); - ++(*levels); - } else break; - } - - return isPolyType( type, env ); - } - - Type * hasPolyBase( Type *type, const TyVarMap &tyVars, int *levels, const TypeSubstitution *env ) { - int dummy; - if ( ! levels ) { levels = &dummy; } - *levels = 0; - - while ( true ) { - type = replaceTypeInst( type, env ); - - if ( PointerType *ptr = dynamic_cast< PointerType *>( type ) ) { - type = ptr->get_base(); - ++(*levels); - } else break; - } - - return isPolyType( type, tyVars, env ); - } ast::Type const * hasPolyBase( @@ -388,45 +190,4 @@ } - bool includesPolyType( Type *type, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( dynamic_cast< TypeInstType * >( type ) ) { - return true; - } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) { - if ( includesPolyType( pointerType->get_base(), env ) ) return true; - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( includesPolyParams( structType->get_parameters(), env ) ) return true; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( includesPolyParams( unionType->get_parameters(), env ) ) return true; - } - return false; - } - - bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) { - type = replaceTypeInst( type, env ); - - if ( TypeInstType *typeInstType = dynamic_cast< TypeInstType * >( type ) ) { - if ( tyVars.contains( typeInstType->get_name() ) ) { - return true; - } - } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) { - if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true; - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true; - } - return false; - } - - FunctionType * getFunctionType( Type *ty ) { - PointerType *ptrType; - if ( ( ptrType = dynamic_cast< PointerType* >( ty ) ) ) { - return dynamic_cast< FunctionType* >( ptrType->get_base() ); // pointer if FunctionType, NULL otherwise - } else { - return dynamic_cast< FunctionType* >( ty ); // pointer if FunctionType, NULL otherwise - } - } - const ast::FunctionType * getFunctionType( const ast::Type * ty ) { if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) { @@ -437,43 +198,4 @@ } - VariableExpr * getBaseVar( Expression *expr, int *levels ) { - int dummy; - if ( ! levels ) { levels = &dummy; } - *levels = 0; - - while ( true ) { - if ( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( expr ) ) { - return varExpr; - } else if ( MemberExpr *memberExpr = dynamic_cast< MemberExpr* >( expr ) ) { - expr = memberExpr->get_aggregate(); - } else if ( AddressExpr *addressExpr = dynamic_cast< AddressExpr* >( expr ) ) { - expr = addressExpr->get_arg(); - } else if ( UntypedExpr *untypedExpr = dynamic_cast< UntypedExpr* >( expr ) ) { - // look for compiler-inserted dereference operator - NameExpr *fn = dynamic_cast< NameExpr* >( untypedExpr->get_function() ); - if ( ! fn || fn->get_name() != std::string("*?") ) return 0; - expr = *untypedExpr->begin_args(); - } else if ( CommaExpr *commaExpr = dynamic_cast< CommaExpr* >( expr ) ) { - // copy constructors insert comma exprs, look at second argument which contains the variable - expr = commaExpr->get_arg2(); - continue; - } else if ( ConditionalExpr * condExpr = dynamic_cast< ConditionalExpr * >( expr ) ) { - int lvl1; - int lvl2; - VariableExpr * var1 = getBaseVar( condExpr->get_arg2(), &lvl1 ); - VariableExpr * var2 = getBaseVar( condExpr->get_arg3(), &lvl2 ); - if ( lvl1 == lvl2 && var1 && var2 && var1->get_var() == var2->get_var() ) { - *levels = lvl1; - return var1; - } - break; - } else break; - - ++(*levels); - } - - return 0; - } - namespace { /// Checks if is a pointer to D @@ -488,20 +210,4 @@ inline D const * as( B const * p ) { return reinterpret_cast( p ); - } - - /// Flattens a declaration list - template - void flattenList( list< DeclarationWithType* > src, Output out ) { - for ( DeclarationWithType* decl : src ) { - ResolvExpr::flatten( decl->get_type(), out ); - } - } - - /// Flattens a list of types - template - void flattenList( list< Type* > src, Output out ) { - for ( Type* ty : src ) { - ResolvExpr::flatten( ty, out ); - } } @@ -515,24 +221,4 @@ } - /// Checks if two lists of parameters are equal up to polymorphic substitution. - bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) { - if ( aparams.size() != bparams.size() ) return false; - - for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin(); - at != aparams.end(); ++at, ++bt ) { - TypeExpr *aparam = dynamic_cast< TypeExpr* >(*at); - assertf(aparam, "Aggregate parameters should be type expressions"); - TypeExpr *bparam = dynamic_cast< TypeExpr* >(*bt); - assertf(bparam, "Aggregate parameters should be type expressions"); - - // xxx - might need to let VoidType be a wildcard here too; could have some voids - // stuffed in for dtype-statics. - // if ( is( aparam->get_type() ) || is( bparam->get_type() ) ) continue; - if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false; - } - - return true; - } - bool paramListsPolyCompatible( std::vector> const & lparams, @@ -559,94 +245,4 @@ return true; } - } - - bool typesPolyCompatible( Type *a, Type *b ) { - type_index aid{ typeid(*a) }; - // polymorphic types always match - if ( aid == type_index{typeid(TypeInstType)} ) return true; - - type_index bid{ typeid(*b) }; - // polymorphic types always match - if ( bid == type_index{typeid(TypeInstType)} ) return true; - - // can't match otherwise if different types - if ( aid != bid ) return false; - - // recurse through type structure (conditions borrowed from Unify.cc) - if ( aid == type_index{typeid(BasicType)} ) { - return as(a)->get_kind() == as(b)->get_kind(); - } else if ( aid == type_index{typeid(PointerType)} ) { - PointerType *ap = as(a), *bp = as(b); - - // void pointers should match any other pointer type - return is( ap->get_base() ) || is( bp->get_base() ) - || typesPolyCompatible( ap->get_base(), bp->get_base() ); - } else if ( aid == type_index{typeid(ReferenceType)} ) { - ReferenceType *ap = as(a), *bp = as(b); - return is( ap->get_base() ) || is( bp->get_base() ) - || typesPolyCompatible( ap->get_base(), bp->get_base() ); - } else if ( aid == type_index{typeid(ArrayType)} ) { - ArrayType *aa = as(a), *ba = as(b); - - if ( aa->get_isVarLen() ) { - if ( ! ba->get_isVarLen() ) return false; - } else { - if ( ba->get_isVarLen() ) return false; - - ConstantExpr *ad = dynamic_cast( aa->get_dimension() ); - ConstantExpr *bd = dynamic_cast( ba->get_dimension() ); - if ( ad && bd - && ad->get_constant()->get_value() != bd->get_constant()->get_value() ) - return false; - } - - return typesPolyCompatible( aa->get_base(), ba->get_base() ); - } else if ( aid == type_index{typeid(FunctionType)} ) { - FunctionType *af = as(a), *bf = as(b); - - vector aparams, bparams; - flattenList( af->get_parameters(), back_inserter( aparams ) ); - flattenList( bf->get_parameters(), back_inserter( bparams ) ); - if ( aparams.size() != bparams.size() ) return false; - - vector areturns, breturns; - flattenList( af->get_returnVals(), back_inserter( areturns ) ); - flattenList( bf->get_returnVals(), back_inserter( breturns ) ); - if ( areturns.size() != breturns.size() ) return false; - - for ( unsigned i = 0; i < aparams.size(); ++i ) { - if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false; - } - for ( unsigned i = 0; i < areturns.size(); ++i ) { - if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false; - } - return true; - } else if ( aid == type_index{typeid(StructInstType)} ) { - StructInstType *aa = as(a), *ba = as(b); - - if ( aa->get_name() != ba->get_name() ) return false; - return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() ); - } else if ( aid == type_index{typeid(UnionInstType)} ) { - UnionInstType *aa = as(a), *ba = as(b); - - if ( aa->get_name() != ba->get_name() ) return false; - return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() ); - } else if ( aid == type_index{typeid(EnumInstType)} ) { - return as(a)->get_name() == as(b)->get_name(); - } else if ( aid == type_index{typeid(TraitInstType)} ) { - return as(a)->get_name() == as(b)->get_name(); - } else if ( aid == type_index{typeid(TupleType)} ) { - TupleType *at = as(a), *bt = as(b); - - vector atypes, btypes; - flattenList( at->get_types(), back_inserter( atypes ) ); - flattenList( bt->get_types(), back_inserter( btypes ) ); - if ( atypes.size() != btypes.size() ) return false; - - for ( unsigned i = 0; i < atypes.size(); ++i ) { - if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false; - } - return true; - } else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type } @@ -763,14 +359,4 @@ } - bool needsBoxing( Type * param, Type * arg, const TyVarMap &exprTyVars, const TypeSubstitution * env ) { - // is parameter is not polymorphic, don't need to box - if ( ! isPolyType( param, exprTyVars ) ) return false; - Type * newType = arg->clone(); - if ( env ) env->apply( newType ); - std::unique_ptr manager( newType ); - // if the argument's type is polymorphic, we don't need to box again! - return ! isPolyType( newType ); - } - bool needsBoxing( const ast::Type * param, const ast::Type * arg, const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) { @@ -786,12 +372,4 @@ return !isPolyType( newType ); } - - bool needsBoxing( Type * param, Type * arg, ApplicationExpr * appExpr, const TypeSubstitution * env ) { - FunctionType * function = getFunctionType( appExpr->function->result ); - assertf( function, "ApplicationExpr has non-function type: %s", toString( appExpr->function->result ).c_str() ); - TyVarMap exprTyVars( TypeDecl::Data{} ); - makeTyVarMap( function, exprTyVars ); - return needsBoxing( param, arg, exprTyVars, env ); - } bool needsBoxing( @@ -806,8 +384,4 @@ } - void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) { - tyVarMap.insert( tyVar->name, TypeDecl::Data{ tyVar } ); - } - void addToTypeVarMap( const ast::TypeDecl * decl, TypeVarMap & typeVars ) { typeVars.insert( ast::TypeEnvKey( decl, 0, 0 ), ast::TypeData( decl ) ); @@ -817,14 +391,4 @@ typeVars.insert( ast::TypeEnvKey( *type ), ast::TypeData( type->base ) ); } - - void makeTyVarMap( Type *type, TyVarMap &tyVarMap ) { - for ( Type::ForallList::const_iterator tyVar = type->get_forall().begin(); tyVar != type->get_forall().end(); ++tyVar ) { - assert( *tyVar ); - addToTyVarMap( *tyVar, tyVarMap ); - } - if ( PointerType *pointer = dynamic_cast< PointerType* >( type ) ) { - makeTyVarMap( pointer->get_base(), tyVarMap ); - } - } void makeTypeVarMap( const ast::Type * type, TypeVarMap & typeVars ) { @@ -846,11 +410,4 @@ } - void printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap ) { - for ( TyVarMap::const_iterator i = tyVarMap.begin(); i != tyVarMap.end(); ++i ) { - os << i->first << " (" << i->second << ") "; - } // for - os << std::endl; - } - } // namespace GenPoly Index: src/GenPoly/GenPoly.h =================================================================== --- src/GenPoly/GenPoly.h (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/GenPoly.h (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -23,6 +23,4 @@ #include "AST/Fwd.hpp" // for ApplicationExpr, BaseInstType, Func... #include "SymTab/Mangler.h" // for Mangler -#include "SynTree/Declaration.h" // for TypeDecl::Data, AggregateDecl, Type... -#include "SynTree/SynTree.h" // for Visitor Nodes namespace ast { @@ -32,5 +30,4 @@ namespace GenPoly { - typedef ErasableScopedMap< std::string, TypeDecl::Data > TyVarMap; struct TypeVarMap : public ErasableScopedMap { TypeVarMap() : ErasableScopedMap( ast::TypeData() ) {} @@ -38,91 +35,50 @@ /// Replaces a TypeInstType by its referrent in the environment, if applicable - Type* replaceTypeInst( Type* type, const TypeSubstitution* env ); - const Type* replaceTypeInst( const Type* type, const TypeSubstitution* env ); const ast::Type * replaceTypeInst( const ast::Type *, const ast::TypeSubstitution * ); /// returns polymorphic type if is polymorphic type, NULL otherwise; will look up substitution in env if provided - Type *isPolyType( Type *type, const TypeSubstitution *env = 0 ); const ast::Type * isPolyType(const ast::Type * type, const ast::TypeSubstitution * env = nullptr); /// returns polymorphic type if is polymorphic type in tyVars, NULL otherwise; will look up substitution in env if provided - Type *isPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); const ast::Type * isPolyType( const ast::Type * type, const TypeVarMap & typeVars, const ast::TypeSubstitution * subst = nullptr ); /// returns dynamic-layout type if is dynamic-layout type in tyVars, NULL otherwise; will look up substitution in env if provided - ReferenceToType *isDynType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); const ast::BaseInstType *isDynType( const ast::Type * type, const TypeVarMap & typeVars, const ast::TypeSubstitution * subst = 0 ); /// true iff function has dynamic-layout return type under the given type variable map - ReferenceToType *isDynRet( FunctionType *function, const TyVarMap &tyVars ); const ast::BaseInstType *isDynRet( const ast::FunctionType * type, const TypeVarMap & typeVars ); /// true iff function has dynamic-layout return type under the type variable map generated from its forall-parameters - ReferenceToType *isDynRet( FunctionType *function ); const ast::BaseInstType *isDynRet( const ast::FunctionType * func ); /// A function needs an adapter if it returns a dynamic-layout value or if any of its parameters have dynamic-layout type - bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVarr ); bool needsAdapter( ast::FunctionType const * adaptee, const TypeVarMap & typeVars ); - /// returns polymorphic type if is pointer to polymorphic type, NULL otherwise; will look up substitution in env if provided - Type *isPolyPtr( Type *type, const TypeSubstitution *env = 0 ); - /// returns polymorphic type if is pointer to polymorphic type in tyVars, NULL otherwise; will look up substitution in env if provided - Type *isPolyPtr( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); const ast::Type * isPolyPtr( const ast::Type * type, const TypeVarMap & typeVars, const ast::TypeSubstitution * env = 0 ); - - /// if the base type (after dereferencing N >= 0 pointers) is a polymorphic type, returns the base type, NULL otherwise; - /// N will be stored in levels, if provided, will look up substitution in env if provided - Type *hasPolyBase( Type *type, int *levels = 0, const TypeSubstitution *env = 0 ); /// if the base type (after dereferencing N >= 0 pointers) is a polymorphic type in tyVars, returns the base type, NULL otherwise; /// N will be stored in levels, if provided, will look up substitution in env if provided - Type *hasPolyBase( Type *type, const TyVarMap &tyVars, int *levels = 0, const TypeSubstitution *env = 0 ); const ast::Type * hasPolyBase( const ast::Type * type, const TypeVarMap & typeVars, int * levels = 0, const ast::TypeSubstitution * env = 0 ); - /// true iff this type or some base of this type after dereferencing pointers is either polymorphic or a generic type with at least one - /// polymorphic parameter; will look up substitution in env if provided. - bool includesPolyType( Type *type, const TypeSubstitution *env = 0 ); - - /// true iff this type or some base of this type after dereferencing pointers is either polymorphic in tyVars, or a generic type with - /// at least one polymorphic parameter in tyVars; will look up substitution in env if provided. - bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); - /// Returns a pointer to the base FunctionType if ty is the type of a function (or pointer to one), NULL otherwise - FunctionType *getFunctionType( Type *ty ); const ast::FunctionType * getFunctionType( const ast::Type * ty ); - /// If expr (after dereferencing N >= 0 pointers) is a variable expression, returns the variable expression, NULL otherwise; - /// N will be stored in levels, if provided - VariableExpr *getBaseVar( Expression *expr, int *levels = 0 ); - /// true iff types are structurally identical, where TypeInstType's match any type. - bool typesPolyCompatible( Type *aty, Type *bty ); bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ); /// true if arg requires boxing given exprTyVars - bool needsBoxing( Type * param, Type * arg, const TyVarMap &exprTyVars, const TypeSubstitution * env ); bool needsBoxing( const ast::Type * param, const ast::Type * arg, const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ); /// true if arg requires boxing in the call to appExpr - bool needsBoxing( Type * param, Type * arg, ApplicationExpr * appExpr, const TypeSubstitution * env ); bool needsBoxing( const ast::Type * param, const ast::Type * arg, const ast::ApplicationExpr * expr, const ast::TypeSubstitution * subst ); /// Adds the type variable `tyVar` to `tyVarMap` - void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ); void addToTypeVarMap( const ast::TypeDecl * type, TypeVarMap & typeVars ); void addToTypeVarMap( const ast::TypeInstType * type, TypeVarMap & typeVars ); /// Adds the declarations in the forall list of type (and its pointed-to type if it's a pointer type) to `tyVarMap` - void makeTyVarMap( Type *type, TyVarMap &tyVarMap ); void makeTypeVarMap( const ast::Type * type, TypeVarMap & typeVars ); void makeTypeVarMap( const ast::FunctionDecl * decl, TypeVarMap & typeVars ); - - /// Prints type variable map - void printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap ); - - /// Gets the mangled name of this type; alias for SymTab::Mangler::mangleType(). - inline std::string mangleType( const Type *ty ) { return SymTab::Mangler::mangleType( ty ); } /// Gets the name of the sizeof parameter for the type, given its mangled name @@ -136,5 +92,4 @@ /// Gets the name of the layout function for a given aggregate type, given its declaration - inline std::string layoutofName( AggregateDecl *decl ) { return std::string( "_layoutof_" ) + decl->get_name(); } inline std::string layoutofName( ast::AggregateDecl const * decl ) { return std::string( "_layoutof_" ) + decl->name; Index: src/GenPoly/InstantiateGeneric.cc =================================================================== --- src/GenPoly/InstantiateGeneric.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ (revision ) @@ -1,591 +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. -// -// InstantiateGeneric.cc -- -// -// Author : Aaron B. Moss -// Created On : Thu Aug 04 18:33:00 2016 -// Last Modified By : Andrew Beach -// Last Modified On : Wed Jul 16 10:17:00 2020 -// Update Count : 2 -// -#include "InstantiateGeneric.h" - -#include // for assertf, assert -#include // for back_inserter, inserter -#include // for list, _List_const_iterator -#include // for move, pair -#include // for vector - -#include "CodeGen/OperatorTable.h" -#include "Common/PassVisitor.h" // for PassVisitor, WithDeclsToAdd -#include "Common/ScopedMap.h" // for ScopedMap -#include "Common/UniqueName.h" // for UniqueName -#include "Common/utility.h" // for deleteAll, cloneAll -#include "GenPoly.h" // for isPolyType, typesPolyCompatible -#include "InitTweak/InitTweak.h" -#include "ResolvExpr/AdjustExprType.hpp" // for adjustExprType -#include "ResolvExpr/Unify.h" // for typesCompatible -#include "ScopedSet.h" // for ScopedSet, ScopedSet<>::iterator -#include "ScrubTyVars.h" // for ScrubTyVars -#include "SynTree/Declaration.h" // for StructDecl, UnionDecl, TypeDecl -#include "SynTree/Expression.h" // for TypeExpr, Expression -#include "SynTree/Mutator.h" // for mutateAll -#include "SynTree/Type.h" // for StructInstType, UnionInstType -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution -#include "SynTree/Visitor.h" // for acceptAll - - -namespace GenPoly { - - /// Abstracts type equality for a list of parameter types - struct TypeList { - TypeList() : params() {} - TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); } - TypeList( std::list< Type* > &&_params ) : params( _params ) {} - - TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); } - TypeList( TypeList &&that ) : params( std::move( that.params ) ) {} - - /// Extracts types from a list of TypeExpr* - TypeList( const std::list< TypeExpr* >& _params ) : params() { - for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) { - params.push_back( (*param)->get_type()->clone() ); - } - } - - TypeList& operator= ( const TypeList &that ) { - deleteAll( params ); - - params.clear(); - cloneAll( that.params, params ); - - return *this; - } - - TypeList& operator= ( TypeList &&that ) { - deleteAll( params ); - - params = std::move( that.params ); - - return *this; - } - - ~TypeList() { deleteAll( params ); } - - bool operator== ( const TypeList& that ) const { - if ( params.size() != that.params.size() ) return false; - - for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { - if ( ! typesPolyCompatible( *it, *jt ) ) return false; - } - return true; - } - - std::list< Type* > params; ///< Instantiation parameters - }; - - /// Maps a key and a TypeList to the some value, accounting for scope - template< typename Key, typename Value > - class InstantiationMap { - /// Wraps value for a specific (Key, TypeList) combination - typedef std::pair< TypeList, Value* > Instantiation; - /// List of TypeLists paired with their appropriate values - typedef std::vector< Instantiation > ValueList; - /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values - typedef ScopedMap< Key*, ValueList > InnerMap; - - InnerMap instantiations; ///< instantiations - - public: - /// Starts a new scope - void beginScope() { instantiations.beginScope(); } - - /// Ends a scope - void endScope() { instantiations.endScope(); } - - /// Gets the value for the (key, typeList) pair, returns NULL on none such. - Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const { - TypeList typeList( params ); - - // scan scopes for matches to the key - for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) { - for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) { - if ( inst->first == typeList ) return inst->second; - } - } - // no matching instantiations found - return 0; - } - - /// Adds a value for a (key, typeList) pair to the current scope - void insert( Key *key, const std::list< TypeExpr* > ¶ms, Value *value ) { - auto it = instantiations.findAt( instantiations.currentScope(), key ); - if ( it == instantiations.end() ) { - instantiations.insert( key, ValueList{ Instantiation{ TypeList( params ), value } } ); - } else { - it->second.push_back( Instantiation{ TypeList( params ), value } ); - } - } - }; - - /// Possible options for a given specialization of a generic type - enum class genericType { - dtypeStatic, ///< Concrete instantiation based solely on {d,f}type-to-void conversions - concrete, ///< Concrete instantiation requiring at least one parameter type - dynamic ///< No concrete instantiation - }; - - genericType& operator |= ( genericType& gt, const genericType& ht ) { - switch ( gt ) { - case genericType::dtypeStatic: - gt = ht; - break; - case genericType::concrete: - if ( ht == genericType::dynamic ) { gt = genericType::dynamic; } - break; - case genericType::dynamic: - // nothing possible - break; - } - return gt; - } - - /// Add cast to dtype-static member expressions so that type information is not lost in GenericInstantiator - struct FixDtypeStatic final : public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { - Expression * postmutate( MemberExpr * memberExpr ); - - void premutate( ApplicationExpr * appExpr ); - void premutate( AddressExpr * addrExpr ); - - template - Expression * fixMemberExpr( AggrInst * inst, MemberExpr * memberExpr ); - - bool isLvalueArg = false; - }; - - /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately - struct GenericInstantiator final : public WithConstTypeSubstitution, public WithDeclsToAdd, public WithVisitorRef, public WithGuards { - /// Map of (generic type, parameter list) pairs to concrete type instantiations - InstantiationMap< AggregateDecl, AggregateDecl > 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_") {} - - Type* postmutate( StructInstType *inst ); - Type* postmutate( UnionInstType *inst ); - - // fix MemberExprs to use the member from the instantiation - void premutate( MemberExpr * memberExpr ); - Expression * postmutate( MemberExpr * memberExpr ); - - void premutate( FunctionType * ) { - GuardValue( inFunctionType ); - inFunctionType = true; - } - - void beginScope(); - void endScope(); - private: - /// Wrap instantiation lookup for structs - StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)instantiations.lookup( inst->get_baseStruct(), typeSubs ); } - /// Wrap instantiation lookup for unions - UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)instantiations.lookup( inst->get_baseUnion(), typeSubs ); } - /// Wrap instantiation insertion for structs - void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { instantiations.insert( inst->get_baseStruct(), typeSubs, decl ); } - /// Wrap instantiation insertion for unions - void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); } - - void replaceParametersWithConcrete( std::list< Expression* >& params ); - Type *replaceWithConcrete( Type *type, bool doClone ); - - /// Strips a dtype-static aggregate decl of its type parameters, marks it as stripped - void stripDtypeParams( AggregateDecl *base, std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs ); - }; - - void instantiateGeneric( std::list< Declaration* > &translationUnit ) { - PassVisitor fixer; - PassVisitor instantiator; - - mutateAll( translationUnit, fixer ); - mutateAll( translationUnit, instantiator ); - } - - bool isDtypeStatic( const std::list< TypeDecl* >& baseParams ) { - return std::all_of( baseParams.begin(), baseParams.end(), []( TypeDecl * 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( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) { - genericType gt = genericType::dtypeStatic; - - // substitute concrete types for given parameters, and incomplete types for placeholders - std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin(); - std::list< Expression* >::const_iterator param = params.begin(); - for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assert(paramType && "Aggregate parameters should be type expressions"); - - if ( (*baseParam)->isComplete() ) { - // substitute parameter for complete (otype or sized dtype) type - if ( isPolyType( paramType->get_type() ) ) { - // substitute polymorphic parameter type in to generic type - out.push_back( paramType->clone() ); - gt = genericType::dynamic; - } else { - // normalize possibly dtype-static parameter type - out.push_back( new TypeExpr{ - ScrubTyVars::scrubAll( paramType->get_type()->clone() ) } ); - gt |= genericType::concrete; - } - } else switch ( (*baseParam)->get_kind() ) { - case TypeDecl::Dtype: - // can pretend that any incomplete dtype is `void` - out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) ); - break; - case TypeDecl::Ftype: - // can pretend that any ftype is `void (*)(void)` - out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) ); - break; - case 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() && param == params.end(), "Type parameters should match type variables" ); - return gt; - } - - /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out - void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs, - std::list< Declaration* >& out ) { - // substitute types into new members - TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() ); - for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { - Declaration *newMember = (*member)->clone(); - subs.apply(newMember); - out.push_back( newMember ); - } - } - - /// Substitutes types of members according to baseParams => typeSubs, working in-place - void substituteMembers( std::list< Declaration* >& members, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs ) { - // substitute types into new members - TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() ); - for ( std::list< Declaration* >::iterator member = members.begin(); member != members.end(); ++member ) { - subs.apply(*member); - } - } - - /// Strips the instances's type parameters - void stripInstParams( ReferenceToType *inst ) { - deleteAll( inst->get_parameters() ); - inst->get_parameters().clear(); - } - - template< typename AggrInst > - static AggrInst * asForward( AggrInst * decl ) { - if ( !decl->body ) { - return nullptr; - } - decl = decl->clone(); - decl->body = false; - deleteAll( decl->members ); - decl->members.clear(); - return decl; - } - - void GenericInstantiator::stripDtypeParams( AggregateDecl *base, std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs ) { - substituteMembers( base->get_members(), baseParams, typeSubs ); - - // xxx - can't delete type parameters because they may have assertions that are used - // deleteAll( baseParams ); - baseParams.clear(); - - dtypeStatics.insert( base ); - } - - /// xxx - more or less copied from box -- these should be merged with those somehow... - void GenericInstantiator::replaceParametersWithConcrete( std::list< Expression* >& params ) { - for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { - TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assertf(paramType, "Aggregate parameters should be type expressions"); - paramType->set_type( replaceWithConcrete( paramType->get_type(), false ) ); - } - } - - Type *GenericInstantiator::replaceWithConcrete( Type *type, bool doClone ) { - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) { - if ( env && ! inFunctionType ) { - Type *concrete = env->lookup( typeInst->get_name() ); - if ( concrete ) { - return concrete->clone(); - } - else return typeInst->clone(); - } - } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { - if ( doClone ) { - structType = structType->clone(); - } - replaceParametersWithConcrete( structType->get_parameters() ); - return structType; - } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { - if ( doClone ) { - unionType = unionType->clone(); - } - replaceParametersWithConcrete( unionType->get_parameters() ); - return unionType; - } - return type; - } - - - Type* GenericInstantiator::postmutate( StructInstType *inst ) { - // exit early if no need for further mutation - if ( inst->get_parameters().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). - replaceWithConcrete( inst, false ); - - // check for an already-instantiatiated dtype-static type - if ( dtypeStatics.find( inst->get_baseStruct() ) != dtypeStatics.end() ) { - stripInstParams( inst ); - return inst; - } - - // check if type can be concretely instantiated; put substitutions into typeSubs - assertf( inst->get_baseParameters(), "Base struct has parameters" ); - std::list< TypeExpr* > typeSubs; - genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ); - switch ( gt ) { - case genericType::dtypeStatic: - stripDtypeParams( inst->get_baseStruct(), *inst->get_baseParameters(), typeSubs ); - stripInstParams( inst ); - break; - - case genericType::concrete: { - // make concrete instantiation of generic type - StructDecl *concDecl = lookup( inst, typeSubs ); - if ( ! concDecl ) { - // set concDecl to new type, insert type declaration into statements to add - concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); - concDecl->set_body( inst->get_baseStruct()->has_body() ); - substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); - // Forward declare before recursion. (TODO: Only when needed, #199.) - insert( inst, typeSubs, concDecl ); - if ( StructDecl *forwardDecl = asForward( concDecl ) ) { - declsToAddBefore.push_back( forwardDecl ); - } - concDecl->acceptMutator( *visitor ); // recursively instantiate members - declsToAddBefore.push_back( concDecl ); // must occur before declaration is added so that member instantiations appear first - } - StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); - newInst->set_baseStruct( concDecl ); - - delete inst; - inst = newInst; - break; - } - - case genericType::dynamic: - // do nothing - break; - } - - deleteAll( typeSubs ); - return inst; - } - - Type* GenericInstantiator::postmutate( UnionInstType *inst ) { - // exit early if no need for further mutation - if ( inst->get_parameters().empty() ) return inst; - - // check for an already-instantiatiated dtype-static type - if ( dtypeStatics.find( inst->get_baseUnion() ) != dtypeStatics.end() ) { - stripInstParams( inst ); - return inst; - } - - // check if type can be concretely instantiated; put substitutions into typeSubs - assert( inst->get_baseParameters() && "Base union has parameters" ); - std::list< TypeExpr* > typeSubs; - genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ); - switch ( gt ) { - case genericType::dtypeStatic: - stripDtypeParams( inst->get_baseUnion(), *inst->get_baseParameters(), typeSubs ); - stripInstParams( inst ); - break; - - case genericType::concrete: - { - // make concrete instantiation of generic type - UnionDecl *concDecl = lookup( inst, typeSubs ); - if ( ! concDecl ) { - // set concDecl to new type, insert type declaration into statements to add - concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); - concDecl->set_body( inst->get_baseUnion()->has_body() ); - substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); - // Forward declare before recursion. (TODO: Only when needed, #199.) - insert( inst, typeSubs, concDecl ); - if ( UnionDecl *forwardDecl = asForward( concDecl ) ) { - declsToAddBefore.push_back( forwardDecl ); - } - concDecl->acceptMutator( *visitor ); // recursively instantiate members - declsToAddBefore.push_back( concDecl ); // must occur before declaration is added so that member instantiations appear first - } - UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); - newInst->set_baseUnion( concDecl ); - - delete inst; - inst = newInst; - break; - } - case genericType::dynamic: - // do nothing - break; - } - - deleteAll( typeSubs ); - return inst; - } - - namespace { - bool isGenericType( Type * t ) { - if ( StructInstType * inst = dynamic_cast< StructInstType * >( t ) ) { - return ! inst->parameters.empty(); - } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( t ) ) { - return ! inst->parameters.empty(); - } - return false; - } - } - - void GenericInstantiator::premutate( MemberExpr * memberExpr ) { - GuardValue( memberIndex ); - memberIndex = -1; - if ( isGenericType( memberExpr->aggregate->result ) ) { - // find the location of the member - AggregateDecl * aggr = memberExpr->aggregate->result->getAggr(); - std::list< Declaration * > & members = aggr->members; - memberIndex = std::distance( members.begin(), std::find( members.begin(), members.end(), memberExpr->member ) ); - assertf( memberIndex < (int)members.size(), "Could not find member %s in generic type %s", toString( memberExpr->member ).c_str(), toString( memberExpr->aggregate ).c_str() ); - } - } - - Expression * GenericInstantiator::postmutate( MemberExpr * memberExpr ) { - if ( memberIndex != -1 ) { - // using the location from the generic type, find the member in the instantiation and rebuild the member expression - AggregateDecl * aggr = memberExpr->aggregate->result->getAggr(); - assertf( memberIndex < (int)aggr->members.size(), "Instantiation somehow has fewer members than the generic type." ); - Declaration * member = *std::next( aggr->members.begin(), memberIndex ); - assertf( member->name == memberExpr->member->name, "Instantiation has different member order than the generic type. %s / %s", toString( member ).c_str(), toString( memberExpr->member ).c_str() ); - DeclarationWithType * field = strict_dynamic_cast< DeclarationWithType * >( member ); - MemberExpr * ret = new MemberExpr( field, memberExpr->aggregate->clone() ); - ResolvExpr::adjustExprType( ret->result ); // pointer decay - std::swap( ret->env, memberExpr->env ); - delete memberExpr; - return ret; - } - return memberExpr; - } - - void GenericInstantiator::beginScope() { - instantiations.beginScope(); - } - - void GenericInstantiator::endScope() { - instantiations.endScope(); - } - - template< typename AggrInst > - Expression * FixDtypeStatic::fixMemberExpr( AggrInst * inst, MemberExpr * memberExpr ) { - // need to cast dtype-static member expressions to their actual type before that type is erased. - // NOTE: the casts here have the third argument (isGenerated) set to false so that these casts persist until Box, where they are needed. - auto & baseParams = *inst->get_baseParameters(); - if ( isDtypeStatic( baseParams ) ) { - if ( ! ResolvExpr::typesCompatible( memberExpr->result, memberExpr->member->get_type(), SymTab::Indexer() ) ) { - // type of member and type of expression differ - Type * concType = memberExpr->result->clone(); - if ( isLvalueArg ) { - // result must be C lvalue, so make a new reference variable with the correct actual type to replace the member expression - // forall(dtype T) - // struct Ptr { - // T * x - // }; - // Ptr(int) p; - // int i; - // p.x = &i; - // becomes - // int *& _dtype_static_member_0 = (int **)&p.x; - // _dtype_static_member_0 = &i; - // Note: this currently creates more temporaries than is strictly necessary, since it does not check for duplicate uses of the same member expression. - static UniqueName tmpNamer( "_dtype_static_member_" ); - Expression * init = new CastExpr( new AddressExpr( memberExpr ), new PointerType( Type::Qualifiers(), concType->clone() ), false ); - ObjectDecl * tmp = ObjectDecl::newObject( tmpNamer.newName(), new ReferenceType( Type::Qualifiers(), concType ), new SingleInit( init ) ); - stmtsToAddBefore.push_back( new DeclStmt( tmp ) ); - return new VariableExpr( tmp ); - } else { - // can simply add a cast to actual type - return new CastExpr( memberExpr, concType, false ); - } - } - } - return memberExpr; - } - - Expression * FixDtypeStatic::postmutate( MemberExpr * memberExpr ) { - Type * aggrType = memberExpr->aggregate->result; - if ( isGenericType( aggrType ) ) { - if ( StructInstType * inst = dynamic_cast< StructInstType * >( aggrType ) ) { - return fixMemberExpr( inst, memberExpr ); - } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( aggrType ) ) { - return fixMemberExpr( inst, memberExpr ); - } - } - return memberExpr; - } - - void FixDtypeStatic::premutate( ApplicationExpr * appExpr ) { - GuardValue( isLvalueArg ); - isLvalueArg = false; - DeclarationWithType * function = InitTweak::getFunction( appExpr ); - if ( function->linkage == LinkageSpec::Intrinsic && CodeGen::isAssignment( function->name ) ) { - // explicitly visit children because only the first argument must be a C lvalue. - visit_children = false; - appExpr->env = maybeMutate( appExpr->env, *visitor ); - appExpr->result = maybeMutate( appExpr->result, *visitor ); - appExpr->function = maybeMutate( appExpr->function, *visitor ); - isLvalueArg = true; - for ( Expression * arg : appExpr->args ) { - arg = maybeMutate( arg, *visitor ); - isLvalueArg = false; - } - } - } - - void FixDtypeStatic::premutate( AddressExpr * ) { - // argument of & must be C lvalue - GuardValue( isLvalueArg ); - isLvalueArg = true; - } -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/Lvalue.cc =================================================================== --- src/GenPoly/Lvalue.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ (revision ) @@ -1,573 +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. -// -// Lvalue.cc -- -// -// Author : Richard C. Bilson -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Mon May 16 14:09:00 2022 -// Update Count : 8 -// - -#include // for strict_dynamic_cast -#include // for string - -#include "Common/ToString.hpp" // for toCString -#include "Common/UniqueName.h" -#include "Common/PassVisitor.h" -#include "GenPoly.h" // for isPolyType -#include "Lvalue.h" - -#include "InitTweak/InitTweak.h" -#include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet -#include "ResolvExpr/Unify.h" // for unify -#include "ResolvExpr/typeops.h" -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/LinkageSpec.h" // for Spec, isBuiltin, Intrinsic -#include "SynTree/Declaration.h" // for Declaration, FunctionDecl -#include "SynTree/Expression.h" // for Expression, ConditionalExpr -#include "SynTree/Mutator.h" // for mutateAll, Mutator -#include "SynTree/Statement.h" // for ReturnStmt, Statement (ptr o... -#include "SynTree/Type.h" // for PointerType, Type, FunctionType -#include "SynTree/Visitor.h" // for Visitor, acceptAll -#include "Validate/FindSpecialDecls.h" // for dereferenceOperator - -#if 0 -#define PRINT(x) x -#else -#define PRINT(x) -#endif - -namespace GenPoly { - namespace { - // TODO: fold this into the general createDeref function?? - Expression * mkDeref( Expression * arg ) { - if ( Validate::dereferenceOperator ) { - // 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 - VariableExpr * deref = new VariableExpr( Validate::dereferenceOperator ); - deref->result = new PointerType( Type::Qualifiers(), deref->result ); - Type * base = InitTweak::getPointerBase( arg->result ); - assertf( base, "expected pointer type in dereference (type was %s)", toString( arg->result ).c_str() ); - ApplicationExpr * ret = new ApplicationExpr( deref, { arg } ); - delete ret->result; - ret->result = base->clone(); - return ret; - } else { - return UntypedExpr::createDeref( arg ); - } - } - - struct ReferenceConversions final : public WithStmtsToAdd, public WithGuards { - Expression * postmutate( CastExpr * castExpr ); - Expression * postmutate( AddressExpr * addrExpr ); - }; - - /// Intrinsic functions that take reference parameters don't REALLY take reference parameters -- their reference arguments must always be implicitly dereferenced. - struct FixIntrinsicArgs final { - Expression * postmutate( ApplicationExpr * appExpr ); - }; - - struct FixIntrinsicResult final : public WithGuards { - enum { - NoSkip, - Skip, - SkipInProgress - } skip = NoSkip; - - void premutate( AsmExpr * ) { GuardValue( skip ); skip = Skip; } - void premutate( ApplicationExpr * ) { GuardValue( skip ); skip = (skip == Skip) ? SkipInProgress : NoSkip; } - - - Expression * postmutate( ApplicationExpr * appExpr ); - void premutate( FunctionDecl * funcDecl ); - bool inIntrinsic = false; - }; - - /// Replace reference types with pointer types - struct ReferenceTypeElimination final { - Type * postmutate( ReferenceType * refType ); - }; - - /// 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 WithVisitorRef { - Expression * postmutate( AddressExpr * addressExpr ); - Expression * postmutate( MemberExpr * memExpr ); - - template - Expression * applyTransformation( Expression * expr, Expression * arg, Func mkExpr ); - }; - - /// Removes redundant &*/*& pattern that this pass can generate - struct CollapseAddrDeref final { - Expression * postmutate( AddressExpr * addressExpr ); - Expression * postmutate( ApplicationExpr * appExpr ); - }; - - struct AddrRef final : public WithGuards, public WithVisitorRef, public WithShortCircuiting { - void premutate( AddressExpr * addrExpr ); - Expression * postmutate( AddressExpr * addrExpr ); - void premutate( Expression * expr ); - void premutate( ApplicationExpr * appExpr ); - void premutate( SingleInit * init ); - - void handleNonAddr( Expression * ); - - bool first = true; - bool current = false; - int refDepth = 0; - bool addCast = false; - }; - } // namespace - - // Stored elsewhere (Lvalue2, initially false). - extern bool referencesEliminated; - - void convertLvalue( std::list< Declaration* > & translationUnit ) { - PassVisitor refCvt; - PassVisitor elim; - PassVisitor genLval; - PassVisitor fixer; - PassVisitor collapser; - PassVisitor addrRef; - PassVisitor intrinsicResults; - mutateAll( translationUnit, intrinsicResults ); - mutateAll( translationUnit, addrRef ); - mutateAll( translationUnit, refCvt ); - mutateAll( translationUnit, fixer ); - mutateAll( translationUnit, collapser ); - mutateAll( translationUnit, genLval ); - mutateAll( translationUnit, elim ); // last because other passes need reference types to work - - // from this point forward, no other pass should create reference types. - referencesEliminated = true; - } - - Expression * generalizedLvalue( Expression * expr ) { - PassVisitor genLval; - return expr->acceptMutator( genLval ); - } - - namespace { - // true for intrinsic function calls that return an lvalue in C - bool isIntrinsicReference( Expression * expr ) { - // known intrinsic-reference prelude functions - static std::set lvalueFunctions = { "*?", "?[?]" }; - if ( UntypedExpr * untyped = dynamic_cast< UntypedExpr * >( expr ) ) { - std::string fname = InitTweak::getFunctionName( untyped ); - return lvalueFunctions.count(fname); - } else if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * > ( expr ) ) { - if ( DeclarationWithType * func = InitTweak::getFunction( appExpr ) ) { - return func->linkage == LinkageSpec::Intrinsic && lvalueFunctions.count(func->name); - } - } - return false; - } - - Expression * FixIntrinsicResult::postmutate( ApplicationExpr * appExpr ) { - if ( skip != SkipInProgress && isIntrinsicReference( appExpr ) ) { - // eliminate reference types from intrinsic applications - now they return lvalues - ReferenceType * result = strict_dynamic_cast< ReferenceType * >( appExpr->result ); - appExpr->result = result->base->clone(); - if ( ! inIntrinsic ) { - // 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 - Expression * ret = new CastExpr( appExpr, result ); - std::swap( ret->env, appExpr->env ); - return ret; - } - delete result; - } - return appExpr; - } - - void FixIntrinsicResult::premutate( FunctionDecl * funcDecl ) { - GuardValue( inIntrinsic ); - inIntrinsic = funcDecl->linkage == LinkageSpec::Intrinsic; - } - - Expression * FixIntrinsicArgs::postmutate( ApplicationExpr * appExpr ) { - // intrinsic functions don't really take reference-typed parameters, so they require an implicit dereference on their arguments. - if ( DeclarationWithType * function = InitTweak::getFunction( appExpr ) ) { - FunctionType * ftype = GenPoly::getFunctionType( function->get_type() ); - assertf( ftype, "Function declaration does not have function type." ); - // can be of differing lengths only when function is variadic - assertf( ftype->parameters.size() == appExpr->args.size() || ftype->isVarArgs, "ApplicationExpr args do not match formal parameter type." ); - - - unsigned int i = 0; - const unsigned int end = ftype->parameters.size(); - - /// The for loop may eagerly dereference the iterators and fail on empty lists - if(i == end) { return appExpr; } - for ( auto p : unsafe_group_iterate( appExpr->args, ftype->parameters ) ) { - Expression *& arg = std::get<0>( p ); - Type * formal = std::get<1>( p )->get_type(); - PRINT( - std::cerr << "pair<0>: " << arg << std::endl; - std::cerr << " -- " << arg->result << std::endl; - std::cerr << "pair<1>: " << formal << std::endl; - ) - if ( dynamic_cast( formal ) ) { - 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 ( function->linkage != LinkageSpec::Intrinsic && 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 - - // NOTE: previously, this condition fixed - // void f(int *&); - // int & x = ...; - // f(&x); - // But now this is taken care of by a reference cast added by AddrRef. 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 AddressExpr( arg ); - // } else if ( function->get_linkage() == LinkageSpec::Intrinsic && InitTweak::getPointerBase( arg->result ) ) { - } else if ( function->linkage == LinkageSpec::Intrinsic && 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; - ) - Type * baseType = InitTweak::getPointerBase( arg->result ); - assertf( baseType, "parameter is reference, arg must be pointer or reference: %s", toString( arg->result ).c_str() ); - PointerType * ptrType = new PointerType( Type::Qualifiers(), baseType->clone() ); - delete arg->result; - arg->result = ptrType; - arg = mkDeref( arg ); - // assertf( arg->result->referenceDepth() == 0, "Reference types should have been eliminated from intrinsic function calls, but weren't: %s", toCString( arg->result ) ); - } - } - ++i; - if (i == end) break; - } - } - return appExpr; - } - - // idea: &&&E: get outer &, inner & - // at inner &, record depth D of reference type of argument of & - // at outer &, add D derefs. - void AddrRef::handleNonAddr( Expression * ) { - // 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 ); - GuardValue( first ); - current = false; - first = true; - } - - void AddrRef::premutate( Expression * expr ) { - handleNonAddr( expr ); - GuardValue( addCast ); - addCast = false; - } - - void AddrRef::premutate( AddressExpr * ) { - GuardValue( current ); - GuardValue( first ); - current = first; // is this the first address-of in the chain? - first = false; // from here out, no longer possible for next address-of to be first in chain - if ( current ) { // this is the outermost address-of in a chain - GuardValue( refDepth ); - refDepth = 0; // set depth to 0 so that postmutate can find the innermost address-of easily - } - } - - Expression * AddrRef::postmutate( AddressExpr * addrExpr ) { - PRINT( std::cerr << "addr ref at " << addrExpr << std::endl; ) - if ( refDepth == 0 ) { - PRINT( std::cerr << "depth 0, get new depth..." << std::endl; ) - // this is the innermost address-of in a chain, record depth D - if ( ! isIntrinsicReference( addrExpr->arg ) ) { - // try to avoid ?[?] - // xxx - 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 = addrExpr->arg->result->referenceDepth(); - PRINT( std::cerr << "arg not intrinsic reference, new depth is: " << refDepth << std::endl; ) - } else { - assertf( false, "AddrRef : address-of should not have intrinsic reference argument: %s", toCString( addrExpr->arg ) ); - } - } - if ( current ) { // this is the outermost address-of in a chain - PRINT( std::cerr << "current, depth is: " << refDepth << std::endl; ) - Expression * ret = addrExpr; - while ( refDepth ) { - // add one dereference for each - ret = mkDeref( 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 && addrExpr->result->referenceDepth() != 0 ) { - PRINT( std::cerr << "adding cast to " << addrExpr->result << std::endl; ) - return new CastExpr( ret, addrExpr->result->clone() ); - } - return ret; - } - PRINT( std::cerr << "not current..." << std::endl; ) - return addrExpr; - } - - void AddrRef::premutate( ApplicationExpr * appExpr ) { - visit_children = false; - GuardValue( addCast ); - handleNonAddr( appExpr ); - for ( Expression *& arg : appExpr->args ) { - // each argument with address-of requires a cast - addCast = true; - arg = arg->acceptMutator( *visitor ); - } - } - - void AddrRef::premutate( SingleInit * ) { - GuardValue( addCast ); - // each initialization context with address-of requires a cast - addCast = true; - } - - - Expression * ReferenceConversions::postmutate( AddressExpr * addrExpr ) { - // 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. - return addrExpr; - } - - Expression * ReferenceConversions::postmutate( CastExpr * castExpr ) { - // xxx - is it possible to convert directly between reference types with a different base? E.g., - // int x; - // (double&)x; - // At the moment, I 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. - - Type * destType = castExpr->result; - Type * srcType = castExpr->arg->result; - assertf( destType, "Cast to no type in: %s", toCString( castExpr ) ); - assertf( srcType, "Cast from no type in: %s", toCString( castExpr ) ); - int depth1 = destType->referenceDepth(); - int depth2 = srcType->referenceDepth(); - int diff = depth1 - depth2; - - if ( diff > 0 && ! castExpr->arg->get_lvalue() ) { - // rvalue to reference conversion -- introduce temporary - // know that reference depth of cast argument is 0, need to introduce n temporaries for reference depth of n, e.g. - // (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( castExpr->arg->location, Warning::RvalueToReferenceConversion, toCString( castExpr->arg ) ); - - static UniqueName tempNamer( "__ref_tmp_" ); - ObjectDecl * temp = ObjectDecl::newObject( tempNamer.newName(), castExpr->arg->result->clone(), new SingleInit( castExpr->arg ) ); - PRINT( std::cerr << "made temp: " << temp << std::endl; ) - stmtsToAddBefore.push_back( new DeclStmt( temp ) ); - for ( int i = 0; i < depth1-1; i++ ) { // xxx - maybe this should be diff-1? check how this works with reference type for srcType - ObjectDecl * newTemp = ObjectDecl::newObject( tempNamer.newName(), new ReferenceType( Type::Qualifiers(), temp->type->clone() ), new SingleInit( new AddressExpr( new VariableExpr( temp ) ) ) ); - PRINT( std::cerr << "made temp" << i << ": " << newTemp << std::endl; ) - stmtsToAddBefore.push_back( new DeclStmt( newTemp ) ); - temp = newTemp; - } - // update diff so that remaining code works out correctly - castExpr->arg = new VariableExpr( temp ); - PRINT( std::cerr << "update cast to: " << castExpr << std::endl; ) - srcType = castExpr->arg->result; - depth2 = srcType->referenceDepth(); - diff = depth1 - depth2; - assert( diff == 1 ); - } - - // handle conversion between different depths - PRINT ( - if ( depth1 || depth2 ) { - std::cerr << "destType: " << destType << " / srcType: " << srcType << std::endl; - std::cerr << "depth: " << depth1 << " / " << depth2 << std::endl; - } - ) - if ( diff > 0 ) { - // conversion to type with more depth (e.g. int & -> int &&): add address-of for each level of difference - Expression * ret = castExpr->arg; - for ( int i = 0; i < diff; ++i ) { - ret = new AddressExpr( ret ); - } - if ( castExpr->arg->get_lvalue() && ! ResolvExpr::typesCompatible( srcType, strict_dynamic_cast( destType )->base, SymTab::Indexer() ) ) { - // must keep cast if cast-to type is different from the actual type - castExpr->arg = ret; - return castExpr; - } - ret->env = castExpr->env; - delete ret->result; - ret->result = castExpr->result; - castExpr->env = nullptr; - castExpr->arg = nullptr; - castExpr->result = nullptr; - delete castExpr; - return ret; - } else if ( diff < 0 ) { - // conversion to type with less depth (e.g. int && -> int &): add dereferences for each level of difference - diff = -diff; // care only about magnitude now - Expression * ret = castExpr->arg; - for ( int i = 0; i < diff; ++i ) { - ret = mkDeref( ret ); - // xxx - try removing one reference here? actually, looks like mkDeref already does this, so more closely look at the types generated. - } - if ( ! ResolvExpr::typesCompatibleIgnoreQualifiers( destType->stripReferences(), srcType->stripReferences(), SymTab::Indexer() ) ) { - // must keep cast if types are different - castExpr->arg = ret; - return castExpr; - } - ret->env = castExpr->env; - delete ret->result; - ret->result = castExpr->result; - assert( ret->get_lvalue() ); // ensure result is lvalue - castExpr->env = nullptr; - castExpr->arg = nullptr; - castExpr->result = nullptr; - delete castExpr; - return ret; - } else { - assert( diff == 0 ); - // conversion between references of the same depth - if ( ResolvExpr::typesCompatible( castExpr->result, castExpr->arg->result, SymTab::Indexer() ) && castExpr->isGenerated ) { - // Remove useless generated casts - PRINT( - std::cerr << "types are compatible, removing cast: " << castExpr << std::endl; - std::cerr << "-- " << castExpr->result << std::endl; - std::cerr << "-- " << castExpr->arg->result << std::endl; - ) - Expression * ret = castExpr->arg; - castExpr->arg = nullptr; - std::swap( castExpr->env, ret->env ); - delete castExpr; - return ret; - } - return castExpr; - } - } - - Type * ReferenceTypeElimination::postmutate( ReferenceType * refType ) { - Type * base = refType->base; - Type::Qualifiers qualifiers = refType->get_qualifiers(); - refType->base = nullptr; - delete refType; - return new PointerType( qualifiers, base ); - } - - template - Expression * GeneralizedLvalue::applyTransformation( Expression * expr, Expression * arg, Func mkExpr ) { - if ( CommaExpr * commaExpr = dynamic_cast< CommaExpr * >( arg ) ) { - Expression * arg1 = commaExpr->arg1->clone(); - Expression * arg2 = commaExpr->arg2->clone(); - Expression * ret = new CommaExpr( arg1, mkExpr( arg2 )->acceptMutator( *visitor ) ); - ret->env = expr->env; - expr->env = nullptr; - delete expr; - return ret; - } else if ( ConditionalExpr * condExpr = dynamic_cast< ConditionalExpr * >( arg ) ) { - Expression * arg1 = condExpr->arg1->clone(); - Expression * arg2 = condExpr->arg2->clone(); - Expression * arg3 = condExpr->arg3->clone(); - ConditionalExpr * ret = new ConditionalExpr( arg1, mkExpr( arg2 )->acceptMutator( *visitor ), mkExpr( arg3 )->acceptMutator( *visitor ) ); - ret->env = expr->env; - expr->env = nullptr; - delete expr; - - // conditional expr type may not be either of the argument types, need to unify - using namespace ResolvExpr; - Type* commonType = nullptr; - TypeEnvironment newEnv; - AssertionSet needAssertions, haveAssertions; - OpenVarSet openVars; - unify( ret->arg2->result, ret->arg3->result, newEnv, needAssertions, haveAssertions, openVars, SymTab::Indexer(), commonType ); - ret->result = commonType ? commonType : ret->arg2->result->clone(); - return ret; - } - return expr; - } - - Expression * GeneralizedLvalue::postmutate( MemberExpr * memExpr ) { - return applyTransformation( memExpr, memExpr->aggregate, [=]( Expression * aggr ) { return new MemberExpr( memExpr->member, aggr ); } ); - } - - Expression * GeneralizedLvalue::postmutate( AddressExpr * addrExpr ) { - return applyTransformation( addrExpr, addrExpr->arg, []( Expression * arg ) { return new AddressExpr( arg ); } ); - } - - Expression * CollapseAddrDeref::postmutate( AddressExpr * addrExpr ) { - Expression * arg = addrExpr->arg; - if ( isIntrinsicReference( arg ) ) { - std::string fname = InitTweak::getFunctionName( arg ); - if ( fname == "*?" ) { - Expression *& arg0 = InitTweak::getCallArg( arg, 0 ); - Expression * ret = arg0; - ret->set_env( addrExpr->env ); - arg0 = nullptr; - addrExpr->env = nullptr; - delete addrExpr; - return ret; - } - } else if ( CastExpr * castExpr = dynamic_cast< CastExpr * > ( 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 ( InitTweak::getPointerBase( castExpr->result ) ) { - addrExpr->arg = castExpr->arg; - castExpr->arg = addrExpr; - castExpr->result = new PointerType( Type::Qualifiers(), castExpr->result ); - return castExpr; - } - } - return addrExpr; - } - - Expression * CollapseAddrDeref::postmutate( ApplicationExpr * appExpr ) { - if ( isIntrinsicReference( appExpr ) ) { - std::string fname = InitTweak::getFunctionName( appExpr ); - if ( fname == "*?" ) { - Expression * arg = InitTweak::getCallArg( appExpr, 0 ); - // xxx - this isn't right, because it can remove casts that should be there... - // while ( CastExpr * castExpr = dynamic_cast< CastExpr * >( arg ) ) { - // arg = castExpr->get_arg(); - // } - if ( AddressExpr * addrExpr = dynamic_cast< AddressExpr * >( arg ) ) { - Expression * ret = addrExpr->arg; - ret->env = appExpr->env; - addrExpr->arg = nullptr; - appExpr->env = nullptr; - delete appExpr; - return ret; - } - } - } - return appExpr; - } - } // namespace -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/ScrubTyVars.cc =================================================================== --- src/GenPoly/ScrubTyVars.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/ScrubTyVars.cc (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -21,97 +21,6 @@ #include "ScrubTyVars.h" #include "SymTab/Mangler.h" // for mangleType -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Typ... -#include "SynTree/Expression.h" // for Expression (ptr only), NameExpr -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for PointerType, TypeInstType, Type namespace GenPoly { - Type * ScrubTyVars::postmutate( TypeInstType * typeInst ) { - if ( ! tyVars ) { - if ( typeInst->get_isFtype() ) { - delete typeInst; - return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ); - } else { - PointerType * ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) ); - delete typeInst; - return ret; - } - } - - TyVarMap::const_iterator tyVar = tyVars->find( typeInst->name ); - if ( tyVar != tyVars->end() ) { - switch ( tyVar->second.kind ) { - case TypeDecl::Dtype: - case TypeDecl::Ttype: - { - PointerType * ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) ); - delete typeInst; - return ret; - } - case TypeDecl::Ftype: - delete typeInst; - return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ); - default: - assertf(false, "Unhandled tyvar kind: %d", tyVar->second.kind); - } // switch - } // if - return typeInst; - } - - Type * ScrubTyVars::mutateAggregateType( Type * ty ) { - if ( shouldScrub( ty ) ) { - PointerType * ret = new PointerType( Type::Qualifiers(), new VoidType( ty->get_qualifiers() ) ); - delete ty; - return ret; - } - return ty; - } - - Type * ScrubTyVars::postmutate( StructInstType * structInst ) { - return mutateAggregateType( structInst ); - } - - Type * ScrubTyVars::postmutate( UnionInstType * unionInst ) { - return mutateAggregateType( unionInst ); - } - - void ScrubTyVars::primeBaseScrub( Type * type ) { - // need to determine whether type needs to be scrubbed to determine whether - // automatic recursion is necessary - if ( Type * t = shouldScrub( type ) ) { - visit_children = false; - GuardValue( dynType ); - dynType = t; - } - } - - Expression * ScrubTyVars::postmutate( SizeofExpr * szeof ) { - // sizeof( T ) => _sizeof_T parameter, which is the size of T - if ( dynType ) { - Expression *expr = new NameExpr( sizeofName( mangleType( dynType ) ) ); - return expr; - } // if - return szeof; - } - - Expression * ScrubTyVars::postmutate( AlignofExpr * algnof ) { - // alignof( T ) => _alignof_T parameter, which is the alignment of T - if ( dynType ) { - Expression *expr = new NameExpr( alignofName( mangleType( dynType ) ) ); - return expr; - } // if - return algnof; - } - - Type * ScrubTyVars::postmutate( PointerType * pointer ) { - if ( dynType ) { - Type * ret = dynType->acceptMutator( *visitor ); - ret->get_qualifiers() |= pointer->get_qualifiers(); - pointer->base = nullptr; - delete pointer; - return ret; - } - return pointer; - } namespace { Index: src/GenPoly/ScrubTyVars.h =================================================================== --- src/GenPoly/ScrubTyVars.h (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/ScrubTyVars.h (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -19,93 +19,7 @@ #include "AST/Fwd.hpp" // for Node -#include "Common/PassVisitor.h" #include "GenPoly.h" // for TyVarMap, isPolyType, isDynType -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for Type (ptr only), PointerType (ptr only) - -class AlignofExpr; -class Expression; -class SizeofExpr; namespace GenPoly { - struct ScrubTyVars : public WithVisitorRef, public WithShortCircuiting, public WithGuards { - /// Whether to scrub all type variables from the provided map, dynamic type variables from the provided map, or all type variables - enum ScrubMode { FromMap, DynamicFromMap, All }; - - ScrubTyVars() : tyVars(nullptr), mode( All ) {} - - ScrubTyVars( const TyVarMap &tyVars, ScrubMode mode = FromMap ): tyVars( &tyVars ), mode( mode ) {} - - public: - /// For all polymorphic types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type, - /// and sizeof/alignof expressions with the proper variable - template< typename SynTreeClass > - static SynTreeClass *scrub( SynTreeClass *target, const TyVarMap &tyVars ); - - /// For all dynamic-layout types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type, - /// and sizeof/alignof expressions with the proper variable - template< typename SynTreeClass > - static SynTreeClass *scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ); - - /// For all polymorphic types, replaces generic types, dtypes, and ftypes with the appropriate void type, - /// and sizeof/alignof expressions with the proper variable - template< typename SynTreeClass > - static SynTreeClass *scrubAll( SynTreeClass *target ); - - /// determine if children should be visited based on whether base type should be scrubbed. - void primeBaseScrub( Type * ); - - void premutate( TypeInstType * ) { visit_children = false; } - void premutate( StructInstType * ) { visit_children = false; } - void premutate( UnionInstType * ) { visit_children = false; } - void premutate( SizeofExpr * szeof ) { primeBaseScrub( szeof->type ); } - void premutate( AlignofExpr * algnof ) { primeBaseScrub( algnof->type ); } - void premutate( PointerType * pointer ) { primeBaseScrub( pointer->base ); } - - Type * postmutate( TypeInstType * typeInst ); - Type * postmutate( StructInstType * structInst ); - Type * postmutate( UnionInstType * unionInst ); - Expression * postmutate( SizeofExpr * szeof ); - Expression * postmutate( AlignofExpr * algnof ); - Type * postmutate( PointerType * pointer ); - - private: - /// Returns the type if it should be scrubbed, NULL otherwise. - Type* shouldScrub( Type *ty ) { - switch ( mode ) { - case FromMap: return isPolyType( ty, *tyVars ); - case DynamicFromMap: return isDynType( ty, *tyVars ); - case All: return isPolyType( ty ); - } - assert(false); return nullptr; // unreachable - // return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars ); - } - - /// Mutates (possibly generic) aggregate types appropriately - Type* mutateAggregateType( Type *ty ); - - const TyVarMap *tyVars; ///< Type variables to scrub - ScrubMode mode; ///< which type variables to scrub? [FromMap] - - Type * dynType = nullptr; ///< result of shouldScrub - }; - - template< typename SynTreeClass > - SynTreeClass * ScrubTyVars::scrub( SynTreeClass *target, const TyVarMap &tyVars ) { - PassVisitor scrubber( tyVars ); - return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) ); - } - - template< typename SynTreeClass > - SynTreeClass * ScrubTyVars::scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ) { - PassVisitor scrubber( tyVars, ScrubTyVars::DynamicFromMap ); - return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) ); - } - - template< typename SynTreeClass > - SynTreeClass * ScrubTyVars::scrubAll( SynTreeClass *target ) { - PassVisitor scrubber; - return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) ); - } // ScrubMode and scrubTypeVarsBase are internal. Index: src/GenPoly/Specialize.cc =================================================================== --- src/GenPoly/Specialize.cc (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ (revision ) @@ -1,338 +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. -// -// Specialize.cc -- -// -// Author : Richard C. Bilson -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Thr Jul 2 17:42:00 2020 -// Update Count : 33 -// - -#include // for assert, assertf -#include // for back_insert_iterator, back_i... -#include // for _Rb_tree_iterator, _Rb_tree_... -#include // for unique_ptr -#include // for string -#include // for get -#include // for pair - -#include "Common/PassVisitor.h" -#include "Common/UniqueName.h" // for UniqueName -#include "Common/utility.h" // for group_iterate -#include "GenPoly.h" // for getFunctionType -#include "InitTweak/InitTweak.h" // for isIntrinsicCallExpr -#include "ResolvExpr/FindOpenVars.h" // for findOpenVars -#include "ResolvExpr/TypeEnvironment.h" // for OpenVarSet, AssertionSet -#include "Specialize.h" -#include "SynTree/LinkageSpec.h" // for C -#include "SynTree/Attribute.h" // for Attribute -#include "SynTree/Declaration.h" // for FunctionDecl, DeclarationWit... -#include "SynTree/Expression.h" // for ApplicationExpr, Expression -#include "SynTree/Label.h" // for Label -#include "SynTree/Mutator.h" // for mutateAll -#include "SynTree/Statement.h" // for CompoundStmt, DeclStmt, Expr... -#include "SynTree/Type.h" // for FunctionType, TupleType, Type -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution -#include "SynTree/Visitor.h" // for Visitor - -namespace GenPoly { - struct Specialize final : public WithConstTypeSubstitution, - public WithDeclsToAdd, public WithVisitorRef { - Expression * postmutate( ApplicationExpr *applicationExpr ); - Expression * postmutate( CastExpr *castExpr ); - - void handleExplicitParams( ApplicationExpr *appExpr ); - Expression * createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ); - Expression * doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams ); - - std::string paramPrefix = "_p"; - }; - - /// Looks up open variables in actual type, returning true if any of them are bound in the environment or formal type. - bool needsPolySpecialization( Type *formalType, Type *actualType, const TypeSubstitution *env ) { - if ( env ) { - using namespace ResolvExpr; - OpenVarSet openVars, closedVars; - AssertionSet need, have; - findOpenVars( formalType, openVars, closedVars, need, have, false ); - findOpenVars( actualType, openVars, closedVars, need, have, true ); - for ( OpenVarSet::const_iterator openVar = openVars.begin(); openVar != openVars.end(); ++openVar ) { - Type *boundType = env->lookup( openVar->first ); - if ( ! boundType ) continue; - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( boundType ) ) { - // bound to another type variable - if ( closedVars.find( typeInst->get_name() ) == closedVars.end() ) { - // bound to a closed variable => must specialize - return true; - } // if - } else { - // variable is bound to a concrete type => must specialize - return true; - } // if - } // for - // none of the type variables are bound - return false; - } else { - // no env - return false; - } // if - } - - /// True if both types have the same structure, but not necessarily the same types. - /// That is, either both types are tuple types with the same size (recursively), or - /// both are not tuple types. - bool matchingTupleStructure( Type * t1, Type * t2 ) { - TupleType * tuple1 = dynamic_cast< TupleType * >( t1 ); - TupleType * tuple2 = dynamic_cast< TupleType * >( t2 ); - if ( tuple1 && tuple2 ) { - if ( tuple1->size() != tuple2->size() ) return false; - for ( auto types : group_iterate( tuple1->get_types(), tuple2->get_types() ) ) { - if ( ! matchingTupleStructure( std::get<0>( types ), std::get<1>( types ) ) ) return false; - } - return true; - } else if ( ! tuple1 && ! tuple2 ) return true; - return false; - } - - // walk into tuple type and find the number of components - size_t singleParameterSize( Type * type ) { - if ( TupleType * tt = dynamic_cast< TupleType * >( type ) ) { - size_t sz = 0; - for ( Type * t : *tt ) { - sz += singleParameterSize( t ); - } - return sz; - } else { - return 1; - } - } - - // find the total number of components in a parameter list - size_t functionParameterSize( FunctionType * ftype ) { - size_t sz = 0; - for ( DeclarationWithType * p : ftype->get_parameters() ) { - sz += singleParameterSize( p->get_type() ); - } - return sz; - } - - bool needsTupleSpecialization( Type *formalType, 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 ( FunctionType * fftype = getFunctionType( formalType ) ) { - if ( fftype->isTtype() ) return true; - // conversion of 0 (null) to function type does not require tuple specialization - if ( dynamic_cast< ZeroType * >( actualType ) ) return false; - FunctionType * aftype = getFunctionType( actualType->stripReferences() ); - assertf( aftype, "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( fftype ) != functionParameterSize( aftype ) ) return false; - // tuple-parameter sizes are the same, but actual parameter sizes differ - must tuple specialize - if ( fftype->parameters.size() != aftype->parameters.size() ) return true; - // total parameter size can be the same, while individual parameters can have different structure - for ( auto params : group_iterate( fftype->parameters, aftype->parameters ) ) { - DeclarationWithType * formal = std::get<0>(params); - DeclarationWithType * actual = std::get<1>(params); - if ( ! matchingTupleStructure( formal->get_type(), actual->get_type() ) ) return true; - } - } - return false; - } - - bool needsSpecialization( Type *formalType, Type *actualType, const TypeSubstitution *env ) { - return needsPolySpecialization( formalType, actualType, env ) || needsTupleSpecialization( formalType, actualType ); - } - - Expression * Specialize::doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams ) { - assertf( actual->result, "attempting to specialize an untyped expression" ); - if ( needsSpecialization( formalType, actual->get_result(), env ) ) { - if ( FunctionType *funType = getFunctionType( formalType ) ) { - if ( ApplicationExpr * appExpr = dynamic_cast( actual ) ) { - return createThunkFunction( funType, appExpr->get_function(), inferParams ); - } else if ( VariableExpr * varExpr = dynamic_cast( actual ) ) { - return createThunkFunction( funType, varExpr, inferParams ); - } else { - // This likely won't work, as anything that could build an ApplicationExpr probably hit one of the previous two branches - return createThunkFunction( funType, actual, inferParams ); - } - } else { - return actual; - } // if - } else { - return actual; - } // if - } - - /// restructures the arguments to match the structure of the formal parameters of the actual function. - /// [begin, end) are the exploded arguments. - template< typename Iterator, typename OutIterator > - void structureArg( Type * type, Iterator & begin, Iterator end, OutIterator out ) { - if ( TupleType * tuple = dynamic_cast< TupleType * >( type ) ) { - std::list< Expression * > exprs; - for ( Type * t : *tuple ) { - structureArg( t, begin, end, back_inserter( exprs ) ); - } - *out++ = new TupleExpr( exprs ); - } else { - assertf( begin != end, "reached the end of the arguments while structuring" ); - *out++ = *begin++; - } - } - - /// explode assuming simple cases: either type is pure tuple (but not tuple expr) or type is non-tuple. - template< typename OutputIterator > - void explodeSimple( Expression * expr, OutputIterator out ) { - if ( TupleType * tupleType = dynamic_cast< TupleType * > ( expr->get_result() ) ) { - // tuple type, recursively index into its components - for ( unsigned int i = 0; i < tupleType->size(); i++ ) { - explodeSimple( new TupleIndexExpr( expr->clone(), i ), out ); - } - delete expr; - } else { - // non-tuple type - output a clone of the expression - *out++ = expr; - } - } - - /// Generates a thunk that calls `actual` with type `funType` and returns its address - Expression * Specialize::createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) { - static UniqueName thunkNamer( "_thunk" ); - - FunctionType *newType = funType->clone(); - if ( env ) { - // it is important to replace only occurrences of type variables that occur free in the - // thunk's type - env->applyFree( newType ); - } // if - // create new thunk with same signature as formal type (C linkage, empty body) - FunctionDecl *thunkFunc = new FunctionDecl( thunkNamer.newName(), Type::StorageClasses(), LinkageSpec::C, newType, new CompoundStmt() ); - thunkFunc->fixUniqueId(); - - // thunks may be generated and not used - silence warning with attribute - thunkFunc->get_attributes().push_back( new Attribute( "unused" ) ); - - // Thunks at the global level must be static to avoid collisions between files. - // (Conversly thunks inside a function must be unique and not static.) - thunkFunc->storageClasses.is_static = !isInFunction(); - - // thread thunk parameters into call to actual function, naming thunk parameters as we go - UniqueName paramNamer( paramPrefix ); - ApplicationExpr *appExpr = new ApplicationExpr( actual ); - - FunctionType * actualType = getFunctionType( actual->get_result() )->clone(); - if ( env ) { - // need to apply the environment to the actual function's type, since it may itself be polymorphic - env->apply( actualType ); - } - std::unique_ptr< FunctionType > actualTypeManager( actualType ); // for RAII - std::list< DeclarationWithType * >::iterator actualBegin = actualType->get_parameters().begin(); - std::list< DeclarationWithType * >::iterator actualEnd = actualType->get_parameters().end(); - - std::list< Expression * > args; - for ( DeclarationWithType* param : thunkFunc->get_functionType()->get_parameters() ) { - // name each thunk parameter and explode it - these are then threaded back into the actual function call. - param->set_name( paramNamer.newName() ); - explodeSimple( new VariableExpr( param ), back_inserter( args ) ); - } - - // walk parameters to the actual function alongside the exploded thunk parameters and restructure the arguments to match the actual parameters. - std::list< Expression * >::iterator argBegin = args.begin(), argEnd = args.end(); - for ( ; actualBegin != actualEnd; ++actualBegin ) { - structureArg( (*actualBegin)->get_type(), argBegin, argEnd, back_inserter( appExpr->get_args() ) ); - } - assertf( argBegin == argEnd, "Did not structure all arguments." ); - - appExpr->env = TypeSubstitution::newFromExpr( appExpr, env ); - if ( inferParams ) { - appExpr->inferParams = *inferParams; - } // if - - // Handle any specializations that may still be present. - { - std::string oldParamPrefix = paramPrefix; - paramPrefix += "p"; - std::list< Declaration * > oldDecls; - oldDecls.splice( oldDecls.end(), declsToAddBefore ); - - appExpr->acceptMutator( *visitor ); - // Write recursive specializations into the thunk body. - for ( Declaration * decl : declsToAddBefore ) { - thunkFunc->statements->kids.push_back( new DeclStmt( decl ) ); - } - - declsToAddBefore = std::move( oldDecls ); - paramPrefix = oldParamPrefix; - } - - // add return (or valueless expression) to the thunk - Statement *appStmt; - if ( funType->returnVals.empty() ) { - appStmt = new ExprStmt( appExpr ); - } else { - appStmt = new ReturnStmt( appExpr ); - } // if - thunkFunc->statements->kids.push_back( appStmt ); - - // Add the thunk definition (converted to DeclStmt if appproprate). - declsToAddBefore.push_back( thunkFunc ); - // return address of thunk function as replacement expression - return new AddressExpr( new VariableExpr( thunkFunc ) ); - } - - void Specialize::handleExplicitParams( ApplicationExpr *appExpr ) { - // create thunks for the explicit parameters - assert( appExpr->function->result ); - FunctionType *function = getFunctionType( appExpr->function->result ); - assert( function ); - std::list< DeclarationWithType* >::iterator formal; - std::list< Expression* >::iterator actual; - for ( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) { - *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->inferParams ); - } - } - - Expression * Specialize::postmutate( ApplicationExpr *appExpr ) { - if ( ! InitTweak::isIntrinsicCallExpr( appExpr ) ) { - // create thunks for the inferred parameters - // don't need to do this for intrinsic calls, because they aren't actually passed - // need 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 appExpr's inferParams and pass them to handleExplicitParams. - handleExplicitParams( appExpr ); - for ( InferredParams::iterator inferParam = appExpr->inferParams.begin(); inferParam != appExpr->inferParams.end(); ++inferParam ) { - inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, &inferParam->second.expr->inferParams ); - } - } - return appExpr; - } - - Expression * Specialize::postmutate( CastExpr *castExpr ) { - if ( castExpr->result->isVoid() ) { - // can't specialize if we don't have a return value - return castExpr; - } - Expression *specialized = doSpecialization( castExpr->result, castExpr->arg, &castExpr->inferParams ); - if ( specialized != castExpr->arg ) { - // assume here that the specialization incorporates the cast - return specialized; - } else { - return castExpr; - } - } - - void convertSpecializations( std::list< Declaration* >& translationUnit ) { - PassVisitor spec; - mutateAll( translationUnit, spec ); - } -} // namespace GenPoly - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/GenPoly/SpecializeNew.cpp =================================================================== --- src/GenPoly/SpecializeNew.cpp (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/SpecializeNew.cpp (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -23,5 +23,4 @@ #include "GenPoly/GenPoly.h" // for getFunctionType #include "ResolvExpr/FindOpenVars.h" // for findOpenVars -#include "ResolvExpr/TypeEnvironment.h" // for FirstOpen, FirstClosed namespace GenPoly { Index: src/GenPoly/module.mk =================================================================== --- src/GenPoly/module.mk (revision 5e0bba5fda3d7351cd7d4b5ad75b54d7c9f4387e) +++ src/GenPoly/module.mk (revision 61efa421be36a355b304d2e9b9e14e493947d332) @@ -23,5 +23,4 @@ SRC += $(SRC_GENPOLY) \ GenPoly/BoxNew.cpp \ - GenPoly/Box.cc \ GenPoly/Box.h \ GenPoly/ErasableScopedMap.h \ @@ -29,12 +28,9 @@ GenPoly/FindFunction.h \ GenPoly/InstantiateGenericNew.cpp \ - GenPoly/InstantiateGeneric.cc \ GenPoly/InstantiateGeneric.h \ GenPoly/LvalueNew.cpp \ - GenPoly/Lvalue.cc \ GenPoly/ScopedSet.h \ GenPoly/ScrubTyVars.cc \ GenPoly/ScrubTyVars.h \ - GenPoly/Specialize.cc \ GenPoly/SpecializeNew.cpp \ GenPoly/Specialize.h