Context Navigation

source: src/Concurrency/Actors.cpp @ a4808ad

Last change on this file since a4808ad was fc1a3e2, checked in by Andrew Beach <ajbeach@…>, 7 months ago
Style update. Focused on indentation and trailing whitespace.
Property mode set to `100644`
File size: 20.8 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	// Actors.cpp -- generate code needed by the actor system
8	//
9	// Author : Colby Parsons
10	// Created On : Thurs Jan 19 15:34:00 2023
11	// Last Modified By : Colby Parsons
12	// Last Modified On : Thurs Jan 19 15:34:00 2023
13	// Update Count : 0
14	//
15
16	#include "AST/Print.hpp"
17	#include "AST/Decl.hpp"
18	#include "AST/Pass.hpp"
19	#include "AST/Type.hpp"
20	#include "AST/Stmt.hpp"
21	#include "AST/TranslationUnit.hpp"
22	#include "AST/Expr.hpp"
23	#include <algorithm>
24	using namespace ast;
25	using namespace std;
26
27	namespace Concurrency {
28
29	struct CollectactorStructDecls : public ast::WithGuards {
30	unordered_set<const StructDecl *> & actorStructDecls;
31	unordered_set<const StructDecl *> & messageStructDecls;
32	const StructDecl ** requestDecl;
33	const EnumDecl ** allocationDecl;
34	const StructDecl ** actorDecl;
35	const StructDecl ** msgDecl;
36	StructDecl * parentDecl;
37	bool insideStruct = false;
38	bool namedDecl = false;
39
40	// finds and sets a ptr to the allocation enum, which is needed in the next pass
41	void previsit( const EnumDecl * decl ) {
42	if( decl->name == "allocation" ) *allocationDecl = decl;
43	}
44
45	// finds and sets a ptr to the actor, message, and request structs, which are needed in the next pass
46	void previsit( const StructDecl * decl ) {
47	if ( !decl->body ) return;
48	if ( decl->name == "actor" ) {
49	actorStructDecls.insert( decl ); // skip inserting fwd decl
50	*actorDecl = decl;
51	} else if( decl->name == "message" ) {
52	messageStructDecls.insert( decl ); // skip inserting fwd decl
53	*msgDecl = decl;
54	} else if( decl->name == "request" ) *requestDecl = decl;
55	else {
56	GuardValue(insideStruct);
57	insideStruct = true;
58	parentDecl = mutate( decl );
59	}
60	}
61
62	// this catches structs of the form:
63	// struct dummy_actor { actor a; };
64	// since they should be:
65	// struct dummy_actor { inline actor; };
66	void previsit ( const ObjectDecl * decl ) {
67	if ( insideStruct && ! decl->name.empty() ) {
68	GuardValue(namedDecl);
69	namedDecl = true;
70	}
71	}
72
73	// this collects the derived actor and message struct decl ptrs
74	void postvisit( const StructInstType * node ) {
75	if ( ! actorDecl \|\| ! msgDecl ) return;
76	if ( insideStruct && !namedDecl ) {
77	auto actorIter = actorStructDecls.find( node->aggr() );
78	if ( actorIter != actorStructDecls.end() ) {
79	actorStructDecls.insert( parentDecl );
80	return;
81	}
82	auto messageIter = messageStructDecls.find( node->aggr() );
83	if ( messageIter != messageStructDecls.end() ) {
84	messageStructDecls.insert( parentDecl );
85	}
86	}
87	}
88
89	public:
90	CollectactorStructDecls( unordered_set<const StructDecl > & actorStructDecls, unordered_set<const StructDecl > & messageStructDecls,
91	const StructDecl requestDecl, const EnumDecl allocationDecl, const StructDecl actorDecl, const StructDecl msgDecl )
92	: actorStructDecls( actorStructDecls ), messageStructDecls( messageStructDecls ), requestDecl( requestDecl ),
93	allocationDecl( allocationDecl ), actorDecl(actorDecl), msgDecl(msgDecl) {}
94	};
95
96	// keeps track of all fwdDecls of message routines so that we can hoist them to right after the appropriate decls
97	class FwdDeclTable {
98
99	// tracks which decls we have seen so that we can hoist the FunctionDecl to the highest point possible
100	struct FwdDeclData {
101	const StructDecl * actorDecl;
102	const StructDecl * msgDecl;
103	FunctionDecl * fwdDecl;
104	bool actorFound;
105	bool msgFound;
106
107	bool readyToInsert() { return actorFound && msgFound; }
108	bool foundActor() { actorFound = true; return readyToInsert(); }
109	bool foundMsg() { msgFound = true; return readyToInsert(); }
110
111	FwdDeclData( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) :
112	actorDecl(actorDecl), msgDecl(msgDecl), fwdDecl(fwdDecl), actorFound(false), msgFound(false) {}
113	};
114
115	// map indexed by actor struct ptr
116	// value is map of all FwdDeclData that contains said actor struct ptr
117	// inner map is indexed by the message struct ptr of FwdDeclData
118	unordered_map<const StructDecl , unordered_map<const StructDecl , FwdDeclData *>> actorMap;
119
120	// this map is the same except the outer map is indexed by message ptr and the inner is indexed by actor ptr
121	unordered_map<const StructDecl , unordered_map<const StructDecl , FwdDeclData *>> msgMap;
122
123	void insert( const StructDecl * decl, const StructDecl * otherDecl, unordered_map<const StructDecl , unordered_map<const StructDecl , FwdDeclData >> & map, FwdDeclData data ) {
124	auto iter = map.find( decl );
125	if ( iter != map.end() ) { // if decl exists in map append data to existing inner map
126	iter->second.emplace( make_pair( otherDecl, data ) );
127	} else { // else create inner map for key
128	map.emplace( make_pair( decl, unordered_map<const StructDecl , FwdDeclData >( { make_pair( otherDecl, data ) } ) ) );
129	}
130	}
131
132	public:
133	// insert decl into table so that we can fwd declare it later (average cost: O(1))
134	void insertDecl( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) {
135	FwdDeclData * declToInsert = new FwdDeclData( actorDecl, msgDecl, fwdDecl );
136	insert( actorDecl, msgDecl, actorMap, declToInsert );
137	insert( msgDecl, actorDecl, msgMap, declToInsert );
138	}
139
140	// returns list of decls to insert after current struct decl
141	// Over the entire pass the runtime of this routine is O(r) where r is the # of receive routines
142	list<FunctionDecl > updateDecl( const StructDecl decl, bool isMsg ) {
143	unordered_map<const StructDecl , unordered_map<const StructDecl , FwdDeclData *>> & map = isMsg ? msgMap : actorMap;
144	unordered_map<const StructDecl , unordered_map<const StructDecl , FwdDeclData *>> & otherMap = isMsg ? actorMap : msgMap;
145	auto iter = map.find( decl );
146	list<FunctionDecl *> toInsertAfter; // this is populated with decls that are ready to insert
147	if ( iter == map.end() ) return toInsertAfter;
148
149	// iterate over inner map
150	unordered_map<const StructDecl , FwdDeclData > & currInnerMap = iter->second;
151	for ( auto innerIter = currInnerMap.begin(); innerIter != currInnerMap.end(); ) {
152	FwdDeclData * currentDatum = innerIter->second;
153	bool readyToInsert = isMsg ? currentDatum->foundMsg() : currentDatum->foundActor();
154	if ( ! readyToInsert ) { ++innerIter; continue; }
155
156	// readyToInsert is true so we are good to insert the forward decl of the message fn
157	toInsertAfter.push_back( currentDatum->fwdDecl );
158
159	// need to remove from other map before deleting
160	// find inner map in other map ( other map is actor map if original is msg map and vice versa )
161	const StructDecl * otherDecl = isMsg ? currentDatum->actorDecl : currentDatum->msgDecl;
162	auto otherMapIter = otherMap.find( otherDecl );
163
164	unordered_map<const StructDecl , FwdDeclData > & otherInnerMap = otherMapIter->second;
165
166	// find the FwdDeclData we need to remove in the other inner map
167	auto otherInnerIter = otherInnerMap.find( decl );
168
169	// remove references to deleted FwdDeclData from current inner map
170	innerIter = currInnerMap.erase( innerIter ); // this does the increment so no explicit inc needed
171
172	// remove references to deleted FwdDeclData from other inner map
173	otherInnerMap.erase( otherInnerIter );
174
175	// if other inner map is now empty, remove key from other outer map
176	if ( otherInnerMap.empty() )
177	otherMap.erase( otherDecl );
178
179	// now we are safe to delete the FwdDeclData since we are done with it
180	// and we have removed all references to it from our data structures
181	delete currentDatum;
182	}
183
184	// if current inner map is now empty, remove key from outer map.
185	// Have to do this after iterating for safety
186	if ( currInnerMap.empty() )
187	map.erase( decl );
188
189	return toInsertAfter;
190	}
191	};
192
193	// generates the definitions of send operators for actors
194	// collects data needed for next pass that does the circular defn resolution
195	// for message send operators (via table above)
196	struct GenFuncsCreateTables : public ast::WithDeclsToAdd<> {
197	unordered_set<const StructDecl *> & actorStructDecls;
198	unordered_set<const StructDecl *> & messageStructDecls;
199	const StructDecl ** requestDecl;
200	const EnumDecl ** allocationDecl;
201	const StructDecl ** actorDecl;
202	const StructDecl ** msgDecl;
203	FwdDeclTable & forwardDecls;
204
205	// generates the operator for actor message sends
206	void postvisit( const FunctionDecl * decl ) {
207	// return if not of the form receive( param1, param2 ) or if it is a forward decl
208	if ( decl->name != "receive" \|\| decl->params.size() != 2 \|\| !decl->stmts ) return;
209
210	// the params should be references
211	const ReferenceType * derivedActorRef = dynamic_cast<const ReferenceType *>(decl->params.at(0)->get_type());
212	const ReferenceType * derivedMsgRef = dynamic_cast<const ReferenceType *>(decl->params.at(1)->get_type());
213	if ( !derivedActorRef \|\| !derivedMsgRef ) return;
214
215	// the references should be to struct instances
216	const StructInstType * arg1InstType = dynamic_cast<const StructInstType *>(derivedActorRef->base.get());
217	const StructInstType * arg2InstType = dynamic_cast<const StructInstType *>(derivedMsgRef->base.get());
218	if ( !arg1InstType \|\| !arg2InstType ) return;
219
220	// If the struct instances are derived actor and message types then generate the message send routine
221	auto actorIter = actorStructDecls.find( arg1InstType->aggr() );
222	auto messageIter = messageStructDecls.find( arg2InstType->aggr() );
223	if ( actorIter != actorStructDecls.end() && messageIter != messageStructDecls.end() ) {
224	//////////////////////////////////////////////////////////////////////
225	// The following generates this wrapper for all receive(derived_actor &, derived_msg &) functions
226	/* base_actor and base_msg are output params
227	static inline allocation __CFA_receive_wrap( derived_actor & receiver, derived_msg & msg, actor base_actor, message base_msg ) {
228	base_actor = &receiver;
229	base_msg = &msg;
230	return receive( receiver, msg );
231	}
232	*/
233	CompoundStmt * wrapBody = new CompoundStmt( decl->location );
234
235	// generates: base_actor = &receiver;
236	wrapBody->push_back( new ExprStmt( decl->location,
237	UntypedExpr::createAssign( decl->location,
238	UntypedExpr::createDeref( decl->location, new NameExpr( decl->location, "base_actor" ) ),
239	new AddressExpr( decl->location, new NameExpr( decl->location, "receiver" ) )
240	)
241	));
242
243	// generates: base_msg = &msg;
244	wrapBody->push_back( new ExprStmt( decl->location,
245	UntypedExpr::createAssign( decl->location,
246	UntypedExpr::createDeref( decl->location, new NameExpr( decl->location, "base_msg" ) ),
247	new AddressExpr( decl->location, new NameExpr( decl->location, "msg" ) )
248	)
249	));
250
251	// generates: return receive( receiver, msg );
252	wrapBody->push_back( new ReturnStmt( decl->location,
253	new UntypedExpr ( decl->location,
254	new NameExpr( decl->location, "receive" ),
255	{
256	new NameExpr( decl->location, "receiver" ),
257	new NameExpr( decl->location, "msg" )
258	}
259	)
260	));
261
262	// create receive wrapper to extract base message and actor pointer
263	// put it all together into the complete function decl from above
264	FunctionDecl * receiveWrapper = new FunctionDecl(
265	decl->location,
266	"__CFA_receive_wrap",
267	{
268	new ObjectDecl(
269	decl->location,
270	"receiver",
271	ast::deepCopy( derivedActorRef )
272	),
273	new ObjectDecl(
274	decl->location,
275	"msg",
276	ast::deepCopy( derivedMsgRef )
277	),
278	new ObjectDecl(
279	decl->location,
280	"base_actor",
281	new PointerType( new PointerType( new StructInstType( *actorDecl ) ) )
282	),
283	new ObjectDecl(
284	decl->location,
285	"base_msg",
286	new PointerType( new PointerType( new StructInstType( *msgDecl ) ) )
287	)
288	}, // params
289	{
290	new ObjectDecl(
291	decl->location,
292	"__CFA_receive_wrap_ret",
293	new EnumInstType( *allocationDecl )
294	)
295	},
296	wrapBody, // body
297	{ Storage::Static }, // storage
298	Linkage::Cforall, // linkage
299	{}, // attributes
300	{ Function::Inline }
301	);
302
303	declsToAddAfter.push_back( receiveWrapper );
304
305	//////////////////////////////////////////////////////////////////////
306	// The following generates this send message operator routine for all receive(derived_actor &, derived_msg &) functions
307	/*
308	static inline derived_actor & ?\|?( derived_actor & receiver, derived_msg & msg ) {
309	request new_req;
310	allocation (*my_work_fn)( derived_actor &, derived_msg & ) = receive;
311	__receive_fn fn = (__receive_fn)my_work_fn;
312	new_req{ &receiver, &msg, fn };
313	send( receiver, new_req );
314	return receiver;
315	}
316	*/
317	CompoundStmt * sendBody = new CompoundStmt( decl->location );
318
319	// Generates: request new_req;
320	sendBody->push_back( new DeclStmt(
321	decl->location,
322	new ObjectDecl(
323	decl->location,
324	"new_req",
325	new StructInstType( *requestDecl )
326	)
327	));
328
329	// Function type is: allocation ()( derived_actor &, derived_msg &, actor , message * )
330	FunctionType * derivedReceive = new FunctionType();
331	derivedReceive->params.push_back( ast::deepCopy( derivedActorRef ) );
332	derivedReceive->params.push_back( ast::deepCopy( derivedMsgRef ) );
333	derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) );
334	derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) );
335	derivedReceive->returns.push_back( new EnumInstType( *allocationDecl ) );
336
337	// Generates: allocation (my_work_fn)( derived_actor &, derived_msg &, actor , message * ) = receive;
338	sendBody->push_back( new DeclStmt(
339	decl->location,
340	new ObjectDecl(
341	decl->location,
342	"my_work_fn",
343	new PointerType( derivedReceive ),
344	new SingleInit( decl->location, new NameExpr( decl->location, "__CFA_receive_wrap" ) )
345	)
346	));
347
348	// Function type is: allocation (*)( actor &, message & )
349	FunctionType * genericReceive = new FunctionType();
350	genericReceive->params.push_back( new ReferenceType( new StructInstType( *actorDecl ) ) );
351	genericReceive->params.push_back( new ReferenceType( new StructInstType( *msgDecl ) ) );
352	genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) );
353	genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) );
354	genericReceive->returns.push_back( new EnumInstType( *allocationDecl ) );
355
356	// Generates: allocation (fn)( actor &, message & ) = (allocation ()( actor &, message & ))my_work_fn;
357	// More readable synonymous code:
358	// typedef allocation (*__receive_fn)(actor &, message &);
359	// __receive_fn fn = (__receive_fn)my_work_fn;
360	sendBody->push_back( new DeclStmt(
361	decl->location,
362	new ObjectDecl(
363	decl->location,
364	"fn",
365	new PointerType( genericReceive ),
366	new SingleInit( decl->location,
367	new CastExpr( decl->location, new NameExpr( decl->location, "my_work_fn" ), new PointerType( genericReceive ), ExplicitCast )
368	)
369	)
370	));
371
372	// Generates: new_req{ (actor )&receiver, (message )&msg, fn };
373	sendBody->push_back( new ExprStmt(
374	decl->location,
375	new UntypedExpr (
376	decl->location,
377	new NameExpr( decl->location, "?{}" ),
378	{
379	new NameExpr( decl->location, "new_req" ),
380	new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "receiver" ) ), new PointerType( new StructInstType( *actorDecl ) ), ExplicitCast ),
381	new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "msg" ) ), new PointerType( new StructInstType( *msgDecl ) ), ExplicitCast ),
382	new NameExpr( decl->location, "fn" )
383	}
384	)
385	));
386
387	// Generates: send( receiver, new_req );
388	sendBody->push_back( new ExprStmt(
389	decl->location,
390	new UntypedExpr (
391	decl->location,
392	new NameExpr( decl->location, "send" ),
393	{
394	{
395	new NameExpr( decl->location, "receiver" ),
396	new NameExpr( decl->location, "new_req" )
397	}
398	}
399	)
400	));
401
402	// Generates: return receiver;
403	sendBody->push_back( new ReturnStmt( decl->location, new NameExpr( decl->location, "receiver" ) ) );
404
405	// put it all together into the complete function decl from above
406	FunctionDecl * sendOperatorFunction = new FunctionDecl(
407	decl->location,
408	"?\|?",
409	{
410	new ObjectDecl(
411	decl->location,
412	"receiver",
413	ast::deepCopy( derivedActorRef )
414	),
415	new ObjectDecl(
416	decl->location,
417	"msg",
418	ast::deepCopy( derivedMsgRef )
419	)
420	}, // params
421	{
422	new ObjectDecl(
423	decl->location,
424	"receiver_ret",
425	ast::deepCopy( derivedActorRef )
426	)
427	},
428	nullptr, // body
429	{ Storage::Static }, // storage
430	Linkage::Cforall, // linkage
431	{}, // attributes
432	{ Function::Inline }
433	);
434
435	// forward decls to resolve use before decl problem for '\|' routines
436	forwardDecls.insertDecl( actorIter, messageIter , ast::deepCopy( sendOperatorFunction ) );
437
438	sendOperatorFunction->stmts = sendBody;
439	declsToAddAfter.push_back( sendOperatorFunction );
440	}
441	}
442
443	public:
444	GenFuncsCreateTables( unordered_set<const StructDecl > & actorStructDecls, unordered_set<const StructDecl > & messageStructDecls,
445	const StructDecl requestDecl, const EnumDecl allocationDecl, const StructDecl actorDecl, const StructDecl msgDecl,
446	FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls),
447	requestDecl(requestDecl), allocationDecl(allocationDecl), actorDecl(actorDecl), msgDecl(msgDecl), forwardDecls(forwardDecls) {}
448	};
449
450
451	// separate pass is needed since this pass resolves circular defn issues
452	// generates the forward declarations of the send operator for actor routines
453	struct FwdDeclOperator : public ast::WithDeclsToAdd<> {
454	unordered_set<const StructDecl *> & actorStructDecls;
455	unordered_set<const StructDecl *> & messageStructDecls;
456	FwdDeclTable & forwardDecls;
457
458	// handles forward declaring the message operator
459	void postvisit( const StructDecl * decl ) {
460	list<FunctionDecl *> toAddAfter;
461	auto actorIter = actorStructDecls.find( decl );
462	if ( actorIter != actorStructDecls.end() ) { // this is a derived actor decl
463	// get list of fwd decls that we can now insert
464	toAddAfter = forwardDecls.updateDecl( decl, false );
465
466	// get rid of decl from actorStructDecls since we no longer need it
467	actorStructDecls.erase( actorIter );
468	} else {
469	auto messageIter = messageStructDecls.find( decl );
470	if ( messageIter == messageStructDecls.end() ) return;
471
472	toAddAfter = forwardDecls.updateDecl( decl, true );
473
474	// get rid of decl from messageStructDecls since we no longer need it
475	messageStructDecls.erase( messageIter );
476	}
477
478	// add the fwd decls to declsToAddAfter
479	for ( FunctionDecl * func : toAddAfter ) {
480	declsToAddAfter.push_back( func );
481	}
482	}
483
484	public:
485	FwdDeclOperator( unordered_set<const StructDecl > & actorStructDecls, unordered_set<const StructDecl > & messageStructDecls,
486	FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), forwardDecls(forwardDecls) {}
487	};
488
489	void implementActors( TranslationUnit & translationUnit ) {
490	// unordered_maps to collect all derived actor and message types
491	unordered_set<const StructDecl *> actorStructDecls;
492	unordered_set<const StructDecl *> messageStructDecls;
493	FwdDeclTable forwardDecls;
494
495	// for storing through the passes
496	// these are populated with various important struct decls
497	const StructDecl * requestDeclPtr = nullptr;
498	const EnumDecl * allocationDeclPtr = nullptr;
499	const StructDecl * actorDeclPtr = nullptr;
500	const StructDecl * msgDeclPtr = nullptr;
501
502	// double pointer to modify local ptrs above
503	const StructDecl ** requestDecl = &requestDeclPtr;
504	const EnumDecl ** allocationDecl = &allocationDeclPtr;
505	const StructDecl ** actorDecl = &actorDeclPtr;
506	const StructDecl ** msgDecl = &msgDeclPtr;
507
508	// first pass collects ptrs to allocation enum, request type, and generic receive fn typedef
509	// also populates maps of all derived actors and messages
510	Pass<CollectactorStructDecls>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl,
511	allocationDecl, actorDecl, msgDecl );
512
513	// check that we have found all the decls we need from <actor.hfa>, if not no need to run the rest of this pass
514	if ( !allocationDeclPtr \|\| !requestDeclPtr \|\| !actorDeclPtr \|\| !msgDeclPtr )
515	return;
516
517	// second pass locates all receive() routines that overload the generic receive fn
518	// it then generates the appropriate operator '\|' send routines for the receive routines
519	Pass<GenFuncsCreateTables>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl,
520	allocationDecl, actorDecl, msgDecl, forwardDecls );
521
522	// The third pass forward declares operator '\|' send routines
523	Pass<FwdDeclOperator>::run( translationUnit, actorStructDecls, messageStructDecls, forwardDecls );
524	}
525
526	} // namespace Concurrency
527
528	// Local Variables: //
529	// tab-width: 4 //
530	// mode: c++ //
531	// compile-command: "make install" //
532	// End: //
533

Note: See TracBrowser for help on using the repository browser.

Download in other formats: