source: src/Tuples/TupleAssignment.cc@ 9058414

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

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