source: src/Tuples/TupleAssignment.cpp@ 85855b0

Last change on this file since 85855b0 was c92bdcc, checked in by Andrew Beach <ajbeach@…>, 17 months ago

Updated the rest of the names in src/ (except for the generated files).
  • Property mode set to 100644
File size: 13.7 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.cpp --
8//
9// Author : Rodolfo G. Esteves
10// Created On : Mon May 18 07:44:20 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Wed Mar 16 14:06:00 2022
13// Update Count : 10
14//
15
16#include "Tuples.hpp"
17
18#include <algorithm> // for transform
19#include <cassert> // for assert
20#include <iterator> // for back_insert_iterator, back...
21#include <list> // for _List_const_iterator, _Lis...
22#include <memory> // for unique_ptr, allocator_trai...
23#include <string> // for string
24#include <vector>
25
26#include "AST/Decl.hpp"
27#include "AST/Init.hpp"
28#include "AST/Pass.hpp"
29#include "AST/Stmt.hpp"
30#include "AST/TypeEnvironment.hpp"
31#include "CodeGen/OperatorTable.hpp"
32#include "Common/UniqueName.hpp" // for UniqueName
33#include "Common/Utility.hpp" // for splice, zipWith
34#include "Explode.hpp" // for explode
35#include "InitTweak/GenInit.hpp" // for genCtorInit
36#include "InitTweak/InitTweak.hpp" // for getPointerBase, isAssignment
37#include "ResolvExpr/CandidateFinder.hpp" // for CandidateFinder
38#include "ResolvExpr/Cost.hpp" // for Cost
39#include "ResolvExpr/Resolver.hpp" // for resolveCtorInit
40#include "ResolvExpr/Typeops.hpp" // for combos
41
42#if 0
43#define PRINT(x) x
44#else
45#define PRINT(x)
46#endif
47
48namespace Tuples {
49
50namespace {
51
52/// Checks if `expr` is of tuple type.
53bool isTuple( const ast::Expr * expr ) {
54 if ( !expr ) return false;
55 assert( expr->result );
56 return dynamic_cast< const ast::TupleType * >( expr->result->stripReferences() );
57}
58
59/// Checks if `expr` is of tuple type or a cast to one.
60bool refToTuple( const ast::Expr * expr ) {
61 assert( expr->result );
62 // Check for function returning tuple of reference types.
63 if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
64 return refToTuple( castExpr->arg );
65 } else {
66 return isTuple( expr );
67 }
68}
69
70/// Dispatcher for tuple (multiple and mass) assignment operations.
71class TupleAssignSpotter final {
72 /// Actually finds tuple assignment operations, by subclass.
73 struct Matcher {
74 ResolvExpr::CandidateList lhs, rhs;
75 TupleAssignSpotter & spotter;
76 CodeLocation location;
77 ResolvExpr::Cost baseCost;
78 std::vector< ast::ptr< ast::ObjectDecl > > tmpDecls;
79 ast::TypeEnvironment env;
80 ast::OpenVarSet open;
81 ast::AssertionSet need;
82
83 void combineState( const ResolvExpr::Candidate & cand ) {
84 env.simpleCombine( cand.env );
85 ast::mergeOpenVars( open, cand.open );
86 need.insert( cand.need.begin(), cand.need.end() );
87 }
88
89 Matcher(
90 TupleAssignSpotter & s, const CodeLocation & loc,
91 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
92 : lhs( l ), rhs( r ), spotter( s ), location( loc ),
93 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ), tmpDecls(),
94 env(), open(), need() {
95 for ( auto & cand : lhs ) combineState( *cand );
96 for ( auto & cand : rhs ) combineState( *cand );
97 }
98 virtual ~Matcher() = default;
99
100 virtual std::vector< ast::ptr< ast::Expr > > match() = 0;
101
102 /// Removes environments from subexpressions within statement expressions, which could
103 /// throw off later passes like those in Box which rely on PolyMutator, and adds the
104 /// bindings to the env.
105 struct EnvRemover {
106 /// Environment to hoist ExprStmt environments to.
107 ast::TypeEnvironment & tenv;
108
109 EnvRemover( ast::TypeEnvironment & e ) : tenv( e ) {}
110
111 const ast::ExprStmt * previsit( const ast::ExprStmt * stmt ) {
112 if ( stmt->expr->env ) {
113 tenv.add( *stmt->expr->env );
114 ast::ExprStmt * mut = mutate( stmt );
115 mut->expr.get_and_mutate()->env = nullptr;
116 return mut;
117 }
118 return stmt;
119 }
120 };
121
122 ast::ObjectDecl * newObject( UniqueName & namer, const ast::Expr * expr ) {
123 assert( expr->result && !expr->result->isVoid() );
124
125 ast::ObjectDecl * ret = new ast::ObjectDecl(
126 location, namer.newName(), expr->result, new ast::SingleInit( location, expr ),
127 ast::Storage::Classes{}, ast::Linkage::Cforall );
128
129 // If expression type is a reference, just need an initializer, otherwise construct.
130 if ( ! expr->result.as< ast::ReferenceType >() ) {
131 // Resolve ctor/dtor for the new object.
132 ast::ptr< ast::Init > ctorInit = ResolvExpr::resolveCtorInit(
133 InitTweak::genCtorInit( location, ret ), spotter.crntFinder.context );
134 // Remove environments from subexpressions of stmtExpr.
135 ast::Pass< EnvRemover > rm( env );
136 ret->init = ctorInit->accept( rm );
137 }
138
139 PRINT( std::cerr << "new object: " << ret << std::endl; )
140 return ret;
141 }
142
143 ast::UntypedExpr * createFunc(
144 const std::string & fname, const ast::ObjectDecl * left,
145 const ast::ObjectDecl * right
146 ) {
147 assert( left );
148 std::vector< ast::ptr< ast::Expr > > args;
149 args.emplace_back( new ast::VariableExpr( location, left ) );
150 if ( right ) { args.emplace_back( new ast::VariableExpr( location, right ) ); }
151
152 if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
153 args.front() = new ast::AddressExpr( location, args.front() );
154 if ( right ) { args.back() = new ast::AddressExpr( location, args.back() ); }
155 return new ast::UntypedExpr(
156 location, new ast::NameExpr( location, "?=?" ), std::move( args ) );
157 } else {
158 return new ast::UntypedExpr(
159 location, new ast::NameExpr( location, fname ), std::move( args ) );
160 }
161 }
162 };
163
164 /// Finds mass-assignment operations.
165 struct MassAssignMatcher final : public Matcher {
166 MassAssignMatcher(
167 TupleAssignSpotter & s, const CodeLocation & loc,
168 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
169 : Matcher( s, loc, l, r ) {}
170
171 std::vector< ast::ptr< ast::Expr > > match() override {
172 static UniqueName lhsNamer( "__massassign_L" );
173 static UniqueName rhsNamer( "__massassign_R" );
174 // Empty tuple case falls into this matcher.
175 assert( lhs.empty() ? rhs.empty() : rhs.size() <= 1 );
176
177 ast::ptr< ast::ObjectDecl > rtmp =
178 1 == rhs.size() ? newObject( rhsNamer, rhs.front()->expr ) : nullptr;
179
180 std::vector< ast::ptr< ast::Expr > > out;
181 for ( ResolvExpr::CandidateRef & lhsCand : lhs ) {
182 // Create a temporary object for each value in
183 // the LHS and create a call involving the RHS.
184 ast::ptr< ast::ObjectDecl > ltmp = newObject( lhsNamer, lhsCand->expr );
185 out.emplace_back( createFunc( spotter.fname, ltmp, rtmp ) );
186 tmpDecls.emplace_back( std::move( ltmp ) );
187 }
188 if ( rtmp ) tmpDecls.emplace_back( std::move( rtmp ) );
189
190 return out;
191 }
192 };
193
194 /// Finds multiple-assignment operations.
195 struct MultipleAssignMatcher final : public Matcher {
196 MultipleAssignMatcher(
197 TupleAssignSpotter & s, const CodeLocation & loc,
198 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
199 : Matcher( s, loc, l, r ) {}
200
201 std::vector< ast::ptr< ast::Expr > > match() override {
202 static UniqueName lhsNamer( "__multassign_L" );
203 static UniqueName rhsNamer( "__multassign_R" );
204
205 if ( lhs.size() != rhs.size() ) return {};
206
207 // Produce a new temporary object for each value in
208 // the LHS and RHS and pairwise create the calls.
209 std::vector< ast::ptr< ast::ObjectDecl > > ltmp, rtmp;
210
211 std::vector< ast::ptr< ast::Expr > > out;
212 for ( unsigned i = 0; i < lhs.size(); ++i ) {
213 ResolvExpr::CandidateRef & lhsCand = lhs[i];
214 ResolvExpr::CandidateRef & rhsCand = rhs[i];
215
216 // Convert RHS to LHS type minus one reference --
217 // important for case where LHS is && and RHS is lvalue.
218 auto lhsType = lhsCand->expr->result.strict_as< ast::ReferenceType >();
219 rhsCand->expr = new ast::CastExpr( rhsCand->expr, lhsType->base );
220 ast::ptr< ast::ObjectDecl > lobj = newObject( lhsNamer, lhsCand->expr );
221 ast::ptr< ast::ObjectDecl > robj = newObject( rhsNamer, rhsCand->expr );
222 out.emplace_back( createFunc( spotter.fname, lobj, robj ) );
223 ltmp.emplace_back( std::move( lobj ) );
224 rtmp.emplace_back( std::move( robj ) );
225
226 // Resolve the cast expression so that rhsCand return type is bound
227 // by the cast type as needed, and transfer the resulting environment.
228 ResolvExpr::CandidateFinder finder( spotter.crntFinder.context, env );
229 finder.find( rhsCand->expr, ResolvExpr::ResolveMode::withAdjustment() );
230 assert( 1 == finder.candidates.size() );
231 env = std::move( finder.candidates.front()->env );
232 }
233
234 splice( tmpDecls, ltmp );
235 splice( tmpDecls, rtmp );
236
237 return out;
238 }
239 };
240
241 ResolvExpr::CandidateFinder & crntFinder;
242 std::string fname;
243 std::unique_ptr< Matcher > matcher;
244
245public:
246 TupleAssignSpotter( ResolvExpr::CandidateFinder & f )
247 : crntFinder( f ), fname(), matcher() {}
248
249 // Find left- and right-hand-sides for mass or multiple assignment.
250 void spot(
251 const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args
252 ) {
253 if ( auto op = expr->func.as< ast::NameExpr >() ) {
254 // Skip non-assignment functions.
255 if ( !CodeGen::isCtorDtorAssign( op->name ) ) return;
256 fname = op->name;
257
258 // Handled by CandidateFinder if applicable (both odd cases).
259 if ( args.empty() || ( 1 == args.size() && CodeGen::isAssignment( fname ) ) ) {
260 return;
261 }
262
263 // Look over all possible left-hand-side.
264 for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) {
265 // Skip non-tuple LHS.
266 if ( !refToTuple( lhsCand->expr ) ) continue;
267
268 // Explode is aware of casts - ensure every LHS
269 // is sent into explode with a reference cast.
270 if ( !lhsCand->expr.as< ast::CastExpr >() ) {
271 lhsCand->expr = new ast::CastExpr(
272 lhsCand->expr, new ast::ReferenceType( lhsCand->expr->result ) );
273 }
274
275 // Explode the LHS so that each field of a tuple-valued expr is assigned.
276 ResolvExpr::CandidateList lhs;
277 explode( *lhsCand, crntFinder.context.symtab, back_inserter(lhs), true );
278 for ( ResolvExpr::CandidateRef & cand : lhs ) {
279 // Each LHS value must be a reference - some come in
280 // with a cast, if not just cast to reference here.
281 if ( !cand->expr->result.as< ast::ReferenceType >() ) {
282 cand->expr = new ast::CastExpr(
283 cand->expr, new ast::ReferenceType( cand->expr->result ) );
284 }
285 }
286
287 if ( 1 == args.size() ) {
288 // Mass default-initialization/destruction.
289 ResolvExpr::CandidateList rhs{};
290 matcher.reset( new MassAssignMatcher( *this, expr->location, lhs, rhs ) );
291 match();
292 } else if ( 2 == args.size() ) {
293 for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) {
294 ResolvExpr::CandidateList rhs;
295 if ( isTuple( rhsCand->expr ) ) {
296 // Multiple assignment:
297 explode( *rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true );
298 matcher.reset(
299 new MultipleAssignMatcher( *this, expr->location, lhs, rhs ) );
300 } else {
301 // Mass assignment:
302 rhs.emplace_back( rhsCand );
303 matcher.reset(
304 new MassAssignMatcher( *this, expr->location, lhs, rhs ) );
305 }
306 match();
307 }
308 } else {
309 // Expand all possible RHS possibilities.
310 std::vector< ResolvExpr::CandidateList > rhsCands;
311 combos(
312 std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) );
313 for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) {
314 // Multiple assignment:
315 ResolvExpr::CandidateList rhs;
316 explode( rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true );
317 matcher.reset(
318 new MultipleAssignMatcher( *this, expr->location, lhs, rhs ) );
319 match();
320 }
321 }
322 }
323 }
324 }
325
326 void match() {
327 assert( matcher );
328
329 std::vector< ast::ptr< ast::Expr > > newAssigns = matcher->match();
330
331 if ( !( matcher->lhs.empty() && matcher->rhs.empty() ) ) {
332 // If both LHS and RHS are empty than this is the empty tuple
333 // case, wherein it's okay for newAssigns to be empty. Otherwise,
334 // return early so that no new candidates are generated.
335 if ( newAssigns.empty() ) return;
336 }
337
338 ResolvExpr::CandidateList crnt;
339 // Now resolve new assignments.
340 for ( const ast::Expr * expr : newAssigns ) {
341 PRINT(
342 std::cerr << "== resolving tuple assign ==" << std::endl;
343 std::cerr << expr << std::endl;
344 )
345
346 ResolvExpr::CandidateFinder finder( crntFinder.context, matcher->env );
347 finder.allowVoid = true;
348
349 try {
350 finder.find( expr, ResolvExpr::ResolveMode::withAdjustment() );
351 } catch (...) {
352 // No match is not failure, just that this tuple assignment is invalid.
353 return;
354 }
355
356 ResolvExpr::CandidateList & cands = finder.candidates;
357 assert( 1 == cands.size() );
358 assert( cands.front()->expr );
359 crnt.emplace_back( std::move( cands.front() ) );
360 }
361
362 // extract expressions from the assignment candidates to produce a list of assignments
363 // that together form a sigle candidate
364 std::vector< ast::ptr< ast::Expr > > solved;
365 for ( ResolvExpr::CandidateRef & cand : crnt ) {
366 solved.emplace_back( cand->expr );
367 matcher->combineState( *cand );
368 }
369
370 crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >(
371 new ast::TupleAssignExpr(
372 matcher->location, std::move( solved ), std::move( matcher->tmpDecls ) ),
373 std::move( matcher->env ), std::move( matcher->open ), std::move( matcher->need ),
374 ResolvExpr::sumCost( crnt ) + matcher->baseCost ) );
375 }
376};
377
378} // anonymous namespace
379
380void handleTupleAssignment(
381 ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign,
382 std::vector< ResolvExpr::CandidateFinder > & args
383) {
384 TupleAssignSpotter spotter( finder );
385 spotter.spot( assign, args );
386}
387
388} // namespace Tuples
389
390// Local Variables: //
391// tab-width: 4 //
392// mode: c++ //
393// compile-command: "make install" //
394// End: //
Note: See TracBrowser for help on using the repository browser.