source: src/Tuples/TupleAssignment.cc @ 4d5e57b

//
// 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.
//
// TupleAssignment.cc --
//
// Author           : Rodolfo G. Esteves
// Created On       : Mon May 18 07:44:20 2015
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Mar 17 09:43:03 2017
// Update Count     : 8
//

#include <algorithm>                       // for transform
#include <cassert>                         // for assert
#include <iterator>                        // for back_insert_iterator, back...
#include <list>                            // for _List_const_iterator, _Lis...
#include <memory>                          // for unique_ptr, allocator_trai...
#include <string>                          // for string
#include <vector>

#include "CodeGen/OperatorTable.h"
#include "Common/UniqueName.h"             // for UniqueName
#include "Common/utility.h"                // for zipWith
#include "Explode.h"                       // for explode
#include "InitTweak/GenInit.h"             // for genCtorInit
#include "InitTweak/InitTweak.h"           // for getPointerBase, isAssignment
#include "Parser/LinkageSpec.h"            // for Cforall
#include "ResolvExpr/Alternative.h"        // for AltList, Alternative
#include "ResolvExpr/AlternativeFinder.h"  // for AlternativeFinder, simpleC...
#include "ResolvExpr/Cost.h"               // for Cost
#include "ResolvExpr/Resolver.h"           // for resolveCtorInit
#include "ResolvExpr/TypeEnvironment.h"    // for TypeEnvironment
#include "ResolvExpr/typeops.h"            // for combos
#include "SynTree/Declaration.h"           // for ObjectDecl
#include "SynTree/Expression.h"            // for Expression, CastExpr, Name...
#include "SynTree/Initializer.h"           // for ConstructorInit, SingleInit
#include "SynTree/Statement.h"             // for ExprStmt
#include "SynTree/Type.h"                  // for Type, Type::Qualifiers
#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
#include "SynTree/Visitor.h"               // for Visitor

#if 0
#define PRINT(x) x
#else
#define PRINT(x)
#endif

namespace Tuples {
        class TupleAssignSpotter {
          public:
                // dispatcher for Tuple (multiple and mass) assignment operations
                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
                void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );

          private:
                void match();

                struct Matcher {
                  public:
                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const 
                                ResolvExpr::AltList& rhs );
                        virtual ~Matcher() {}
                        virtual void match( std::list< Expression * > &out ) = 0;
                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
                        ResolvExpr::AltList lhs, rhs;
                        TupleAssignSpotter &spotter;
                        ResolvExpr::Cost baseCost;
                        std::list< ObjectDecl * > tmpDecls;
                        ResolvExpr::TypeEnvironment compositeEnv;
                };

                struct MassAssignMatcher : public Matcher {
                  public:
                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, 
                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                        virtual void match( std::list< Expression * > &out );
                };

                struct MultipleAssignMatcher : public Matcher {
                  public:
                        MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, 
                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                        virtual void match( std::list< Expression * > &out );
                };

                ResolvExpr::AlternativeFinder &currentFinder;
                std::string fname;
                std::unique_ptr< Matcher > matcher;
        };

        /// true if expr is an expression of tuple type
        bool isTuple( Expression *expr ) {
                if ( ! expr ) return false;
                assert( expr->result );
                return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
        }

        template< typename AltIter >
        bool isMultAssign( AltIter begin, AltIter end ) {
                // multiple assignment if more than one alternative in the range or if
                // the alternative is a tuple
                if ( begin == end ) return false;
                if ( isTuple( begin->expr ) ) return true;
                return ++begin != end;
        }

        bool refToTuple( Expression *expr ) {
                assert( expr->get_result() );
                // also check for function returning tuple of reference types
                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
                        return refToTuple( castExpr->get_arg() );
                } else {
                        return isTuple( expr );
                }
                return false;
        }

        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, 
                                std::vector<ResolvExpr::AlternativeFinder> &args ) {
                TupleAssignSpotter spotter( currentFinder );
                spotter.spot( expr, args );
        }

        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
                : currentFinder(f) {}

        void TupleAssignSpotter::spot( UntypedExpr * expr, 
                        std::vector<ResolvExpr::AlternativeFinder> &args ) {
                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
                                fname = op->get_name();

                                // AlternativeFinder will naturally handle this case case, if it's legal
                                if ( args.size() == 0 ) return;

                                // if an assignment only takes 1 argument, that's odd, but maybe someone wrote 
                                // the function, in which case AlternativeFinder will handle it normally
                                if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;

                                // look over all possible left-hand-sides
                                for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
                                        // skip non-tuple LHS
                                        if ( ! refToTuple(lhsAlt.expr) ) continue;

                                        // explode is aware of casts - ensure every LHS expression is sent into explode 
                                        // with a reference cast
                                        // xxx - this seems to change the alternatives before the normal 
                                        //  AlternativeFinder flow; maybe this is desired?
                                        if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
                                                lhsAlt.expr = new CastExpr( lhsAlt.expr, 
                                                                new ReferenceType( Type::Qualifiers(), 
                                                                        lhsAlt.expr->get_result()->clone() ) );
                                        }

                                        // explode the LHS so that each field of a tuple-valued-expr is assigned
                                        ResolvExpr::AltList lhs;
                                        explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
                                        for ( ResolvExpr::Alternative& alt : lhs ) {
                                                // each LHS value must be a reference - some come in with a cast expression, 
                                                // if not just cast to reference here
                                                if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
                                                        alt.expr = new CastExpr( alt.expr, 
                                                                new ReferenceType( Type::Qualifiers(), 
                                                                        alt.expr->get_result()->clone() ) );
                                                }
                                        }

                                        if ( args.size() == 1 ) {
                                                // mass default-initialization/destruction
                                                ResolvExpr::AltList rhs{};
                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
                                                match();
                                        } else if ( args.size() > 2 ) {
                                                // expand all possible RHS possibilities
                                                // TODO build iterative version of this instead of using combos
                                                std::vector< ResolvExpr::AltList > rhsAlts;
                                                combos( std::next(args.begin(), 1), args.end(), 
                                                        std::back_inserter( rhsAlts ) );
                                                for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
                                                        // multiple assignment
                                                        ResolvExpr::AltList rhs;
                                                        explode( rhsAlt, currentFinder.get_indexer(), 
                                                                std::back_inserter(rhs), true );
                                                        matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
                                                        match();
                                                }
                                        } else {
                                                for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
                                                        ResolvExpr::AltList rhs;
                                                        if ( isTuple(rhsAlt.expr) ) {
                                                                // multiple assignment
                                                                explode( rhsAlt, currentFinder.get_indexer(),  
                                                                        std::back_inserter(rhs), true );
                                                                matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
                                                        } else {
                                                                // mass assignment
                                                                rhs.push_back( rhsAlt );
                                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
                                                        }
                                                        match();
                                                }
                                        }
                                }
                        }
                }
        }

        void TupleAssignSpotter::match() {
                assert ( matcher != 0 );

                std::list< Expression * > new_assigns;
                matcher->match( new_assigns );

                if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
                        // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
                        // if not the empty tuple case, return early so that no new alternatives are generated.
                        if ( new_assigns.empty() ) return;
                }
                ResolvExpr::AltList current;
                // now resolve new assignments
                for ( std::list< Expression * >::iterator i = new_assigns.begin(); 
                                i != new_assigns.end(); ++i ) {
                        PRINT(
                                std::cerr << "== resolving tuple assign ==" << std::endl;
                                std::cerr << *i << std::endl;
                        )

                        ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(), 
                                currentFinder.get_environ() };
                        try {
                                finder.findWithAdjustment(*i);
                        } catch (...) {
                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
                        }
                        // prune expressions that don't coincide with
                        ResolvExpr::AltList alts = finder.get_alternatives();
                        assert( alts.size() == 1 );
                        assert( alts.front().expr != 0 );
                        current.push_back( alts.front() );
                }

                // extract expressions from the assignment alternatives to produce a list of assignments that
                // together form a single alternative
                std::list< Expression *> solved_assigns;
                for ( ResolvExpr::Alternative & alt : current ) {
                        solved_assigns.push_back( alt.expr->clone() );
                }
                // combine assignment environments into combined expression environment
                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(
                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, 
                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
        }

        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, 
                const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs ) 
        : lhs(lhs), rhs(rhs), spotter(spotter), 
          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
                simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
                simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
        }

        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
                assert( left );
                std::list< Expression * > args;
                args.push_back( new VariableExpr( left ) );
                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
                if ( right ) args.push_back( new VariableExpr( right ) );
                return new UntypedExpr( new NameExpr( fname ), args );
        }

        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
        // xxx - maybe this should happen in alternative finder for every StmtExpr?
        // xxx - it's possible that these environments could contain some useful information. Maybe the right thing to do is aggregate the environments and pass the aggregate back to be added into the compositeEnv
        struct EnvRemover : public Visitor {
                virtual void visit( ExprStmt * stmt ) {
                        delete stmt->get_expr()->get_env();
                        stmt->get_expr()->set_env( nullptr );
                        Visitor::visit( stmt );
                }
        };

        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
                assert( expr->result && ! expr->get_result()->isVoid() );
                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
                if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
                        ret->set_init( ctorInit );
                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
                        EnvRemover rm; // remove environments from subexpressions of StmtExprs
                        ctorInit->accept( rm );
                }
                PRINT( std::cerr << "new object: " << ret << std::endl; )
                return ret;
        }

        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
                static UniqueName lhsNamer( "__massassign_L" );
                static UniqueName rhsNamer( "__massassign_R" );
                // empty tuple case falls into this matcher, hence the second part of the assert
                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );

                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
                        // create a temporary object for each value in the lhs and create a call involving the rhs
                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
                        tmpDecls.push_back( ltmp );
                }
                if ( rtmp ) tmpDecls.push_back( rtmp );
        }

        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
                static UniqueName lhsNamer( "__multassign_L" );
                static UniqueName rhsNamer( "__multassign_R" );

                if ( lhs.size() == rhs.size() ) {
                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
                        std::list< ObjectDecl * > ltmp;
                        std::list< ObjectDecl * > rtmp;
                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
                                return newObject( lhsNamer, alt.expr );
                        });
                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
                                return newObject( rhsNamer, alt.expr );
                        });
                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
                        tmpDecls.splice( tmpDecls.end(), ltmp );
                        tmpDecls.splice( tmpDecls.end(), rtmp );
                }
        }
} // namespace Tuples

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