source: src/Tuples/TupleAssignment.cc @ 1d2b64f

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 1d2b64f was 1d2b64f, checked in by Rob Schluntz <rschlunt@…>, 5 years ago

combine environments and costs in tuple assignment, resolve ctor/dtors for tuple assignment temporaries

  • Property mode set to 100644
File size: 11.3 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 : Rob Schluntz
12// Last Modified On : Wed Nov 9 13:48:42 2016
13// Update Count     : 2
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 "InitTweak/InitTweak.h"
25#include "InitTweak/GenInit.h"
26
27#include <functional>
28#include <algorithm>
29#include <iterator>
30#include <iostream>
31#include <cassert>
32#include <set>
33#include <unordered_set>
34
35namespace Tuples {
36        class TupleAssignSpotter {
37          public:
38                // dispatcher for Tuple (multiple and mass) assignment operations
39                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
40                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
41
42          private:
43                void match();
44
45                struct Matcher {
46                  public:
47                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
48                        virtual ~Matcher() {}
49                        virtual void match( std::list< Expression * > &out ) = 0;
50                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
51                        ResolvExpr::AltList lhs, rhs;
52                        TupleAssignSpotter &spotter;
53                        ResolvExpr::Cost baseCost;
54                        std::list< ObjectDecl * > tmpDecls;
55                        ResolvExpr::TypeEnvironment compositeEnv;
56                };
57
58                struct MassAssignMatcher : public Matcher {
59                  public:
60                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
61                        virtual void match( std::list< Expression * > &out );
62                };
63
64                struct MultipleAssignMatcher : public Matcher {
65                  public:
66                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
67                        virtual void match( std::list< Expression * > &out );
68                };
69
70                ResolvExpr::AlternativeFinder &currentFinder;
71                std::string fname;
72                std::unique_ptr< Matcher > matcher;
73        };
74
75        /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function
76        bool isTuple( Expression *expr ) {
77                if ( ! expr ) return false;
78                assert( expr->has_result() );
79                return dynamic_cast<TupleExpr *>(expr) || expr->get_result()->size() > 1;
80        }
81
82        template< typename AltIter >
83        bool isMultAssign( AltIter begin, AltIter end ) {
84                // multiple assignment if more than one alternative in the range or if
85                // the alternative is a tuple
86                if ( begin == end ) return false;
87                if ( isTuple( begin->expr ) ) return true;
88                return ++begin != end;
89        }
90
91        bool pointsToTuple( Expression *expr ) {
92                // also check for function returning tuple of reference types
93                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
94                        return pointsToTuple( castExpr->get_arg() );
95                } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
96                        return isTuple( addr->get_arg() );
97                }
98                return false;
99        }
100
101        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
102                TupleAssignSpotter spotter( currentFinder );
103                spotter.spot( expr, possibilities );
104        }
105
106        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
107                : currentFinder(f) {}
108
109        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
110                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
111                        if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
112                                fname = op->get_name();
113                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
114                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
115                                        if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
116                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
117                                                continue;
118                                        }
119
120                                        assert( ! ali->empty() );
121                                        // grab args 2-N and group into a TupleExpr
122                                        const ResolvExpr::Alternative & alt1 = ali->front();
123                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
124                                        if ( pointsToTuple(alt1.expr) ) {
125                                                if ( isMultAssign( begin, end ) ) {
126                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
127                                                } else {
128                                                        // mass assignment
129                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
130                                                }
131                                                match();
132                                        }
133                                }
134                        }
135                }
136        }
137
138        void TupleAssignSpotter::match() {
139                assert ( matcher != 0 );
140
141                std::list< Expression * > new_assigns;
142                matcher->match( new_assigns );
143
144                if ( new_assigns.empty() ) return;
145                ResolvExpr::AltList current;
146                // now resolve new assignments
147                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
148                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
149                        try {
150                                finder.findWithAdjustment(*i);
151                        } catch (...) {
152                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
153                        }
154                        // prune expressions that don't coincide with
155                        ResolvExpr::AltList alts = finder.get_alternatives();
156                        assert( alts.size() == 1 );
157                        assert( alts.front().expr != 0 );
158                        current.push_back( alts.front() );
159                }
160
161                // extract expressions from the assignment alternatives to produce a list of assignments that
162                // together form a single alternative
163                std::list< Expression *> solved_assigns;
164                for ( ResolvExpr::Alternative & alt : current ) {
165                        solved_assigns.push_back( alt.expr->clone() );
166                }
167                // combine assignment environments into combined expression environment
168                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
169                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
170        }
171
172        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
173                assert( ! alts.empty() );
174                // combine argument environments into combined expression environment
175                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
176
177                ResolvExpr::Alternative lhsAlt = alts.front();
178                // peel off the cast that exists on ctor/dtor expressions
179                bool isCast = false;
180                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
181                        lhsAlt.expr = castExpr->get_arg();
182                        castExpr->set_arg( nullptr );
183                        delete castExpr;
184                        isCast = true;
185                }
186
187                // explode the lhs so that each field of the tuple-valued-expr is assigned.
188                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs) );
189
190                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
191                if ( isCast ) {
192                        for ( ResolvExpr::Alternative & alt : lhs ) {
193                                Expression *& expr = alt.expr;
194                                Type * castType = expr->get_result()->clone();
195                                Type * type = InitTweak::getPointerBase( castType );
196                                assert( type );
197                                type->get_qualifiers() -= Type::Qualifiers(true, true, true, false, true, true);
198                                type->set_isLvalue( true ); // xxx - might not need this
199                                expr = new CastExpr( expr, castType );
200                        }
201                }
202        }
203
204        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
205                assert( alts.size() == 1 || alts.size() == 2 );
206                if ( alts.size() == 2 ) {
207                        rhs.push_back( alts.back() );
208                }
209        }
210
211        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
212                // explode the rhs so that each field of the tuple-valued-expr is assigned.
213                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs) );
214        }
215
216        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
217                assert( left );
218                std::list< Expression * > args;
219                args.push_back( new AddressExpr( UntypedExpr::createDeref( new VariableExpr( left ) ) ) );
220                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
221                if ( right ) args.push_back( new VariableExpr( right ) );
222                return new UntypedExpr( new NameExpr( fname ), args );
223        }
224
225        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
226        // xxx - maybe this should happen in alternative finder for every StmtExpr?
227        // 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
228        struct EnvRemover : public Visitor {
229                virtual void visit( ExprStmt * stmt ) {
230                        delete stmt->get_expr()->get_env();
231                        stmt->get_expr()->set_env( nullptr );
232                        Visitor::visit( stmt );
233                }
234        };
235
236        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
237                assert( expr->has_result() && ! expr->get_result()->isVoid() );
238                ObjectDecl * ret = new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
239                ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
240                ret->set_init( ctorInit );
241                ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
242                EnvRemover rm; // remove environments from subexpressions of StmtExprs
243                ctorInit->accept( rm );
244                return ret;
245        }
246
247        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
248                static UniqueName lhsNamer( "__massassign_L" );
249                static UniqueName rhsNamer( "__massassign_R" );
250                assert ( ! lhs.empty() && rhs.size() <= 1);
251
252                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
253                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
254                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
255                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
256                        tmpDecls.push_back( ltmp );
257                }
258                if ( rtmp ) tmpDecls.push_back( rtmp );
259        }
260
261        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
262                static UniqueName lhsNamer( "__multassign_L" );
263                static UniqueName rhsNamer( "__multassign_R" );
264
265                // xxx - need more complicated matching?
266                if ( lhs.size() == rhs.size() ) {
267                        std::list< ObjectDecl * > ltmp;
268                        std::list< ObjectDecl * > rtmp;
269                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
270                                return newObject( lhsNamer, alt.expr );
271                        });
272                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
273                                return newObject( rhsNamer, alt.expr );
274                        });
275                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
276                        tmpDecls.splice( tmpDecls.end(), ltmp );
277                        tmpDecls.splice( tmpDecls.end(), rtmp );
278                }
279        }
280} // namespace Tuples
281
282// Local Variables: //
283// tab-width: 4 //
284// mode: c++ //
285// compile-command: "make install" //
286// End: //
Note: See TracBrowser for help on using the repository browser.