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

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 4c8621ac was 4c8621ac, checked in by Rob Schluntz <rschlunt@…>, 5 years ago

allow construction, destruction, and assignment for empty tuples, allow matching a ttype parameter with an empty tuple, fix specialization to work with empty tuples and void functions

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