Changes in / [3e2f5e3:3623f9d]
- Files:
-
- 9 edited
-
doc/papers/concurrency/Paper.tex (modified) (37 diffs)
-
src/AST/Type.hpp (modified) (1 diff)
-
src/ResolvExpr/CastCost.cc (modified) (6 diffs)
-
src/ResolvExpr/ConversionCost.h (modified) (1 diff)
-
src/ResolvExpr/PtrsAssignable.cc (modified) (2 diffs)
-
src/ResolvExpr/PtrsCastable.cc (modified) (5 diffs)
-
src/ResolvExpr/ResolveTypeof.cc (modified) (4 diffs)
-
src/ResolvExpr/Resolver.cc (modified) (2 diffs)
-
src/ResolvExpr/typeops.h (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/concurrency/Paper.tex
r3e2f5e3 r3623f9d 280 280 The runtime also ensures multiple monitors can be safely acquired \emph{simultaneously} (deadlock free), and this feature is fully integrated with all monitor synchronization mechanisms. 281 281 All control-flow features integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers. 282 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming 282 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages. 283 283 }% 284 284 … … 301 301 In many ways, \CFA is to C as Scala~\cite{Scala} is to Java, providing a \emph{research vehicle} for new typing and control-flow capabilities on top of a highly popular programming language allowing immediate dissemination. 302 302 Within the \CFA framework, new control-flow features are created from scratch because ISO \Celeven defines only a subset of the \CFA extensions, where the overlapping features are concurrency~\cite[\S~7.26]{C11}. 303 However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}, and \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error -prone;303 However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}, and \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error prone; 304 304 no high-level language concurrency features are defined. 305 305 Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-9 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C11 concurrency approach. … … 312 312 As a result, languages like Java, Scala, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopt the 1:1 kernel-threading model, with a variety of presentation mechanisms. 313 313 From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,Marcel}, including putting green threads back into Java~\cite{Quasar}. 314 The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing medium work 314 The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing medium work-units to facilitate load balancing by the runtime~\cite{Verch12}. 315 315 As well, user-threading facilitates a simpler concurrency approach using thread objects that leverage sequential patterns versus events with call-backs~\cite{Adya02,vonBehren03}. 316 316 Finally, performant user-threading implementations (both time and space) meet or exceed direct kernel-threading implementations, while achieving the programming advantages of high concurrency levels and safety. 317 317 318 A further effort over the past two decades is the development of language memory models to deal with the conflict between language features and compiler/hardware optimizations, \ie, some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}.318 A further effort over the past two decades is the development of language memory-models to deal with the conflict between language features and compiler/hardware optimizations, i.e., some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}. 319 319 The consequence is that a language must provide sufficient tools to program around safety issues, as inline and library code is all sequential to the compiler. 320 One solution is low-level qualifiers and functions ( \eg, @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs.320 One solution is low-level qualifiers and functions (e.g., @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs. 321 321 A safer solution is high-level language constructs so the \emph{compiler} knows the optimization boundaries, and hence, provides implicit safety. 322 This problem is best know nwith respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{322 This problem is best know with respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{ 323 323 \CFA exception handling will be presented in a separate paper. 324 The key feature that dovetails with this paper is non local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}324 The key feature that dovetails with this paper is non-local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++} 325 325 } and coroutines. 326 Finally, language solutions allow matching constructs with language paradigm, \ie, imperative and functional languages often have different presentations of the same concept to fit their programming model.326 Finally, language solutions allow matching constructs with language paradigm, i.e., imperative and functional languages often have different presentations of the same concept to fit their programming model. 327 327 328 328 Finally, it is important for a language to provide safety over performance \emph{as the default}, allowing careful reduction of safety for performance when necessary. 329 Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, \ie, once there is spurious wakeup, signals-as-hints follow.329 Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, i.e., once there is spurious wakeup, signals-as-hints follows. 330 330 However, spurious wakeup is \emph{not} a foundational concurrency property~\cite[\S~8]{Buhr05a}, it is a performance design choice. 331 Similarly, signals-as-hints areoften a performance decision.332 We argue removing spurious wakeup and signals-as-hints make concurrent programming significantly safer because it removes local non-determinism and matches with programmer expectation.331 Similarly, signals-as-hints is often a performance decision. 332 We argue removing spurious wakeup and signals-as-hints makes concurrent programming significantly safer because it removes local non-determinism and matches with programmer expectation. 333 333 (Author experience teaching concurrency is that students are highly confused by these semantics.) 334 334 Clawing back performance, when local non-determinism is unimportant, should be an option not the default. … … 337 337 Most augmented traditional (Fortran 18~\cite{Fortran18}, Cobol 14~\cite{Cobol14}, Ada 12~\cite{Ada12}, Java 11~\cite{Java11}) and new languages (Go~\cite{Go}, Rust~\cite{Rust}, and D~\cite{D}), except \CC, diverge from C with different syntax and semantics, only interoperate indirectly with C, and are not systems languages, for those with managed memory. 338 338 As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten. 339 While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set ( \eg, objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.339 While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (e.g., objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC. 340 340 Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base. 341 341 \CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems. … … 343 343 344 344 \CFA embraces user-level threading, language extensions for advanced control-flow, and safety as the default. 345 We present comparative examples so the reader can judge if the \CFA control-flow extensions are better and safer than those in other concurrent, imperative programming 345 We present comparative examples so the reader can judge if the \CFA control-flow extensions are better and safer than those in other concurrent, imperative programming-languages, and perform experiments to show the \CFA runtime is competitive with other similar mechanisms. 346 346 The main contributions of this work are: 347 347 \begin{itemize} … … 349 349 language-level generators, coroutines and user-level threading, which respect the expectations of C programmers. 350 350 \item 351 monitor synchronization without barging, and the ability to safely acquiring multiple monitors \emph{simultaneously} (deadlock free), while seamlessly integrating these capabilit ieswith all monitor synchronization mechanisms.351 monitor synchronization without barging, and the ability to safely acquiring multiple monitors \emph{simultaneously} (deadlock free), while seamlessly integrating these capability with all monitor synchronization mechanisms. 352 352 \item 353 353 providing statically type-safe interfaces that integrate with the \CFA polymorphic type-system and other language features. … … 367 367 \section{Stateful Function} 368 368 369 The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, \eg, plugin, device driver, finite-state machine.369 The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, e.g., plugin, device driver, finite-state machine. 370 370 Hence, a stateful function may not end when it returns to its caller, allowing it to be restarted with the data and execution location present at the point of suspension. 371 371 This capability is accomplished by retaining a data/execution \emph{closure} between invocations. 372 If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, \eg, suspending outside the generator is prohibited.373 If the closure is variabl ysized, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions.372 If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, e.g., suspending outside the generator is prohibited. 373 If the closure is variable sized, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions. 374 374 Hence, refactoring a stackless coroutine may require changing it to stackful. 375 A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, \ie, resume/suspend operations are remembered through the closure not the stack.375 A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, i.e., resume/suspend operations are remembered through the closure not the stack. 376 376 As well, activating a stateful function is \emph{asymmetric} or \emph{symmetric}, identified by resume/suspend (no cycles) and resume/resume (cycles). 377 377 A fixed closure activated by modified call/return is faster than a variable closure activated by context switching. 378 Additionally, any storage management for the closure (especially in unmanaged languages, \ie, no garbage collection) must also be factored into design and performance.378 Additionally, any storage management for the closure (especially in unmanaged languages, i.e., no garbage collection) must also be factored into design and performance. 379 379 Therefore, selecting between stackless and stackful semantics is a tradeoff between programming requirements and performance, where stackless is faster and stackful is more general. 380 380 Note, creation cost is amortized across usage, so activation cost is usually the dominant factor. … … 603 603 the top initialization state appears at the start and the middle execution state is denoted by statement @suspend@. 604 604 Any local variables in @main@ \emph{are not retained} between calls; 605 hence local variable sare only for temporary computations \emph{between} suspends.605 hence local variable are only for temporary computations \emph{between} suspends. 606 606 All retained state \emph{must} appear in the generator's type. 607 607 As well, generator code containing a @suspend@ cannot be refactored into a helper function called by the generator, because @suspend@ is implemented via @return@, so a return from the helper function goes back to the current generator not the resumer. … … 618 618 sout | (int)f1() | (double)f1() | f2( 2 ); // alternative interface, cast selects call based on return type, step 2 values 619 619 \end{cfa} 620 Now, the generator can be a separately 620 Now, the generator can be a separately-compiled opaque-type only accessed through its interface functions. 621 621 For contrast, Figure~\ref{f:PythonFibonacci} shows the equivalent Python Fibonacci generator, which does not use a generator type, and hence only has a single interface, but an implicit closure. 622 622 … … 624 624 (This restriction is removed by the coroutine in Section~\ref{s:Coroutine}.) 625 625 This requirement follows from the generality of variable-size local-state, \eg local state with a variable-length array requires dynamic allocation because the array size is unknown at compile time. 626 However, dynamic allocation significantly increases the cost of generator creation/destruction and is a show stopper for embedded real-time programming.626 However, dynamic allocation significantly increases the cost of generator creation/destruction and is a show-stopper for embedded real-time programming. 627 627 But more importantly, the size of the generator type is tied to the local state in the generator main, which precludes separate compilation of the generator main, \ie a generator must be inlined or local state must be dynamically allocated. 628 628 With respect to safety, we believe static analysis can discriminate local state from temporary variables in a generator, \ie variable usage spanning @suspend@, and generate a compile-time error. … … 648 648 \end{center} 649 649 The example takes advantage of resuming a generator in the constructor to prime the loops so the first character sent for formatting appears inside the nested loops. 650 The destructor provides a newline if formatted text ends with a full line.650 The destructor provides a newline, if formatted text ends with a full line. 651 651 Figure~\ref{f:CFormatSim} shows the C implementation of the \CFA input generator with one additional field and the computed @goto@. 652 652 For contrast, Figure~\ref{f:PythonFormatter} shows the equivalent Python format generator with the same properties as the Fibonacci generator. … … 669 669 In contrast, the execution state is large, with one @resume@ and seven @suspend@s. 670 670 Hence, the key benefits of the generator are correctness, safety, and maintenance because the execution states are transcribed directly into the programming language rather than using a table-driven approach. 671 Because FSMs can be complex and frequently occur in important domains, direct support of the generator is crucial in a system programminglanguage.671 Because FSMs can be complex and occur frequently in important domains, direct support of the generator is crucial in a systems programming-language. 672 672 673 673 \begin{figure} … … 782 782 The steps for symmetric control-flow are creating, executing, and terminating the cycle. 783 783 Constructing the cycle must deal with definition-before-use to close the cycle, \ie, the first generator must know about the last generator, which is not within scope. 784 (This issue occurs for any cyclic datastructure.)784 (This issues occurs for any cyclic data-structure.) 785 785 % The example creates all the generators and then assigns the partners that form the cycle. 786 786 % Alternatively, the constructor can assign the partners as they are declared, except the first, and the first-generator partner is set after the last generator declaration to close the cycle. … … 792 792 793 793 Figure~\ref{f:CPingPongSim} shows the implementation of the symmetric generator, where the complexity is the @resume@, which needs an extension to the calling convention to perform a forward rather than backward jump. 794 This jump -starts at the top of the next generator main to re-execute the normal calling convention to make space on the stack for its local variables.794 This jump starts at the top of the next generator main to re-execute the normal calling convention to make space on the stack for its local variables. 795 795 However, before the jump, the caller must reset its stack (and any registers) equivalent to a @return@, but subsequently jump forward. 796 796 This semantics is basically a tail-call optimization, which compilers already perform. … … 862 862 863 863 Finally, part of this generator work was inspired by the recent \CCtwenty generator proposal~\cite{C++20Coroutine19} (which they call coroutines). 864 Our work provides the same high-performance asymmetric 865 An additional \CCtwenty generator feature allows @suspend@ and @resume@ to be followed by a restricted compound 864 Our work provides the same high-performance asymmetric-generators as \CCtwenty, and extends their work with symmetric generators. 865 An additional \CCtwenty generator feature allows @suspend@ and @resume@ to be followed by a restricted compound-statement that is executed after the current generator has reset its stack but before calling the next generator, specified with \CFA syntax: 866 866 \begin{cfa} 867 867 ... suspend`{ ... }`; … … 879 879 A coroutine is specified by replacing @generator@ with @coroutine@ for the type. 880 880 Coroutine generality results in higher cost for creation, due to dynamic stack allocation, execution, due to context switching among stacks, and terminating, due to possible stack unwinding and dynamic stack deallocation. 881 A series of different kinds of coroutines and their implementation sdemonstrate how coroutines extend generators.881 A series of different kinds of coroutines and their implementation demonstrate how coroutines extend generators. 882 882 883 883 First, the previous generator examples are converted to their coroutine counterparts, allowing local-state variables to be moved from the generator type into the coroutine main. … … 1164 1164 \end{cfa} 1165 1165 \end{tabular} 1166 \caption{Producer / consumer: resume-resume cycle, bi directional communication}1166 \caption{Producer / consumer: resume-resume cycle, bi-directional communication} 1167 1167 \label{f:ProdCons} 1168 1168 \end{figure} … … 1208 1208 Furthermore, each deallocated coroutine must guarantee all destructors are run for object allocated in the coroutine type \emph{and} allocated on the coroutine's stack at the point of suspension, which can be arbitrarily deep. 1209 1209 When a coroutine's main ends, its stack is already unwound so any stack allocated objects with destructors have been finalized. 1210 The na\"{i}ve semantics for coroutine-cycle termination is tocontext switch to the last resumer, like executing a @suspend@/@return@ in a generator.1210 The na\"{i}ve semantics for coroutine-cycle termination is context switch to the last resumer, like executing a @suspend@/@return@ in a generator. 1211 1211 However, for coroutines, the last resumer is \emph{not} implicitly below the current stack frame, as for generators, because each coroutine's stack is independent. 1212 1212 Unfortunately, it is impossible to determine statically if a coroutine is in a cycle and unrealistic to check dynamically (graph-cycle problem). … … 1214 1214 1215 1215 Our solution is to context switch back to the first resumer (starter) once the coroutine ends. 1216 This semantics works well for the most common asymmetric and symmetric coroutine usage 1216 This semantics works well for the most common asymmetric and symmetric coroutine usage-patterns. 1217 1217 For asymmetric coroutines, it is common for the first resumer (starter) coroutine to be the only resumer. 1218 1218 All previous generators converted to coroutines have this property. 1219 For symmetric coroutines, it is common for the cycle creator to persist for the life time of the cycle.1219 For symmetric coroutines, it is common for the cycle creator to persist for the life-time of the cycle. 1220 1220 Hence, the starter coroutine is remembered on the first resume and ending the coroutine resumes the starter. 1221 1221 Figure~\ref{f:ProdConsRuntimeStacks} shows this semantic by the dashed lines from the end of the coroutine mains: @prod@ starts @cons@ so @cons@ resumes @prod@ at the end, and the program main starts @prod@ so @prod@ resumes the program main at the end. … … 1285 1285 \end{cfa} 1286 1286 Note, copying generators/coroutines/threads is not meaningful. 1287 For example, both the resumer and suspender descriptors can have bi directional pointers;1287 For example, both the resumer and suspender descriptors can have bi-directional pointers; 1288 1288 copying these coroutines does not update the internal pointers so behaviour of both copies would be difficult to understand. 1289 1289 Furthermore, two coroutines cannot logically execute on the same stack. 1290 1290 A deep coroutine copy, which copies the stack, is also meaningless in an unmanaged language (no garbage collection), like C, because the stack may contain pointers to object within it that require updating for the copy. 1291 1291 The \CFA @dtype@ property provides no \emph{implicit} copying operations and the @is_coroutine@ trait provides no \emph{explicit} copying operations, so all coroutines must be passed by reference (pointer). 1292 The function definitions ensure there is a staticallytyped @main@ function that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the coroutine descriptor from its handle.1292 The function definitions ensures there is a statically-typed @main@ function that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the coroutine descriptor from its handle. 1293 1293 The @main@ function has no return value or additional parameters because the coroutine type allows an arbitrary number of interface functions with corresponding arbitrary typed input/output values versus fixed ones. 1294 1294 The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ function, and possibly redefining \textsf{suspend} and @resume@. … … 1342 1342 For a VLS stack allocation/deallocation is an inexpensive adjustment of the stack pointer, modulo any stack constructor costs (\eg initial frame setup). 1343 1343 For heap stack allocation, allocation/deallocation is an expensive heap allocation (where the heap can be a shared resource), modulo any stack constructor costs. 1344 With heap stack allocation, it is also possible to use a split (segmented) stack calling 1344 With heap stack allocation, it is also possible to use a split (segmented) stack calling-convention, available with gcc and clang, so the stack is variable sized. 1345 1345 Currently, \CFA supports stack/heap allocated descriptors but only fixed-sized heap allocated stacks. 1346 1346 In \CFA debug-mode, the fixed-sized stack is terminated with a write-only page, which catches most stack overflows. … … 1359 1359 \label{s:Concurrency} 1360 1360 1361 Concurrency is nondeterministic scheduling of independent sequential execution 1361 Concurrency is nondeterministic scheduling of independent sequential execution-paths (threads), where each thread has its own stack. 1362 1362 A single thread with multiple call stacks, \newterm{coroutining}~\cite{Conway63,Marlin80}, does \emph{not} imply concurrency~\cite[\S~2]{Buhr05a}. 1363 1363 In coroutining, coroutines self-schedule the thread across stacks so execution is deterministic. … … 1367 1367 The transition to concurrency, even for a single thread with multiple stacks, occurs when coroutines context switch to a \newterm{scheduling coroutine}, introducing non-determinism from the coroutine perspective~\cite[\S~3,]{Buhr05a}. 1368 1368 Therefore, a minimal concurrency system requires coroutines \emph{in conjunction with a nondeterministic scheduler}. 1369 The resulting execution system now follows a cooperative threading 1369 The resulting execution system now follows a cooperative threading-model~\cite{Adya02,libdill}, called \newterm{non-preemptive scheduling}. 1370 1370 Adding \newterm{preemption} introduces non-cooperative scheduling, where context switching occurs randomly between any two instructions often based on a timer interrupt, called \newterm{preemptive scheduling}. 1371 1371 While a scheduler introduces uncertain execution among explicit context switches, preemption introduces uncertainty by introducing implicit context switches. … … 1497 1497 \end{cquote} 1498 1498 Like coroutines, the @dtype@ property prevents \emph{implicit} copy operations and the @is_thread@ trait provides no \emph{explicit} copy operations, so threads must be passed by reference (pointer). 1499 Similarly, the function definitions ensure there is a staticallytyped @main@ function that is the thread starting point (first stack frame), a mechanism to get (read) the thread descriptor from its handle, and a special destructor to prevent deallocation while the thread is executing.1499 Similarly, the function definitions ensures there is a statically-typed @main@ function that is the thread starting point (first stack frame), a mechanism to get (read) the thread descriptor from its handle, and a special destructor to prevent deallocation while the thread is executing. 1500 1500 (The qualifier @mutex@ for the destructor parameter is discussed in Section~\ref{s:Monitor}.) 1501 1501 The difference between the coroutine and thread is that a coroutine borrows a thread from its caller, so the first thread resuming a coroutine creates the coroutine's stack and starts running the coroutine main on the stack; … … 1512 1512 Hence, a programmer must learn and manipulate two sets of design/programming patterns. 1513 1513 While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account. 1514 In contrast, approaches based on stateful models more closely resemble the standard call/return programming 1514 In contrast, approaches based on stateful models more closely resemble the standard call/return programming-model, resulting in a single programming paradigm. 1515 1515 1516 1516 At the lowest level, concurrent control is implemented by atomic operations, upon which different kinds of locking mechanisms are constructed, \eg semaphores~\cite{Dijkstra68b}, barriers, and path expressions~\cite{Campbell74}. … … 1520 1520 1521 1521 One of the most natural, elegant, and efficient mechanisms for mutual exclusion and synchronization for shared-memory systems is the \emph{monitor}. 1522 First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}, many concurrent programming 1522 First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}, many concurrent programming-languages provide monitors as an explicit language construct: \eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}. 1523 1523 In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as mutex locks or semaphores to simulate monitors. 1524 For these reasons, \CFA selected monitors as the core high-level concurrency 1524 For these reasons, \CFA selected monitors as the core high-level concurrency-construct, upon which higher-level approaches can be easily constructed. 1525 1525 1526 1526 … … 1571 1571 % (While a constructor may publish its address into a global variable, doing so generates a race-condition.) 1572 1572 The prefix increment operation, @++?@, is normally @mutex@, indicating mutual exclusion is necessary during function execution, to protect the incrementing from race conditions, unless there is an atomic increment instruction for the implementation type. 1573 The assignment operators provide bi directional conversion between an atomic and normal integer without accessing field @cnt@;1573 The assignment operators provide bi-directional conversion between an atomic and normal integer without accessing field @cnt@; 1574 1574 these operations only need @mutex@, if reading/writing the implementation type is not atomic. 1575 1575 The atomic counter is used without any explicit mutual-exclusion and provides thread-safe semantics, which is similar to the \CC template @std::atomic@. … … 1593 1593 Similar safety is offered by \emph{explicit} mechanisms like \CC RAII; 1594 1594 monitor \emph{implicit} safety ensures no programmer usage errors. 1595 Furthermore, RAII mechan isms cannot handle complex synchronization within a monitor, where the monitor lock may not be released on function exit because it is passed to an unblocking thread;1595 Furthermore, RAII mechansims cannot handle complex synchronization within a monitor, where the monitor lock may not be released on function exit because it is passed to an unblocking thread; 1596 1596 RAII is purely a mutual-exclusion mechanism (see Section~\ref{s:Scheduling}). 1597 1597 … … 1632 1632 1633 1633 The benefit of mandatory monitor qualifiers is self-documentation, but requiring both @mutex@ and \lstinline[morekeywords=nomutex]@nomutex@ for all monitor parameters is redundant. 1634 Instead, the semantics ha sone qualifier as the default and the other required.1634 Instead, the semantics have one qualifier as the default and the other required. 1635 1635 For example, make the safe @mutex@ qualifier the default because assuming \lstinline[morekeywords=nomutex]@nomutex@ may cause subtle errors. 1636 1636 Alternatively, make the unsafe \lstinline[morekeywords=nomutex]@nomutex@ qualifier the default because it is the \emph{normal} parameter semantics while @mutex@ parameters are rare. … … 1809 1809 Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion, so either the signaller or signallee can proceed. 1810 1810 For internal scheduling, threads are unblocked from condition queues using @signal@, where the signallee is moved to urgent and the signaller continues (solid line). 1811 Multiple signals move multiple signallees to urgent until the condition is empty.1811 Multiple signals move multiple signallees to urgent, until the condition is empty. 1812 1812 When the signaller exits or waits, a thread blocked on urgent is processed before calling threads to prevent barging. 1813 1813 (Java conceptually moves the signalled thread to the calling queue, and hence, allows barging.) … … 1819 1819 The @waitfor@ has the same semantics as @signal_block@, where the signalled thread executes before the signallee, which waits on urgent. 1820 1820 Executing multiple @waitfor@s from different signalled functions causes the calling threads to move to urgent. 1821 External scheduling requires urgent to be a stack, because the signaller ex pects to execute immediately after the specified monitor call has exited or waited.1821 External scheduling requires urgent to be a stack, because the signaller excepts to execute immediately after the specified monitor call has exited or waited. 1822 1822 Internal scheduling behaves the same for an urgent stack or queue, except for multiple signalling, where the threads unblock from urgent in reverse order from signalling. 1823 1823 If the restart order is important, multiple signalling by a signal thread can be transformed into daisy-chain signalling among threads, where each thread signals the next thread. … … 2143 2143 \end{figure} 2144 2144 2145 Note, a group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, \eg:2145 Note, a group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, e.g.: 2146 2146 \begin{cfa} 2147 2147 if ( C1 ) waitfor( mem1 ); when ( C1 ) waitfor( mem1 ); … … 2256 2256 \label{s:LooseObjectDefinitions} 2257 2257 2258 In an object-oriented programming 2258 In an object-oriented programming-language, a class includes an exhaustive list of operations. 2259 2259 A new class can add members via static inheritance but the subclass still has an exhaustive list of operations. 2260 2260 (Dynamic member adding, \eg JavaScript~\cite{JavaScript}, is not considered.) … … 2671 2671 \subsection{Preemption} 2672 2672 2673 Nondeterministic preemption provides fairness from long -running threads, and forces concurrent programmers to write more robust programs, rather than relying on code between cooperative scheduling to be atomic.2673 Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on code between cooperative scheduling to be atomic. 2674 2674 This atomic reliance can fail on multi-core machines, because execution across cores is nondeterministic. 2675 2675 A different reason for not supporting preemption is that it significantly complicates the runtime system, \eg Microsoft runtime does not support interrupts and on Linux systems, interrupts are complex (see below). 2676 Preemption is normally handled by setting a count down timer on each virtual processor.2677 When the timer expires, an interrupt is delivered, and the interrupt handler resets the count down timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtimekernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code.2676 Preemption is normally handled by setting a count-down timer on each virtual processor. 2677 When the timer expires, an interrupt is delivered, and the interrupt handler resets the count-down timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtime-kernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code. 2678 2678 Multiple signal handlers may be pending. 2679 2679 When control eventually switches back to the signal handler, it returns normally, and execution continues in the interrupted user thread, even though the return from the signal handler may be on a different kernel thread than the one where the signal is delivered. … … 2685 2685 \begin{cquote} 2686 2686 A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked. 2687 If more than one of the threads has the signal unblocked, then the kernel chooses an arbitrary thread to which it willdeliver the signal.2687 If more than one of the threads has the signal unblocked, then the kernel chooses an arbitrary thread to which to deliver the signal. 2688 2688 SIGNAL(7) - Linux Programmer's Manual 2689 2689 \end{cquote} … … 2691 2691 To ensure each virtual processor receives a preemption signal, a discrete-event simulation is run on a special virtual processor, and only it sets and receives timer events. 2692 2692 Virtual processors register an expiration time with the discrete-event simulator, which is inserted in sorted order. 2693 The simulation sets the count down timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed.2693 The simulation sets the count-down timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed. 2694 2694 Processing a preemption event sends an \emph{internal} @SIGUSR1@ signal to the registered virtual processor, which is always delivered to that processor. 2695 2695 … … 2913 2913 \paragraph{Mutual-Exclusion} 2914 2914 2915 Uncontented mutual exclusion, which frequently occurs, is measured by entering/leaving a critical section.2915 Uncontented mutual exclusion, which occurs frequently, is measured by entering/leaving a critical section. 2916 2916 For monitors, entering and leaving a monitor function is measured. 2917 2917 To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured. -
src/AST/Type.hpp
r3e2f5e3 r3623f9d 164 164 static const char *typeNames[]; 165 165 166 BasicType( Kind k, CV::Qualifiers q = {}, std::vector<ptr<Attribute>> && as = {} ) 167 : Type(q, std::move(as)), kind(k) {} 166 BasicType( Kind k, CV::Qualifiers q = {} ) : Type(q), kind(k) {} 168 167 169 168 /// Check if this type represents an integer type -
src/ResolvExpr/CastCost.cc
r3e2f5e3 r3623f9d 16 16 #include <cassert> // for assert 17 17 18 #include "AST/Print.hpp"19 #include "AST/SymbolTable.hpp"20 #include "AST/Type.hpp"21 #include "AST/TypeEnvironment.hpp"22 18 #include "ConversionCost.h" // for ConversionCost 23 19 #include "Cost.h" // for Cost, Cost::infinity … … 35 31 36 32 namespace ResolvExpr { 37 struct CastCost _old: public ConversionCost {33 struct CastCost : public ConversionCost { 38 34 public: 39 CastCost _old( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc );35 CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc ); 40 36 41 37 using ConversionCost::previsit; … … 82 78 }); 83 79 } else { 84 PassVisitor<CastCost_old> converter( 80 #warning cast on castCost artifact of having two functions, remove when port done 81 PassVisitor<CastCost> converter( 85 82 dest, indexer, env, 86 83 (Cost (*)( Type *, Type *, const SymTab::Indexer &, const TypeEnvironment & )) … … 96 93 } 97 94 98 CastCost _old::CastCost_old( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )95 CastCost::CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc ) 99 96 : ConversionCost( dest, indexer, env, costFunc ) { 100 97 } 101 98 102 void CastCost _old::postvisit( BasicType *basicType ) {99 void CastCost::postvisit( BasicType *basicType ) { 103 100 PointerType *destAsPointer = dynamic_cast< PointerType* >( dest ); 104 101 if ( destAsPointer && basicType->isInteger() ) { … … 110 107 } 111 108 112 void CastCost _old::postvisit( PointerType *pointerType ) {109 void CastCost::postvisit( PointerType *pointerType ) { 113 110 if ( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) { 114 111 if ( pointerType->get_qualifiers() <= destAsPtr->get_qualifiers() && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) { … … 133 130 } 134 131 135 namespace { 136 struct CastCost_new : public ConversionCost_new { 137 using ConversionCost_new::previsit; 138 using ConversionCost_new::postvisit; 139 140 CastCost_new( 141 const ast::Type * dst, const ast::SymbolTable & symtab, 142 const ast::TypeEnvironment & env, CostCalculation costFunc ) 143 : ConversionCost_new( dst, symtab, env, costFunc ) {} 144 145 void postvisit( const ast::BasicType * basicType ) { 146 auto ptr = dynamic_cast< const ast::PointerType * >( dst ); 147 if ( ptr && basicType->isInteger() ) { 148 // needed for, e.g. unsigned long => void * 149 cost = Cost::unsafe; 150 } else { 151 cost = conversionCost( basicType, dst, symtab, env ); 152 } 153 } 154 155 void postvisit( const ast::PointerType * pointerType ) { 156 if ( auto ptr = dynamic_cast< const ast::PointerType * >( dst ) ) { 157 if ( 158 pointerType->qualifiers <= ptr->qualifiers 159 && typesCompatibleIgnoreQualifiers( pointerType->base, ptr->base, symtab, env ) 160 ) { 161 cost = Cost::safe; 162 } else { 163 ast::TypeEnvironment newEnv{ env }; 164 if ( auto wParams = pointerType->base.as< ast::ParameterizedType >() ) { 165 newEnv.add( wParams->forall ); 166 } 167 int castResult = ptrsCastable( pointerType->base, ptr->base, symtab, newEnv ); 168 if ( castResult > 0 ) { 169 cost = Cost::safe; 170 } else if ( castResult < 0 ) { 171 cost = Cost::infinity; 172 } 173 } 174 } else if ( auto basic = dynamic_cast< const ast::BasicType * >( dst ) ) { 175 if ( basic->isInteger() ) { 176 // necessary for, e.g. void * => unsigned long 177 cost = Cost::unsafe; 178 } 179 } 180 } 181 }; 182 } // anonymous namespace 183 184 Cost castCost( 185 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab, 186 const ast::TypeEnvironment & env 187 ) { 188 if ( auto typeInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) { 189 if ( const ast::EqvClass * eqvClass = env.lookup( typeInst->name ) ) { 190 // check cast cost against bound type, if present 191 if ( eqvClass->bound ) { 192 return castCost( src, eqvClass->bound, symtab, env ); 193 } else { 194 return Cost::infinity; 195 } 196 } else if ( const ast::NamedTypeDecl * named = symtab.lookupType( typeInst->name ) ) { 197 // all typedefs should be gone by now 198 auto type = strict_dynamic_cast< const ast::TypeDecl * >( named ); 199 if ( type->base ) { 200 return castCost( src, type->base, symtab, env ) + Cost::safe; 201 } 202 } 132 Cost castCost( 133 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab, 134 const ast::TypeEnvironment & env 135 ) { 136 #warning unimplmented 137 (void)src; (void)dst; (void)symtab; (void)env; 138 assert(false); 139 return Cost::zero; 203 140 } 204 205 PRINT(206 std::cerr << "castCost ::: src is ";207 ast::print( std::cerr, src );208 std::cerr << std::endl << "dest is ";209 ast::print( std::cerr, dst );210 std::cerr << std::endl << "env is" << std::endl;211 ast::print( std::cerr, env, 2 );212 )213 214 if ( typesCompatibleIgnoreQualifiers( src, dst, symtab, env ) ) {215 PRINT( std::cerr << "compatible!" << std::endl; )216 return Cost::zero;217 } else if ( dynamic_cast< const ast::VoidType * >( dst ) ) {218 return Cost::safe;219 } else if ( auto refType = dynamic_cast< const ast::ReferenceType * >( dst ) ) {220 PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; )221 #warning cast on ptrsCastable artifact of having two functions, remove when port done222 return convertToReferenceCost(223 src, refType, symtab, env,224 ( int (*)(225 const ast::Type *, const ast::Type *, const ast::SymbolTable &,226 const ast::TypeEnvironment & )227 ) ptrsCastable );228 } else {229 #warning cast on castCost artifact of having two functions, remove when port done230 ast::Pass< CastCost_new > converter{231 dst, symtab, env,232 ( Cost (*)(233 const ast::Type *, const ast::Type *, const ast::SymbolTable &,234 const ast::TypeEnvironment & )235 ) castCost };236 src->accept( converter );237 return converter.pass.cost;238 }239 }240 241 141 } // namespace ResolvExpr 242 142 -
src/ResolvExpr/ConversionCost.h
r3e2f5e3 r3623f9d 74 74 const ast::SymbolTable &, const ast::TypeEnvironment &)>; 75 75 76 #warning when the old ConversionCost is removed, get ride of the _new suffix.76 // TODO: When the old ConversionCost is removed, get ride of the _new suffix. 77 77 class ConversionCost_new : public ast::WithShortCircuiting { 78 protected:79 78 const ast::Type * dst; 80 79 const ast::SymbolTable & symtab; -
src/ResolvExpr/PtrsAssignable.cc
r3e2f5e3 r3623f9d 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 11:44:11 2015 11 // Last Modified By : Andrew12 // Last Modified On : Mon Jun 24 15:29:00 201913 // Update Count : 911 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Wed Mar 2 17:36:05 2016 13 // Update Count : 8 14 14 // 15 15 16 #include "typeops.h" 17 18 #include "AST/Pass.hpp" 19 #include "AST/Type.hpp" 20 #include "AST/TypeEnvironment.hpp" 16 #include "AST/Fwd.hpp" 21 17 #include "Common/PassVisitor.h" 22 18 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment … … 112 108 void PtrsAssignable::postvisit( __attribute__((unused)) OneType *oneType ) {} 113 109 114 // TODO: Get rid of the `_new` suffix when the old version is removed.115 struct PtrsAssignable_new : public ast::WithShortCircuiting {116 const ast::Type * dst;117 const ast::TypeEnvironment & typeEnv;118 int result;119 120 PtrsAssignable_new( const ast::Type * dst, const ast::TypeEnvironment & env ) :121 dst( dst ), typeEnv( env ), result( 0 ) {}122 123 void previsit( Type * ) { visit_children = false; }124 125 void postvisit( const ast::EnumInstType * ) {126 if ( dynamic_cast< const ast::BasicType * >( dst ) ) {127 // int * = E *, etc. is safe. This isn't technically correct, as each128 // enum has one basic type that it is compatible with, an that type can129 // differ from enum to enum. Without replicating GCC's internal logic,130 // there is no way to know which type this particular enum is compatible131 // with, so punt on this for now.132 result = 1;133 }134 }135 void postvisit( const ast::TypeInstType * inst ) {136 if ( const ast::EqvClass * eqv = typeEnv.lookup( inst->name ) ) {137 if ( eqv->bound ) {138 // T * = S * for any S depends on the type bound to T139 result = ptrsAssignable( eqv->bound, dst, typeEnv );140 }141 }142 }143 };144 145 110 int ptrsAssignable( const ast::Type * src, const ast::Type * dst, 146 111 const ast::TypeEnvironment & env ) { 147 if ( const ast::TypeInstType * dstAsInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) { 148 if ( const ast::EqvClass * eqv = env.lookup( dstAsInst->name ) ) { 149 return ptrsAssignable( src, eqv->bound, env ); 150 } 151 } 152 if ( dynamic_cast< const ast::VoidType * >( dst ) ) { 153 return -1; 154 } else { 155 ast::Pass<PtrsAssignable_new> visitor( dst, env ); 156 src->accept( visitor ); 157 return visitor.pass.result; 158 } 159 160 // see ticket #136 (this should be able to replace the visitor). 161 #if 0 162 if ( const ast::TypeInstType * dstAsTypeInst = 163 dynamic_cast< const ast::TypeInstType* >( dst ) ) { 164 if ( const ast::EqvClass * eqv = env.lookup( dstAsTypeInst->get_name() ) ) { 165 return ptrsAssignable( src, eqv->type, env ); 166 } // if 167 } // if 168 if ( dynamic_cast< VoidType* >( dst ) ) { 169 // void * = T * for any T is unsafe 170 // xxx - this should be safe, but that currently breaks the build 171 return -1; 172 } else if ( dynamic_cast< EnumInstType * >( src ) ) { 173 if ( dynamic_cast< BasicType * >( dst ) ) { 174 // int * = E *, etc. is safe. This isn't technically correct, as each 175 // enum has one basic type that it is compatible with, an that type can 176 // differ from enum to enum. Without replicating GCC's internal logic, 177 // there is no way to know which type this particular enum is compatible 178 // with, so punt on this for now. 179 return 1; 180 } 181 } else if ( const ast::TypeInstType * typeInstType = 182 dynamic_cast< const ast::TypeInstType * >( src ) ) { 183 if ( const ast::EqvClass * eqv = env.lookup( typeInstType->name ) ) { 184 if ( eqv->bound ) { 185 // T * = S * for any S depends on the type bound to T 186 return ptrsAssignable( eqv->bound, dst, env ); 187 } 188 } 189 } 112 #warning unimplemented 113 (void)src; 114 (void)dst; 115 (void)env; 116 assert(0); 190 117 return 0; 191 #endif192 118 } 193 119 -
src/ResolvExpr/PtrsCastable.cc
r3e2f5e3 r3623f9d 14 14 // 15 15 16 #include "AST/Decl.hpp"17 #include "AST/Pass.hpp"18 #include "AST/Type.hpp"19 #include "AST/TypeEnvironment.hpp"20 16 #include "Common/PassVisitor.h" 21 17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment … … 27 23 28 24 namespace ResolvExpr { 29 struct PtrsCastable _old: public WithShortCircuiting {25 struct PtrsCastable : public WithShortCircuiting { 30 26 public: 31 PtrsCastable _old( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer );27 PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ); 32 28 33 29 int get_result() const { return result; } … … 90 86 return objectCast( src, env, indexer ); 91 87 } else { 92 PassVisitor<PtrsCastable _old> ptrs( dest, env, indexer );88 PassVisitor<PtrsCastable> ptrs( dest, env, indexer ); 93 89 src->accept( ptrs ); 94 90 return ptrs.pass.get_result(); … … 96 92 } 97 93 98 PtrsCastable _old::PtrsCastable_old( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer )94 PtrsCastable::PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) 99 95 : dest( dest ), result( 0 ), env( env ), indexer( indexer ) { 100 96 } 101 97 102 void PtrsCastable _old::postvisit( VoidType * ) {98 void PtrsCastable::postvisit( VoidType * ) { 103 99 result = objectCast( dest, env, indexer ); 104 100 } 105 101 106 void PtrsCastable _old::postvisit( BasicType * ) {102 void PtrsCastable::postvisit( BasicType * ) { 107 103 result = objectCast( dest, env, indexer ); 108 104 } 109 105 110 void PtrsCastable _old::postvisit( PointerType * ) {106 void PtrsCastable::postvisit( PointerType * ) { 111 107 result = objectCast( dest, env, indexer ); 112 108 } 113 109 114 void PtrsCastable _old::postvisit( ArrayType * ) {110 void PtrsCastable::postvisit( ArrayType * ) { 115 111 result = objectCast( dest, env, indexer ); 116 112 } 117 113 118 void PtrsCastable _old::postvisit( FunctionType * ) {114 void PtrsCastable::postvisit( FunctionType * ) { 119 115 // result = -1; 120 116 result = functionCast( dest, env, indexer ); 121 117 } 122 118 123 void PtrsCastable _old::postvisit( StructInstType * ) {119 void PtrsCastable::postvisit( StructInstType * ) { 124 120 result = objectCast( dest, env, indexer ); 125 121 } 126 122 127 void PtrsCastable _old::postvisit( UnionInstType * ) {123 void PtrsCastable::postvisit( UnionInstType * ) { 128 124 result = objectCast( dest, env, indexer ); 129 125 } 130 126 131 void PtrsCastable _old::postvisit( EnumInstType * ) {127 void PtrsCastable::postvisit( EnumInstType * ) { 132 128 if ( dynamic_cast< EnumInstType* >( dest ) ) { 133 129 result = 1; … … 143 139 } 144 140 145 void PtrsCastable _old::postvisit( TraitInstType * ) {}141 void PtrsCastable::postvisit( TraitInstType * ) {} 146 142 147 void PtrsCastable _old::postvisit(TypeInstType *inst) {143 void PtrsCastable::postvisit(TypeInstType *inst) { 148 144 //result = objectCast( inst, env, indexer ) > 0 && objectCast( dest, env, indexer ) > 0 ? 1 : -1; 149 145 result = objectCast( inst, env, indexer ) == objectCast( dest, env, indexer ) ? 1 : -1; 150 146 } 151 147 152 void PtrsCastable _old::postvisit( TupleType * ) {148 void PtrsCastable::postvisit( TupleType * ) { 153 149 result = objectCast( dest, env, indexer ); 154 150 } 155 151 156 void PtrsCastable _old::postvisit( VarArgsType * ) {152 void PtrsCastable::postvisit( VarArgsType * ) { 157 153 result = objectCast( dest, env, indexer ); 158 154 } 159 155 160 void PtrsCastable _old::postvisit( ZeroType * ) {156 void PtrsCastable::postvisit( ZeroType * ) { 161 157 result = objectCast( dest, env, indexer ); 162 158 } 163 159 164 void PtrsCastable _old::postvisit( OneType * ) {160 void PtrsCastable::postvisit( OneType * ) { 165 161 result = objectCast( dest, env, indexer ); 166 162 } 167 168 namespace {169 // can this type be cast to an object (1 for yes, -1 for no)170 int objectCast(171 const ast::Type * src, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab172 ) {173 if ( dynamic_cast< const ast::FunctionType * >( src ) ) {174 return -1;175 } else if ( auto inst = dynamic_cast< const ast::TypeInstType * >( src ) ) {176 if ( const ast::NamedTypeDecl * named = symtab.lookupType( inst->name ) ) {177 if ( auto tyDecl = dynamic_cast< const ast::TypeDecl * >( named ) ) {178 if ( tyDecl->kind == ast::TypeVar::Ftype ) {179 return -1;180 }181 }182 } else if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {183 if ( eqvClass->data.kind == ast::TypeVar::Ftype ) {184 return -1;185 }186 }187 }188 189 return 1;190 }191 192 // can this type be cast to a function (inverse of objectCast)193 int functionCast(194 const ast::Type * src, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab195 ) {196 return -1 * objectCast( src, env, symtab );197 }198 199 class PtrsCastable_new : public ast::WithShortCircuiting {200 const ast::Type * dst;201 const ast::TypeEnvironment & env;202 const ast::SymbolTable & symtab;203 public:204 int result;205 206 PtrsCastable_new(207 const ast::Type * d, const ast::TypeEnvironment & e, const ast::SymbolTable & syms )208 : dst( d ), env( e ), symtab( syms ), result( 0 ) {}209 210 void previsit( const ast::Type * ) { visit_children = false; }211 212 void postvisit( const ast::VoidType * ) {213 result = objectCast( dst, env, symtab );214 }215 216 void postvisit( const ast::BasicType * ) {217 result = objectCast( dst, env, symtab );218 }219 220 void postvisit( const ast::PointerType * ) {221 result = objectCast( dst, env, symtab );222 }223 224 void postvisit( const ast::ArrayType * ) {225 result = objectCast( dst, env, symtab );226 }227 228 void postvisit( const ast::FunctionType * ) {229 result = functionCast( dst, env, symtab );230 }231 232 void postvisit( const ast::StructInstType * ) {233 result = objectCast( dst, env, symtab );234 }235 236 void postvisit( const ast::UnionInstType * ) {237 result = objectCast( dst, env, symtab );238 }239 240 void postvisit( const ast::EnumInstType * ) {241 if ( dynamic_cast< const ast::EnumInstType * >( dst ) ) {242 result = 1;243 } else if ( auto bt = dynamic_cast< const ast::BasicType * >( dst ) ) {244 if ( bt->kind == ast::BasicType::SignedInt ) {245 result = 0;246 } else {247 result = 1;248 }249 } else {250 result = objectCast( dst, env, symtab );251 }252 }253 254 void postvisit( const ast::TraitInstType * ) {}255 256 void postvisit( const ast::TypeInstType * inst ) {257 // check trait and destination type are both object or both function258 result = objectCast( inst, env, symtab ) == objectCast( dst, env, symtab ) ? 1 : -1;259 }260 261 void postvisit( const ast::TupleType * ) {262 result = objectCast( dst, env, symtab );263 }264 265 void postvisit( const ast::VarArgsType * ) {266 result = objectCast( dst, env, symtab );267 }268 269 void postvisit( const ast::ZeroType * ) {270 result = objectCast( dst, env, symtab );271 }272 273 void postvisit( const ast::OneType * ) {274 result = objectCast( dst, env, symtab );275 }276 277 };278 } // anonymous namespace279 280 int ptrsCastable(281 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,282 const ast::TypeEnvironment & env283 ) {284 if ( auto inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {285 if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {286 return ptrsAssignable( src, eqvClass->bound, env );287 }288 }289 290 if ( dynamic_cast< const ast::VoidType * >( dst ) ) {291 return objectCast( src, env, symtab );292 } else {293 ast::Pass< PtrsCastable_new > ptrs{ dst, env, symtab };294 src->accept( ptrs );295 return ptrs.pass.result;296 }297 }298 299 163 } // namespace ResolvExpr 300 164 -
src/ResolvExpr/ResolveTypeof.cc
r3e2f5e3 r3623f9d 18 18 #include <cassert> // for assert 19 19 20 #include "AST/CVQualifiers.hpp"21 #include "AST/Node.hpp"22 #include "AST/Pass.hpp"23 #include "AST/Type.hpp"24 #include "AST/TypeEnvironment.hpp"25 20 #include "Common/PassVisitor.h" // for PassVisitor 26 #include "Common/utility.h" // for copy27 21 #include "Resolver.h" // for resolveInVoidContext 28 22 #include "SynTree/Expression.h" // for Expression … … 48 42 } 49 43 50 class ResolveTypeof _old: public WithShortCircuiting {44 class ResolveTypeof : public WithShortCircuiting { 51 45 public: 52 ResolveTypeof _old( const SymTab::Indexer &indexer ) : indexer( indexer ) {}46 ResolveTypeof( const SymTab::Indexer &indexer ) : indexer( indexer ) {} 53 47 void premutate( TypeofType *typeofType ); 54 48 Type * postmutate( TypeofType *typeofType ); … … 59 53 60 54 Type * resolveTypeof( Type *type, const SymTab::Indexer &indexer ) { 61 PassVisitor<ResolveTypeof _old> mutator( indexer );55 PassVisitor<ResolveTypeof> mutator( indexer ); 62 56 return type->acceptMutator( mutator ); 63 57 } 64 58 65 void ResolveTypeof _old::premutate( TypeofType * ) {59 void ResolveTypeof::premutate( TypeofType * ) { 66 60 visit_children = false; 67 61 } 68 62 69 Type * ResolveTypeof _old::postmutate( TypeofType *typeofType ) {63 Type * ResolveTypeof::postmutate( TypeofType *typeofType ) { 70 64 #if 0 71 65 std::cerr << "resolving typeof: "; … … 114 108 } 115 109 116 namespace { 117 struct ResolveTypeof_new : public ast::WithShortCircuiting { 118 const ast::SymbolTable & localSymtab; 119 120 ResolveTypeof_new( const ast::SymbolTable & syms ) : localSymtab( syms ) {} 121 122 void premutate( const ast::TypeofType * ) { visit_children = false; } 123 124 const ast::Type * postmutate( const ast::TypeofType * typeofType ) { 125 // pass on null expression 126 if ( ! typeofType->expr ) return typeofType; 127 128 ast::ptr< ast::Type > newType; 129 if ( auto tyExpr = typeofType->expr.as< ast::TypeExpr >() ) { 130 // typeof wrapping type 131 newType = tyExpr->type; 132 } else { 133 // typeof wrapping expression 134 ast::TypeEnvironment dummy; 135 ast::ptr< ast::Expr > newExpr = 136 resolveInVoidContext( typeofType->expr, localSymtab, dummy ); 137 assert( newExpr->result && ! newExpr->result->isVoid() ); 138 newType = newExpr->result; 139 } 140 141 // clear qualifiers for base, combine with typeoftype quals regardless 142 if ( typeofType->kind == ast::TypeofType::Basetypeof ) { 143 // replace basetypeof(<enum>) by int 144 if ( newType.as< ast::EnumInstType >() ) { 145 newType = new ast::BasicType{ 146 ast::BasicType::SignedInt, newType->qualifiers, copy(newType->attributes) }; 147 } 148 reset_qualifiers( 149 newType, 150 ( newType->qualifiers & ~ast::CV::EquivQualifiers ) | typeofType->qualifiers ); 151 } else { 152 add_qualifiers( newType, typeofType->qualifiers ); 153 } 154 155 return newType; 156 } 157 }; 158 } // anonymous namespace 159 160 const ast::Type * resolveTypeof( const ast::Type * type , const ast::SymbolTable & symtab ) { 161 ast::Pass< ResolveTypeof_new > mutator{ symtab }; 162 return type->accept( mutator ); 163 } 164 110 const ast::Type * resolveTypeof( const ast::Type * type , const ast::SymbolTable & symtab ) { 111 #warning unimplemented 112 (void)type; (void)symtab; 113 assert(false); 114 return nullptr; 115 } 165 116 } // namespace ResolvExpr 166 117 -
src/ResolvExpr/Resolver.cc
r3e2f5e3 r3623f9d 1226 1226 const ast::StaticAssertDecl * previsit( const ast::StaticAssertDecl * ); 1227 1227 1228 const ast::ArrayType *previsit( const ast::ArrayType * );1229 const ast::PointerType *previsit( const ast::PointerType * );1228 void previsit( const ast::ArrayType * ); 1229 void previsit( const ast::PointerType * ); 1230 1230 1231 1231 const ast::ExprStmt * previsit( const ast::ExprStmt * ); … … 1334 1334 1335 1335 template< typename PtrType > 1336 const PtrType * handlePtrType( const PtrType * type, const ast::SymbolTable & symtab ) { 1337 if ( type->dimension ) { 1338 #warning should use new equivalent to Validate::SizeType rather than sizeType here 1339 ast::ptr< ast::Type > sizeType = new ast::BasicType{ ast::BasicType::LongUnsignedInt }; 1340 ast::mutate_field( 1341 type, &PtrType::dimension, 1342 findSingleExpression( type->dimension, sizeType, symtab ) ); 1343 } 1344 return type; 1345 } 1346 1347 const ast::ArrayType * Resolver_new::previsit( const ast::ArrayType * at ) { 1348 return handlePtrType( at, symtab ); 1349 } 1350 1351 const ast::PointerType * Resolver_new::previsit( const ast::PointerType * pt ) { 1352 return handlePtrType( pt, symtab ); 1336 void handlePtrType( const PtrType * type, const ast::SymbolTable & symtab ) { 1337 #warning unimplemented; needs support for new Validate::SizeType global 1338 (void)type; (void)symtab; 1339 assert( false ); 1340 } 1341 1342 void Resolver_new::previsit( const ast::ArrayType * at ) { 1343 handlePtrType( at, symtab ); 1344 } 1345 1346 void Resolver_new::previsit( const ast::PointerType * pt ) { 1347 handlePtrType( pt, symtab ); 1353 1348 } 1354 1349 -
src/ResolvExpr/typeops.h
r3e2f5e3 r3623f9d 99 99 // in PtrsCastable.cc 100 100 int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ); 101 int ptrsCastable(102 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,103 const ast::TypeEnvironment & env );104 101 105 102 // in Unify.cc
Note:
See TracChangeset
for help on using the changeset viewer.
