source: src/Concurrency/Actors.cpp @ 1d66a91

Last change on this file since 1d66a91 was b065dbb, checked in by caparsons <caparson@…>, 12 months ago

refactored actors to not need base pointers in envelopes
  • Property mode set to 100644
File size: 24.5 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                {},                     // forall
268                {
269                    new ObjectDecl(
270                        decl->location,
271                        "receiver",
272                        ast::deepCopy( derivedActorRef )
273                    ),
274                    new ObjectDecl(
275                        decl->location,
276                        "msg",
277                        ast::deepCopy( derivedMsgRef )
278                    ),
279                    new ObjectDecl(
280                        decl->location,
281                        "base_actor",
282                        new PointerType( new PointerType( new StructInstType( *actorDecl ) ) )
283                    ),
284                    new ObjectDecl(
285                        decl->location,
286                        "base_msg",
287                        new PointerType( new PointerType( new StructInstType( *msgDecl ) ) )
288                    )
289                },                      // params
290                { 
291                    new ObjectDecl(
292                        decl->location,
293                        "__CFA_receive_wrap_ret",
294                        new EnumInstType( *allocationDecl )
295                    )
296                },
297                wrapBody,               // body
298                { Storage::Static },    // storage
299                Linkage::Cforall,       // linkage
300                {},                     // attributes
301                { Function::Inline }
302            );
303
304            declsToAddAfter.push_back( receiveWrapper );
305
306            //////////////////////////////////////////////////////////////////////
307            // The following generates this send message operator routine for all receive(derived_actor &, derived_msg &) functions
308            /*
309                static inline derived_actor & ?|?( derived_actor & receiver, derived_msg & msg ) {
310                    request new_req;
311                    allocation (*my_work_fn)( derived_actor &, derived_msg & ) = receive;
312                    __receive_fn fn = (__receive_fn)my_work_fn;
313                    new_req{ &receiver, &msg, fn };
314                    send( receiver, new_req );
315                    return receiver;
316                }
317            */ 
318            CompoundStmt * sendBody = new CompoundStmt( decl->location );
319
320            // Generates: request new_req;
321            sendBody->push_back( new DeclStmt(
322                decl->location,
323                new ObjectDecl(
324                    decl->location,
325                    "new_req",
326                    new StructInstType( *requestDecl )
327                )
328            ));
329           
330            // Function type is: allocation (*)( derived_actor &, derived_msg &, actor **, message ** )
331            FunctionType * derivedReceive = new FunctionType();
332            derivedReceive->params.push_back( ast::deepCopy( derivedActorRef ) );
333            derivedReceive->params.push_back( ast::deepCopy( derivedMsgRef ) );
334            derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) );
335            derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) );
336            derivedReceive->returns.push_back( new EnumInstType( *allocationDecl ) );
337
338            // Generates: allocation (*my_work_fn)( derived_actor &, derived_msg &, actor **, message ** ) = receive;
339            sendBody->push_back( new DeclStmt(
340                decl->location,
341                new ObjectDecl(
342                    decl->location,
343                    "my_work_fn",
344                    new PointerType( derivedReceive ),
345                    new SingleInit( decl->location, new NameExpr( decl->location, "__CFA_receive_wrap" ) )
346                )
347            ));
348
349            // Function type is: allocation (*)( actor &, message & )
350            FunctionType * genericReceive = new FunctionType();
351            genericReceive->params.push_back( new ReferenceType( new StructInstType( *actorDecl ) ) );
352            genericReceive->params.push_back( new ReferenceType( new StructInstType( *msgDecl ) ) );
353            genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) );
354            genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) );
355            genericReceive->returns.push_back( new EnumInstType( *allocationDecl ) );
356
357            // Generates: allocation (*fn)( actor &, message & ) = (allocation (*)( actor &, message & ))my_work_fn;
358            // More readable synonymous code:
359            //     typedef allocation (*__receive_fn)(actor &, message &);
360            //     __receive_fn fn = (__receive_fn)my_work_fn;
361            sendBody->push_back( new DeclStmt(
362                decl->location,
363                new ObjectDecl(
364                    decl->location,
365                    "fn",
366                    new PointerType( genericReceive ),
367                    new SingleInit( decl->location, 
368                        new CastExpr( decl->location, new NameExpr( decl->location, "my_work_fn" ), new PointerType( genericReceive ), ExplicitCast )
369                    )
370                )
371            ));
372
373            // Generates: new_req{ (actor *)&receiver, (message *)&msg, fn };
374            sendBody->push_back( new ExprStmt(
375                decl->location,
376                                new UntypedExpr (
377                    decl->location, 
378                                        new NameExpr( decl->location, "?{}" ),
379                                        {
380                                                new NameExpr( decl->location, "new_req" ),
381                        new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "receiver" ) ), new PointerType( new StructInstType( *actorDecl ) ), ExplicitCast ),
382                        new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "msg" ) ), new PointerType( new StructInstType( *msgDecl ) ), ExplicitCast ),
383                        new NameExpr( decl->location, "fn" )
384                                        }
385                                )
386                        ));
387
388            // Generates: send( receiver, new_req );
389            sendBody->push_back( new ExprStmt(
390                decl->location,
391                                new UntypedExpr (
392                    decl->location,
393                                        new NameExpr( decl->location, "send" ),
394                                        {
395                                                {
396                            new NameExpr( decl->location, "receiver" ),
397                            new NameExpr( decl->location, "new_req" )
398                        }
399                                        }
400                                )
401                        ));
402           
403            // Generates: return receiver;
404            sendBody->push_back( new ReturnStmt( decl->location, new NameExpr( decl->location, "receiver" ) ) );
405
406            // put it all together into the complete function decl from above
407            FunctionDecl * sendOperatorFunction = new FunctionDecl(
408                decl->location,
409                "?|?",
410                {},                     // forall
411                {
412                    new ObjectDecl(
413                        decl->location,
414                        "receiver",
415                        ast::deepCopy( derivedActorRef )
416                    ),
417                    new ObjectDecl(
418                        decl->location,
419                        "msg",
420                        ast::deepCopy( derivedMsgRef )
421                    )
422                },                      // params
423                { 
424                    new ObjectDecl(
425                        decl->location,
426                        "receiver_ret",
427                        ast::deepCopy( derivedActorRef )
428                    )
429                },
430                nullptr,               // body
431                { Storage::Static },    // storage
432                Linkage::Cforall,       // linkage
433                {},                     // attributes
434                { Function::Inline }
435            );
436           
437            // forward decls to resolve use before decl problem for '|' routines
438            forwardDecls.insertDecl( *actorIter, *messageIter , ast::deepCopy( sendOperatorFunction ) );
439
440            sendOperatorFunction->stmts = sendBody;
441            declsToAddAfter.push_back( sendOperatorFunction );
442        }
443        }
444
445  public:
446    GenFuncsCreateTables( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls,
447        const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl, 
448        FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), 
449        requestDecl(requestDecl), allocationDecl(allocationDecl), actorDecl(actorDecl), msgDecl(msgDecl), forwardDecls(forwardDecls) {}
450};
451
452
453// separate pass is needed since this pass resolves circular defn issues
454// generates the forward declarations of the send operator for actor routines
455struct FwdDeclOperator : public ast::WithDeclsToAdd<> {
456    unordered_set<const StructDecl *> & actorStructDecls;
457    unordered_set<const StructDecl *>  & messageStructDecls;
458    FwdDeclTable & forwardDecls;
459
460    // handles forward declaring the message operator
461    void postvisit( const StructDecl * decl ) {
462        list<FunctionDecl *> toAddAfter;
463        auto actorIter = actorStructDecls.find( decl );
464        if ( actorIter != actorStructDecls.end() ) { // this is a derived actor decl
465            // get list of fwd decls that we can now insert
466            toAddAfter = forwardDecls.updateDecl( decl, false );
467
468            // get rid of decl from actorStructDecls since we no longer need it
469            actorStructDecls.erase( actorIter );
470        } else {
471            auto messageIter = messageStructDecls.find( decl );
472            if ( messageIter == messageStructDecls.end() ) return;
473
474            toAddAfter = forwardDecls.updateDecl( decl, true );
475
476            // get rid of decl from messageStructDecls since we no longer need it
477            messageStructDecls.erase( messageIter );
478        }
479
480        // add the fwd decls to declsToAddAfter
481        for ( FunctionDecl * func : toAddAfter ) {
482            declsToAddAfter.push_back( func );
483        }
484    }
485
486  public:
487    FwdDeclOperator( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls, 
488        FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), forwardDecls(forwardDecls) {}
489};
490
491void implementActors( TranslationUnit & translationUnit ) {
492    // unordered_maps to collect all derived actor and message types
493    unordered_set<const StructDecl *> actorStructDecls;
494    unordered_set<const StructDecl *> messageStructDecls;
495    FwdDeclTable forwardDecls;
496
497    // for storing through the passes
498    // these are populated with various important struct decls
499    const StructDecl * requestDeclPtr = nullptr;
500    const EnumDecl * allocationDeclPtr = nullptr;
501    const StructDecl * actorDeclPtr = nullptr;
502    const StructDecl * msgDeclPtr = nullptr;
503
504    // double pointer to modify local ptrs above
505    const StructDecl ** requestDecl = &requestDeclPtr;
506    const EnumDecl ** allocationDecl = &allocationDeclPtr;
507    const StructDecl ** actorDecl = &actorDeclPtr;
508    const StructDecl ** msgDecl = &msgDeclPtr;
509
510    // first pass collects ptrs to allocation enum, request type, and generic receive fn typedef
511    // also populates maps of all derived actors and messages
512    Pass<CollectactorStructDecls>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 
513        allocationDecl, actorDecl, msgDecl );
514
515    // check that we have found all the decls we need from <actor.hfa>, if not no need to run the rest of this pass
516    if ( !allocationDeclPtr || !requestDeclPtr || !actorDeclPtr || !msgDeclPtr ) 
517        return;
518
519    // second pass locates all receive() routines that overload the generic receive fn
520    // it then generates the appropriate operator '|' send routines for the receive routines
521    Pass<GenFuncsCreateTables>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 
522        allocationDecl, actorDecl, msgDecl, forwardDecls );
523
524    // The third pass forward declares operator '|' send routines
525    Pass<FwdDeclOperator>::run( translationUnit, actorStructDecls, messageStructDecls, forwardDecls );
526}
527
528
529} // namespace Concurrency
530
531// Local Variables: //
532// tab-width: 4 //
533// mode: c++ //
534// compile-command: "make install" //
535// End: //
536
Note: See TracBrowser for help on using the repository browser.