source: src/Tuples/TupleAssignment.cc @ 5fb6830

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

Simplify tuple assignment code now that explode is reference-cast-aware

  • Property mode set to 100644
File size: 11.7 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                // explode is aware of casts - ensure every LHS expression is sent into explode with a reference cast
185                if ( ! dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
186                        lhsAlt.expr = new CastExpr( lhsAlt.expr, new ReferenceType( Type::Qualifiers(), lhsAlt.expr->get_result()->clone() ) );
187                }
188
189                // explode the lhs so that each field of the tuple-valued-expr is assigned.
190                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
191
192                for ( ResolvExpr::Alternative & alt : lhs ) {
193                        // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here.
194                        if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) {
195                                alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) );
196                        }
197                }
198        }
199
200        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
201                assert( alts.size() == 1 || alts.size() == 2 );
202                if ( alts.size() == 2 ) {
203                        rhs.push_back( alts.back() );
204                }
205        }
206
207        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
208                // explode the rhs so that each field of the tuple-valued-expr is assigned.
209                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
210        }
211
212        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
213                assert( left );
214                std::list< Expression * > args;
215                args.push_back( new VariableExpr( left ) );
216                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
217                if ( right ) args.push_back( new VariableExpr( right ) );
218                return new UntypedExpr( new NameExpr( fname ), args );
219        }
220
221        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
222        // xxx - maybe this should happen in alternative finder for every StmtExpr?
223        // 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
224        struct EnvRemover : public Visitor {
225                virtual void visit( ExprStmt * stmt ) {
226                        delete stmt->get_expr()->get_env();
227                        stmt->get_expr()->set_env( nullptr );
228                        Visitor::visit( stmt );
229                }
230        };
231
232        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
233                assert( expr->has_result() && ! expr->get_result()->isVoid() );
234                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
235                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
236                if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
237                        ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
238                        ret->set_init( ctorInit );
239                        ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
240                        EnvRemover rm; // remove environments from subexpressions of StmtExprs
241                        ctorInit->accept( rm );
242                }
243                return ret;
244        }
245
246        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
247                static UniqueName lhsNamer( "__massassign_L" );
248                static UniqueName rhsNamer( "__massassign_R" );
249                // empty tuple case falls into this matcher, hence the second part of the assert
250                assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
251
252                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
253                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
254                        // create a temporary object for each value in the lhs and create a call involving the rhs
255                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
256                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
257                        tmpDecls.push_back( ltmp );
258                }
259                if ( rtmp ) tmpDecls.push_back( rtmp );
260        }
261
262        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
263                static UniqueName lhsNamer( "__multassign_L" );
264                static UniqueName rhsNamer( "__multassign_R" );
265
266                if ( lhs.size() == rhs.size() ) {
267                        // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
268                        std::list< ObjectDecl * > ltmp;
269                        std::list< ObjectDecl * > rtmp;
270                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
271                                return newObject( lhsNamer, alt.expr );
272                        });
273                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
274                                return newObject( rhsNamer, alt.expr );
275                        });
276                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
277                        tmpDecls.splice( tmpDecls.end(), ltmp );
278                        tmpDecls.splice( tmpDecls.end(), rtmp );
279                }
280        }
281} // namespace Tuples
282
283// Local Variables: //
284// tab-width: 4 //
285// mode: c++ //
286// compile-command: "make install" //
287// End: //
Note: See TracBrowser for help on using the repository browser.