source: src/Concurrency/Actors.cpp @ ed96731

Last change on this file since ed96731 was ed96731, checked in by Andrew Beach <ajbeach@…>, 30 hours ago

With{Stmts,Decls}ToAdd? how has an -X version like WithSymbolTableX. Although these -X versions might be useful can could possibly be removed in the future. (This is a therapy commit.)
  • 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>
24using namespace ast;
25using namespace std;
26
27namespace Concurrency {
28
29struct 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
97class 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)
196struct 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
453struct 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
489void 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.