source: src/Tuples/TupleAssignment.cc @ f585450

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

Add debug prints to TupleAssignment?.cc

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