source: src/Tuples/TupleAssignment.cc @ bff227f

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

Refactor operator predicates into OperatorTable?.cc

  • Property mode set to 100644
File size: 11.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 "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
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->has_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.