source: src/Tuples/TupleAssignment.cpp@ 3eb5f993

Last change on this file since 3eb5f993 was 405dbb3, checked in by Andrew Beach <ajbeach@…>, 16 months ago

Noticing that a function could have an early exit to save a level of indentation lead to a larger refactor. Slight code improvements besides the formatting change.
  • 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.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
244public:
245 TupleAssignSpotter( ResolvExpr::CandidateFinder & f )
246 : crntFinder( f ), fname() {}
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 /// Wrapper around matcher.match.
253 void match( Matcher & matcher );
254};
255
256void TupleAssignSpotter::spot(
257 const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args
258) {
259 // Skip non-"assignment" functions.
260 auto op = expr->func.as< ast::NameExpr >();
261 if ( nullptr == op || !CodeGen::isCtorDtorAssign( op->name ) ) return;
262
263 // Handled by CandidateFinder if applicable (both odd cases).
264 if ( args.empty() || ( 1 == args.size() && CodeGen::isAssignment( op->name ) ) ) {
265 return;
266 }
267
268 fname = op->name;
269
270 // Look over all possible left-hand-side.
271 for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) {
272 // Skip non-tuple LHS.
273 if ( !refToTuple( lhsCand->expr ) ) continue;
274
275 // Explode is aware of casts - ensure every LHS
276 // is sent into explode with a reference cast.
277 if ( !lhsCand->expr.as< ast::CastExpr >() ) {
278 lhsCand->expr = new ast::CastExpr(
279 lhsCand->expr, new ast::ReferenceType( lhsCand->expr->result ) );
280 }
281
282 // Explode the LHS so that each field of a tuple-valued expr is assigned.
283 ResolvExpr::CandidateList lhs;
284 explode( *lhsCand, crntFinder.context.symtab, back_inserter(lhs), true );
285 for ( ResolvExpr::CandidateRef & cand : lhs ) {
286 // Each LHS value must be a reference - some come in
287 // with a cast, if not just cast to reference here.
288 if ( !cand->expr->result.as< ast::ReferenceType >() ) {
289 cand->expr = new ast::CastExpr(
290 cand->expr, new ast::ReferenceType( cand->expr->result ) );
291 }
292 }
293
294 if ( 1 == args.size() ) {
295 // Mass default-initialization/destruction.
296 ResolvExpr::CandidateList rhs{};
297 MassAssignMatcher matcher( *this, expr->location, lhs, rhs );
298 match( matcher );
299 } else if ( 2 == args.size() ) {
300 for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) {
301 ResolvExpr::CandidateList rhs;
302 if ( isTuple( rhsCand->expr ) ) {
303 // Multiple assignment:
304 explode( *rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true );
305 MultipleAssignMatcher matcher( *this, expr->location, lhs, rhs );
306 match( matcher );
307 } else {
308 // Mass assignment:
309 rhs.emplace_back( rhsCand );
310 MassAssignMatcher matcher( *this, expr->location, lhs, rhs );
311 match( matcher );
312 }
313 }
314 } else {
315 // Expand all possible RHS possibilities.
316 std::vector< ResolvExpr::CandidateList > rhsCands;
317 combos(
318 std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) );
319 for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) {
320 // Multiple assignment:
321 ResolvExpr::CandidateList rhs;
322 explode( rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true );
323 MultipleAssignMatcher matcher( *this, expr->location, lhs, rhs );
324 match( matcher );
325 }
326 }
327 }
328}
329
330void TupleAssignSpotter::match( TupleAssignSpotter::Matcher & matcher ) {
331 std::vector< ast::ptr< ast::Expr > > newAssigns = matcher.match();
332
333 if ( !( matcher.lhs.empty() && matcher.rhs.empty() ) ) {
334 // If both LHS and RHS are empty than this is the empty tuple
335 // case, wherein it's okay for newAssigns to be empty. Otherwise,
336 // return early so that no new candidates are generated.
337 if ( newAssigns.empty() ) return;
338 }
339
340 ResolvExpr::CandidateList crnt;
341 // Now resolve new assignments.
342 for ( const ast::Expr * expr : newAssigns ) {
343 PRINT(
344 std::cerr << "== resolving tuple assign ==" << std::endl;
345 std::cerr << expr << std::endl;
346 )
347
348 ResolvExpr::CandidateFinder finder( crntFinder.context, matcher.env );
349 finder.allowVoid = true;
350
351 try {
352 finder.find( expr, ResolvExpr::ResolveMode::withAdjustment() );
353 } catch (...) {
354 // No match is not failure, just that this tuple assignment is invalid.
355 return;
356 }
357
358 ResolvExpr::CandidateList & cands = finder.candidates;
359 assert( 1 == cands.size() );
360 assert( cands.front()->expr );
361 crnt.emplace_back( std::move( cands.front() ) );
362 }
363
364 // extract expressions from the assignment candidates to produce a list of assignments
365 // that together form a sigle candidate
366 std::vector< ast::ptr< ast::Expr > > solved;
367 for ( ResolvExpr::CandidateRef & cand : crnt ) {
368 solved.emplace_back( cand->expr );
369 matcher.combineState( *cand );
370 }
371
372 crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >(
373 new ast::TupleAssignExpr(
374 matcher.location, std::move( solved ), std::move( matcher.tmpDecls ) ),
375 std::move( matcher.env ), std::move( matcher.open ), std::move( matcher.need ),
376 ResolvExpr::sumCost( crnt ) + matcher.baseCost ) );
377}
378
379} // anonymous namespace
380
381void handleTupleAssignment(
382 ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign,
383 std::vector< ResolvExpr::CandidateFinder > & args
384) {
385 TupleAssignSpotter spotter( finder );
386 spotter.spot( assign, args );
387}
388
389} // namespace Tuples
390
391// Local Variables: //
392// tab-width: 4 //
393// mode: c++ //
394// compile-command: "make install" //
395// End: //
Note: See TracBrowser for help on using the repository browser.