source: src/Tuples/TupleAssignment.cc @ effdde0

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 effdde0 was d29fa5f, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Remove has_result

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