source: src/Tuples/TupleAssignment.cc @ e3e16bc

//
// 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 "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 "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

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

          private:
                void match();

                struct Matcher {
                  public:
                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
                        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 & alts );
                        virtual void match( std::list< Expression * > &out );
                };

                struct MultipleAssignMatcher : public Matcher {
                  public:
                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
                        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->has_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, const std::list<ResolvExpr::AltList> &possibilities ) {
                TupleAssignSpotter spotter( currentFinder );
                spotter.spot( expr, possibilities );
        }

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

        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
                                fname = op->get_name();
                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
                                        if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) {
                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
                                                continue;
                                        }

                                        assert( ! ali->empty() );
                                        // grab args 2-N and group into a TupleExpr
                                        const ResolvExpr::Alternative & alt1 = ali->front();
                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
                                        if ( refToTuple(alt1.expr) ) {
                                                if ( isMultAssign( begin, end ) ) {
                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
                                                } else {
                                                        // mass assignment
                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
                                                }
                                                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 ) {
                        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 &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
                assert( ! alts.empty() );
                // combine argument environments into combined expression environment
                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );

                ResolvExpr::Alternative lhsAlt = alts.front();
                // explode is aware of casts - ensure every LHS expression is sent into explode with a reference cast
                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 the tuple-valued-expr is assigned.
                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );

                for ( ResolvExpr::Alternative & alt : lhs ) {
                        // every LHS value must be a reference - some come in with a cast expression, if it doesn't 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() ) );
                        }
                }
        }

        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
                assert( alts.size() == 1 || alts.size() == 2 );
                if ( alts.size() == 2 ) {
                        rhs.push_back( alts.back() );
                }
        }

        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
                // explode the rhs so that each field of the tuple-valued-expr is assigned.
                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
        }

        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->has_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 );
                }
                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: //