Index: src/Concurrency/Actors.cpp =================================================================== --- src/Concurrency/Actors.cpp (revision 9d0ff307d494aafc3fc5c8d77da096d4c12b58eb) +++ src/Concurrency/Actors.cpp (revision 96ddc629ac15699df3b7f35ada756efea94d903f) @@ -21,11 +21,13 @@ #include "AST/TranslationUnit.hpp" #include "AST/Expr.hpp" +#include using namespace ast; +using namespace std; namespace Concurrency { struct CollectactorStructDecls : public ast::WithGuards { - std::map & actorStructDecls; - std::map & messageStructDecls; + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; const StructDecl ** requestDecl; const EnumDecl ** allocationDecl; @@ -51,8 +53,8 @@ if ( ! *actorDecl || ! *msgDecl ) return; if ( insideStruct ) { - if ( node->aggr() == *actorDecl ) { - actorStructDecls.insert({parentDecl, 1}); + if ( node->aggr() == *actorDecl ) { // C_TODO: see if we need to check for empty name + actorStructDecls.insert( parentDecl ); } else if ( node->aggr() == *msgDecl ) { - messageStructDecls.insert({parentDecl, 1}); + messageStructDecls.insert( parentDecl ); } } @@ -60,5 +62,5 @@ public: - CollectactorStructDecls( std::map & actorStructDecls, std::map & messageStructDecls, + CollectactorStructDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl ) : actorStructDecls( actorStructDecls ), messageStructDecls( messageStructDecls ), requestDecl( requestDecl ), @@ -66,12 +68,123 @@ }; +// keeps track of all fwdDecls of message routines so that we can hoist them to right after the appropriate decls +class FwdDeclTable { + + // tracks which decls we have seen so that we can hoist the FunctionDecl to the highest point possible + struct FwdDeclData { + const StructDecl * actorDecl; + const StructDecl * msgDecl; + FunctionDecl * fwdDecl; + bool actorFound; + bool msgFound; + + bool readyToInsert() { return actorFound && msgFound; } + bool foundActor() { actorFound = true; return readyToInsert(); } + bool foundMsg() { msgFound = true; return readyToInsert(); } + + FwdDeclData( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) : + actorDecl(actorDecl), msgDecl(msgDecl), fwdDecl(fwdDecl), actorFound(false), msgFound(false) {} + }; + + // map indexed by actor struct ptr + // value is map of all FwdDeclData that contains said actor struct ptr + // inner map is indexed by the message struct ptr of FwdDeclData + unordered_map> actorMap; + + // this map is the same except the outer map is indexed by message ptr and the inner is indexed by actor ptr + unordered_map> msgMap; + + void insert( const StructDecl * decl, const StructDecl * otherDecl, unordered_map> & map, FwdDeclData * data ) { + auto iter = map.find( decl ); + if ( iter != map.end() ) { // if decl exists in map append data to existing inner map + iter->second.emplace( make_pair( otherDecl, data ) ); + } else { // else create inner map for key + map.emplace( make_pair( decl, unordered_map( { make_pair( otherDecl, data ) } ) ) ); // C_TODO: maybe emplace? + } + } + + public: + // insert decl into table so that we can fwd declare it later (average cost: O(1)) + void insertDecl( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) { + FwdDeclData * declToInsert = new FwdDeclData( actorDecl, msgDecl, fwdDecl ); + insert( actorDecl, msgDecl, actorMap, declToInsert ); + insert( msgDecl, actorDecl, msgMap, declToInsert ); + } + + // returns list of decls to insert after current struct decl + // Over the entire pass the runtime of this routine is O(r) where r is the # of receive routines + list updateDecl( const StructDecl * decl, bool isMsg ) { + unordered_map> & map = isMsg ? msgMap : actorMap; + unordered_map> & otherMap = isMsg ? actorMap : msgMap; + auto iter = map.find( decl ); + + list toInsertAfter; // this is populated with decls that are ready to insert + if ( iter == map.end() ) return toInsertAfter; + + unordered_map & currInnerMap = iter->second; + + cout << "a" << endl; + // iterate over inner map + for ( auto innerIter = currInnerMap.begin(); innerIter != currInnerMap.end(); ) { + cout << "b: " << decl->name << endl; + FwdDeclData * currentDatum = innerIter->second; + printf("P: %p\n", currentDatum->fwdDecl ); + + bool readyToInsert = isMsg ? currentDatum->foundMsg() : currentDatum->foundActor(); + if ( ! readyToInsert ) { ++innerIter; continue; } + + cout << "c" << endl; + // readyToInsert is true so we are good to insert the forward decl of the message fn + toInsertAfter.push_back( currentDatum->fwdDecl ); + + cout << "d" << endl; + + const StructDecl * otherDecl = isMsg ? currentDatum->actorDecl : currentDatum->msgDecl; + + // need to remove from other map before deleting + // find inner map of FwdDeclData in other map ( other map is actor map if original is msg map and vice versa ) + auto otherMapIter = otherMap.find( otherDecl ); + + unordered_map & otherInnerMap = otherMapIter->second; + + cout << "e" << endl; + // find the FwdDeclData we need to remove in the other inner map + auto otherInnerIter = otherInnerMap.find( decl ); + + cout << "f" << endl; + // now we are safe to delete the FwdDeclData since we are done with it + // have to delete before we invalidate the iterator + delete currentDatum; // C_TODO: move down since this no longer iterator dependant + + cout << "g" << endl; + // remove references to deleted FwdDeclData from current inner map + innerIter = currInnerMap.erase( innerIter ); // this does the increment so no explicit inc needed + + cout << "h" << endl; + // remove references to deleted FwdDeclData from other inner map + otherInnerMap.erase( otherInnerIter ); + + // if other inner map is now empty, remove key from other outer map + if ( otherInnerMap.empty() ) + otherMap.erase( otherDecl ); + } + + // if current inner map is now empty, remove key from outer map. + // Have to do this after iterating for safety + if ( currInnerMap.empty() ) + map.erase( decl ); + + return toInsertAfter; + } +}; + struct GenReceiveDecls : public ast::WithDeclsToAdd<> { - std::map & actorStructDecls; - std::map & messageStructDecls; + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; const StructDecl ** requestDecl; const EnumDecl ** allocationDecl; const StructDecl ** actorDecl; const StructDecl ** msgDecl; - std::vector & forwardDecls; + FwdDeclTable & forwardDecls; void postvisit( const FunctionDecl * decl ) { @@ -90,5 +203,7 @@ // If the struct instances are derived actor and message types then generate the message send routine - if ( actorStructDecls.count( arg1InstType->aggr() ) && messageStructDecls.count( arg2InstType->aggr() ) ) { + auto actorIter = actorStructDecls.find( arg1InstType->aggr() ); + auto messageIter = messageStructDecls.find( arg2InstType->aggr() ); + if ( actorIter != actorStructDecls.end() && messageIter != messageStructDecls.end() ) { // check that we have found all the decls we need from @@ -225,5 +340,6 @@ // forward decls to resolve use before decl problem for '|' routines - forwardDecls.push_back( ast::deepCopy( sendOperatorFunction ) ); + forwardDecls.insertDecl( *actorIter, *messageIter , ast::deepCopy( sendOperatorFunction ) ); + // forwardDecls.push_back( ast::deepCopy( sendOperatorFunction ) ); sendOperatorFunction->stmts = sendBody; @@ -233,51 +349,51 @@ public: - GenReceiveDecls( std::map & actorStructDecls, std::map & messageStructDecls, + GenReceiveDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl, - std::vector & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), + FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), requestDecl(requestDecl), allocationDecl(allocationDecl), actorDecl(actorDecl), msgDecl(msgDecl), forwardDecls(forwardDecls) {} }; struct GenFwdDecls : public ast::WithDeclsToAdd<> { - std::map & actorStructDecls; - std::map & messageStructDecls; - std::vector & forwardDecls; - bool done; - - void postvisit( const FunctionDecl * decl ) { - if ( done ) return; - // return if not of the form receive( param1, param2 ) or if it is a forward decl - if ( decl->name != "receive" || decl->params.size() != 2 || !decl->stmts ) return; - - // the params should be references - const ReferenceType * derivedActorRef = dynamic_cast(decl->params.at(0)->get_type()); - const ReferenceType * derivedMsgRef = dynamic_cast(decl->params.at(1)->get_type()); - if ( !derivedActorRef || !derivedMsgRef ) return; - - // the references should be to struct instances - const StructInstType * arg1InstType = dynamic_cast(derivedActorRef->base.get()); - const StructInstType * arg2InstType = dynamic_cast(derivedMsgRef->base.get()); - if ( !arg1InstType || !arg2InstType ) return; - - // If the struct instances are derived actor and message types then generate the message send routine - if ( actorStructDecls.count( arg1InstType->aggr() ) && messageStructDecls.count( arg2InstType->aggr() ) ) { - done = true; - for ( const auto & func : forwardDecls ) { - declsToAddBefore.push_back( func ); - } + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; + FwdDeclTable & forwardDecls; + + void postvisit( const StructDecl * decl ) { + list toAddAfter; + auto actorIter = actorStructDecls.find( decl ); + if ( actorIter != actorStructDecls.end() ) { // this is a derived actor decl + // get list of fwd decls that we can now insert + toAddAfter = forwardDecls.updateDecl( decl, false ); + + // get rid of decl from actorStructDecls since we no longer need it + actorStructDecls.erase( actorIter ); + } else { + auto messageIter = messageStructDecls.find( decl ); + if ( messageIter == messageStructDecls.end() ) return; + + toAddAfter = forwardDecls.updateDecl( decl, true ); + + // get rid of decl from messageStructDecls since we no longer need it + messageStructDecls.erase( messageIter ); + } + + // add the fwd decls to declsToAddAfter + for ( FunctionDecl * func : toAddAfter ) { + declsToAddAfter.push_back( func ); } } public: - GenFwdDecls( std::map & actorStructDecls, std::map & messageStructDecls, - std::vector & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), - forwardDecls(forwardDecls), done(false) {} + GenFwdDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, + FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), + forwardDecls(forwardDecls) {} }; void implementActors( TranslationUnit & translationUnit ) { - // maps to collect all derived actor and message types - std::map actorStructDecls; - std::map messageStructDecls; - std::vector forwardDecls; + // unordered_maps to collect all derived actor and message types + unordered_set actorStructDecls; + unordered_set messageStructDecls; + FwdDeclTable forwardDecls; // for storing through the passes