source: src/Tuples/TupleAssignment.cc @ f831177

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since f831177 was f831177, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

address exprs are now only exploded for tuple assignments

  • Property mode set to 100644
File size: 11.7 KB
RevLine 
[51587aa]1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
[5af62f1]7// TupleAssignment.cc --
[51587aa]8//
[843054c2]9// Author           : Rodolfo G. Esteves
[51587aa]10// Created On       : Mon May 18 07:44:20 2015
[b3b2077]11// Last Modified By : Rob Schluntz
12// Last Modified On : Wed Nov 9 13:48:42 2016
[51587aa]13// Update Count     : 2
14//
15
[51b7345]16#include "ResolvExpr/AlternativeFinder.h"
17#include "ResolvExpr/Alternative.h"
18#include "ResolvExpr/typeops.h"
19#include "SynTree/Expression.h"
[6eb8948]20#include "SynTree/Initializer.h"
21#include "Tuples.h"
[141b786]22#include "Explode.h"
[d3b7937]23#include "Common/SemanticError.h"
[65660bd]24#include "InitTweak/InitTweak.h"
[1d2b64f]25#include "InitTweak/GenInit.h"
[51b7345]26
27#include <functional>
28#include <algorithm>
29#include <iterator>
30#include <iostream>
31#include <cassert>
32#include <set>
[5af62f1]33#include <unordered_set>
[51b7345]34
35namespace Tuples {
[5af62f1]36        class TupleAssignSpotter {
37          public:
38                // dispatcher for Tuple (multiple and mass) assignment operations
39                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
[65660bd]40                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
[5af62f1]41
42          private:
43                void match();
44
[6eb8948]45                struct Matcher {
[5af62f1]46                  public:
[65660bd]47                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
[5af62f1]48                        virtual ~Matcher() {}
49                        virtual void match( std::list< Expression * > &out ) = 0;
[1d2b64f]50                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
[3c13c03]51                        ResolvExpr::AltList lhs, rhs;
[5af62f1]52                        TupleAssignSpotter &spotter;
[1d2b64f]53                        ResolvExpr::Cost baseCost;
[6eb8948]54                        std::list< ObjectDecl * > tmpDecls;
[1d2b64f]55                        ResolvExpr::TypeEnvironment compositeEnv;
[5af62f1]56                };
57
[6eb8948]58                struct MassAssignMatcher : public Matcher {
[5af62f1]59                  public:
[65660bd]60                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
[5af62f1]61                        virtual void match( std::list< Expression * > &out );
62                };
63
[6eb8948]64                struct MultipleAssignMatcher : public Matcher {
[5af62f1]65                  public:
[65660bd]66                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
[5af62f1]67                        virtual void match( std::list< Expression * > &out );
68                };
69
70                ResolvExpr::AlternativeFinder &currentFinder;
[65660bd]71                std::string fname;
72                std::unique_ptr< Matcher > matcher;
[5af62f1]73        };
74
[f831177]75        /// true if expr is an expression of tuple type
[5af62f1]76        bool isTuple( Expression *expr ) {
[51587aa]77                if ( ! expr ) return false;
[aa8f9df]78                assert( expr->has_result() );
[f831177]79                return dynamic_cast< TupleType * >( expr->get_result() );
[51587aa]80        }
81
[65660bd]82        template< typename AltIter >
83        bool isMultAssign( AltIter begin, AltIter end ) {
84                // multiple assignment if more than one alternative in the range or if
85                // the alternative is a tuple
86                if ( begin == end ) return false;
87                if ( isTuple( begin->expr ) ) return true;
88                return ++begin != end;
89        }
90
[5af62f1]91        bool pointsToTuple( Expression *expr ) {
92                // also check for function returning tuple of reference types
[65660bd]93                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
94                        return pointsToTuple( castExpr->get_arg() );
95                } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
[5af62f1]96                        return isTuple( addr->get_arg() );
[51587aa]97                }
98                return false;
99        }
100
[65660bd]101        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
[5af62f1]102                TupleAssignSpotter spotter( currentFinder );
103                spotter.spot( expr, possibilities );
104        }
[51587aa]105
[5af62f1]106        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
107                : currentFinder(f) {}
[51587aa]108
[65660bd]109        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
110                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
111                        if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
112                                fname = op->get_name();
113                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
114                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
115                                        if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
116                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
117                                                continue;
118                                        }
[51587aa]119
[65660bd]120                                        assert( ! ali->empty() );
121                                        // grab args 2-N and group into a TupleExpr
122                                        const ResolvExpr::Alternative & alt1 = ali->front();
123                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
[3c13c03]124                                        if ( pointsToTuple(alt1.expr) ) {
[65660bd]125                                                if ( isMultAssign( begin, end ) ) {
126                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
[5af62f1]127                                                } else {
[51587aa]128                                                        // mass assignment
[65660bd]129                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
[51587aa]130                                                }
[5af62f1]131                                                match();
[51587aa]132                                        }
133                                }
134                        }
135                }
136        }
137
[5af62f1]138        void TupleAssignSpotter::match() {
139                assert ( matcher != 0 );
[51587aa]140
[5af62f1]141                std::list< Expression * > new_assigns;
142                matcher->match( new_assigns );
143
[f831177]144                if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
145                        // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
146                        // if not the empty tuple case, return early so that no new alternatives are generated.
147                        if ( new_assigns.empty() ) return;
148                }
[5af62f1]149                ResolvExpr::AltList current;
150                // now resolve new assignments
151                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
152                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
[ac9ca96]153                        try {
154                                finder.findWithAdjustment(*i);
155                        } catch (...) {
[1d2b64f]156                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
[ac9ca96]157                        }
[5af62f1]158                        // prune expressions that don't coincide with
159                        ResolvExpr::AltList alts = finder.get_alternatives();
160                        assert( alts.size() == 1 );
161                        assert( alts.front().expr != 0 );
[908cc83]162                        current.push_back( alts.front() );
[5af62f1]163                }
164
[6eb8948]165                // extract expressions from the assignment alternatives to produce a list of assignments that
166                // together form a single alternative
167                std::list< Expression *> solved_assigns;
168                for ( ResolvExpr::Alternative & alt : current ) {
169                        solved_assigns.push_back( alt.expr->clone() );
170                }
[1d2b64f]171                // combine assignment environments into combined expression environment
172                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
173                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
[51587aa]174        }
175
[1d2b64f]176        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
[65660bd]177                assert( ! alts.empty() );
[1d2b64f]178                // combine argument environments into combined expression environment
179                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
180
[65660bd]181                ResolvExpr::Alternative lhsAlt = alts.front();
182                // peel off the cast that exists on ctor/dtor expressions
183                bool isCast = false;
184                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
185                        lhsAlt.expr = castExpr->get_arg();
186                        castExpr->set_arg( nullptr );
187                        delete castExpr;
188                        isCast = true;
189                }
[3c13c03]190
[65660bd]191                // explode the lhs so that each field of the tuple-valued-expr is assigned.
[f831177]192                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
[b3b2077]193
[65660bd]194                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
195                if ( isCast ) {
196                        for ( ResolvExpr::Alternative & alt : lhs ) {
197                                Expression *& expr = alt.expr;
198                                Type * castType = expr->get_result()->clone();
199                                Type * type = InitTweak::getPointerBase( castType );
200                                assert( type );
201                                type->get_qualifiers() -= Type::Qualifiers(true, true, true, false, true, true);
202                                type->set_isLvalue( true ); // xxx - might not need this
203                                expr = new CastExpr( expr, castType );
204                        }
[3c13c03]205                }
206        }
207
[b3b2077]208        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
[65660bd]209                assert( alts.size() == 1 || alts.size() == 2 );
210                if ( alts.size() == 2 ) {
211                        rhs.push_back( alts.back() );
212                }
[51587aa]213        }
214
[65660bd]215        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
[3c13c03]216                // explode the rhs so that each field of the tuple-valued-expr is assigned.
[f831177]217                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
[51587aa]218        }
219
[65660bd]220        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
221                assert( left );
[5af62f1]222                std::list< Expression * > args;
[b3b2077]223                args.push_back( new AddressExpr( UntypedExpr::createDeref( new VariableExpr( left ) ) ) );
[65660bd]224                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
225                if ( right ) args.push_back( new VariableExpr( right ) );
226                return new UntypedExpr( new NameExpr( fname ), args );
[51587aa]227        }
228
[1d2b64f]229        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
230        // xxx - maybe this should happen in alternative finder for every StmtExpr?
231        // 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
232        struct EnvRemover : public Visitor {
233                virtual void visit( ExprStmt * stmt ) {
234                        delete stmt->get_expr()->get_env();
235                        stmt->get_expr()->set_env( nullptr );
236                        Visitor::visit( stmt );
237                }
238        };
239
240        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
[aa8f9df]241                assert( expr->has_result() && ! expr->get_result()->isVoid() );
[1d2b64f]242                ObjectDecl * ret = new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
243                ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
244                ret->set_init( ctorInit );
245                ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
246                EnvRemover rm; // remove environments from subexpressions of StmtExprs
247                ctorInit->accept( rm );
248                return ret;
[6eb8948]249        }
250
[5af62f1]251        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
[6eb8948]252                static UniqueName lhsNamer( "__massassign_L" );
253                static UniqueName rhsNamer( "__massassign_R" );
[f831177]254                // empty tuple case falls into this matcher, hence the second part of the assert
255                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
[51587aa]256
[65660bd]257                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
[3c13c03]258                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
[f831177]259                        // create a temporary object for each value in the lhs and create a call involving the rhs
[65660bd]260                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
261                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
[6eb8948]262                        tmpDecls.push_back( ltmp );
[5af62f1]263                }
[65660bd]264                if ( rtmp ) tmpDecls.push_back( rtmp );
[51b7345]265        }
266
[5af62f1]267        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
[6eb8948]268                static UniqueName lhsNamer( "__multassign_L" );
269                static UniqueName rhsNamer( "__multassign_R" );
[b3b2077]270
[51587aa]271                if ( lhs.size() == rhs.size() ) {
[f831177]272                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
[6eb8948]273                        std::list< ObjectDecl * > ltmp;
274                        std::list< ObjectDecl * > rtmp;
[1d2b64f]275                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
[65660bd]276                                return newObject( lhsNamer, alt.expr );
[6eb8948]277                        });
[1d2b64f]278                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
[3c13c03]279                                return newObject( rhsNamer, alt.expr );
[6eb8948]280                        });
[65660bd]281                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
[6eb8948]282                        tmpDecls.splice( tmpDecls.end(), ltmp );
283                        tmpDecls.splice( tmpDecls.end(), rtmp );
[5af62f1]284                }
[51587aa]285        }
[51b7345]286} // namespace Tuples
[51587aa]287
288// Local Variables: //
289// tab-width: 4 //
290// mode: c++ //
291// compile-command: "make install" //
292// End: //
Note: See TracBrowser for help on using the repository browser.