Index: doc/LaTeXmacros/lstlang.sty =================================================================== --- doc/LaTeXmacros/lstlang.sty (revision 85855b0f02c6f17de398969fbe7ab4810d76737a) +++ doc/LaTeXmacros/lstlang.sty (revision 42cdd07d1887eb665ac08cdda6678637cad05905) @@ -8,6 +8,6 @@ %% Created On : Sat May 13 16:34:42 2017 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Mon Apr 15 11:28:44 2024 -%% Update Count : 43 +%% Last Modified On : Fri May 31 14:36:02 2024 +%% Update Count : 44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -115,5 +115,5 @@ morekeywords={ alignas, _Alignas, alignof, _Alignof, __alignof, __alignof__, and, asm, __asm, __asm__, _Atomic, __attribute, __attribute__, - __auto_type, basetypeof, _Bool, catch, catchResume, choose, coerce, corun, cofor, _Complex, __complex, __complex__, + __auto_type, basetypeof, _Bool, bool, catch, catchResume, choose, coerce, corun, cofor, _Complex, __complex, __complex__, __const, __const__, continue, coroutine, _Decimal32, _Decimal64, _Decimal128, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally, fixup, __float80, float80, __float128, float128, _Float16, _Float32, _Float32x, _Float64, Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision 85855b0f02c6f17de398969fbe7ab4810d76737a) +++ doc/bibliography/pl.bib (revision 42cdd07d1887eb665ac08cdda6678637cad05905) @@ -813,5 +813,4 @@ title = {The Art of Multiprocessor Programming}, year = 2008, - isbn = {0123705916, 9780123705914}, publisher = {Morgan Kaufmann Publishers}, address = {San Francisco}, @@ -928,7 +927,18 @@ month = sep, year = 2013, - pages = {46--53}, + pages = {46-53}, publisher = {ACM}, address = {New York, NY, USA}, +} + +@inproceedings{Aravind18, + contributer = {pabuhr@plg}, + author = {Alex Aravind}, + title = {Barrier Synchronization: Simplified, Generalized, and Solved without Mutual Exclusion}, + organization= {IEEE International Parallel and Distributed Processing Symposium Workshops}, + series = {IPDPSW'18}, + month = may, + year = 2018, + pages = {773-782}, } @@ -1106,4 +1116,14 @@ publisher = {ACM}, address = {New York, NY, USA}, +} + +@article{Brooks87, + author = {Eugene D. Brooks III}, + title = {The Butterfly Barrier}, + journal = {International Journal of Parallel Programming}, + volume = 15, + number = 4, + pages = {295-307}, + year = 1987, } @@ -4340,4 +4360,17 @@ chapter = {1}, publisher = {The MIT Press} +} + +@article{Lamport08, + keywords = {concurrency, barrier}, + contributer = {pabuhr@plg}, + author = {Leslie Lamport}, + title = {Implementing Dataflow with Threads}, + journal = {Distributed Computing}, + year = 2008, + month = jul, + volume = 21, + number = 3, + pages = {163-181}, } @@ -5171,6 +5204,4 @@ journal = {ACM Trans. Parallel Comput.}, issn = {2329-4949}, - url = {https://doi.org/10.1145/3584696}, - doi = {10.1145/3584696}, articleno = 11, numpages = 23, @@ -7769,4 +7800,14 @@ } +@book{Scott24, + author = {Michael L. Scott and Trevor Brown}, + booktitle = {Shared-Memory Synchronization}, + series = {Synthesis Lectures on Computer Architecture}, + edition = {2nd}, + year = 2024, + publisher = {Springer International Publishing}, + address = {Cham, Switzerland}, +} + @inproceedings{Leissa14, title = {{S}ierra: a {SIMD} extension for {C}++}, @@ -8661,4 +8702,14 @@ } +@article{Hensgen88, + author = {Debra Hensgen and Raphael Finkel and Udi Manber}, + title = {Two algorithms for barrier synchronization}, + journal = {International Journal of Parallel Programming}, + volume = 17, + number = 1, + pages = {1-17}, + year = 1988, +} + @article{Leroy00, keywords = {type-systems, exceptions}, @@ -8752,5 +8803,5 @@ title = {Understanding Control Flow: Concurrent Programming using $\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}}}, publisher = {Springer}, - address = {Switzerland}, + address = {Cham, Switzerland}, year = 2016, } Index: doc/proposals/modules.md =================================================================== --- doc/proposals/modules.md (revision 85855b0f02c6f17de398969fbe7ab4810d76737a) +++ doc/proposals/modules.md (revision 42cdd07d1887eb665ac08cdda6678637cad05905) @@ -5,14 +5,25 @@ ====================== -Modules are a term for the base in separate compilation. Different languages have different ways to implement it, for C/C++ the module is the code/source file and usually header file. +In this proposal we will be descussing modules. Although their exact nature changes between programming languages, modules are the smallest unit of code reuse between programs, or the base unit in separate compilation. Modules, and the extended module system, will be tied up in various stages of compilation and execution, with a particular focus on visibility between different parts of the program. + +Note that terminology is not fixed across languages. For instance, some languages use the word package or library instead. Module was chosen as the generic term because it seems to have the least amount of other uses (for example, a package is sometimes a group of modules). + +In C there is no formal definition of module, but informally modules are a pair of files, the body file (.c) and the header (.h). The header provides the interface and the body file gives the implementation. (A translation unit is a source file, usually a .c file, and all the recursively included files.) Some modules, like the main module, Uses of Modules --------------- -The most straight forward purpose of modules is to enable separate compilation. -This in turn reduces recompilation, by isolating changes, and parallel compilation, but making modules independent. +This section covers the features module system to allow for the separatation of code across modules and why -An related feature is sharing information between modules. Information needed by other modules must be shared. However, avoiding sharing extra information can further isolating changes, and can also reduces the work of compiling a single module. +Modules are often, but not always, the means by which a language views source files. There is almost always some kind of parity between modules and source files, with modules being mapped onto one (or a few) source files. Sometimes the use of modules is used to find the approprate source files, requring this parity to be enforced in the language. Other times the parity is just a convention or is enforced for other reasons. -Modules are also used as a base for other organizational features. Such as namespacing on module names, using the module as a space for visibility modifiers. +[] + +If there is a universal feature of modules, it is information visibility. Modules decide what information within them is visible to other modules. Here visibility is the course grained sense of "visible in another module for any purpose". + +[] + +Accessablity is the more fine grained partner to visibility, allowing for information to be visible, but only usable for certain purposes. This includes privacy and friendship - only usable in certain parts of the program - or inlining information - only usable by the optimizer. + +In languages that have namespacing/qualified-names, modules will often interact with namespaces. Such as each module placing its declarations in a namespace of the same name. C Comparisons @@ -80,4 +91,29 @@ Second, this does nothing to solve the oversized header issue. It does not reduce any requirements on what includes need to be use. +Alternate Solutions +------------------- +There are other ways C's modules could be improved in Cforall. + +Explicit Module Blocks +...................... +Instead of trying map files to modules, they could instead be declared explicitly. Marking out the beginning and the end of a section of code as a module. If built on top of the body/header and include system might look like this. + +> extern module NAME { +> BODY +> } +> +> module NAME { +> BODY +> } + +The extern module goes in the header, the other module goes in the body. The basic usage is the forward declarations in the header module and the body contains the definitions. It can be used to check that the two sets match, but on its own it is only replicates the current header/body divide with a bit more explicit syntax. However, it can be used as the base for a lot of features of the module linkage system. It does solve the "knowning two declarations came from the same other module" problem (and could work with namespaces) but is otherwise very similar for a heavier syntax. + +Compiled Headers +................ +Most programming languages do not share source code between modules. Instead each module is compiled without looking at the source code in other modules. The result of compilation includes all the information required for later stages of compilation and information for compiling other modules. + +This is a more popular pattern more recent programming languages. It does have some advantages, such as reducing the amount of times that a file will need to be processed and can cut out unneeded transitive information. It is downsides include adding dependences between modules and it prevents any circlar dependences between modules. + +There is one other notable downside, and that is retrofitting this pattern on top of C. The problems with GCC precompiled headers and C++ modules give some indication of how tricky the situation is. The problem is the C pre-processor, not only is this the tool by which modules are implemented, but they contain information for the preprocessor itself, such as macros. Macro definitions must also be applied to the text of source files and so must be preserved. This might be possible in cases with strict dependences from the included file, but there are more unusual uses where macros depend on their context (previous includes or a define before the include) in their definition and these would almost imposible to translate over. ########################################################################################## @@ -86,5 +122,5 @@ ----' -Programming languages are divided into those embedded in an IDE, think Smalltalk and Racket, largely manipulating a symbol-table/abstract-symbol-tree, and those where the IDE is an external program largely manipulating program text. +Programming languages are divided into those embedded in an IDE, think Smalltalk and Lisp, Database, largely manipulating a symbol-table/abstract-symbol-tree, and those where the IDE is an external program largely manipulating program text. Separate compilation in programming languages without an embedded IDE is the process of giving a compiler command a series of files that are read and processed as a whole. The compiler output is placed in another set of files for execution loading or further processing. @@ -97,4 +133,6 @@ In a file system where file-links can be embedded in data creating a tree, duplicate source code can be eliminated by generating a complex linking structure among the source files. Without embedded file-links, dynamic embedding using #include/import is necessary to compose all the program components necessary for a compilation. + +inlining? I see two separate issues with respect to program structuring for controlling visibility and initializing a program. Index: src/InitTweak/GenInit.cpp =================================================================== --- src/InitTweak/GenInit.cpp (revision 85855b0f02c6f17de398969fbe7ab4810d76737a) +++ src/InitTweak/GenInit.cpp (revision 42cdd07d1887eb665ac08cdda6678637cad05905) @@ -32,5 +32,4 @@ #include "Common/ToString.hpp" // for toCString #include "Common/UniqueName.hpp" // for UniqueName -#include "Common/Utility.hpp" // for ValueGuard, maybeClone #include "GenPoly/GenPoly.hpp" // for getFunctionType, isPolyType #include "GenPoly/ScopedSet.hpp" // for ScopedSet, ScopedSet<>::const_iter... @@ -277,5 +276,4 @@ } // need to clear and reset qualifiers when determining if a type is managed - // ValueGuard< Type::Qualifiers > qualifiers( type->get_qualifiers() ); auto tmp = shallowCopy(type); tmp->qualifiers = {}; Index: src/Tuples/TupleAssignment.cpp =================================================================== --- src/Tuples/TupleAssignment.cpp (revision 85855b0f02c6f17de398969fbe7ab4810d76737a) +++ src/Tuples/TupleAssignment.cpp (revision 42cdd07d1887eb665ac08cdda6678637cad05905) @@ -241,138 +241,139 @@ ResolvExpr::CandidateFinder & crntFinder; std::string fname; - std::unique_ptr< Matcher > matcher; public: TupleAssignSpotter( ResolvExpr::CandidateFinder & f ) - : crntFinder( f ), fname(), matcher() {} - - // Find left- and right-hand-sides for mass or multiple assignment. + : crntFinder( f ), fname() {} + + /// Find left- and right-hand-sides for mass or multiple assignment. void spot( const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args - ) { - if ( auto op = expr->func.as< ast::NameExpr >() ) { - // Skip non-assignment functions. - if ( !CodeGen::isCtorDtorAssign( op->name ) ) return; - fname = op->name; - - // Handled by CandidateFinder if applicable (both odd cases). - if ( args.empty() || ( 1 == args.size() && CodeGen::isAssignment( fname ) ) ) { - return; - } - - // Look over all possible left-hand-side. - for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) { - // Skip non-tuple LHS. - if ( !refToTuple( lhsCand->expr ) ) continue; - - // Explode is aware of casts - ensure every LHS - // is sent into explode with a reference cast. - if ( !lhsCand->expr.as< ast::CastExpr >() ) { - lhsCand->expr = new ast::CastExpr( - lhsCand->expr, new ast::ReferenceType( lhsCand->expr->result ) ); + ); + /// Wrapper around matcher.match. + void match( Matcher & matcher ); +}; + +void TupleAssignSpotter::spot( + const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args +) { + // Skip non-"assignment" functions. + auto op = expr->func.as< ast::NameExpr >(); + if ( nullptr == op || !CodeGen::isCtorDtorAssign( op->name ) ) return; + + // Handled by CandidateFinder if applicable (both odd cases). + if ( args.empty() || ( 1 == args.size() && CodeGen::isAssignment( op->name ) ) ) { + return; + } + + fname = op->name; + + // Look over all possible left-hand-side. + for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) { + // Skip non-tuple LHS. + if ( !refToTuple( lhsCand->expr ) ) continue; + + // Explode is aware of casts - ensure every LHS + // is sent into explode with a reference cast. + if ( !lhsCand->expr.as< ast::CastExpr >() ) { + lhsCand->expr = new ast::CastExpr( + lhsCand->expr, new ast::ReferenceType( lhsCand->expr->result ) ); + } + + // Explode the LHS so that each field of a tuple-valued expr is assigned. + ResolvExpr::CandidateList lhs; + explode( *lhsCand, crntFinder.context.symtab, back_inserter(lhs), true ); + for ( ResolvExpr::CandidateRef & cand : lhs ) { + // Each LHS value must be a reference - some come in + // with a cast, if not just cast to reference here. + if ( !cand->expr->result.as< ast::ReferenceType >() ) { + cand->expr = new ast::CastExpr( + cand->expr, new ast::ReferenceType( cand->expr->result ) ); + } + } + + if ( 1 == args.size() ) { + // Mass default-initialization/destruction. + ResolvExpr::CandidateList rhs{}; + MassAssignMatcher matcher( *this, expr->location, lhs, rhs ); + match( matcher ); + } else if ( 2 == args.size() ) { + for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) { + ResolvExpr::CandidateList rhs; + if ( isTuple( rhsCand->expr ) ) { + // Multiple assignment: + explode( *rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true ); + MultipleAssignMatcher matcher( *this, expr->location, lhs, rhs ); + match( matcher ); + } else { + // Mass assignment: + rhs.emplace_back( rhsCand ); + MassAssignMatcher matcher( *this, expr->location, lhs, rhs ); + match( matcher ); } - - // Explode the LHS so that each field of a tuple-valued expr is assigned. - ResolvExpr::CandidateList lhs; - explode( *lhsCand, crntFinder.context.symtab, back_inserter(lhs), true ); - for ( ResolvExpr::CandidateRef & cand : lhs ) { - // Each LHS value must be a reference - some come in - // with a cast, if not just cast to reference here. - if ( !cand->expr->result.as< ast::ReferenceType >() ) { - cand->expr = new ast::CastExpr( - cand->expr, new ast::ReferenceType( cand->expr->result ) ); - } - } - - if ( 1 == args.size() ) { - // Mass default-initialization/destruction. - ResolvExpr::CandidateList rhs{}; - matcher.reset( new MassAssignMatcher( *this, expr->location, lhs, rhs ) ); - match(); - } else if ( 2 == args.size() ) { - for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) { - ResolvExpr::CandidateList rhs; - if ( isTuple( rhsCand->expr ) ) { - // Multiple assignment: - explode( *rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true ); - matcher.reset( - new MultipleAssignMatcher( *this, expr->location, lhs, rhs ) ); - } else { - // Mass assignment: - rhs.emplace_back( rhsCand ); - matcher.reset( - new MassAssignMatcher( *this, expr->location, lhs, rhs ) ); - } - match(); - } - } else { - // Expand all possible RHS possibilities. - std::vector< ResolvExpr::CandidateList > rhsCands; - combos( - std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) ); - for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) { - // Multiple assignment: - ResolvExpr::CandidateList rhs; - explode( rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true ); - matcher.reset( - new MultipleAssignMatcher( *this, expr->location, lhs, rhs ) ); - match(); - } - } - } - } - } - - void match() { - assert( matcher ); - - std::vector< ast::ptr< ast::Expr > > newAssigns = matcher->match(); - - if ( !( matcher->lhs.empty() && matcher->rhs.empty() ) ) { - // If both LHS and RHS are empty than this is the empty tuple - // case, wherein it's okay for newAssigns to be empty. Otherwise, - // return early so that no new candidates are generated. - if ( newAssigns.empty() ) return; - } - - ResolvExpr::CandidateList crnt; - // Now resolve new assignments. - for ( const ast::Expr * expr : newAssigns ) { - PRINT( - std::cerr << "== resolving tuple assign ==" << std::endl; - std::cerr << expr << std::endl; - ) - - ResolvExpr::CandidateFinder finder( crntFinder.context, matcher->env ); - finder.allowVoid = true; - - try { - finder.find( expr, ResolvExpr::ResolveMode::withAdjustment() ); - } catch (...) { - // No match is not failure, just that this tuple assignment is invalid. - return; - } - - ResolvExpr::CandidateList & cands = finder.candidates; - assert( 1 == cands.size() ); - assert( cands.front()->expr ); - crnt.emplace_back( std::move( cands.front() ) ); - } - - // extract expressions from the assignment candidates to produce a list of assignments - // that together form a sigle candidate - std::vector< ast::ptr< ast::Expr > > solved; - for ( ResolvExpr::CandidateRef & cand : crnt ) { - solved.emplace_back( cand->expr ); - matcher->combineState( *cand ); - } - - crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >( - new ast::TupleAssignExpr( - matcher->location, std::move( solved ), std::move( matcher->tmpDecls ) ), - std::move( matcher->env ), std::move( matcher->open ), std::move( matcher->need ), - ResolvExpr::sumCost( crnt ) + matcher->baseCost ) ); - } -}; + } + } else { + // Expand all possible RHS possibilities. + std::vector< ResolvExpr::CandidateList > rhsCands; + combos( + std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) ); + for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) { + // Multiple assignment: + ResolvExpr::CandidateList rhs; + explode( rhsCand, crntFinder.context.symtab, back_inserter( rhs ), true ); + MultipleAssignMatcher matcher( *this, expr->location, lhs, rhs ); + match( matcher ); + } + } + } +} + +void TupleAssignSpotter::match( TupleAssignSpotter::Matcher & matcher ) { + std::vector< ast::ptr< ast::Expr > > newAssigns = matcher.match(); + + if ( !( matcher.lhs.empty() && matcher.rhs.empty() ) ) { + // If both LHS and RHS are empty than this is the empty tuple + // case, wherein it's okay for newAssigns to be empty. Otherwise, + // return early so that no new candidates are generated. + if ( newAssigns.empty() ) return; + } + + ResolvExpr::CandidateList crnt; + // Now resolve new assignments. + for ( const ast::Expr * expr : newAssigns ) { + PRINT( + std::cerr << "== resolving tuple assign ==" << std::endl; + std::cerr << expr << std::endl; + ) + + ResolvExpr::CandidateFinder finder( crntFinder.context, matcher.env ); + finder.allowVoid = true; + + try { + finder.find( expr, ResolvExpr::ResolveMode::withAdjustment() ); + } catch (...) { + // No match is not failure, just that this tuple assignment is invalid. + return; + } + + ResolvExpr::CandidateList & cands = finder.candidates; + assert( 1 == cands.size() ); + assert( cands.front()->expr ); + crnt.emplace_back( std::move( cands.front() ) ); + } + + // extract expressions from the assignment candidates to produce a list of assignments + // that together form a sigle candidate + std::vector< ast::ptr< ast::Expr > > solved; + for ( ResolvExpr::CandidateRef & cand : crnt ) { + solved.emplace_back( cand->expr ); + matcher.combineState( *cand ); + } + + crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >( + new ast::TupleAssignExpr( + matcher.location, std::move( solved ), std::move( matcher.tmpDecls ) ), + std::move( matcher.env ), std::move( matcher.open ), std::move( matcher.need ), + ResolvExpr::sumCost( crnt ) + matcher.baseCost ) ); +} } // anonymous namespace