source: src/Tuples/TupleAssignment.cc@ 8655363

Last change on this file since 8655363 was 4a89b52, checked in by Andrew Beach <ajbeach@…>, 22 months ago

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