Changeset b067d9b for src/Tuples/TupleAssignment.cc

Timestamp:

Oct 29, 2019, 4:01:24 PM (6 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

773db65, 9421f3d8

Parents:

7951100 (diff), 8364209 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• src/Tuples/TupleAssignment.cc (modified) (11 diffs)

src/Tuples/TupleAssignment.cc

@@ -22 +22 @@
 #include <vector>
 
+#include "AST/Decl.hpp"
+#include "AST/Init.hpp"
+#include "AST/Pass.hpp"
+#include "AST/Stmt.hpp"
+#include "AST/TypeEnvironment.hpp"
 #include "CodeGen/OperatorTable.h"
 #include "Common/PassVisitor.h"
 #include "Common/UniqueName.h"             // for UniqueName
-#include "Common/utility.h"                // for zipWith
+#include "Common/utility.h"                // for splice, zipWith
 #include "Explode.h"                       // for explode
 #include "InitTweak/GenInit.h"             // for genCtorInit
@@ -51 +56 @@
 
 namespace Tuples {
-        class TupleAssignSpotter {
+        class TupleAssignSpotter_old {
           public:
                 // dispatcher for Tuple (multiple and mass) assignment operations
-                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
+                TupleAssignSpotter_old( ResolvExpr::AlternativeFinder & );
                 void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
 
@@ -62 +67 @@
                 struct Matcher {
                   public:
-                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
-                                ResolvExpr::AltList& rhs );
+                        Matcher( TupleAssignSpotter_old &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 );
+
+                        void combineState( const ResolvExpr::Alternative& alt ) {
+                                compositeEnv.simpleCombine( alt.env );
+                                ResolvExpr::mergeOpenVars( openVars, alt.openVars );
+                                cloneAll( alt.need, need );
+                        }
+
+                        void combineState( const ResolvExpr::AltList& alts ) {
+                                for ( const ResolvExpr::Alternative& alt : alts ) { combineState( alt ); }
+                        }
+
                         ResolvExpr::AltList lhs, rhs;
-                        TupleAssignSpotter &spotter;
+                        TupleAssignSpotter_old &spotter;
                         ResolvExpr::Cost baseCost;
                         std::list< ObjectDecl * > tmpDecls;
                         ResolvExpr::TypeEnvironment compositeEnv;
+                        ResolvExpr::OpenVarSet openVars;
+                        ResolvExpr::AssertionSet need;
                 };
 
                 struct MassAssignMatcher : public Matcher {
                   public:
-                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
+                        MassAssignMatcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs,
                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                         virtual void match( std::list< Expression * > &out );
@@ -83 +102 @@
                 struct MultipleAssignMatcher : public Matcher {
                   public:
-                        MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
+                        MultipleAssignMatcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs,
                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                         virtual void match( std::list< Expression * > &out );
@@ -122 +141 @@
         void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
                                 std::vector<ResolvExpr::AlternativeFinder> &args ) {
-                TupleAssignSpotter spotter( currentFinder );
+                TupleAssignSpotter_old spotter( currentFinder );
                 spotter.spot( expr, args );
         }
 
-        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
+        TupleAssignSpotter_old::TupleAssignSpotter_old( ResolvExpr::AlternativeFinder &f )
                 : currentFinder(f) {}
 
-        void TupleAssignSpotter::spot( UntypedExpr * expr,
+        void TupleAssignSpotter_old::spot( UntypedExpr * expr,
                         std::vector<ResolvExpr::AlternativeFinder> &args ) {
                 if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
@@ -210 +229 @@
         }
 
-        void TupleAssignSpotter::match() {
+        void TupleAssignSpotter_old::match() {
                 assert ( matcher != 0 );
 
@@ -245 +264 @@
                 }
 
-                // extract expressions from the assignment alternatives to produce a list of assignments that
-                // together form a single alternative
+                // 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 );
+                        matcher->combineState( alt );
+                }
+
                 // xxx -- was push_front
-                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
-                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
-                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
-        }
-
-        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
+                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative{
+                        new TupleAssignExpr{ solved_assigns, matcher->tmpDecls }, matcher->compositeEnv,
+                        matcher->openVars,
+                        ResolvExpr::AssertionList( matcher->need.begin(), matcher->need.end() ),
+                        ResolvExpr::sumCost( current ) + matcher->baseCost } );
+        }
+
+        TupleAssignSpotter_old::Matcher::Matcher( TupleAssignSpotter_old &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 );
+                combineState( lhs );
+                combineState( rhs );
         }
 
@@ -297 +318 @@
         };
 
-        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
+        ObjectDecl * TupleAssignSpotter_old::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->result->clone(), new SingleInit( expr->clone() ) );
@@ -313 +334 @@
         }
 
-        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
+        void TupleAssignSpotter_old::MassAssignMatcher::match( std::list< Expression * > &out ) {
                 static UniqueName lhsNamer( "__massassign_L" );
                 static UniqueName rhsNamer( "__massassign_R" );
@@ -331 +352 @@
         }
 
-        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
+        void TupleAssignSpotter_old::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
                 static UniqueName lhsNamer( "__multassign_L" );
                 static UniqueName rhsNamer( "__multassign_R" );
@@ -361 +382 @@
                 }
         }
+
+namespace {
+        /// true if `expr` is of tuple type
+        bool isTuple( const ast::Expr * expr ) {
+                if ( ! expr ) return false;
+                assert( expr->result );
+                return dynamic_cast< const ast::TupleType * >( expr->result->stripReferences() );
+        }
+
+        /// true if `expr` is of tuple type or a reference to one
+        bool refToTuple( const ast::Expr * expr ) {
+                assert( expr->result );
+                // check for function returning tuple of reference types
+                if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
+                        return refToTuple( castExpr->arg );
+                } else {
+                        return isTuple( expr );
+                }
+        }
+
+        /// Dispatcher for tuple (multiple and mass) assignment operations
+        class TupleAssignSpotter_new final {
+                /// Actually finds tuple assignment operations, by subclass
+                struct Matcher {
+                        ResolvExpr::CandidateList lhs, rhs;
+                        TupleAssignSpotter_new & spotter;
+                        CodeLocation location;
+                        ResolvExpr::Cost baseCost;
+                        std::vector< ast::ptr< ast::ObjectDecl > > tmpDecls;
+                        ast::TypeEnvironment env;
+                        ast::OpenVarSet open;
+                        ast::AssertionSet need;
+
+                        void combineState( const ResolvExpr::Candidate & cand ) {
+                                env.simpleCombine( cand.env );
+                                ast::mergeOpenVars( open, cand.open );
+                                need.insert( cand.need.begin(), cand.need.end() );
+                        }
+
+                        Matcher(
+                                TupleAssignSpotter_new & s, const CodeLocation & loc,
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : lhs( l ), rhs( r ), spotter( s ), location( loc ),
+                          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ), tmpDecls(),
+                          env(), open(), need() {
+                                for ( auto & cand : lhs ) combineState( *cand );
+                                for ( auto & cand : rhs ) combineState( *cand );
+                        }
+                        virtual ~Matcher() = default;
+
+                        virtual std::vector< ast::ptr< ast::Expr > > match() = 0;
+
+                        /// removes environments from subexpressions within statement expressions, which could
+                        /// throw off later passes like those in Box which rely on PolyMutator, and adds the
+                        /// bindings to the env
+                        struct EnvRemover {
+                                /// environment to hoist ExprStmt environments to
+                                ast::TypeEnvironment & tenv;
+
+                                EnvRemover( ast::TypeEnvironment & e ) : tenv( e ) {}
+
+                                const ast::ExprStmt * previsit( const ast::ExprStmt * stmt ) {
+                                        if ( stmt->expr->env ) {
+                                                tenv.add( *stmt->expr->env );
+                                                ast::ExprStmt * mut = mutate( stmt );
+                                                mut->expr.get_and_mutate()->env = nullptr;
+                                                return mut;
+                                        }
+                                        return stmt;
+                                }
+                        };
+
+                        ast::ObjectDecl * newObject( UniqueName & namer, const ast::Expr * expr ) {
+                                assert( expr->result && ! expr->result->isVoid() );
+
+                                ast::ObjectDecl * ret = new ast::ObjectDecl{
+                                        location, namer.newName(), expr->result, new ast::SingleInit{ location, expr },
+                                        ast::Storage::Classes{}, ast::Linkage::Cforall };
+
+                                // if expression type is a reference, just need an initializer, otherwise construct
+                                if ( ! expr->result.as< ast::ReferenceType >() ) {
+                                        // resolve ctor/dtor for the new object
+                                        ast::ptr< ast::Init > ctorInit = ResolvExpr::resolveCtorInit(
+                                                        InitTweak::genCtorInit( location, ret ), spotter.crntFinder.symtab );
+                                        // remove environments from subexpressions of stmtExpr
+                                        ast::Pass< EnvRemover > rm{ env };
+                                        ret->init = ctorInit->accept( rm );
+                                }
+
+                                PRINT( std::cerr << "new object: " << ret << std::endl; )
+                                return ret;
+                        }
+
+                        ast::UntypedExpr * createFunc(
+                                const std::string & fname, const ast::ObjectDecl * left,
+                                const ast::ObjectDecl * right
+                        ) {
+                                assert( left );
+                                std::vector< ast::ptr< ast::Expr > > args;
+                                args.emplace_back( new ast::VariableExpr{ location, left } );
+                                if ( right ) { args.emplace_back( new ast::VariableExpr{ location, right } ); }
+
+                                if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
+                                        args.front() = new ast::AddressExpr{ location, args.front() };
+                                        if ( right ) { args.back() = new ast::AddressExpr{ location, args.back() }; }
+                                        return new ast::UntypedExpr{
+                                                location, new ast::NameExpr{ location, "?=?" }, std::move(args) };
+                                } else {
+                                        return new ast::UntypedExpr{
+                                                location, new ast::NameExpr{ location, fname }, std::move(args) };
+                                }
+                        }
+                };
+
+                /// Finds mass-assignment operations
+                struct MassAssignMatcher final : public Matcher {
+                        MassAssignMatcher(
+                                TupleAssignSpotter_new & s, const CodeLocation & loc,
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : Matcher( s, loc, l, r ) {}
+
+                        std::vector< ast::ptr< ast::Expr > > match() override {
+                                static UniqueName lhsNamer( "__massassign_L" );
+                                static UniqueName rhsNamer( "__massassign_R" );
+                                // empty tuple case falls into this matcher
+                                assert( lhs.empty() ? rhs.empty() : rhs.size() <= 1 );
+
+                                ast::ptr< ast::ObjectDecl > rtmp =
+                                        rhs.size() == 1 ? newObject( rhsNamer, rhs.front()->expr ) : nullptr;
+
+                                std::vector< ast::ptr< ast::Expr > > out;
+                                for ( ResolvExpr::CandidateRef & lhsCand : lhs ) {
+                                        // create a temporary object for each value in the LHS and create a call
+                                        // involving the RHS
+                                        ast::ptr< ast::ObjectDecl > ltmp = newObject( lhsNamer, lhsCand->expr );
+                                        out.emplace_back( createFunc( spotter.fname, ltmp, rtmp ) );
+                                        tmpDecls.emplace_back( std::move( ltmp ) );
+                                }
+                                if ( rtmp ) tmpDecls.emplace_back( std::move( rtmp ) );
+
+                                return out;
+                        }
+                };
+
+                /// Finds multiple-assignment operations
+                struct MultipleAssignMatcher final : public Matcher {
+                        MultipleAssignMatcher(
+                                TupleAssignSpotter_new & s, const CodeLocation & loc,
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : Matcher( s, loc, l, r ) {}
+
+                        std::vector< ast::ptr< ast::Expr > > match() override {
+                                static UniqueName lhsNamer( "__multassign_L" );
+                                static UniqueName rhsNamer( "__multassign_R" );
+
+                                if ( lhs.size() != rhs.size() ) return {};
+
+                                // produce a new temporary object for each value in the LHS and RHS and pairwise
+                                // create the calls
+                                std::vector< ast::ptr< ast::ObjectDecl > > ltmp, rtmp;
+
+                                std::vector< ast::ptr< ast::Expr > > out;
+                                for ( unsigned i = 0; i < lhs.size(); ++i ) {
+                                        ResolvExpr::CandidateRef & lhsCand = lhs[i];
+                                        ResolvExpr::CandidateRef & rhsCand = rhs[i];
+
+                                        // convert RHS to LHS type minus one reference -- important for case where LHS
+                                        // is && and RHS is lvalue
+                                        auto lhsType = lhsCand->expr->result.strict_as< ast::ReferenceType >();
+                                        rhsCand->expr = new ast::CastExpr{ rhsCand->expr, lhsType->base };
+                                        ast::ptr< ast::ObjectDecl > lobj = newObject( lhsNamer, lhsCand->expr );
+                                        ast::ptr< ast::ObjectDecl > robj = newObject( rhsNamer, rhsCand->expr );
+                                        out.emplace_back( createFunc( spotter.fname, lobj, robj ) );
+                                        ltmp.emplace_back( std::move( lobj ) );
+                                        rtmp.emplace_back( std::move( robj ) );
+
+                                        // resolve the cast expression so that rhsCand return type is bound by the cast
+                                        // type as needed, and transfer the resulting environment
+                                        ResolvExpr::CandidateFinder finder{ spotter.crntFinder.symtab, env };
+                                        finder.find( rhsCand->expr, ResolvExpr::ResolvMode::withAdjustment() );
+                                        assert( finder.candidates.size() == 1 );
+                                        env = std::move( finder.candidates.front()->env );
+                                }
+
+                                splice( tmpDecls, ltmp );
+                                splice( tmpDecls, rtmp );
+
+                                return out;
+                        }
+                };
+
+                ResolvExpr::CandidateFinder & crntFinder;
+                std::string fname;
+                std::unique_ptr< Matcher > matcher;
+
+        public:
+                TupleAssignSpotter_new( ResolvExpr::CandidateFinder & f )
+                : crntFinder( f ), fname(), matcher() {}
+
+                // find left- and right-hand-sides for mass or multiple assignment
+                void spot(
+                        const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args
+                ) {
+                        if ( auto op = expr->func.as< ast::NameExpr >() ) {
+                                // skip non-assignment functions
+                                if ( ! CodeGen::isCtorDtorAssign( op->name ) ) return;
+                                fname = op->name;
+
+                                // handled by CandidateFinder if applicable (both odd cases)
+                                if ( args.empty() || ( args.size() == 1 && CodeGen::isAssignment( fname ) ) ) {
+                                        return;
+                                }
+
+                                // look over all possible left-hand-side
+                                for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) {
+                                        // skip non-tuple LHS
+                                        if ( ! refToTuple( lhsCand->expr ) ) continue;
+
+                                        // explode is aware of casts - ensure every LHS is sent into explode with a
+                                        // reference cast
+                                        if ( ! lhsCand->expr.as< ast::CastExpr >() ) {
+                                                lhsCand->expr = new ast::CastExpr{
+                                                        lhsCand->expr, new ast::ReferenceType{ lhsCand->expr->result } };
+                                        }
+
+                                        // explode the LHS so that each field of a tuple-valued expr is assigned
+                                        ResolvExpr::CandidateList lhs;
+                                        explode( *lhsCand, crntFinder.symtab, back_inserter(lhs), true );
+                                        for ( ResolvExpr::CandidateRef & cand : lhs ) {
+                                                // each LHS value must be a reference - some come in with a cast, if not
+                                                // just cast to reference here
+                                                if ( ! cand->expr->result.as< ast::ReferenceType >() ) {
+                                                        cand->expr = new ast::CastExpr{
+                                                                cand->expr, new ast::ReferenceType{ cand->expr->result } };
+                                                }
+                                        }
+
+                                        if ( args.size() == 1 ) {
+                                                // mass default-initialization/destruction
+                                                ResolvExpr::CandidateList rhs{};
+                                                matcher.reset( new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                match();
+                                        } else if ( args.size() == 2 ) {
+                                                for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) {
+                                                        ResolvExpr::CandidateList rhs;
+                                                        if ( isTuple( rhsCand->expr ) ) {
+                                                                // multiple assignment
+                                                                explode( *rhsCand, crntFinder.symtab, back_inserter(rhs), true );
+                                                                matcher.reset(
+                                                                        new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        } else {
+                                                                // mass assignment
+                                                                rhs.emplace_back( rhsCand );
+                                                                matcher.reset(
+                                                                        new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        }
+                                                        match();
+                                                }
+                                        } else {
+                                                // expand all possible RHS possibilities
+                                                std::vector< ResolvExpr::CandidateList > rhsCands;
+                                                combos(
+                                                        std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) );
+                                                for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) {
+                                                        // multiple assignment
+                                                        ResolvExpr::CandidateList rhs;
+                                                        explode( rhsCand, crntFinder.symtab, back_inserter(rhs), true );
+                                                        matcher.reset(
+                                                                new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        match();
+                                                }
+                                        }
+                                }
+                        }
+                }
+
+                void match() {
+                        assert( matcher );
+
+                        std::vector< ast::ptr< ast::Expr > > newAssigns = matcher->match();
+
+                        if ( ! ( matcher->lhs.empty() && matcher->rhs.empty() ) ) {
+                                // if both LHS and RHS are empty than this is the empty tuple case, wherein it's
+                                // okay for newAssigns to be empty. Otherwise, return early so that no new
+                                // candidates are generated
+                                if ( newAssigns.empty() ) return;
+                        }
+
+                        ResolvExpr::CandidateList crnt;
+                        // now resolve new assignments
+                        for ( const ast::Expr * expr : newAssigns ) {
+                                PRINT(
+                                        std::cerr << "== resolving tuple assign ==" << std::endl;
+                                        std::cerr << expr << std::endl;
+                                )
+
+                                ResolvExpr::CandidateFinder finder{ crntFinder.symtab, matcher->env };
+
+                                try {
+                                        finder.find( expr, ResolvExpr::ResolvMode::withAdjustment() );
+                                } catch (...) {
+                                        // no match is not failure, just that this tuple assignment is invalid
+                                        return;
+                                }
+
+                                ResolvExpr::CandidateList & cands = finder.candidates;
+                                assert( cands.size() == 1 );
+                                assert( cands.front()->expr );
+                                crnt.emplace_back( std::move( cands.front() ) );
+                        }
+
+                        // extract expressions from the assignment candidates to produce a list of assignments
+                        // that together form a sigle candidate
+                        std::vector< ast::ptr< ast::Expr > > solved;
+                        for ( ResolvExpr::CandidateRef & cand : crnt ) {
+                                solved.emplace_back( cand->expr );
+                                matcher->combineState( *cand );
+                        }
+
+                        crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >(
+                                new ast::TupleAssignExpr{
+                                        matcher->location, std::move( solved ), std::move( matcher->tmpDecls ) },
+                                std::move( matcher->env ), std::move( matcher->open ), std::move( matcher->need ),
+                                ResolvExpr::sumCost( crnt ) + matcher->baseCost ) );
+                }
+        };
+} // anonymous namespace
+
+void handleTupleAssignment(
+        ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign,
+        std::vector< ResolvExpr::CandidateFinder > & args
+) {
+        TupleAssignSpotter_new spotter{ finder };
+        spotter.spot( assign, args );
+}
+
 } // namespace Tuples