source: src/Tuples/TupleAssignment.cc @ 3f7e12c

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 3f7e12c was 3f7e12c, checked in by Aaron Moss <a3moss@…>, 4 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

  • 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                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(
254                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, 
255                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
256        }
257
258        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, 
259                const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs ) 
260        : lhs(lhs), rhs(rhs), spotter(spotter), 
261          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
262                simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
263                simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
264        }
265
266        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
267                assert( left );
268                std::list< Expression * > args;
269                args.push_back( new VariableExpr( left ) );
270                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
271                if ( right ) args.push_back( new VariableExpr( right ) );
272                return new UntypedExpr( new NameExpr( fname ), args );
273        }
274
275        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
276        // xxx - maybe this should happen in alternative finder for every StmtExpr?
277        // 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
278        struct EnvRemover : public Visitor {
279                virtual void visit( ExprStmt * stmt ) {
280                        delete stmt->get_expr()->get_env();
281                        stmt->get_expr()->set_env( nullptr );
282                        Visitor::visit( stmt );
283                }
284        };
285
286        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
287                assert( expr->result && ! expr->get_result()->isVoid() );
288                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
289                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
290                if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
291                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
292                        ret->set_init( ctorInit );
293                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
294                        EnvRemover rm; // remove environments from subexpressions of StmtExprs
295                        ctorInit->accept( rm );
296                }
297                PRINT( std::cerr << "new object: " << ret << std::endl; )
298                return ret;
299        }
300
301        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
302                static UniqueName lhsNamer( "__massassign_L" );
303                static UniqueName rhsNamer( "__massassign_R" );
304                // empty tuple case falls into this matcher, hence the second part of the assert
305                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
306
307                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
308                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
309                        // create a temporary object for each value in the lhs and create a call involving the rhs
310                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
311                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
312                        tmpDecls.push_back( ltmp );
313                }
314                if ( rtmp ) tmpDecls.push_back( rtmp );
315        }
316
317        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
318                static UniqueName lhsNamer( "__multassign_L" );
319                static UniqueName rhsNamer( "__multassign_R" );
320
321                if ( lhs.size() == rhs.size() ) {
322                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
323                        std::list< ObjectDecl * > ltmp;
324                        std::list< ObjectDecl * > rtmp;
325                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
326                                return newObject( lhsNamer, alt.expr );
327                        });
328                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
329                                return newObject( rhsNamer, alt.expr );
330                        });
331                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
332                        tmpDecls.splice( tmpDecls.end(), ltmp );
333                        tmpDecls.splice( tmpDecls.end(), rtmp );
334                }
335        }
336} // namespace Tuples
337
338// Local Variables: //
339// tab-width: 4 //
340// mode: c++ //
341// compile-command: "make install" //
342// End: //
Note: See TracBrowser for help on using the repository browser.