source: src/Tuples/TupleAssignment.cc @ d20a343

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

Add cast to LHS type in tuple multiple assignment

  • Property mode set to 100644
File size: 14.4 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 : Peter A. Buhr
12// Last Modified On : Fri Mar 17 09:43:03 2017
13// Update Count     : 8
14//
15
16#include <algorithm>                       // for transform
17#include <cassert>                         // for assert
18#include <iterator>                        // for back_insert_iterator, back...
19#include <list>                            // for _List_const_iterator, _Lis...
20#include <memory>                          // for unique_ptr, allocator_trai...
21#include <string>                          // for string
22#include <vector>
23
24#include "CodeGen/OperatorTable.h"
25#include "Common/PassVisitor.h"
26#include "Common/UniqueName.h"             // for UniqueName
27#include "Common/utility.h"                // for zipWith
28#include "Explode.h"                       // for explode
29#include "InitTweak/GenInit.h"             // for genCtorInit
30#include "InitTweak/InitTweak.h"           // for getPointerBase, isAssignment
31#include "Parser/LinkageSpec.h"            // for Cforall
32#include "ResolvExpr/Alternative.h"        // for AltList, Alternative
33#include "ResolvExpr/AlternativeFinder.h"  // for AlternativeFinder, simpleC...
34#include "ResolvExpr/Cost.h"               // for Cost
35#include "ResolvExpr/Resolver.h"           // for resolveCtorInit
36#include "ResolvExpr/TypeEnvironment.h"    // for TypeEnvironment
37#include "ResolvExpr/typeops.h"            // for combos
38#include "SynTree/Declaration.h"           // for ObjectDecl
39#include "SynTree/Expression.h"            // for Expression, CastExpr, Name...
40#include "SynTree/Initializer.h"           // for ConstructorInit, SingleInit
41#include "SynTree/Statement.h"             // for ExprStmt
42#include "SynTree/Type.h"                  // for Type, Type::Qualifiers
43#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
44#include "SynTree/Visitor.h"               // for Visitor
45
46#if 0
47#define PRINT(x) x
48#else
49#define PRINT(x)
50#endif
51
52namespace Tuples {
53        class TupleAssignSpotter {
54          public:
55                // dispatcher for Tuple (multiple and mass) assignment operations
56                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
57                void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
58
59          private:
60                void match();
61
62                struct Matcher {
63                  public:
64                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
65                                ResolvExpr::AltList& rhs );
66                        virtual ~Matcher() {}
67                        virtual void match( std::list< Expression * > &out ) = 0;
68                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
69                        ResolvExpr::AltList lhs, rhs;
70                        TupleAssignSpotter &spotter;
71                        ResolvExpr::Cost baseCost;
72                        std::list< ObjectDecl * > tmpDecls;
73                        ResolvExpr::TypeEnvironment compositeEnv;
74                };
75
76                struct MassAssignMatcher : public Matcher {
77                  public:
78                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
79                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
80                        virtual void match( std::list< Expression * > &out );
81                };
82
83                struct MultipleAssignMatcher : public Matcher {
84                  public:
85                        MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
86                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
87                        virtual void match( std::list< Expression * > &out );
88                };
89
90                ResolvExpr::AlternativeFinder &currentFinder;
91                std::string fname;
92                std::unique_ptr< Matcher > matcher;
93        };
94
95        /// true if expr is an expression of tuple type
96        bool isTuple( Expression *expr ) {
97                if ( ! expr ) return false;
98                assert( expr->result );
99                return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
100        }
101
102        template< typename AltIter >
103        bool isMultAssign( AltIter begin, AltIter end ) {
104                // multiple assignment if more than one alternative in the range or if
105                // the alternative is a tuple
106                if ( begin == end ) return false;
107                if ( isTuple( begin->expr ) ) return true;
108                return ++begin != end;
109        }
110
111        bool refToTuple( Expression *expr ) {
112                assert( expr->get_result() );
113                // also check for function returning tuple of reference types
114                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
115                        return refToTuple( castExpr->get_arg() );
116                } else {
117                        return isTuple( expr );
118                }
119                return false;
120        }
121
122        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
123                                std::vector<ResolvExpr::AlternativeFinder> &args ) {
124                TupleAssignSpotter spotter( currentFinder );
125                spotter.spot( expr, args );
126        }
127
128        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
129                : currentFinder(f) {}
130
131        void TupleAssignSpotter::spot( UntypedExpr * expr,
132                        std::vector<ResolvExpr::AlternativeFinder> &args ) {
133                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
134                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
135                                fname = op->get_name();
136
137                                // AlternativeFinder will naturally handle this case case, if it's legal
138                                if ( args.size() == 0 ) return;
139
140                                // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
141                                // the function, in which case AlternativeFinder will handle it normally
142                                if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;
143
144                                // look over all possible left-hand-sides
145                                for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
146                                        // skip non-tuple LHS
147                                        if ( ! refToTuple(lhsAlt.expr) ) continue;
148
149                                        // explode is aware of casts - ensure every LHS expression is sent into explode
150                                        // with a reference cast
151                                        // xxx - this seems to change the alternatives before the normal
152                                        //  AlternativeFinder flow; maybe this is desired?
153                                        if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
154                                                lhsAlt.expr = new CastExpr( lhsAlt.expr,
155                                                                new ReferenceType( Type::Qualifiers(),
156                                                                        lhsAlt.expr->result->clone() ) );
157                                        }
158
159                                        // explode the LHS so that each field of a tuple-valued-expr is assigned
160                                        ResolvExpr::AltList lhs;
161                                        explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
162                                        for ( ResolvExpr::Alternative& alt : lhs ) {
163                                                // each LHS value must be a reference - some come in with a cast expression,
164                                                // if not just cast to reference here
165                                                if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
166                                                        alt.expr = new CastExpr( alt.expr,
167                                                                new ReferenceType( Type::Qualifiers(),
168                                                                        alt.expr->get_result()->clone() ) );
169                                                }
170                                        }
171
172                                        if ( args.size() == 1 ) {
173                                                // mass default-initialization/destruction
174                                                ResolvExpr::AltList rhs{};
175                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
176                                                match();
177                                        } else if ( args.size() > 2 ) {
178                                                // expand all possible RHS possibilities
179                                                // TODO build iterative version of this instead of using combos
180                                                std::vector< ResolvExpr::AltList > rhsAlts;
181                                                combos( std::next(args.begin(), 1), args.end(),
182                                                        std::back_inserter( rhsAlts ) );
183                                                for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
184                                                        // multiple assignment
185                                                        ResolvExpr::AltList rhs;
186                                                        explode( rhsAlt, currentFinder.get_indexer(),
187                                                                std::back_inserter(rhs), true );
188                                                        matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
189                                                        match();
190                                                }
191                                        } else {
192                                                for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
193                                                        ResolvExpr::AltList rhs;
194                                                        if ( isTuple(rhsAlt.expr) ) {
195                                                                // multiple assignment
196                                                                explode( rhsAlt, currentFinder.get_indexer(),
197                                                                        std::back_inserter(rhs), true );
198                                                                matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
199                                                        } else {
200                                                                // mass assignment
201                                                                rhs.push_back( rhsAlt );
202                                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
203                                                        }
204                                                        match();
205                                                }
206                                        }
207                                }
208                        }
209                }
210        }
211
212        void TupleAssignSpotter::match() {
213                assert ( matcher != 0 );
214
215                std::list< Expression * > new_assigns;
216                matcher->match( new_assigns );
217
218                if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
219                        // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
220                        // if not the empty tuple case, return early so that no new alternatives are generated.
221                        if ( new_assigns.empty() ) return;
222                }
223                ResolvExpr::AltList current;
224                // now resolve new assignments
225                for ( std::list< Expression * >::iterator i = new_assigns.begin();
226                                i != new_assigns.end(); ++i ) {
227                        PRINT(
228                                std::cerr << "== resolving tuple assign ==" << std::endl;
229                                std::cerr << *i << std::endl;
230                        )
231
232                        ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
233                                currentFinder.get_environ() };
234                        try {
235                                finder.findWithAdjustment(*i);
236                        } catch (...) {
237                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
238                        }
239                        // prune expressions that don't coincide with
240                        ResolvExpr::AltList alts = finder.get_alternatives();
241                        assert( alts.size() == 1 );
242                        assert( alts.front().expr != 0 );
243                        current.push_back( alts.front() );
244                }
245
246                // extract expressions from the assignment alternatives to produce a list of assignments that
247                // together form a single alternative
248                std::list< Expression *> solved_assigns;
249                for ( ResolvExpr::Alternative & alt : current ) {
250                        solved_assigns.push_back( alt.expr->clone() );
251                }
252                // combine assignment environments into combined expression environment
253                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
254                // xxx -- was push_front
255                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
256                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
257                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
258        }
259
260        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
261                const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
262        : lhs(lhs), rhs(rhs), spotter(spotter),
263          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
264                simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
265                simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
266        }
267
268        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
269                assert( left );
270                std::list< Expression * > args;
271                args.push_back( new VariableExpr( left ) );
272                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
273                if ( right ) args.push_back( new VariableExpr( right ) );
274                if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
275                        args.front() = new AddressExpr( args.front() );
276                        if ( right ) args.back() = new AddressExpr( args.back() );
277                        return new UntypedExpr( new NameExpr( "?=?" ), args );
278                } else {
279                        return new UntypedExpr( new NameExpr( fname ), args );
280                }
281        }
282
283        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator, and adds the bindings to the compositeEnv
284        // xxx - maybe this should happen in alternative finder for every StmtExpr?
285        struct EnvRemover {
286                void previsit( ExprStmt * stmt ) {
287                        assert( compositeEnv );
288                        if ( stmt->expr->env ) {
289                                compositeEnv->add( *stmt->expr->env );
290                                delete stmt->expr->env;
291                                stmt->expr->env = nullptr;
292                        }
293                }
294
295                ResolvExpr::TypeEnvironment * compositeEnv = nullptr;
296        };
297
298        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
299                assert( expr->result && ! expr->get_result()->isVoid() );
300                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->result->clone(), new SingleInit( expr->clone() ) );
301                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
302                if ( ! dynamic_cast< ReferenceType * >( expr->result ) ) {
303                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
304                        ret->init = ctorInit;
305                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
306                        PassVisitor<EnvRemover> rm; // remove environments from subexpressions of StmtExprs
307                        rm.pass.compositeEnv = &compositeEnv;
308                        ctorInit->accept( rm );
309                }
310                PRINT( std::cerr << "new object: " << ret << std::endl; )
311                return ret;
312        }
313
314        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
315                static UniqueName lhsNamer( "__massassign_L" );
316                static UniqueName rhsNamer( "__massassign_R" );
317                // empty tuple case falls into this matcher, hence the second part of the assert
318                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
319
320                // xxx - may need to split this up into multiple declarations, because potential conversion to references
321                //  probably should not reference local variable - see MultipleAssignMatcher::match
322                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
323                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
324                        // create a temporary object for each value in the lhs and create a call involving the rhs
325                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
326                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
327                        tmpDecls.push_back( ltmp );
328                }
329                if ( rtmp ) tmpDecls.push_back( rtmp );
330        }
331
332        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
333                static UniqueName lhsNamer( "__multassign_L" );
334                static UniqueName rhsNamer( "__multassign_R" );
335
336                if ( lhs.size() == rhs.size() ) {
337                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
338                        std::list< ObjectDecl * > ltmp;
339                        std::list< ObjectDecl * > rtmp;
340                        for ( auto p : group_iterate( lhs, rhs ) ) {
341                                ResolvExpr::Alternative & lhsAlt = std::get<0>(p);
342                                ResolvExpr::Alternative & rhsAlt = std::get<1>(p);
343                                // convert RHS to LHS type minus one reference -- important for the case where LHS is && and RHS is lvalue, etc.
344                                ReferenceType * lhsType = strict_dynamic_cast<ReferenceType *>( lhsAlt.expr->result );
345                                rhsAlt.expr = new CastExpr( rhsAlt.expr, lhsType->base->clone() );
346                                ObjectDecl * lobj = newObject( lhsNamer, lhsAlt.expr );
347                                ObjectDecl * robj = newObject( rhsNamer, rhsAlt.expr );
348                                out.push_back( createFunc(spotter.fname, lobj, robj) );
349                                ltmp.push_back( lobj );
350                                rtmp.push_back( robj );
351                        }
352                        tmpDecls.splice( tmpDecls.end(), ltmp );
353                        tmpDecls.splice( tmpDecls.end(), rtmp );
354                }
355        }
356} // namespace Tuples
357
358// Local Variables: //
359// tab-width: 4 //
360// mode: c++ //
361// compile-command: "make install" //
362// End: //
Note: See TracBrowser for help on using the repository browser.