Changes in / [ea91c42:33218c6]
- Files:
-
- 23 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/text/concurrency.tex
rea91c42 r33218c6 4 4 % ====================================================================== 5 5 % ====================================================================== 6 Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. 7 8 Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. 9 10 An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. 6 Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. 7 8 Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. 9 10 An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. 11 11 12 12 One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., 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}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct. … … 101 101 } 102 102 \end{cfacode} 103 The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order. 103 The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order. 104 104 105 105 However, such use leads the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown on several occasion\cit, solving this problem requires: … … 169 169 \end{tabular} 170 170 \end{center} 171 Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. 171 Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. 172 172 173 173 % ====================================================================== … … 178 178 Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be complex to support. However, it is shown that entry-point locking solves most of the issues. 179 179 180 First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. 181 182 Before looking into complex control flow, it is important to present the difference between the two acquiring options : \gls{callsite-locking} and \gls{entry-point-locking}, i.e. acquiring the monitors before making a mutex routine call or as the first instruction of the mutex routinecall. For example:180 First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. 181 182 Before looking into complex control-flow, it is important to present the difference between the two acquiring options : callsite and entry-point locking, i.e. acquiring the monitors before making a mutex routine call or as the first operation of the mutex routine-call. For example: 183 183 \begin{center} 184 184 \setlength\tabcolsep{1.5pt} … … 245 245 \end{center} 246 246 247 \Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else. Note that the \code{mutex} keyword relies on the resolver rather than another form of language, which mean that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example: 247 \Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else. 248 249 Note the \code{mutex} keyword relies on the resolver, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example: 248 250 \begin{cfacode} 249 251 //Incorrect 250 252 //T is not a monitor 251 253 forall(dtype T) 252 void foo(T * mutex t); 254 void foo(T * mutex t); 253 255 254 256 //Correct 255 //this function only works on monitors 257 //this function only works on monitors 256 258 //(any monitor) 257 259 forall(dtype T | is_monitor(T)) 258 void bar(T * mutex t)); 260 void bar(T * mutex t)); 259 261 \end{cfacode} 260 262 … … 267 269 In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this is generally achieved with internal or external scheduling as in\cit. Since internal scheduling of single monitors is mostly a solved problem, this proposal concentraits on extending internal scheduling to multiple monitors at once. Indeed, like the \gls{group-acquire} semantics, internal scheduling extends to multiple monitors at once in a way that is natural to the user but requires additional complexity on the implementation side. 268 270 269 First, Here is a simple example of such a technique:271 First, here is a simple example of such a technique: 270 272 271 273 \begin{cfacode} … … 289 291 \end{cfacode} 290 292 291 There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. 293 There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. 292 294 293 295 An important aspect to take into account here is that \CFA does not allow barging, which means that once function \code{bar} releases the monitor, foo is guaranteed to resume immediately after (unless some other thread waited on the same condition). This guarantees offers the benefit of not having to loop arount waits in order to guarantee that a condition is still met. The main reason \CFA offers this guarantee is that users can easily introduce barging if it becomes a necessity but adding barging prevention or barging avoidance is more involved without language support. Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design of \CFA concurrency. … … 317 319 \end{pseudo} 318 320 \end{multicols} 319 320 The previous example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention. 321 The example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention. 321 322 322 323 A direct extension of the previous example is the \gls{group-acquire} version: … … 337 338 \end{pseudo} 338 339 \end{multicols} 339 340 340 This version uses \gls{group-acquire} (denoted using the \& symbol), but the presence of multiple monitors does not add a particularly new meaning. Synchronization happens between the two threads in exactly the same way and order. The only difference is that mutual exclusion covers more monitors. On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate. 341 341 … … 397 397 \end{center} 398 398 399 It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 1 7), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. We are therefore left withthree options:399 It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 16), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. There are three options: 400 400 401 401 \subsubsection{Delaying signals} 402 The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed is what fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single groupd of object. Effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.402 The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed because this semantics fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single group of object, effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections. 403 403 \begin{multicols}{2} 404 404 Waiter … … 424 424 \end{pseudo} 425 425 \end{multicols} 426 However, this solution can become much more complicated depending on what is executed while secretly holding B . Indeed, nothing prevents a user from signalling monitor A on a different condition variable:426 However, this solution can become much more complicated depending on what is executed while secretly holding B (at line 10). Indeed, nothing prevents a user from signalling monitor A on a different condition variable: 427 427 \newpage 428 428 \begin{multicols}{2} … … 459 459 \end{multicols} 460 460 461 The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen. Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.462 463 \paragraph{Case 1: thread 1 will go first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.464 \paragraph{Case 2: thread 2 will go first.} In this case, the problem is that monitor B needs to be passed to thread 1. This can be done directly or using thread 2 as an intermediate.461 The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen. 462 463 \paragraph{Case 1: thread 1 goes first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it. 464 \paragraph{Case 2: thread 2 goes first.} In this case, the problem is that monitor B needs to be passed to thread 1, which can be done directly or using thread 2 as an intermediate. 465 465 \\ 466 466 467 Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect. 468 467 469 In both cases however, the threads need to be able to distinguish on a per monitor basis which ones need to be released and which ones need to be transferred. Which means monitors cannot be handled as a single homogenous group. 468 470 469 471 \subsubsection{Dependency graphs} 470 In the Listing 1 pseudo-code, there is a solution which would statisfy both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example the following code which is just a direct extension to three monitors requires at least three ownership transfer and has multiple solutions:472 In the Listing 1 pseudo-code, there is a solution which statisfies both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example, the following code, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions: 471 473 472 474 \begin{multicols}{2} … … 496 498 497 499 \subsubsection{Partial signalling} 498 Finally, the solution that was chosen for \CFA is to use partial signalling. Consider the following case:500 Finally, the solution that is chosen for \CFA is to use partial signalling. Consider the following case: 499 501 500 502 \begin{multicols}{2} … … 518 520 \end{pseudo} 519 521 \end{multicols} 520 521 The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated in to only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation. 522 The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated into only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation. 522 523 523 524 % ====================================================================== … … 526 527 % ====================================================================== 527 528 % ====================================================================== 528 An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation . Thisis achieved using the \code{signal_block} routine\footnote{name to be discussed}.529 An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the \code{signal_block} routine\footnote{name to be discussed}. 529 530 530 531 For example here is an example highlighting the difference in behaviour: … … 625 626 bool inUse; 626 627 public: 627 void P() { 628 if(inUse) wait(c); 628 void P() { 629 if(inUse) wait(c); 629 630 inUse = true; 630 631 } 631 void V() { 632 inUse = false; 633 signal(c); 632 void V() { 633 inUse = false; 634 signal(c); 634 635 } 635 636 } … … 639 640 bool inUse; 640 641 public: 641 void P() { 642 if(inUse) _Accept(V); 642 void P() { 643 if(inUse) _Accept(V); 643 644 inUse = true; 644 645 } 645 void g() { 646 void g() { 646 647 inUse = false; 647 648 -
doc/proposals/concurrency/version
rea91c42 r33218c6 1 0.9.1 191 0.9.122 -
src/CodeGen/CodeGenerator.cc
rea91c42 r33218c6 13 13 // Update Count : 485 14 14 // 15 #include "CodeGenerator.h" 15 16 16 17 #include <cassert> // for assert, assertf 17 18 #include <list> // for _List_iterator, list, list<>::it... 18 19 19 #include "CodeGenerator.h"20 20 #include "Common/SemanticError.h" // for SemanticError 21 21 #include "Common/UniqueName.h" // for UniqueName -
src/CodeGen/GenType.cc
rea91c42 r33218c6 13 13 // Update Count : 22 14 14 // 15 #include "GenType.h" 15 16 16 17 #include <cassert> // for assert, assertf … … 19 20 20 21 #include "CodeGenerator.h" // for CodeGenerator 21 #include "GenType.h"22 22 #include "SynTree/Declaration.h" // for DeclarationWithType 23 23 #include "SynTree/Expression.h" // for Expression -
src/CodeGen/Generate.cc
rea91c42 r33218c6 13 13 // Update Count : 6 14 14 // 15 #include "Generate.h" 15 16 16 17 #include <iostream> // for ostream, endl, operator<< … … 20 21 #include "CodeGenerator.h" // for CodeGenerator, doSemicolon, oper... 21 22 #include "GenType.h" // for genPrettyType 22 #include "Generate.h"23 23 #include "Parser/LinkageSpec.h" // for isBuiltin, isGeneratable 24 24 #include "SynTree/BaseSyntaxNode.h" // for BaseSyntaxNode -
src/CodeTools/TrackLoc.cc
rea91c42 r33218c6 16 16 #include "TrackLoc.h" 17 17 18 #include <cstdlib> // for size_t, exit, EXIT_FAILURE 19 #include <iostream> // for operator<<, ostream, basic_ostream 20 #include <iterator> // for back_inserter, inserter 21 #include <stack> // for stack 22 #include <string> // for operator<<, string 23 #include <typeindex> // for type_index 18 #include <cstdlib> // for exit, EXIT_FAILURE 19 #include <iostream> // for operator<<, ostream, basic_ostream 20 #include <stack> // for stack 21 #include <string> // for operator<<, string 22 #include <typeindex> // for type_index 24 23 25 #include "Common/PassVisitor.h" // for PassVisitor 26 #include "Common/PassVisitor.impl.h" // for acceptAll 27 #include "Common/SemanticError.h" // for SemanticError 28 #include "Common/utility.h" // for CodeLocation 29 #include "SynTree/BaseSyntaxNode.h" // for BaseSyntaxNode 30 #include "SynTree/Mutator.h" // for mutateAll 31 #include "SynTree/Visitor.h" // for acceptAll 24 #include "Common/PassVisitor.h" // for PassVisitor 25 #include "Common/utility.h" // for CodeLocation 26 #include "SynTree/BaseSyntaxNode.h" // for BaseSyntaxNode 32 27 33 28 class Declaration; … … 46 41 std::stack< CodeLocation * > parents; 47 42 public: 48 LocationPrinter(size_t printLevel) : 43 LocationPrinter(size_t printLevel) : 49 44 printLevel(printLevel), lastNode(nullptr) 50 45 {} … … 65 60 if ( !parents.empty() ) { 66 61 node->location = *parents.top(); 67 } 62 } 68 63 else if (nullptr != lastNode) { 69 64 node->location = *lastNode; 70 } 65 } 71 66 else { 72 67 std::cerr << "Top level node has no CodeLocation " << name << std::endl; -
src/Common/PassVisitor.impl.h
rea91c42 r33218c6 1 1 #pragma once 2 // IWYU pragma: private, include "PassVisitor.h" 2 3 3 4 #define VISIT_START( node ) \ -
src/Common/PassVisitor.proto.h
rea91c42 r33218c6 1 1 #pragma once 2 // IWYU pragma: private, include "PassVisitor.h" 2 3 3 4 template<typename pass_type> -
src/SymTab/AddVisit.h
rea91c42 r33218c6 14 14 // 15 15 16 #include "SynTree/Statement.h" 17 16 18 namespace SymTab { 17 19 void addDecls( std::list< Declaration* > &declsToAdd, std::list< Statement* > &statements, std::list< Statement* >::iterator i ); … … 28 30 29 31 if ( stmt == stmts.end() ) break; 30 32 31 33 // run mutator on statement 32 34 maybeAccept( *stmt, visitor ); … … 59 61 60 62 if ( decl == translationUnit.end() ) break; 61 63 62 64 // run mutator on declaration 63 65 maybeAccept( *decl, visitor ); -
src/SymTab/Autogen.cc
rea91c42 r33218c6 13 13 // Update Count : 62 14 14 // 15 16 #include <list>17 #include <iterator>18 #include "SynTree/Visitor.h"19 #include "SynTree/Type.h"20 #include "SynTree/Statement.h"21 #include "SynTree/TypeSubstitution.h"22 #include "Common/utility.h"23 #include "AddVisit.h"24 #include "MakeLibCfa.h"25 15 #include "Autogen.h" 26 #include "GenPoly/ScopedSet.h" 27 #include "Common/ScopedMap.h" 28 #include "SymTab/Mangler.h" 29 #include "GenPoly/DeclMutator.h" 16 17 #include <algorithm> // for count_if 18 #include <cassert> // for safe_dynamic_cast, assert, assertf 19 #include <iterator> // for back_insert_iterator, back_inserter 20 #include <list> // for list, _List_iterator, list<>::iter... 21 #include <set> // for set, _Rb_tree_const_iterator 22 #include <vector> // for vector 23 24 #include "AddVisit.h" // for addVisit 25 #include "Common/ScopedMap.h" // for ScopedMap<>::const_iterator, Scope... 26 #include "Common/utility.h" // for cloneAll, operator+ 27 #include "GenPoly/DeclMutator.h" // for DeclMutator 28 #include "GenPoly/ScopedSet.h" // for ScopedSet, ScopedSet<>::iterator 29 #include "SymTab/Mangler.h" // for Mangler 30 #include "SynTree/Mutator.h" // for maybeMutate 31 #include "SynTree/Statement.h" // for CompoundStmt, ReturnStmt, ExprStmt 32 #include "SynTree/Type.h" // for FunctionType, Type, TypeInstType 33 #include "SynTree/Visitor.h" // for maybeAccept, Visitor, acceptAll 34 35 class Attribute; 30 36 31 37 namespace SymTab { … … 512 518 // Make function polymorphic in same parameters as generic union, if applicable 513 519 const std::list< TypeDecl* > & typeParams = aggregateDecl->get_parameters(); // List of type variables to be placed on the generated functions 514 520 515 521 // default ctor/dtor need only first parameter 516 522 // void ?{}(T *); void ^?{}(T *); -
src/SymTab/Autogen.h
rea91c42 r33218c6 16 16 #pragma once 17 17 18 #include <string> 19 #include "SynTree/Statement.h" 20 #include "SynTree/Expression.h" 21 #include "SynTree/Declaration.h" 22 #include "SynTree/Initializer.h" 23 #include "InitTweak/InitTweak.h" 18 #include <cassert> // for assert 19 #include <iterator> // for back_insert_iterator, back_inserter 20 #include <list> // for list 21 #include <string> // for string, operator== 22 23 #include "Common/UniqueName.h" // for UniqueName 24 #include "InitTweak/InitTweak.h" // for InitExpander 25 #include "Parser/LinkageSpec.h" // for C 26 #include "SynTree/Constant.h" // for Constant 27 #include "SynTree/Declaration.h" // for ObjectDecl, Declaration (ptr only) 28 #include "SynTree/Expression.h" // for UntypedExpr, NameExpr, VariableExpr 29 #include "SynTree/Initializer.h" // for SingleInit 30 #include "SynTree/Label.h" // for Label, noLabels 31 #include "SynTree/Statement.h" // for Statement (ptr only), CompoundStmt 32 #include "SynTree/Type.h" // for Type, ArrayType, Type::Qualifiers 24 33 25 34 namespace SymTab { … … 154 163 if ( isUnnamedBitfield( obj ) ) return; 155 164 156 bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && obj->get_bitfieldWidth() == NULL) );165 bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && ! obj->get_bitfieldWidth() ) ); 157 166 std::list< Statement * > stmts; 158 167 genCall( srcParam, dstParam, fname, back_inserter( stmts ), obj->get_type(), addCast, forward ); -
src/SymTab/FixFunction.cc
rea91c42 r33218c6 15 15 16 16 #include "FixFunction.h" 17 #include "SynTree/Declaration.h" 18 #include "SynTree/Type.h" 19 #include "SynTree/Expression.h" 20 #include "Common/utility.h" 17 18 #include <list> // for list 19 20 #include "Common/utility.h" // for maybeClone 21 #include "SynTree/Declaration.h" // for FunctionDecl, ObjectDecl, Declarati... 22 #include "SynTree/Type.h" // for ArrayType, PointerType, Type, Basic... 21 23 22 24 namespace SymTab { -
src/SymTab/FixFunction.h
rea91c42 r33218c6 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // FixFunction.h -- 7 // FixFunction.h -- 8 8 // 9 9 // Author : Richard C. Bilson … … 16 16 #pragma once 17 17 18 #include "SynTree/Mutator.h" 18 #include "SynTree/Mutator.h" // for Mutator 19 #include "SynTree/SynTree.h" // for Types 19 20 20 21 namespace SymTab { … … 43 44 virtual Type* mutate(ZeroType *zeroType); 44 45 virtual Type* mutate(OneType *oneType); 45 46 46 47 bool isVoid; 47 48 }; -
src/SymTab/ImplementationType.cc
rea91c42 r33218c6 15 15 16 16 #include "ImplementationType.h" 17 #include "SynTree/Type.h" 18 #include "SynTree/Declaration.h" 19 #include "SynTree/Visitor.h" 20 #include "SymTab/Indexer.h" 21 #include "Common/utility.h" 17 18 #include <list> // for list, _List_iterator, list<>::iterator 19 20 #include "SymTab/Indexer.h" // for Indexer 21 #include "SynTree/Declaration.h" // for NamedTypeDecl 22 #include "SynTree/Type.h" // for TupleType, Type, ArrayType, Pointer... 23 #include "SynTree/Visitor.h" // for Visitor 22 24 23 25 -
src/SymTab/ImplementationType.h
rea91c42 r33218c6 16 16 #pragma once 17 17 18 #include "SynTree/SynTree.h" 19 #include "SymTab/Indexer.h" 18 class Type; 20 19 21 20 namespace SymTab { 21 class Indexer; 22 22 23 Type *implementationType( Type *, const SymTab::Indexer &indexer ); 23 24 -
src/SymTab/Indexer.cc
rea91c42 r33218c6 16 16 #include "Indexer.h" 17 17 18 #include <string> 19 #include <typeinfo> 20 #include <unordered_map> 21 #include <unordered_set> 22 #include <utility> 23 #include <algorithm> 24 25 #include "Mangler.h" 26 27 #include "Common/utility.h" 28 29 #include "ResolvExpr/typeops.h" 30 31 #include "SynTree/Declaration.h" 32 #include "SynTree/Type.h" 33 #include "SynTree/Expression.h" 34 #include "SynTree/Initializer.h" 35 #include "SynTree/Statement.h" 36 37 #include "InitTweak/InitTweak.h" 18 #include <cassert> // for assert, safe_dynamic_cast 19 #include <iostream> // for operator<<, basic_ostream, ostream 20 #include <string> // for string, operator<<, operator!= 21 #include <unordered_map> // for operator!=, unordered_map<>::const... 22 #include <unordered_set> // for unordered_set 23 #include <utility> // for pair, make_pair, move 24 25 #include "Common/SemanticError.h" // for SemanticError 26 #include "Common/utility.h" // for cloneAll 27 #include "InitTweak/InitTweak.h" // for isConstructor, isCopyFunction, isC... 28 #include "Mangler.h" // for Mangler 29 #include "Parser/LinkageSpec.h" // for isMangled, isOverridable, Spec 30 #include "ResolvExpr/typeops.h" // for typesCompatible 31 #include "SynTree/Constant.h" // for Constant 32 #include "SynTree/Declaration.h" // for DeclarationWithType, FunctionDecl 33 #include "SynTree/Expression.h" // for Expression, ImplicitCopyCtorExpr 34 #include "SynTree/Initializer.h" // for Initializer 35 #include "SynTree/Statement.h" // for CompoundStmt, Statement, ForStmt (... 36 #include "SynTree/Type.h" // for Type, StructInstType, UnionInstType 38 37 39 38 #define debugPrint(x) if ( doDebug ) { std::cout << x; } -
src/SymTab/Indexer.h
rea91c42 r33218c6 16 16 #pragma once 17 17 18 #include <list> 19 #include <string> 18 #include <iosfwd> // for ostream 19 #include <list> // for list 20 #include <string> // for string 20 21 21 #include "SynTree/Visitor.h" 22 #include "SynTree/Visitor.h" // for Visitor 23 #include "SynTree/SynTree.h" // for AST nodes 22 24 23 25 namespace SymTab { … … 125 127 126 128 struct Impl; 129 127 130 Impl *tables; ///< Copy-on-write instance of table data structure 128 131 unsigned long scope; ///< Scope index of this pointer -
src/SymTab/Mangler.cc
rea91c42 r33218c6 13 13 // Update Count : 21 14 14 // 15 16 #include <cassert>17 #include <string>18 #include <algorithm>19 #include <iterator>20 #include <functional>21 #include <set>22 23 #include "SynTree/Declaration.h"24 #include "SynTree/Type.h"25 #include "SynTree/Expression.h"26 #include "SynTree/Initializer.h"27 #include "SynTree/Statement.h"28 15 #include "Mangler.h" 29 #include "CodeGen/OperatorTable.h" 16 17 #include <algorithm> // for copy, transform 18 #include <cassert> // for assert, assertf 19 #include <functional> // for const_mem_fun_t, mem_fun 20 #include <iterator> // for ostream_iterator, back_insert_ite... 21 #include <list> // for _List_iterator, list, _List_const... 22 #include <string> // for string, operator<<, basic_string 23 24 #include "CodeGen/OperatorTable.h" // for OperatorInfo, operatorLookup 25 #include "Common/utility.h" // for toString 26 #include "Parser/LinkageSpec.h" // for Spec, isOverridable, AutoGen, Int... 27 #include "SynTree/Declaration.h" // for TypeDecl, DeclarationWithType 28 #include "SynTree/Expression.h" // for TypeExpr, Expression, operator<< 29 #include "SynTree/Type.h" // for Type, ReferenceToType, Type::Fora... 30 30 31 31 namespace SymTab { -
src/SymTab/Mangler.h
rea91c42 r33218c6 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // Mangler.h -- 7 // Mangler.h -- 8 8 // 9 9 // Author : Richard C. Bilson … … 16 16 #pragma once 17 17 18 #include <sstream> 19 #include "SynTree/SynTree.h" 20 #include "SynTree/Visitor.h" 18 #include <map> // for map, map<>::value_compare 19 #include <sstream> // for ostringstream 20 #include <string> // for string 21 #include <utility> // for pair 22 23 #include "SynTree/SynTree.h" // for Types 24 #include "SynTree/Visitor.h" // for Visitor, maybeAccept 21 25 22 26 namespace SymTab { … … 47 51 virtual void visit( ZeroType *zeroType ); 48 52 virtual void visit( OneType *oneType ); 49 53 50 54 std::string get_mangleName() { return mangleName.str(); } 51 55 private: … … 57 61 bool mangleOverridable; ///< Specially mangle overridable built-in methods 58 62 bool typeMode; ///< Produce a unique mangled name for a type 59 63 60 64 Mangler( bool mangleOverridable, bool typeMode ); 61 65 Mangler( const Mangler & ); 62 66 63 67 void mangleDecl( DeclarationWithType *declaration ); 64 68 void mangleRef( ReferenceToType *refType, std::string prefix ); 65 69 void mangleGenericRef( ReferenceToType *refType, std::string prefix ); 66 70 67 71 void printQualifiers( Type *type ); 68 72 }; // Mangler -
src/SymTab/TypeEquality.cc
rea91c42 r33218c6 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // TypeEquality.cc -- 7 // TypeEquality.cc -- 8 8 // 9 9 // Author : Rob Schluntz … … 13 13 // Update Count : 37 14 14 // 15 16 #include <list>17 #include <iterator>18 #include "Validate.h"19 #include "SynTree/Visitor.h"20 #include "SynTree/Type.h"21 #include "SynTree/Statement.h"22 #include "SynTree/TypeSubstitution.h"23 #include "Indexer.h"24 15 #include "TypeEquality.h" 16 17 #include <cassert> // for assert 18 #include <list> // for list, list<>::iterator, _List_iterator 19 #include <string> // for operator==, string, basic_string 20 21 #include "SynTree/Constant.h" // for Constant 22 #include "SynTree/Declaration.h" // for DeclarationWithType 23 #include "SynTree/Expression.h" // for ConstantExpr, Expression 24 #include "SynTree/Type.h" // for Type, ArrayType, FunctionType, Enum... 25 #include "SynTree/Visitor.h" // for Visitor 25 26 26 27 namespace SymTab { 27 28 class TypeEquality : public Visitor { 28 29 public: 29 TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ), 30 TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ), 30 31 vlaErr( vlaErr ) {} 31 32 bool result; … … 71 72 handleQualifiers( basicType ); 72 73 if ( BasicType * bt = dynamic_cast< BasicType * >( other ) ) { 73 result = result && basicType->get_kind() == bt->get_kind(); 74 result = result && basicType->get_kind() == bt->get_kind(); 74 75 } else { 75 76 result = false; … … 98 99 99 100 if ( vlaErr ) { 100 // useful for comparing typedef types - in this case, we 101 // useful for comparing typedef types - in this case, we 101 102 // want types to appear distinct if either is a VLA type 102 103 if ( arrayType->get_isVarLen() || at->get_isVarLen() ) { … … 146 147 147 148 // parameter types must be equivalent 148 it1 = funcType->get_parameters().begin(); 149 it1 = funcType->get_parameters().begin(); 149 150 it2 = ft->get_parameters().begin(); 150 151 for ( ; it1 != funcType->get_parameters().end(); ++it1, ++it2 ) { -
src/SymTab/TypeEquality.h
rea91c42 r33218c6 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // TypeEquality.h -- 7 // TypeEquality.h -- 8 8 // 9 9 // Author : Rob Schluntz … … 14 14 // 15 15 16 class Type; 17 16 18 namespace SymTab { 17 19 // compare types t1 and t2 for equality 18 // if vlaErr is true, then if at least one of the types is a 19 // variable-length array type, then the result will be false 20 // if vlaErr is true, then if at least one of the types is a 21 // variable-length array type, then the result will be false 20 22 bool typeEquals( Type * t1, Type * t2, bool vlaErr = false ); 21 23 } // namespace SymTab -
src/SymTab/Validate.cc
rea91c42 r33218c6 38 38 // definition occurs later in the input. 39 39 40 #include <algorithm>41 #include <iterator>42 #include <list>43 44 #include "CodeGen/CodeGenerator.h"45 46 #include "Common/PassVisitor.h"47 #include "Common/ScopedMap.h"48 #include "Common/UniqueName.h"49 #include "Common/utility.h"50 51 #include "Concurrency/Keywords.h"52 53 #include "GenPoly/DeclMutator.h"54 55 #include "InitTweak/InitTweak.h"56 57 #include "AddVisit.h"58 #include "Autogen.h"59 #include "FixFunction.h"60 // #include "ImplementationType.h"61 #include "Indexer.h"62 #include "MakeLibCfa.h"63 #include "TypeEquality.h"64 40 #include "Validate.h" 65 41 66 #include "ResolvExpr/typeops.h" 67 68 #include "SynTree/Attribute.h" 69 #include "SynTree/Expression.h" 70 #include "SynTree/Mutator.h" 71 #include "SynTree/Statement.h" 72 #include "SynTree/Type.h" 73 #include "SynTree/TypeSubstitution.h" 74 #include "SynTree/Visitor.h" 42 #include <cstddef> // for size_t 43 #include <algorithm> // for move, transform 44 #include <cassert> // for safe_dynamic_cast, assertf 45 #include <iterator> // for back_inserter, inserter, back_... 46 #include <list> // for list, _List_iterator, list<>::... 47 #include <map> // for _Rb_tree_iterator, map, map<>:... 48 #include <memory> // for unique_ptr, allocator 49 #include <string> // for string, operator+, operator== 50 #include <tuple> // for get 51 #include <utility> // for pair, make_pair 52 53 #include "AddVisit.h" // for addVisit 54 #include "Autogen.h" // for SizeType, autogenerateRoutines 55 #include "CodeGen/CodeGenerator.h" // for genName 56 #include "Common/PassVisitor.h" // for PassVisitor, WithDeclsToAdd 57 #include "Common/ScopedMap.h" // for ScopedMap<>::const_iterator 58 #include "Common/SemanticError.h" // for SemanticError 59 #include "Common/UniqueName.h" // for UniqueName 60 #include "Common/utility.h" // for operator+, cloneAll, deleteAll 61 #include "Concurrency/Keywords.h" // for applyKeywords, implementMutexF... 62 #include "FixFunction.h" // for FixFunction 63 #include "Indexer.h" // for Indexer 64 #include "InitTweak/InitTweak.h" // for isCtorDtor, isCtorDtorAssign 65 #include "Parser/LinkageSpec.h" // for C, Cforall 66 #include "ResolvExpr/typeops.h" // for extractResultType, typesCompat... 67 #include "SynTree/Attribute.h" // for Attribute 68 #include "SynTree/Constant.h" // for Constant 69 #include "SynTree/Declaration.h" // for EnumDecl, StructDecl, UnionDecl 70 #include "SynTree/Expression.h" // for TypeExpr, CompoundLiteralExpr 71 #include "SynTree/Initializer.h" // for ListInit, Initializer, noDesig... 72 #include "SynTree/Mutator.h" // for mutateAll, Mutator 73 #include "SynTree/Statement.h" // for CompoundStmt, DeclStmt, Return... 74 #include "SynTree/Type.h" // for Type, TypeInstType, TraitInstType 75 #include "SynTree/TypeSubstitution.h" // for TypeSubstitution, applySubstit... 76 #include "SynTree/Visitor.h" // for acceptAll, Visitor 75 77 76 78 #define debugPrint( x ) if ( doDebug ) { std::cout << x; } … … 605 607 // a return statement in a void-returning function in C. The expression is treated as if it 606 608 // were cast to void. 607 if ( returnStmt->get_expr() == NULL&& returnVals.size() != 0 ) {609 if ( ! returnStmt->get_expr() && returnVals.size() != 0 ) { 608 610 throw SemanticError( "Non-void function returns no values: " , returnStmt ); 609 611 } … … 836 838 void validateGeneric( Aggr * inst ) { 837 839 std::list< TypeDecl * > * params = inst->get_baseParameters(); 838 if ( params != NULL) {840 if ( params ) { 839 841 std::list< Expression * > & args = inst->get_parameters(); 840 842 … … 937 939 void ArrayLength::previsit( ObjectDecl * objDecl ) { 938 940 if ( ArrayType * at = dynamic_cast< ArrayType * >( objDecl->get_type() ) ) { 939 if ( at->get_dimension() != nullptr) return;941 if ( at->get_dimension() ) return; 940 942 if ( ListInit * init = dynamic_cast< ListInit * >( objDecl->get_init() ) ) { 941 943 at->set_dimension( new ConstantExpr( Constant::from_ulong( init->get_initializers().size() ) ) ); -
src/SymTab/Validate.h
rea91c42 r33218c6 17 17 #pragma once 18 18 19 #include "SynTree/SynTree.h" 19 #include <list> // for list 20 21 class Declaration; 22 class Type; 20 23 21 24 namespace SymTab {
Note: See TracChangeset
for help on using the changeset viewer.