source: src/Tuples/TupleAssignment.cc @ 03321e4

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 03321e4 was 03321e4, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Fixed headers for tuples folder

  • Property mode set to 100644
File size: 12.9 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
23#include "Common/UniqueName.h"             // for UniqueName
24#include "Common/utility.h"                // for zipWith
25#include "Explode.h"                       // for explode
26#include "InitTweak/GenInit.h"             // for genCtorInit
27#include "InitTweak/InitTweak.h"           // for getPointerBase, isAssignment
28#include "Parser/LinkageSpec.h"            // for Cforall
29#include "ResolvExpr/Alternative.h"        // for AltList, Alternative
30#include "ResolvExpr/AlternativeFinder.h"  // for AlternativeFinder, simpleC...
31#include "ResolvExpr/Cost.h"               // for Cost
32#include "ResolvExpr/Resolver.h"           // for resolveCtorInit
33#include "ResolvExpr/TypeEnvironment.h"    // for TypeEnvironment
34#include "SynTree/Declaration.h"           // for ObjectDecl
35#include "SynTree/Expression.h"            // for Expression, CastExpr, Name...
36#include "SynTree/Initializer.h"           // for ConstructorInit, SingleInit
37#include "SynTree/Statement.h"             // for ExprStmt
38#include "SynTree/Type.h"                  // for Type, Type::Qualifiers
39#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
40#include "SynTree/Visitor.h"               // for Visitor
41
42namespace Tuples {
43        class TupleAssignSpotter {
44          public:
45                // dispatcher for Tuple (multiple and mass) assignment operations
46                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
47                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
48
49          private:
50                void match();
51
52                struct Matcher {
53                  public:
54                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
55                        virtual ~Matcher() {}
56                        virtual void match( std::list< Expression * > &out ) = 0;
57                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
58                        ResolvExpr::AltList lhs, rhs;
59                        TupleAssignSpotter &spotter;
60                        ResolvExpr::Cost baseCost;
61                        std::list< ObjectDecl * > tmpDecls;
62                        ResolvExpr::TypeEnvironment compositeEnv;
63                };
64
65                struct MassAssignMatcher : public Matcher {
66                  public:
67                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
68                        virtual void match( std::list< Expression * > &out );
69                };
70
71                struct MultipleAssignMatcher : public Matcher {
72                  public:
73                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
74                        virtual void match( std::list< Expression * > &out );
75                };
76
77                ResolvExpr::AlternativeFinder &currentFinder;
78                std::string fname;
79                std::unique_ptr< Matcher > matcher;
80        };
81
82        /// true if expr is an expression of tuple type
83        bool isTuple( Expression *expr ) {
84                if ( ! expr ) return false;
85                assert( expr->has_result() );
86                return dynamic_cast< TupleType * >( expr->get_result() );
87        }
88
89        template< typename AltIter >
90        bool isMultAssign( AltIter begin, AltIter end ) {
91                // multiple assignment if more than one alternative in the range or if
92                // the alternative is a tuple
93                if ( begin == end ) return false;
94                if ( isTuple( begin->expr ) ) return true;
95                return ++begin != end;
96        }
97
98        bool pointsToTuple( Expression *expr ) {
99                // also check for function returning tuple of reference types
100                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
101                        return pointsToTuple( castExpr->get_arg() );
102                } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
103                        return isTuple( addr->get_arg() );
104                }
105                return false;
106        }
107
108        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
109                TupleAssignSpotter spotter( currentFinder );
110                spotter.spot( expr, possibilities );
111        }
112
113        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
114                : currentFinder(f) {}
115
116        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
117                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
118                        if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
119                                fname = op->get_name();
120                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
121                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
122                                        if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
123                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
124                                                continue;
125                                        }
126
127                                        assert( ! ali->empty() );
128                                        // grab args 2-N and group into a TupleExpr
129                                        const ResolvExpr::Alternative & alt1 = ali->front();
130                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
131                                        if ( pointsToTuple(alt1.expr) ) {
132                                                if ( isMultAssign( begin, end ) ) {
133                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
134                                                } else {
135                                                        // mass assignment
136                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
137                                                }
138                                                match();
139                                        }
140                                }
141                        }
142                }
143        }
144
145        void TupleAssignSpotter::match() {
146                assert ( matcher != 0 );
147
148                std::list< Expression * > new_assigns;
149                matcher->match( new_assigns );
150
151                if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
152                        // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
153                        // if not the empty tuple case, return early so that no new alternatives are generated.
154                        if ( new_assigns.empty() ) return;
155                }
156                ResolvExpr::AltList current;
157                // now resolve new assignments
158                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
159                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
160                        try {
161                                finder.findWithAdjustment(*i);
162                        } catch (...) {
163                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
164                        }
165                        // prune expressions that don't coincide with
166                        ResolvExpr::AltList alts = finder.get_alternatives();
167                        assert( alts.size() == 1 );
168                        assert( alts.front().expr != 0 );
169                        current.push_back( alts.front() );
170                }
171
172                // extract expressions from the assignment alternatives to produce a list of assignments that
173                // together form a single alternative
174                std::list< Expression *> solved_assigns;
175                for ( ResolvExpr::Alternative & alt : current ) {
176                        solved_assigns.push_back( alt.expr->clone() );
177                }
178                // combine assignment environments into combined expression environment
179                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
180                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
181        }
182
183        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
184                assert( ! alts.empty() );
185                // combine argument environments into combined expression environment
186                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
187
188                ResolvExpr::Alternative lhsAlt = alts.front();
189                // peel off the cast that exists on ctor/dtor expressions
190                bool isCast = false;
191                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
192                        lhsAlt.expr = castExpr->get_arg();
193                        castExpr->set_arg( nullptr );
194                        delete castExpr;
195                        isCast = true;
196                }
197
198                // explode the lhs so that each field of the tuple-valued-expr is assigned.
199                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
200
201                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
202                if ( isCast ) {
203                        for ( ResolvExpr::Alternative & alt : lhs ) {
204                                Expression *& expr = alt.expr;
205                                Type * castType = expr->get_result()->clone();
206                                Type * type = InitTweak::getPointerBase( castType );
207                                assert( type );
208                                type->get_qualifiers() -= Type::Qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Atomic );
209                                type->set_lvalue( true ); // xxx - might not need this
210                                expr = new CastExpr( expr, castType );
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 AddressExpr( UntypedExpr::createDeref( 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                ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
251                ret->set_init( ctorInit );
252                ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
253                EnvRemover rm; // remove environments from subexpressions of StmtExprs
254                ctorInit->accept( rm );
255                return ret;
256        }
257
258        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
259                static UniqueName lhsNamer( "__massassign_L" );
260                static UniqueName rhsNamer( "__massassign_R" );
261                // empty tuple case falls into this matcher, hence the second part of the assert
262                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
263
264                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
265                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
266                        // create a temporary object for each value in the lhs and create a call involving the rhs
267                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
268                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
269                        tmpDecls.push_back( ltmp );
270                }
271                if ( rtmp ) tmpDecls.push_back( rtmp );
272        }
273
274        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
275                static UniqueName lhsNamer( "__multassign_L" );
276                static UniqueName rhsNamer( "__multassign_R" );
277
278                if ( lhs.size() == rhs.size() ) {
279                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
280                        std::list< ObjectDecl * > ltmp;
281                        std::list< ObjectDecl * > rtmp;
282                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
283                                return newObject( lhsNamer, alt.expr );
284                        });
285                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
286                                return newObject( rhsNamer, alt.expr );
287                        });
288                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
289                        tmpDecls.splice( tmpDecls.end(), ltmp );
290                        tmpDecls.splice( tmpDecls.end(), rtmp );
291                }
292        }
293} // namespace Tuples
294
295// Local Variables: //
296// tab-width: 4 //
297// mode: c++ //
298// compile-command: "make install" //
299// End: //
Note: See TracBrowser for help on using the repository browser.