source: src/Tuples/TupleAssignment.cc@ 09ab71a

ADT arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 09ab71a was 2c187378, checked in by Aaron Moss <a3moss@…>, 7 years ago

Fix memory bugs in deferred resolution
  • Property mode set to 100644
File size: 15.1 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,
65 const ResolvExpr::AltList& rhs );
66 virtual ~Matcher() {}
67
68 virtual void match( std::list< Expression * > &out ) = 0;
69 ObjectDecl * newObject( UniqueName & namer, Expression * expr );
70
71 void combineState( const ResolvExpr::Alternative& alt ) {
72 compositeEnv.simpleCombine( alt.env );
73 ResolvExpr::mergeOpenVars( openVars, alt.openVars );
74 cloneAll( alt.need, need );
75 }
76
77 void combineState( const ResolvExpr::AltList& alts ) {
78 for ( const ResolvExpr::Alternative& alt : alts ) { combineState( alt ); }
79 }
80
81 ResolvExpr::AltList lhs, rhs;
82 TupleAssignSpotter &spotter;
83 ResolvExpr::Cost baseCost;
84 std::list< ObjectDecl * > tmpDecls;
85 ResolvExpr::TypeEnvironment compositeEnv;
86 ResolvExpr::OpenVarSet openVars;
87 ResolvExpr::AssertionSet need;
88 };
89
90 struct MassAssignMatcher : public Matcher {
91 public:
92 MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
93 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
94 virtual void match( std::list< Expression * > &out );
95 };
96
97 struct MultipleAssignMatcher : public Matcher {
98 public:
99 MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
100 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
101 virtual void match( std::list< Expression * > &out );
102 };
103
104 ResolvExpr::AlternativeFinder &currentFinder;
105 std::string fname;
106 std::unique_ptr< Matcher > matcher;
107 };
108
109 /// true if expr is an expression of tuple type
110 bool isTuple( Expression *expr ) {
111 if ( ! expr ) return false;
112 assert( expr->result );
113 return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
114 }
115
116 template< typename AltIter >
117 bool isMultAssign( AltIter begin, AltIter end ) {
118 // multiple assignment if more than one alternative in the range or if
119 // the alternative is a tuple
120 if ( begin == end ) return false;
121 if ( isTuple( begin->expr ) ) return true;
122 return ++begin != end;
123 }
124
125 bool refToTuple( Expression *expr ) {
126 assert( expr->get_result() );
127 // also check for function returning tuple of reference types
128 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
129 return refToTuple( castExpr->get_arg() );
130 } else {
131 return isTuple( expr );
132 }
133 return false;
134 }
135
136 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
137 std::vector<ResolvExpr::AlternativeFinder> &args ) {
138 TupleAssignSpotter spotter( currentFinder );
139 spotter.spot( expr, args );
140 }
141
142 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
143 : currentFinder(f) {}
144
145 void TupleAssignSpotter::spot( UntypedExpr * expr,
146 std::vector<ResolvExpr::AlternativeFinder> &args ) {
147 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
148 if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
149 fname = op->get_name();
150
151 // AlternativeFinder will naturally handle this case case, if it's legal
152 if ( args.size() == 0 ) return;
153
154 // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
155 // the function, in which case AlternativeFinder will handle it normally
156 if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;
157
158 // look over all possible left-hand-sides
159 for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
160 // skip non-tuple LHS
161 if ( ! refToTuple(lhsAlt.expr) ) continue;
162
163 // explode is aware of casts - ensure every LHS expression is sent into explode
164 // with a reference cast
165 // xxx - this seems to change the alternatives before the normal
166 // AlternativeFinder flow; maybe this is desired?
167 if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
168 lhsAlt.expr = new CastExpr( lhsAlt.expr,
169 new ReferenceType( Type::Qualifiers(),
170 lhsAlt.expr->result->clone() ) );
171 }
172
173 // explode the LHS so that each field of a tuple-valued-expr is assigned
174 ResolvExpr::AltList lhs;
175 explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
176 for ( ResolvExpr::Alternative& alt : lhs ) {
177 // each LHS value must be a reference - some come in with a cast expression,
178 // if not just cast to reference here
179 if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
180 alt.expr = new CastExpr( alt.expr,
181 new ReferenceType( Type::Qualifiers(),
182 alt.expr->get_result()->clone() ) );
183 }
184 }
185
186 if ( args.size() == 1 ) {
187 // mass default-initialization/destruction
188 ResolvExpr::AltList rhs{};
189 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
190 match();
191 } else if ( args.size() > 2 ) {
192 // expand all possible RHS possibilities
193 // TODO build iterative version of this instead of using combos
194 std::vector< ResolvExpr::AltList > rhsAlts;
195 combos( std::next(args.begin(), 1), args.end(),
196 std::back_inserter( rhsAlts ) );
197 for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
198 // multiple assignment
199 ResolvExpr::AltList rhs;
200 explode( rhsAlt, currentFinder.get_indexer(),
201 std::back_inserter(rhs), true );
202 matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
203 match();
204 }
205 } else {
206 for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
207 ResolvExpr::AltList rhs;
208 if ( isTuple(rhsAlt.expr) ) {
209 // multiple assignment
210 explode( rhsAlt, currentFinder.get_indexer(),
211 std::back_inserter(rhs), true );
212 matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
213 } else {
214 // mass assignment
215 rhs.push_back( rhsAlt );
216 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
217 }
218 match();
219 }
220 }
221 }
222 }
223 }
224 }
225
226 void TupleAssignSpotter::match() {
227 assert ( matcher != 0 );
228
229 std::list< Expression * > new_assigns;
230 matcher->match( new_assigns );
231
232 if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
233 // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
234 // if not the empty tuple case, return early so that no new alternatives are generated.
235 if ( new_assigns.empty() ) return;
236 }
237 ResolvExpr::AltList current;
238 // now resolve new assignments
239 for ( std::list< Expression * >::iterator i = new_assigns.begin();
240 i != new_assigns.end(); ++i ) {
241 PRINT(
242 std::cerr << "== resolving tuple assign ==" << std::endl;
243 std::cerr << *i << std::endl;
244 )
245
246 ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
247 matcher->compositeEnv };
248
249 try {
250 finder.findWithAdjustment(*i);
251 } catch (...) {
252 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
253 }
254 // prune expressions that don't coincide with
255 ResolvExpr::AltList alts = finder.get_alternatives();
256 assert( alts.size() == 1 );
257 assert( alts.front().expr != 0 );
258 current.push_back( alts.front() );
259 }
260
261 // extract expressions from the assignment alternatives to produce a list of assignments
262 // that together form a single alternative
263 std::list< Expression *> solved_assigns;
264 for ( ResolvExpr::Alternative & alt : current ) {
265 solved_assigns.push_back( alt.expr->clone() );
266 matcher->combineState( alt );
267 }
268
269 // xxx -- was push_front
270 currentFinder.get_alternatives().push_back( ResolvExpr::Alternative{
271 new TupleAssignExpr{ solved_assigns, matcher->tmpDecls }, matcher->compositeEnv,
272 matcher->openVars,
273 ResolvExpr::AssertionList( matcher->need.begin(), matcher->need.end() ),
274 ResolvExpr::sumCost( current ) + matcher->baseCost } );
275 }
276
277 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
278 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
279 : lhs(lhs), rhs(rhs), spotter(spotter),
280 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
281 combineState( lhs );
282 combineState( rhs );
283 }
284
285 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
286 assert( left );
287 std::list< Expression * > args;
288 args.push_back( new VariableExpr( left ) );
289 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
290 if ( right ) args.push_back( new VariableExpr( right ) );
291 if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
292 args.front() = new AddressExpr( args.front() );
293 if ( right ) args.back() = new AddressExpr( args.back() );
294 return new UntypedExpr( new NameExpr( "?=?" ), args );
295 } else {
296 return new UntypedExpr( new NameExpr( fname ), args );
297 }
298 }
299
300 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator, and adds the bindings to the compositeEnv
301 // xxx - maybe this should happen in alternative finder for every StmtExpr?
302 struct EnvRemover {
303 void previsit( ExprStmt * stmt ) {
304 assert( compositeEnv );
305 if ( stmt->expr->env ) {
306 compositeEnv->add( *stmt->expr->env );
307 delete stmt->expr->env;
308 stmt->expr->env = nullptr;
309 }
310 }
311
312 ResolvExpr::TypeEnvironment * compositeEnv = nullptr;
313 };
314
315 ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
316 assert( expr->result && ! expr->get_result()->isVoid() );
317 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->result->clone(), new SingleInit( expr->clone() ) );
318 // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
319 if ( ! dynamic_cast< ReferenceType * >( expr->result ) ) {
320 ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
321 ret->init = ctorInit;
322 ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
323 PassVisitor<EnvRemover> rm; // remove environments from subexpressions of StmtExprs
324 rm.pass.compositeEnv = &compositeEnv;
325 ctorInit->accept( rm );
326 }
327 PRINT( std::cerr << "new object: " << ret << std::endl; )
328 return ret;
329 }
330
331 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
332 static UniqueName lhsNamer( "__massassign_L" );
333 static UniqueName rhsNamer( "__massassign_R" );
334 // empty tuple case falls into this matcher, hence the second part of the assert
335 assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
336
337 // xxx - may need to split this up into multiple declarations, because potential conversion to references
338 // probably should not reference local variable - see MultipleAssignMatcher::match
339 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
340 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
341 // create a temporary object for each value in the lhs and create a call involving the rhs
342 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
343 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
344 tmpDecls.push_back( ltmp );
345 }
346 if ( rtmp ) tmpDecls.push_back( rtmp );
347 }
348
349 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
350 static UniqueName lhsNamer( "__multassign_L" );
351 static UniqueName rhsNamer( "__multassign_R" );
352
353 if ( lhs.size() == rhs.size() ) {
354 // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
355 std::list< ObjectDecl * > ltmp;
356 std::list< ObjectDecl * > rtmp;
357 for ( auto p : group_iterate( lhs, rhs ) ) {
358 ResolvExpr::Alternative & lhsAlt = std::get<0>(p);
359 ResolvExpr::Alternative & rhsAlt = std::get<1>(p);
360 // convert RHS to LHS type minus one reference -- important for the case where LHS is && and RHS is lvalue, etc.
361 ReferenceType * lhsType = strict_dynamic_cast<ReferenceType *>( lhsAlt.expr->result );
362 rhsAlt.expr = new CastExpr( rhsAlt.expr, lhsType->base->clone() );
363 ObjectDecl * lobj = newObject( lhsNamer, lhsAlt.expr );
364 ObjectDecl * robj = newObject( rhsNamer, rhsAlt.expr );
365 out.push_back( createFunc(spotter.fname, lobj, robj) );
366 ltmp.push_back( lobj );
367 rtmp.push_back( robj );
368
369 // resolve the cast expression so that rhsAlt return type is bound by the cast type as needed, and transfer the resulting environment
370 ResolvExpr::AlternativeFinder finder{ spotter.currentFinder.get_indexer(), compositeEnv };
371 finder.findWithAdjustment( rhsAlt.expr );
372 assert( finder.get_alternatives().size() == 1 );
373 compositeEnv = std::move( finder.get_alternatives().front().env );
374 }
375 tmpDecls.splice( tmpDecls.end(), ltmp );
376 tmpDecls.splice( tmpDecls.end(), rtmp );
377 }
378 }
379} // namespace Tuples
380
381// Local Variables: //
382// tab-width: 4 //
383// mode: c++ //
384// compile-command: "make install" //
385// End: //
Note: See TracBrowser for help on using the repository browser.