source: src/Tuples/TupleAssignment.cc @ 9058414

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

Generate reference assignment for reference component of a tuple assignment

  • Property mode set to 100644
File size: 14.0 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->get_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.
284        // xxx - maybe this should happen in alternative finder for every StmtExpr?
285        // 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
286        struct EnvRemover {
287                void previsit( ExprStmt * stmt ) {
288                        delete stmt->expr->env;
289                        stmt->expr->env = nullptr;
290                }
291        };
292
293        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
294                assert( expr->result && ! expr->get_result()->isVoid() );
295                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
296                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
297                if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
298                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
299                        ret->init = ctorInit;
300                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
301                        PassVisitor<EnvRemover> rm; // remove environments from subexpressions of StmtExprs
302                        ctorInit->accept( rm );
303                }
304                PRINT( std::cerr << "new object: " << ret << std::endl; )
305                return ret;
306        }
307
308        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
309                static UniqueName lhsNamer( "__massassign_L" );
310                static UniqueName rhsNamer( "__massassign_R" );
311                // empty tuple case falls into this matcher, hence the second part of the assert
312                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
313
314                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
315                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
316                        // create a temporary object for each value in the lhs and create a call involving the rhs
317                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
318                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
319                        tmpDecls.push_back( ltmp );
320                }
321                if ( rtmp ) tmpDecls.push_back( rtmp );
322        }
323
324        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
325                static UniqueName lhsNamer( "__multassign_L" );
326                static UniqueName rhsNamer( "__multassign_R" );
327
328                if ( lhs.size() == rhs.size() ) {
329                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
330                        std::list< ObjectDecl * > ltmp;
331                        std::list< ObjectDecl * > rtmp;
332                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
333                                return newObject( lhsNamer, alt.expr );
334                        });
335                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
336                                return newObject( rhsNamer, alt.expr );
337                        });
338                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
339                        tmpDecls.splice( tmpDecls.end(), ltmp );
340                        tmpDecls.splice( tmpDecls.end(), rtmp );
341                }
342        }
343} // namespace Tuples
344
345// Local Variables: //
346// tab-width: 4 //
347// mode: c++ //
348// compile-command: "make install" //
349// End: //
Note: See TracBrowser for help on using the repository browser.