source: src/InitTweak/FixInit.cc @ d9f1b2d

//
// 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.
//
// FixInit.h --
//
// Author           : Rob Schluntz
// Created On       : Wed Jan 13 16:29:30 2016
// Last Modified By : Rob Schluntz
// Last Modified On : Fri May 13 11:44:26 2016
// Update Count     : 30
//

#include <stack>
#include <list>
#include "FixInit.h"
#include "InitTweak.h"
#include "ResolvExpr/Resolver.h"
#include "ResolvExpr/typeops.h"
#include "SynTree/Declaration.h"
#include "SynTree/Type.h"
#include "SynTree/Expression.h"
#include "SynTree/Statement.h"
#include "SynTree/Initializer.h"
#include "SynTree/Mutator.h"
#include "SymTab/Indexer.h"
#include "GenPoly/PolyMutator.h"

bool ctordtorp = false;
#define PRINT( text ) if ( ctordtorp ) { text }

namespace InitTweak {
        namespace {
                const std::list<Label> noLabels;
                const std::list<Expression*> noDesignators;
        }

        class InsertImplicitCalls : public GenPoly::PolyMutator {
        public:
                /// wrap function application expressions as ImplicitCopyCtorExpr nodes
                /// so that it is easy to identify which function calls need their parameters
                /// to be copy constructed
                static void insert( std::list< Declaration * > & translationUnit );

                virtual Expression * mutate( ApplicationExpr * appExpr );
        };

        class ResolveCopyCtors : public SymTab::Indexer {
        public:
                /// generate temporary ObjectDecls for each argument and return value of each
                /// ImplicitCopyCtorExpr, generate/resolve copy construction expressions for each,
                /// and generate/resolve destructors for both arguments and return value temporaries
                static void resolveImplicitCalls( std::list< Declaration * > & translationUnit );

                virtual void visit( ImplicitCopyCtorExpr * impCpCtorExpr );

                /// create and resolve ctor/dtor expression: fname(var, [cpArg])
                ApplicationExpr * makeCtorDtor( const std::string & fname, ObjectDecl * var, Expression * cpArg = NULL );
                /// true if type does not need to be copy constructed to ensure correctness
                bool skipCopyConstruct( Type * );
        private:
                TypeSubstitution * env;
        };

        class FixInit : public GenPoly::PolyMutator {
          public:
                /// expand each object declaration to use its constructor after it is declared.
                /// insert destructor calls at the appropriate places
                static void fixInitializers( std::list< Declaration * > &translationUnit );

                virtual DeclarationWithType * mutate( ObjectDecl *objDecl );

                virtual CompoundStmt * mutate( CompoundStmt * compoundStmt );
                virtual Statement * mutate( ReturnStmt * returnStmt );
                virtual Statement * mutate( BranchStmt * branchStmt );

          private:
                // stack of list of statements - used to differentiate scopes
                std::list< std::list< Statement * > > dtorStmts;
        };

        class FixCopyCtors : public GenPoly::PolyMutator {
          public:
                /// expand ImplicitCopyCtorExpr nodes into the temporary declarations, copy constructors,
                /// call expression, and destructors
                static void fixCopyCtors( std::list< Declaration * > &translationUnit );

                virtual Expression * mutate( ImplicitCopyCtorExpr * impCpCtorExpr );

          private:
                // stack of list of statements - used to differentiate scopes
                std::list< std::list< Statement * > > dtorStmts;
        };

        void fix( std::list< Declaration * > & translationUnit ) {
                InsertImplicitCalls::insert( translationUnit );
                ResolveCopyCtors::resolveImplicitCalls( translationUnit );
                FixInit::fixInitializers( translationUnit );
                // FixCopyCtors must happen after FixInit, so that destructors are placed correctly
                FixCopyCtors::fixCopyCtors( translationUnit );
        }

        void InsertImplicitCalls::insert( std::list< Declaration * > & translationUnit ) {
                InsertImplicitCalls inserter;
                mutateAll( translationUnit, inserter );
        }

        void ResolveCopyCtors::resolveImplicitCalls( std::list< Declaration * > & translationUnit ) {
                ResolveCopyCtors resolver;
                acceptAll( translationUnit, resolver );
        }

        void FixInit::fixInitializers( std::list< Declaration * > & translationUnit ) {
                FixInit fixer;
                mutateAll( translationUnit, fixer );
        }

        void FixCopyCtors::fixCopyCtors( std::list< Declaration * > & translationUnit ) {
                FixCopyCtors fixer;
                mutateAll( translationUnit, fixer );
        }

        Expression * InsertImplicitCalls::mutate( ApplicationExpr * appExpr ) {
                appExpr = dynamic_cast< ApplicationExpr * >( Mutator::mutate( appExpr ) );
                assert( appExpr );

                if ( VariableExpr * function = dynamic_cast< VariableExpr * > ( appExpr->get_function() ) ) {
                        if ( function->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
                                // optimization: don't need to copy construct in order to call intrinsic functions
                                return appExpr;
                        } else if ( FunctionDecl * funcDecl = dynamic_cast< FunctionDecl * > ( function->get_var() ) ) {
                                FunctionType * ftype = funcDecl->get_functionType();
                                if ( (funcDecl->get_name() == "?{}" || funcDecl->get_name() == "?=?") && ftype->get_parameters().size() == 2 ) {
                                        Type * t1 = ftype->get_parameters().front()->get_type();
                                        Type * t2 = ftype->get_parameters().back()->get_type();
                                        PointerType * ptrType = dynamic_cast< PointerType * > ( t1 );
                                        assert( ptrType );
                                        if ( ResolvExpr::typesCompatible( ptrType->get_base(), t2, SymTab::Indexer() ) ) {
                                                // optimization: don't need to copy construct in order to call a copy constructor or
                                                // assignment operator
                                                return appExpr;
                                        }
                                } else if ( funcDecl->get_name() == "^?{}" ) {
                                        // correctness: never copy construct arguments to a destructor
                                        return appExpr;
                                }
                        }
                }
                PRINT( std::cerr << "InsertImplicitCalls: adding a wrapper " << appExpr << std::endl; )

                // wrap each function call so that it is easy to identify nodes that have to be copy constructed
                ImplicitCopyCtorExpr * expr = new ImplicitCopyCtorExpr( appExpr );
                // save the type substitution onto the new node so that it is easy to find.
                // Ensure it is not deleted with the ImplicitCopyCtorExpr by removing it before deletion.
                // The substitution is needed to obtain the type of temporary variables so that copy constructor
                // calls can be resolved. Normally this is what PolyMutator is for, but the pass that resolves
                // copy constructor calls must be an Indexer. We could alternatively make a PolyIndexer which
                // saves the environment, or compute the types of temporaries here, but it's much simpler to
                // save the environment here, and more cohesive to compute temporary variables and resolve copy
                // constructor calls together.
                assert( env );
                expr->set_env( env );
                return expr;
        }

        bool ResolveCopyCtors::skipCopyConstruct( Type * type ) {
                return dynamic_cast< VarArgsType * >( type ) || GenPoly::getFunctionType( type );
        }

        ApplicationExpr * ResolveCopyCtors::makeCtorDtor( const std::string & fname, ObjectDecl * var, Expression * cpArg ) {
                assert( var );
                UntypedExpr * untyped = new UntypedExpr( new NameExpr( fname ) );
                untyped->get_args().push_back( new AddressExpr( new VariableExpr( var ) ) );
                if (cpArg) untyped->get_args().push_back( cpArg );

                // resolve copy constructor
                // should only be one alternative for copy ctor and dtor expressions, since
                // all arguments are fixed (VariableExpr and already resolved expression)
                PRINT( std::cerr << "ResolvingCtorDtor " << untyped << std::endl; )
                ApplicationExpr * resolved = dynamic_cast< ApplicationExpr * >( ResolvExpr::findVoidExpression( untyped, *this ) );
                if ( resolved->get_env() ) {
                        env->add( *resolved->get_env() );
                }

                assert( resolved );
                delete untyped;
                return resolved;
        }

        void ResolveCopyCtors::visit( ImplicitCopyCtorExpr *impCpCtorExpr ) {
                static UniqueName tempNamer("_tmp_cp");
                static UniqueName retNamer("_tmp_cp_ret");

                PRINT( std::cerr << "ResolveCopyCtors: " << impCpCtorExpr << std::endl; )
                Visitor::visit( impCpCtorExpr );
                env = impCpCtorExpr->get_env(); // xxx - maybe we really should just have a PolyIndexer...

                ApplicationExpr * appExpr = impCpCtorExpr->get_callExpr();

                // take each argument and attempt to copy construct it.
                for ( Expression * & arg : appExpr->get_args() ) {
                        PRINT( std::cerr << "Type Substitution: " << *impCpCtorExpr->get_env() << std::endl; )
                        // xxx - need to handle tuple arguments
                        assert( ! arg->get_results().empty() );
                        Type * result = arg->get_results().front();
                        if ( skipCopyConstruct( result ) ) continue; // skip certain non-copyable types
                        // type may involve type variables, so apply type substitution to get temporary variable's actual type
                        result = result->clone();
                        impCpCtorExpr->get_env()->apply( result );
                        ObjectDecl * tmp = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, result, 0 );
                        tmp->get_type()->set_isConst( false );

                        // create and resolve copy constructor
                        PRINT( std::cerr << "makeCtorDtor for an argument" << std::endl; )
                        ApplicationExpr * cpCtor = makeCtorDtor( "?{}", tmp, arg );

                        // if the chosen constructor is intrinsic, the copy is unnecessary, so
                        // don't create the temporary and don't call the copy constructor
                        VariableExpr * function = dynamic_cast< VariableExpr * >( cpCtor->get_function() );
                        assert( function );
                        if ( function->get_var()->get_linkage() != LinkageSpec::Intrinsic ) {
                                // replace argument to function call with temporary
                                arg = new CommaExpr( cpCtor, new VariableExpr( tmp ) );
                                impCpCtorExpr->get_tempDecls().push_back( tmp );
                                impCpCtorExpr->get_dtors().push_front( makeCtorDtor( "^?{}", tmp ) );
                        }
                }

                // each return value from the call needs to be connected with an ObjectDecl
                // at the call site, which is initialized with the return value and is destructed
                // later
                // xxx - handle multiple return values
                ApplicationExpr * callExpr = impCpCtorExpr->get_callExpr();
                // xxx - is this right? callExpr may not have the right environment, because it was attached
                // at a higher level. Trying to pass that environment along.
                callExpr->set_env( impCpCtorExpr->get_env()->clone() );
                for ( Type * result : appExpr->get_results() ) {
                        result = result->clone();
                        impCpCtorExpr->get_env()->apply( result );
                        ObjectDecl * ret = new ObjectDecl( retNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, result, 0 );
                        ret->get_type()->set_isConst( false );
                        impCpCtorExpr->get_returnDecls().push_back( ret );
                        PRINT( std::cerr << "makeCtorDtor for a return" << std::endl; )
                        impCpCtorExpr->get_dtors().push_front( makeCtorDtor( "^?{}", ret ) );
                }
                PRINT( std::cerr << "after Resolving: " << impCpCtorExpr << std::endl; )
        }


        Expression * FixCopyCtors::mutate( ImplicitCopyCtorExpr * impCpCtorExpr ) {
                PRINT( std::cerr << "FixCopyCtors: " << impCpCtorExpr << std::endl; )

                impCpCtorExpr = dynamic_cast< ImplicitCopyCtorExpr * >( Mutator::mutate( impCpCtorExpr ) );
                assert( impCpCtorExpr );

                std::list< ObjectDecl * > & tempDecls = impCpCtorExpr->get_tempDecls();
                std::list< ObjectDecl * > & returnDecls = impCpCtorExpr->get_returnDecls();
                std::list< Expression * > & dtors = impCpCtorExpr->get_dtors();

                // add all temporary declarations and their constructors
                for ( ObjectDecl * obj : tempDecls ) {
                        stmtsToAdd.push_back( new DeclStmt( noLabels, obj ) );
                }
                for ( ObjectDecl * obj : returnDecls ) {
                        stmtsToAdd.push_back( new DeclStmt( noLabels, obj ) );
                }

                // add destructors after current statement
                for ( Expression * dtor : dtors ) {
                        stmtsToAddAfter.push_back( new ExprStmt( noLabels, dtor ) );
                }

                // xxx - update to work with multiple return values
                ObjectDecl * returnDecl = returnDecls.empty() ? NULL : returnDecls.front();
                Expression * callExpr = impCpCtorExpr->get_callExpr();

                PRINT( std::cerr << "Coming out the back..." << impCpCtorExpr << std::endl; )

                // xxx - some of these aren't necessary, and can be removed once this is stable
                dtors.clear();
                tempDecls.clear();
                returnDecls.clear();
                impCpCtorExpr->set_callExpr( NULL );
                impCpCtorExpr->set_env( NULL );
                delete impCpCtorExpr;

                if ( returnDecl ) {
                        UntypedExpr * assign = new UntypedExpr( new NameExpr( "?=?" ) );
                        assign->get_args().push_back( new VariableExpr( returnDecl ) );
                        assign->get_args().push_back( callExpr );
                        // know the result type of the assignment is the type of the LHS (minus the pointer), so
                        // add that onto the assignment expression so that later steps have the necessary information
                        assign->add_result( returnDecl->get_type()->clone() );

                        Expression * retExpr = new CommaExpr( assign, new VariableExpr( returnDecl ) );
                        if ( callExpr->get_results().front()->get_isLvalue() ) {
                                // lvalue returning functions are funny. Lvalue.cc inserts a *? in front of any
                                // lvalue returning non-intrinsic function. Add an AddressExpr to the call to negate
                                // the derefence and change the type of the return temporary from T to T* to properly
                                // capture the return value. Then dereference the result of the comma expression, since
                                // the lvalue returning call was originally wrapped with an AddressExpr.
                                // Effectively, this turns
                                //   lvalue T f();
                                //   &*f()
                                // into
                                //   T * tmp_cp_retN;
                                //   tmp_cp_ret_N = &*(tmp_cp_ret_N = &*f(), tmp_cp_ret);
                                // which work out in terms of types, but is pretty messy. It would be nice to find a better way.
                                assign->get_args().back() = new AddressExpr( assign->get_args().back() );

                                Type * resultType = returnDecl->get_type()->clone();
                                returnDecl->set_type( new PointerType( Type::Qualifiers(), returnDecl->get_type() ) );
                                UntypedExpr * deref = new UntypedExpr( new NameExpr( "*?" ) );
                                deref->get_args().push_back( retExpr );
                                deref->add_result( resultType );
                                retExpr = deref;
                        }
                        // xxx - might need to set env on retExpr...
                        // retExpr->set_env( env->clone() );
                        return retExpr;
                } else {
                        return callExpr;
                }
        }

        DeclarationWithType *FixInit::mutate( ObjectDecl *objDecl ) {
                // first recursively handle pieces of ObjectDecl so that they aren't missed by other visitors
                // when the init is removed from the ObjectDecl
                objDecl = dynamic_cast< ObjectDecl * >( Mutator::mutate( objDecl ) );

                if ( ConstructorInit * ctorInit = dynamic_cast< ConstructorInit * >( objDecl->get_init() ) ) {
                        // a decision should have been made by the resolver, so ctor and init are not both non-NULL
                        assert( ! ctorInit->get_ctor() || ! ctorInit->get_init() );
                        if ( Statement * ctor = ctorInit->get_ctor() ) {
                                if ( objDecl->get_storageClass() == DeclarationNode::Static ) {
                                        // generate:
                                        // static bool __objName_uninitialized = true;
                                        // if (__objName_uninitialized) {
                                        //   __ctor(__objName);
                                        //   void dtor_atexit() {
                                        //     __dtor(__objName);
                                        //   }
                                        //   on_exit(dtorOnExit, &__objName);
                                        //   __objName_uninitialized = false;
                                        // }

                                        // generate first line
                                        BasicType * boolType = new BasicType( Type::Qualifiers(), BasicType::Bool );
                                        SingleInit * boolInitExpr = new SingleInit( new ConstantExpr( Constant( boolType->clone(), "1" ) ), noDesignators );
                                        ObjectDecl * isUninitializedVar = new ObjectDecl( objDecl->get_mangleName() + "_uninitialized", DeclarationNode::Static, LinkageSpec::Cforall, 0, boolType, boolInitExpr );
                                        isUninitializedVar->fixUniqueId();

                                        // void dtor_atexit(...) {...}
                                        FunctionDecl * dtorCaller = new FunctionDecl( objDecl->get_mangleName() + "_dtor_atexit", DeclarationNode::NoStorageClass, LinkageSpec::C, new FunctionType( Type::Qualifiers(), false ), new CompoundStmt( noLabels ), false, false );
                                        dtorCaller->fixUniqueId();
                                        dtorCaller->get_statements()->get_kids().push_back( ctorInit->get_dtor() );

                                        // on_exit(dtor_atexit);
                                        UntypedExpr * callAtexit = new UntypedExpr( new NameExpr( "atexit" ) );
                                        callAtexit->get_args().push_back( new VariableExpr( dtorCaller ) );

                                        // __objName_uninitialized = false;
                                        UntypedExpr * setTrue = new UntypedExpr( new NameExpr( "?=?" ) );
                                        setTrue->get_args().push_back( new VariableExpr( isUninitializedVar ) );
                                        setTrue->get_args().push_back( new ConstantExpr( Constant( boolType->clone(), "0" ) ) );

                                        // generate body of if
                                        CompoundStmt * initStmts = new CompoundStmt( noLabels );
                                        std::list< Statement * > & body = initStmts->get_kids();
                                        body.push_back( ctor );
                                        body.push_back( new DeclStmt( noLabels, dtorCaller ) );
                                        body.push_back( new ExprStmt( noLabels, callAtexit ) );
                                        body.push_back( new ExprStmt( noLabels, setTrue ) );

                                        // put it all together
                                        IfStmt * ifStmt = new IfStmt( noLabels, new VariableExpr( isUninitializedVar ), initStmts, 0 );
                                        stmtsToAddAfter.push_back( new DeclStmt( noLabels, isUninitializedVar ) );
                                        stmtsToAddAfter.push_back( ifStmt );
                                } else {
                                        stmtsToAddAfter.push_back( ctor );
                                        dtorStmts.back().push_front( ctorInit->get_dtor() );
                                }
                                objDecl->set_init( NULL );
                                ctorInit->set_ctor( NULL );
                                ctorInit->set_dtor( NULL );  // xxx - only destruct when constructing? Probably not?
                        } else if ( Initializer * init = ctorInit->get_init() ) {
                                objDecl->set_init( init );
                                ctorInit->set_init( NULL );
                        } else {
                                // no constructor and no initializer, which is okay
                                objDecl->set_init( NULL );
                        }
                        delete ctorInit;
                }
                return objDecl;
        }

        namespace {
                template<typename Iterator, typename OutputIterator>
                void insertDtors( Iterator begin, Iterator end, OutputIterator out ) {
                        for ( Iterator it = begin ; it != end ; ++it ) {
                                // remove if instrinsic destructor statement. Note that this is only called
                                // on lists of implicit dtors, so if the user manually calls an intrinsic
                                // dtor then the call must (and will) still be generated since the argument
                                // may contain side effects.
                                if ( ! isInstrinsicSingleArgCallStmt( *it ) ) {
                                        // don't need to call intrinsic dtor, because it does nothing, but
                                        // non-intrinsic dtors must be called
                                        *out++ = (*it)->clone();
                                }
                        }
                }
        }

        CompoundStmt * FixInit::mutate( CompoundStmt * compoundStmt ) {
                // mutate statements - this will also populate dtorStmts list.
                // don't want to dump all destructors when block is left,
                // just the destructors associated with variables defined in this block,
                // so push a new list to the top of the stack so that we can differentiate scopes
                dtorStmts.push_back( std::list<Statement *>() );

                compoundStmt = PolyMutator::mutate( compoundStmt );
                std::list< Statement * > & statements = compoundStmt->get_kids();

                insertDtors( dtorStmts.back().begin(), dtorStmts.back().end(), back_inserter( statements ) );

                deleteAll( dtorStmts.back() );
                dtorStmts.pop_back();
                return compoundStmt;
        }

        Statement * FixInit::mutate( ReturnStmt * returnStmt ) {
                for ( std::list< std::list< Statement * > >::reverse_iterator list = dtorStmts.rbegin(); list != dtorStmts.rend(); ++list ) {
                        insertDtors( list->begin(), list->end(), back_inserter( stmtsToAdd ) );
                }
                return Mutator::mutate( returnStmt );
        }

        Statement * FixInit::mutate( BranchStmt * branchStmt ) {
                // TODO: adding to the end of a block isn't sufficient, since
                // return/break/goto should trigger destructor when block is left.
                switch( branchStmt->get_type() ) {
                        case BranchStmt::Continue:
                        case BranchStmt::Break:
                                insertDtors( dtorStmts.back().begin(), dtorStmts.back().end(), back_inserter( stmtsToAdd ) );
                                break;
                        case BranchStmt::Goto:
                                // xxx
                                // if goto leaves a block, generate dtors for every block it leaves
                                // if goto is in same block but earlier statement, destruct every object that was defined after the statement
                                break;
                        default:
                                assert( false );
                }
                return Mutator::mutate( branchStmt );
        }


} // namespace InitTweak

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //