source: src/Tuples/TupleAssignment.cc@ 4c8621ac

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 4c8621ac was 4c8621ac, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

allow construction, destruction, and assignment for empty tuples, allow matching a ttype parameter with an empty tuple, fix specialization to work with empty tuples and void functions
  • Property mode set to 100644
File size: 13.5 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 : Rob Schluntz
12// Last Modified On : Wed Nov 9 13:48:42 2016
13// Update Count : 2
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 "InitTweak/InitTweak.h"
25#include "InitTweak/GenInit.h"
26
27#include <functional>
28#include <algorithm>
29#include <iterator>
30#include <iostream>
31#include <cassert>
32#include <set>
33#include <unordered_set>
34
35namespace Tuples {
36 class TupleAssignSpotter {
37 public:
38 // dispatcher for Tuple (multiple and mass) assignment operations
39 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
40 void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
41
42 private:
43 void match();
44 void handleEmptyTuple( const ResolvExpr::AltList & alts );
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, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function
77 bool isTuple( Expression *expr ) {
78 if ( ! expr ) return false;
79 assert( expr->has_result() );
80 return dynamic_cast<TupleExpr *>(expr) || expr->get_result()->size() > 1;
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 pointsToTuple( Expression *expr ) {
93 // also check for function returning tuple of reference types
94 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
95 return pointsToTuple( castExpr->get_arg() );
96 } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
97 return isTuple( addr->get_arg() );
98 }
99 return false;
100 }
101
102 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
103 TupleAssignSpotter spotter( currentFinder );
104 spotter.spot( expr, possibilities );
105 }
106
107 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
108 : currentFinder(f) {}
109
110 void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
111 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
112 if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
113 fname = op->get_name();
114 for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
115 if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
116 if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
117 // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
118 continue;
119 }
120
121 assert( ! ali->empty() );
122 // grab args 2-N and group into a TupleExpr
123 const ResolvExpr::Alternative & alt1 = ali->front();
124 auto begin = std::next(ali->begin(), 1), end = ali->end();
125 if ( pointsToTuple(alt1.expr) ) {
126 if ( isMultAssign( begin, end ) ) {
127 matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
128 } else {
129 // mass assignment
130 matcher.reset( new MassAssignMatcher( *this, *ali ) );
131 }
132 match();
133 } else {
134 // handle empty case specially. It is easy to cause conflicts for tuple assignment when we consider any expression with Tuple type to be a tuple.
135 // Instead, only tuple expressions and expressions with at least 2 results are considered tuples for tuple assignment. This most obviously leaves out the
136 // nullary and unary cases. The unary case is handled nicely by the alternative finder as is. For example, an expression of type [int] will be exploded
137 // into a list of one element (combined with the RHS elements), which will easily allow for intrinsic construction. This seems like a best case scenario anyway,
138 // since intrinsic construction is much simpler from a code-gen perspective than tuple construction is.
139 // This leaves the empty case, which is not easily handled by existing alternative finder logic. Instead, it seems simple enough to hanlde here that if the left
140 // side is an empty tuple, then the right side is allowed to be either an empty tuple or an empty list. Fortunately, these cases are identical when exploded.
141 handleEmptyTuple( *ali );
142 }
143 }
144 }
145 }
146 }
147
148 void TupleAssignSpotter::match() {
149 assert ( matcher != 0 );
150
151 std::list< Expression * > new_assigns;
152 matcher->match( new_assigns );
153
154 if ( new_assigns.empty() ) return;
155 ResolvExpr::AltList current;
156 // now resolve new assignments
157 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
158 ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
159 try {
160 finder.findWithAdjustment(*i);
161 } catch (...) {
162 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
163 }
164 // prune expressions that don't coincide with
165 ResolvExpr::AltList alts = finder.get_alternatives();
166 assert( alts.size() == 1 );
167 assert( alts.front().expr != 0 );
168 current.push_back( alts.front() );
169 }
170
171 // extract expressions from the assignment alternatives to produce a list of assignments that
172 // together form a single alternative
173 std::list< Expression *> solved_assigns;
174 for ( ResolvExpr::Alternative & alt : current ) {
175 solved_assigns.push_back( alt.expr->clone() );
176 }
177 // combine assignment environments into combined expression environment
178 simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
179 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current ) + matcher->baseCost ) );
180 }
181
182 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
183 assert( ! alts.empty() );
184 // combine argument environments into combined expression environment
185 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
186
187 ResolvExpr::Alternative lhsAlt = alts.front();
188 // peel off the cast that exists on ctor/dtor expressions
189 bool isCast = false;
190 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
191 lhsAlt.expr = castExpr->get_arg();
192 castExpr->set_arg( nullptr );
193 delete castExpr;
194 isCast = true;
195 }
196
197 // explode the lhs so that each field of the tuple-valued-expr is assigned.
198 explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs) );
199
200 // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
201 if ( isCast ) {
202 for ( ResolvExpr::Alternative & alt : lhs ) {
203 Expression *& expr = alt.expr;
204 Type * castType = expr->get_result()->clone();
205 Type * type = InitTweak::getPointerBase( castType );
206 assert( type );
207 type->get_qualifiers() -= Type::Qualifiers(true, true, true, false, true, true);
208 type->set_isLvalue( true ); // xxx - might not need this
209 expr = new CastExpr( expr, castType );
210 }
211 }
212 }
213
214 TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
215 assert( alts.size() == 1 || alts.size() == 2 );
216 if ( alts.size() == 2 ) {
217 rhs.push_back( alts.back() );
218 }
219 }
220
221 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
222 // explode the rhs so that each field of the tuple-valued-expr is assigned.
223 explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs) );
224 }
225
226 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
227 assert( left );
228 std::list< Expression * > args;
229 args.push_back( new AddressExpr( UntypedExpr::createDeref( new VariableExpr( left ) ) ) );
230 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
231 if ( right ) args.push_back( new VariableExpr( right ) );
232 return new UntypedExpr( new NameExpr( fname ), args );
233 }
234
235 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
236 // xxx - maybe this should happen in alternative finder for every StmtExpr?
237 // 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
238 struct EnvRemover : public Visitor {
239 virtual void visit( ExprStmt * stmt ) {
240 delete stmt->get_expr()->get_env();
241 stmt->get_expr()->set_env( nullptr );
242 Visitor::visit( stmt );
243 }
244 };
245
246 ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
247 assert( expr->has_result() && ! expr->get_result()->isVoid() );
248 ObjectDecl * ret = new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
249 ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
250 ret->set_init( ctorInit );
251 ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
252 EnvRemover rm; // remove environments from subexpressions of StmtExprs
253 ctorInit->accept( rm );
254 return ret;
255 }
256
257 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
258 static UniqueName lhsNamer( "__massassign_L" );
259 static UniqueName rhsNamer( "__massassign_R" );
260 assert( ! lhs.empty() && rhs.size() <= 1 );
261
262 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
263 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
264 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
265 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
266 tmpDecls.push_back( ltmp );
267 }
268 if ( rtmp ) tmpDecls.push_back( rtmp );
269 }
270
271 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
272 static UniqueName lhsNamer( "__multassign_L" );
273 static UniqueName rhsNamer( "__multassign_R" );
274
275 // xxx - need more complicated matching?
276 if ( lhs.size() == rhs.size() ) {
277 std::list< ObjectDecl * > ltmp;
278 std::list< ObjectDecl * > rtmp;
279 std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
280 return newObject( lhsNamer, alt.expr );
281 });
282 std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
283 return newObject( rhsNamer, alt.expr );
284 });
285 zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
286 tmpDecls.splice( tmpDecls.end(), ltmp );
287 tmpDecls.splice( tmpDecls.end(), rtmp );
288 }
289 }
290
291 // empty case is okay when right side is also "empty" (empty explosion handles no argument case as well as empty tuple case)
292 void TupleAssignSpotter::handleEmptyTuple( const ResolvExpr::AltList & alts ) {
293 assert( ! alts.empty() );
294 Expression * lhs = alts.front().expr;
295 if ( PointerType * ptrType = dynamic_cast< PointerType * >( lhs->get_result() ) ) {
296 if ( TupleType * tupleType = dynamic_cast< TupleType * >( ptrType->get_base() ) ) {
297 if ( tupleType->size() == 0 ) {
298 ResolvExpr::AltList rhs;
299 explode( std::next(alts.begin(), 1), alts.end(), currentFinder.get_indexer(), back_inserter(rhs) );
300 if ( rhs.empty() ) {
301 // okay, no other case is allowed
302 ResolvExpr::TypeEnvironment compositeEnv;
303 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
304 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative( new TupleAssignExpr( std::list< Expression * >(), std::list< ObjectDecl * >() ), compositeEnv, ResolvExpr::sumCost( alts ) ) );
305 }
306 }
307 }
308 }
309 }
310} // namespace Tuples
311
312// Local Variables: //
313// tab-width: 4 //
314// mode: c++ //
315// compile-command: "make install" //
316// End: //
Note: See TracBrowser for help on using the repository browser.