source: src/Tuples/TupleAssignment.cc @ 7d49b72

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

Fix tuple assignment for tuple expression LHS by adding reference cast to every component

  • Property mode set to 100644
File size: 12.2 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 "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 "CodeGen/OperatorTable.h"
25#include "InitTweak/InitTweak.h"
26#include "InitTweak/GenInit.h"
27
28#include <functional>
29#include <algorithm>
30#include <iterator>
31#include <iostream>
32#include <cassert>
33#include <set>
34#include <unordered_set>
35
36namespace Tuples {
37        class TupleAssignSpotter {
38          public:
39                // dispatcher for Tuple (multiple and mass) assignment operations
40                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
41                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
42
43          private:
44                void match();
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
77        bool isTuple( Expression *expr ) {
78                if ( ! expr ) return false;
79                assert( expr->has_result() );
80                return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
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 refToTuple( Expression *expr ) {
93                assert( expr->get_result() );
94                // also check for function returning tuple of reference types
95                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
96                        return refToTuple( castExpr->get_arg() );
97                } else {
98                        return isTuple( expr );
99                }
100                return false;
101        }
102
103        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
104                TupleAssignSpotter spotter( currentFinder );
105                spotter.spot( expr, possibilities );
106        }
107
108        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
109                : currentFinder(f) {}
110
111        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
112                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
113                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
114                                fname = op->get_name();
115                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
116                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
117                                        if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) {
118                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
119                                                continue;
120                                        }
121
122                                        assert( ! ali->empty() );
123                                        // grab args 2-N and group into a TupleExpr
124                                        const ResolvExpr::Alternative & alt1 = ali->front();
125                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
126                                        if ( refToTuple(alt1.expr) ) {
127                                                if ( isMultAssign( begin, end ) ) {
128                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
129                                                } else {
130                                                        // mass assignment
131                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
132                                                }
133                                                match();
134                                        }
135                                }
136                        }
137                }
138        }
139
140        void TupleAssignSpotter::match() {
141                assert ( matcher != 0 );
142
143                std::list< Expression * > new_assigns;
144                matcher->match( new_assigns );
145
146                if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
147                        // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
148                        // if not the empty tuple case, return early so that no new alternatives are generated.
149                        if ( new_assigns.empty() ) return;
150                }
151                ResolvExpr::AltList current;
152                // now resolve new assignments
153                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
154                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
155                        try {
156                                finder.findWithAdjustment(*i);
157                        } catch (...) {
158                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
159                        }
160                        // prune expressions that don't coincide with
161                        ResolvExpr::AltList alts = finder.get_alternatives();
162                        assert( alts.size() == 1 );
163                        assert( alts.front().expr != 0 );
164                        current.push_back( alts.front() );
165                }
166
167                // extract expressions from the assignment alternatives to produce a list of assignments that
168                // together form a single alternative
169                std::list< Expression *> solved_assigns;
170                for ( ResolvExpr::Alternative & alt : current ) {
171                        solved_assigns.push_back( alt.expr->clone() );
172                }
173                // combine assignment environments into combined expression environment
174                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
175                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
176        }
177
178        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
179                assert( ! alts.empty() );
180                // combine argument environments into combined expression environment
181                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
182
183                ResolvExpr::Alternative lhsAlt = alts.front();
184                // peel off the cast that exists on ctor/dtor expressions
185                bool isCast = false;
186                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
187                        lhsAlt.expr = castExpr->get_arg();
188                        castExpr->set_arg( nullptr );
189                        delete castExpr;
190                        isCast = true;
191                }
192
193                // explode the lhs so that each field of the tuple-valued-expr is assigned.
194                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
195
196                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
197                if ( isCast ) {
198                        for ( ResolvExpr::Alternative & alt : lhs ) {
199                                Expression *& expr = alt.expr;
200                                Type * type = expr->get_result()->clone();
201                                type->get_qualifiers() -= Type::Qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Atomic );
202                                expr = new CastExpr( expr, new ReferenceType( Type::Qualifiers(), type ) );
203                        }
204                }
205
206                for ( ResolvExpr::Alternative & alt : lhs ) {
207                        // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here.
208                        // TODO: can this somehow be merge with the cast code directly above?
209                        if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) {
210                                alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) );
211                        }
212                }
213        }
214
215        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
216                assert( alts.size() == 1 || alts.size() == 2 );
217                if ( alts.size() == 2 ) {
218                        rhs.push_back( alts.back() );
219                }
220        }
221
222        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
223                // explode the rhs so that each field of the tuple-valued-expr is assigned.
224                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
225        }
226
227        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
228                assert( left );
229                std::list< Expression * > args;
230                args.push_back( new VariableExpr( left ) );
231                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
232                if ( right ) args.push_back( new VariableExpr( right ) );
233                return new UntypedExpr( new NameExpr( fname ), args );
234        }
235
236        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
237        // xxx - maybe this should happen in alternative finder for every StmtExpr?
238        // 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
239        struct EnvRemover : public Visitor {
240                virtual void visit( ExprStmt * stmt ) {
241                        delete stmt->get_expr()->get_env();
242                        stmt->get_expr()->set_env( nullptr );
243                        Visitor::visit( stmt );
244                }
245        };
246
247        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
248                assert( expr->has_result() && ! expr->get_result()->isVoid() );
249                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
250                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
251                if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
252                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
253                        ret->set_init( ctorInit );
254                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
255                        EnvRemover rm; // remove environments from subexpressions of StmtExprs
256                        ctorInit->accept( rm );
257                }
258                return ret;
259        }
260
261        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
262                static UniqueName lhsNamer( "__massassign_L" );
263                static UniqueName rhsNamer( "__massassign_R" );
264                // empty tuple case falls into this matcher, hence the second part of the assert
265                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
266
267                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
268                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
269                        // create a temporary object for each value in the lhs and create a call involving the rhs
270                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
271                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
272                        tmpDecls.push_back( ltmp );
273                }
274                if ( rtmp ) tmpDecls.push_back( rtmp );
275        }
276
277        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
278                static UniqueName lhsNamer( "__multassign_L" );
279                static UniqueName rhsNamer( "__multassign_R" );
280
281                if ( lhs.size() == rhs.size() ) {
282                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
283                        std::list< ObjectDecl * > ltmp;
284                        std::list< ObjectDecl * > rtmp;
285                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
286                                return newObject( lhsNamer, alt.expr );
287                        });
288                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
289                                return newObject( rhsNamer, alt.expr );
290                        });
291                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
292                        tmpDecls.splice( tmpDecls.end(), ltmp );
293                        tmpDecls.splice( tmpDecls.end(), rtmp );
294                }
295        }
296} // namespace Tuples
297
298// Local Variables: //
299// tab-width: 4 //
300// mode: c++ //
301// compile-command: "make install" //
302// End: //
Note: See TracBrowser for help on using the repository browser.