source: src/Tuples/TupleAssignment.cc @ 8a78dd3

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 8a78dd3 was bd4f2e9, checked in by Aaron Moss <a3moss@…>, 7 years ago

Switch AltList? to std::vector from std::list

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