Index: automake/cfa.m4 =================================================================== --- automake/cfa.m4 (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ automake/cfa.m4 (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -66,4 +66,5 @@ "x86-64" ) cannon_arch_name="x64";; "x86_64" ) cannon_arch_name="x64";; + "aarch64" ) cannon_arch_name="x64";; "x86" ) cannon_arch_name="x86";; "i386" ) cannon_arch_name="x86";; @@ -75,5 +76,5 @@ "armv7l" ) cannon_arch_name="arm";; *) - >&2 echo "Unkown architecture " $arch_name; + >&2 echo "Unknown architecture " $arch_name; exit 1 ;; Index: benchmark/Makefile.am =================================================================== --- benchmark/Makefile.am (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ benchmark/Makefile.am (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -11,6 +11,6 @@ ## Created On : Sun May 31 09:08:15 2015 ## Last Modified By : Peter A. Buhr -## Last Modified On : Mon Jun 24 16:45:42 2019 -## Update Count : 53 +## Last Modified On : Mon Jul 29 18:02:19 2019 +## Update Count : 54 ############################################################################### @@ -50,5 +50,6 @@ REPEAT = ${abs_top_builddir}/tools/repeat STATS = ${abs_top_srcdir}/tools/stat.py -repeats = 3 # 30 +# NEED AT LEAST 4 DATA VALUES FOR BENCHMARKS BECAUSE THE MAX AND MIN VALUES ARE REMOVED +repeats = 5 # 31 for benchmarks skipcompile = no TIME_FORMAT = "%E" Index: benchmark/creation/JavaThread.java =================================================================== --- benchmark/creation/JavaThread.java (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ benchmark/creation/JavaThread.java (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -1,18 +1,56 @@ public class JavaThread { + // Simplistic low-quality Marsaglia Shift-XOR pseudo-random number generator. + // Bijective + // Cycle length for non-zero values is 4G-1. + // 0 is absorbing and should be avoided -- fixed point. + // The returned value is typically masked to produce a positive value. + static volatile int Ticket = 0 ; + + private static int nextRandom (int x) { + if (x == 0) { + // reseed the PRNG + // Ticket is accessed infrequently and does not constitute a coherence hot-spot. + // Note that we use a non-atomic racy increment -- the race is rare and benign. + // If the race is a concern switch to an AtomicInteger. + // In addition accesses to the RW volatile global "Ticket" variable are not + // (readily) predictable at compile-time so the JIT will not be able to elide + // nextRandom() invocations. + x = ++Ticket ; + if (x == 0) x = 1 ; + } + x ^= x << 6; + x ^= x >>> 21; + x ^= x << 7; + return x ; + } + static int x = 2; + + static private final int NoOfTimes = Integer.parseInt("10000") ; + public static class MyThread extends Thread { @Override public void run() {} } - - public static void main(String[] args) throws InterruptedException { - int NoOfTimes = 50000; - long start = System.nanoTime(); + public static void helper() throws InterruptedException { for(int i = 1; i <= NoOfTimes; i += 1) { - JavaThread.MyThread m = new JavaThread.MyThread(); - m.start(); + MyThread m = new MyThread(); + x = nextRandom( x ); + m.start(); m.join(); } + } + public static void InnerMain() throws InterruptedException { + long start = System.nanoTime(); + helper(); long end = System.nanoTime(); - System.out.println( (end - start) / NoOfTimes); + System.out.println( (end - start) / NoOfTimes ); + } + public static void main(String[] args) throws InterruptedException { + for (int n = Integer.parseInt("5"); --n >= 0 ; ) { + InnerMain(); + Thread.sleep(2000); // 2 seconds + x = nextRandom(x); + } + if ( x == 0 ) System.out.println(x); } } Index: benchmark/ctxswitch/JavaThread.java =================================================================== --- benchmark/ctxswitch/JavaThread.java (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ benchmark/ctxswitch/JavaThread.java (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -1,11 +1,49 @@ public class JavaThread { - public static void main(String[] args) { - int NoOfTimes = 5000000; - long start = System.nanoTime(); + // Simplistic low-quality Marsaglia Shift-XOR pseudo-random number generator. + // Bijective + // Cycle length for non-zero values is 4G-1. + // 0 is absorbing and should be avoided -- fixed point. + // The returned value is typically masked to produce a positive value. + static volatile int Ticket = 0 ; + + private static int nextRandom (int x) { + if (x == 0) { + // reseed the PRNG + // Ticket is accessed infrequently and does not constitute a coherence hot-spot. + // Note that we use a non-atomic racy increment -- the race is rare and benign. + // If the race is a concern switch to an AtomicInteger. + // In addition accesses to the RW volatile global "Ticket" variable are not + // (readily) predictable at compile-time so the JIT will not be able to elide + // nextRandom() invocations. + x = ++Ticket ; + if (x == 0) x = 1 ; + } + x ^= x << 6; + x ^= x >>> 21; + x ^= x << 7; + return x ; + } + static int x = 2; + + static private final int NoOfTimes = Integer.parseInt("1000000") ; + + public static void helper() { for(int i = 1; i <= NoOfTimes; i += 1) { Thread.yield(); } + } + public static void InnerMain() { + long start = System.nanoTime(); + helper(); long end = System.nanoTime(); - System.out.println( (end - start) / NoOfTimes); + System.out.println( (end - start) / NoOfTimes ); + } + public static void main(String[] args) throws InterruptedException { + for (int n = Integer.parseInt("5"); --n >= 0 ; ) { + InnerMain(); + Thread.sleep(2000); // 2 seconds + x = nextRandom(x); + } + if ( x == 0 ) System.out.println(x); } } Index: benchmark/mutex/JavaThread.java =================================================================== --- benchmark/mutex/JavaThread.java (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ benchmark/mutex/JavaThread.java (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -1,14 +1,56 @@ public class JavaThread { - public synchronized void noop() {} + // Simplistic low-quality Marsaglia Shift-XOR pseudo-random number generator. + // Bijective + // Cycle length for non-zero values is 4G-1. + // 0 is absorbing and should be avoided -- fixed point. + // The returned value is typically masked to produce a positive value. + static volatile int Ticket = 0 ; - public static void main(String[] args) { - int NoOfTimes = 5000000; + private static int nextRandom (int x) { + if (x == 0) { + // reseed the PRNG + // Ticket is accessed infrequently and does not constitute a coherence hot-spot. + // Note that we use a non-atomic racy increment -- the race is rare and benign. + // If the race is a concern switch to an AtomicInteger. + // In addition accesses to the RW volatile global "Ticket" variable are not + // (readily) predictable at compile-time so the JIT will not be able to elide + // nextRandom() invocations. + x = ++Ticket ; + if (x == 0) x = 1 ; + } + x ^= x << 6; + x ^= x >>> 21; + x ^= x << 7; + return x ; + } + static int x = 2; + + static private final int NoOfTimes = Integer.parseInt("100000000") ; + + public synchronized void noop() { + x = nextRandom( x ); + } + public static void helper() throws InterruptedException { JavaThread j = new JavaThread(); - long start = System.nanoTime(); + // Inhibit biased locking ... + x = (j.hashCode() ^ System.identityHashCode(j)) | 1 ; for(int i = 1; i <= NoOfTimes; i += 1) { + x = nextRandom(x); j.noop(); } + } + public static void InnerMain() throws InterruptedException { + long start = System.nanoTime(); + helper(); long end = System.nanoTime(); - System.out.println( (end - start) / NoOfTimes); + System.out.println( (end - start) / NoOfTimes ); + } + public static void main(String[] args) throws InterruptedException { + for (int n = Integer.parseInt("5"); --n >= 0 ; ) { + InnerMain(); + Thread.sleep(2000); // 2 seconds + x = nextRandom(x); + } + if ( x == 0 ) System.out.println(x); } } Index: benchmark/schedint/JavaThread.java =================================================================== --- benchmark/schedint/JavaThread.java (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ benchmark/schedint/JavaThread.java (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -1,4 +1,5 @@ class Monitor { public static volatile Boolean go = false; + public static volatile Boolean next = false; } @@ -13,6 +14,8 @@ while( Monitor.go ) { synchronized(this.m) { + Monitor.next = false; this.m.notify(); } + while( ! Monitor.next && Monitor.go ); // spin until woken } } @@ -20,6 +23,39 @@ public class JavaThread { - public static void main(String[] args) throws InterruptedException { - int NoOfTimes = 50000; + // Simplistic low-quality Marsaglia Shift-XOR pseudo-random number generator. + // Bijective + // Cycle length for non-zero values is 4G-1. + // 0 is absorbing and should be avoided -- fixed point. + // The returned value is typically masked to produce a positive value. + static volatile int Ticket = 0 ; + + private static int nextRandom (int x) { + if (x == 0) { + // reseed the PRNG + // Ticket is accessed infrequently and does not constitute a coherence hot-spot. + // Note that we use a non-atomic racy increment -- the race is rare and benign. + // If the race is a concern switch to an AtomicInteger. + // In addition accesses to the RW volatile global "Ticket" variable are not + // (readily) predictable at compile-time so the JIT will not be able to elide + // nextRandom() invocations. + x = ++Ticket ; + if (x == 0) x = 1 ; + } + x ^= x << 6; + x ^= x >>> 21; + x ^= x << 7; + return x ; + } + static int x = 2; + + static private final int NoOfTimes = Integer.parseInt("1000000") ; + + public static void helper( Monitor m ) throws InterruptedException { + for(int i = 1; i <= NoOfTimes; i += 1) { + m.wait(); // relase monitor lock + m.next = true; + } + } + public static void InnerMain() throws InterruptedException { Monitor m = new Monitor(); long start, end; @@ -31,7 +67,5 @@ } start = System.nanoTime(); - for(int i = 1; i <= NoOfTimes; i += 1) { - m.wait(); - } + helper( m ); end = System.nanoTime(); } @@ -40,3 +74,11 @@ System.out.println( (end - start) / NoOfTimes); } + public static void main(String[] args) throws InterruptedException { + for (int n = Integer.parseInt("5"); --n >= 0 ; ) { + InnerMain(); + Thread.sleep(2000); // 2 seconds + x = nextRandom(x); + } + if ( x == 0 ) System.out.println(x); + } } Index: configure =================================================================== --- configure (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ configure (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -3433,4 +3433,5 @@ "x86-64" ) cannon_arch_name="x64";; "x86_64" ) cannon_arch_name="x64";; + "aarch64" ) cannon_arch_name="x64";; "x86" ) cannon_arch_name="x86";; "i386" ) cannon_arch_name="x86";; @@ -3442,5 +3443,5 @@ "armv7l" ) cannon_arch_name="arm";; *) - >&2 echo "Unkown architecture " $arch_name; + >&2 echo "Unknown architecture " $arch_name; exit 1 ;; @@ -3474,4 +3475,5 @@ "x86-64" ) cannon_arch_name="x64";; "x86_64" ) cannon_arch_name="x64";; + "aarch64" ) cannon_arch_name="x64";; "x86" ) cannon_arch_name="x86";; "i386" ) cannon_arch_name="x86";; @@ -3483,5 +3485,5 @@ "armv7l" ) cannon_arch_name="arm";; *) - >&2 echo "Unkown architecture " $arch_name; + >&2 echo "Unknown architecture " $arch_name; exit 1 ;; Index: doc/papers/concurrency/Paper.tex =================================================================== --- doc/papers/concurrency/Paper.tex (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ doc/papers/concurrency/Paper.tex (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -307,7 +307,7 @@ 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. 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}. -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; +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 mutex/condition locks, which is low-level and error-prone; no high-level language concurrency features are defined. -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. +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 (possibly because the effort to add concurrency to \CC). Finally, while the \Celeven standard does not state a threading model, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}. @@ -333,5 +333,7 @@ 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. -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. +Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging}\footnote{ +The notion of competitive succession instead of direct handoff, \ie a lock owner releases the lock and an arriving thread acquires it ahead of preexisting waiter threads. +} (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. However, spurious wakeup is \emph{not} a foundational concurrency property~\cite[\S~8]{Buhr05a}, it is a performance design choice. Similarly, signals-as-hints are often a performance decision. @@ -351,5 +353,5 @@ 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. The main contributions of this work are: -\begin{itemize} +\begin{itemize}[topsep=3pt,itemsep=1pt] \item language-level generators, coroutines and user-level threading, which respect the expectations of C programmers. @@ -370,6 +372,14 @@ \end{itemize} +Section~\ref{s:StatefulFunction} begins advanced control by introducing sequential functions that retain data and execution state between calls, which produces constructs @generator@ and @coroutine@. +Section~\ref{s:Concurrency} begins concurrency, or how to create (fork) and destroy (join) a thread, which produces the @thread@ construct. +Section~\ref{s:MutualExclusionSynchronization} discusses the two mechanisms to restricted nondeterminism when controlling shared access to resources (mutual exclusion) and timing relationships among threads (synchronization). +Section~\ref{s:Monitor} shows how both mutual exclusion and synchronization are safely embedded in the @monitor@ and @thread@ constructs. +Section~\ref{s:CFARuntimeStructure} describes the large-scale mechanism to structure (cluster) threads and virtual processors (kernel threads). +Section~\ref{s:Performance} uses a series of microbenchmarks to compare \CFA threading with pthreads, Java OpenJDK-9, Go 1.12.6 and \uC 7.0.0. + \section{Stateful Function} +\label{s:StatefulFunction} 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. @@ -617,5 +627,7 @@ Figure~\ref{f:CFibonacciSim} shows the C implementation of the \CFA generator only needs one additional field, @next@, to handle retention of execution state. The computed @goto@ at the start of the generator main, which branches after the previous suspend, adds very little cost to the resume call. -Finally, an explicit generator type provides both design and performance benefits, such as multiple type-safe interface functions taking and returning arbitrary types. +Finally, an explicit generator type provides both design and performance benefits, such as multiple type-safe interface functions taking and returning arbitrary types.\footnote{ +The \CFA operator syntax uses \lstinline|?| to denote operands, which allows precise definitions for pre, post, and infix operators, \eg \lstinline|++?|, \lstinline|?++|, and \lstinline|?+?|, in addition \lstinline|?\{\}| denotes a constructor, as in \lstinline|foo `f` = `\{`...`\}`|, \lstinline|^?\{\}| denotes a destructor, and \lstinline|?()| is \CC function call \lstinline|operator()|. +}% \begin{cfa} int ?()( Fib & fib ) { return `resume( fib )`.fn; } $\C[3.9in]{// function-call interface}$ @@ -1511,4 +1523,5 @@ \section{Mutual Exclusion / Synchronization} +\label{s:MutualExclusionSynchronization} Unrestricted nondeterminism is meaningless as there is no way to know when the result is completed without synchronization. @@ -1551,5 +1564,5 @@ higher-level mechanisms often simplify usage by adding better coupling between synchronization and data, \eg receive-specific versus receive-any thread in message passing or offering specialized solutions, \eg barrier lock. Often synchronization is used to order access to a critical section, \eg ensuring a waiting writer thread enters the critical section before a calling reader thread. -If the calling reader is scheduled before the waiting writer, the reader has \newterm{barged}. +If the calling reader is scheduled before the waiting writer, the reader has barged. Barging can result in staleness/freshness problems, where a reader barges ahead of a writer and reads temporally stale data, or a writer barges ahead of another writer overwriting data with a fresh value preventing the previous value from ever being read (lost computation). Preventing or detecting barging is an involved challenge with low-level locks, which is made easier through higher-level constructs. @@ -2120,7 +2133,7 @@ -\subsection{Extended \protect\lstinline@waitfor@} - -Figure~\ref{f:ExtendedWaitfor} show the extended form of the @waitfor@ statement to conditionally accept one of a group of mutex functions, with an optional statement to be performed \emph{after} the mutex function finishes. +\subsection{\texorpdfstring{Extended \protect\lstinline@waitfor@}{Extended waitfor}} + +Figure~\ref{f:ExtendedWaitfor} shows the extended form of the @waitfor@ statement to conditionally accept one of a group of mutex functions, with an optional statement to be performed \emph{after} the mutex function finishes. For a @waitfor@ clause to be executed, its @when@ must be true and an outstanding call to its corresponding member(s) must exist. The \emph{conditional-expression} of a @when@ may call a function, but the function must not block or context switch. @@ -2131,4 +2144,5 @@ Hence, the terminating @else@ clause allows a conditional attempt to accept a call without blocking. If both @timeout@ and @else@ clause are present, the @else@ must be conditional, or the @timeout@ is never triggered. +There is also a traditional future wait queue (not shown) (\eg Microsoft (@WaitForMultipleObjects@)), to wait for a specified number of future elements in the queue. \begin{figure} @@ -2355,5 +2369,5 @@ -\subsection{\protect\lstinline@mutex@ Threads} +\subsection{\texorpdfstring{\protect\lstinline@mutex@ Threads}{mutex Threads}} Threads in \CFA can also be monitors to allow \emph{direct communication} among threads, \ie threads can have mutex functions that are called by other threads. @@ -2499,6 +2513,6 @@ \renewcommand{\arraystretch}{1.25} %\setlength{\tabcolsep}{5pt} -\begin{tabular}{c|c|l|l} -\multicolumn{2}{c|}{object properties} & \multicolumn{2}{c}{mutual exclusion} \\ +\begin{tabular}{c|c||l|l} +\multicolumn{2}{c||}{object properties} & \multicolumn{2}{c}{mutual exclusion} \\ \hline thread & stateful & \multicolumn{1}{c|}{No} & \multicolumn{1}{c}{Yes} \\ @@ -2605,5 +2619,5 @@ -\section{\protect\CFA Runtime Structure} +\section{Runtime Structure} \label{s:CFARuntimeStructure} @@ -2709,5 +2723,5 @@ \section{Performance} -\label{results} +\label{s:Performance} To verify the implementation of the \CFA runtime, a series of microbenchmarks are performed comparing \CFA with pthreads, Java OpenJDK-9, Go 1.12.6 and \uC 7.0.0. @@ -2715,5 +2729,5 @@ The benchmark computer is an AMD Opteron\texttrademark\ 6380 NUMA 64-core, 8 socket, 2.5 GHz processor, running Ubuntu 16.04.6 LTS, and \CFA/\uC are compiled with gcc 6.5. -All benchmarks are run using the following harness. +All benchmarks are run using the following harness. (The Java harness is augmented to circumvent JIT issues.) \begin{cfa} unsigned int N = 10_000_000; @@ -2754,13 +2768,150 @@ \begin{tabular}[t]{@{}r*{3}{D{.}{.}{5.2}}@{}} \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ -\CFA Coroutine Lazy & 14.3 & 14.3 & 0.32 \\ -\CFA Coroutine Eager & 522.8 & 525.3 & 5.81 \\ -\CFA Thread & 1257.8 & 1291.2 & 86.19 \\ -\uC Coroutine & 92.2 & 91.4 & 1.58 \\ -\uC Thread & 499.5 & 500.1 & 5.67 \\ -Goroutine & 4397.0 & 4362.8 & 390.77 \\ -Java Thread & 107405.0 & 107794.8 & 1601.33 \\ -% Qthreads & 159.9 & 159.6 & 0.73 \\ -Pthreads & 32920.9 & 32882.7 & 213.55 +\CFA Coroutine Lazy & 13.2 & 13.1 & 0.44 \\ +\CFA Coroutine Eager & 531.3 & 536.0 & 26.54 \\ +\CFA Thread & 2074.9 & 2066.5 & 170.76 \\ +\uC Coroutine & 89.6 & 90.5 & 1.83 \\ +\uC Thread & 528.2 & 528.5 & 4.94 \\ +Goroutine & 4068.0 & 4113.1 & 414.55 \\ +Java Thread & 103848.5 & 104295.4 & 2637.57 \\ +Pthreads & 33112.6 & 33127.1 & 165.90 +\end{tabular} +\end{multicols} + + +\paragraph{Context-Switching} + +In procedural programming, the cost of a function call is important as modularization (refactoring) increases. +(In many cases, a compiler inlines function calls to eliminate this cost.) +Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor. +The coroutine test is from resumer to suspender and from suspender to resumer, which is two context switches. +The thread test is using yield to enter and return from the runtime kernel, which is two context switches. +The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling. +Figure~\ref{f:ctx-switch} only shows the \CFA code for coroutines/threads (other systems are similar) with all results in Table~\ref{tab:ctx-switch}. + +\begin{multicols}{2} +\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} +\begin{cfa}[aboveskip=0pt,belowskip=0pt] +@coroutine@ C {} c; +void main( C & ) { for ( ;; ) { @suspend;@ } } +int main() { // coroutine test + BENCH( for ( N ) { @resume( c );@ } ) + sout | result`ns; +} +int main() { // task test + BENCH( for ( N ) { @yield();@ } ) + sout | result`ns; +} +\end{cfa} +\captionof{figure}{\CFA context-switch benchmark} +\label{f:ctx-switch} + +\columnbreak + +\vspace*{-16pt} +\captionof{table}{Context switch comparison (nanoseconds)} +\label{tab:ctx-switch} +\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} +\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ +C function & 1.8 & 1.8 & 0.01 \\ +\CFA generator & 2.4 & 2.2 & 0.25 \\ +\CFA Coroutine & 36.2 & 36.2 & 0.25 \\ +\CFA Thread & 93.2 & 93.5 & 2.09 \\ +\uC Coroutine & 52.0 & 52.1 & 0.51 \\ +\uC Thread & 96.2 & 96.3 & 0.58 \\ +Goroutine & 141.0 & 141.3 & 3.39 \\ +Java Thread & 374.0 & 375.8 & 10.38 \\ +Pthreads Thread & 361.0 & 365.3 & 13.19 +\end{tabular} +\end{multicols} + + +\paragraph{Mutual-Exclusion} + +Uncontented mutual exclusion, which frequently occurs, is measured by entering/leaving a critical section. +For monitors, entering and leaving a monitor function is measured. +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. +Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}. +Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. + +\begin{multicols}{2} +\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} +\begin{cfa} +@monitor@ M {} m1/*, m2, m3, m4*/; +void __attribute__((noinline)) +do_call( M & @mutex m/*, m2, m3, m4*/@ ) {} +int main() { + BENCH( + for( N ) do_call( m1/*, m2, m3, m4*/ ); + ) + sout | result`ns; +} +\end{cfa} +\captionof{figure}{\CFA acquire/release mutex benchmark} +\label{f:mutex} + +\columnbreak + +\vspace*{-16pt} +\captionof{table}{Mutex comparison (nanoseconds)} +\label{tab:mutex} +\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} +\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ +test and test-and-test lock & 19.1 & 18.9 & 0.40 \\ +\CFA @mutex@ function, 1 arg. & 45.9 & 46.6 & 1.45 \\ +\CFA @mutex@ function, 2 arg. & 105.0 & 104.7 & 3.08 \\ +\CFA @mutex@ function, 4 arg. & 165.0 & 167.6 & 5.65 \\ +\uC @monitor@ member rtn. & 54.0 & 53.7 & 0.82 \\ +Java synchronized method & 31.0 & 31.1 & 0.50 \\ +Pthreads Mutex Lock & 33.6 & 32.6 & 1.14 +\end{tabular} +\end{multicols} + + +\paragraph{External Scheduling} + +External scheduling is measured using a cycle of two threads calling and accepting the call using the @waitfor@ statement. +Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}. +Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. + +\begin{multicols}{2} +\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} +\vspace*{-16pt} +\begin{cfa} +volatile int go = 0; +@monitor@ M {} m; +thread T {}; +void __attribute__((noinline)) +do_call( M & @mutex@ ) {} +void main( T & ) { + while ( go == 0 ) { yield(); } + while ( go == 1 ) { do_call( m ); } +} +int __attribute__((noinline)) +do_wait( M & @mutex@ m ) { + go = 1; // continue other thread + BENCH( for ( N ) { @waitfor( do_call, m );@ } ) + go = 0; // stop other thread + sout | result`ns; +} +int main() { + T t; + do_wait( m ); +} +\end{cfa} +\captionof{figure}{\CFA external-scheduling benchmark} +\label{f:ext-sched} + +\columnbreak + +\vspace*{-16pt} +\captionof{table}{External-scheduling comparison (nanoseconds)} +\label{tab:ext-sched} +\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} +\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ +\CFA @waitfor@, 1 @monitor@ & 376.4 & 376.8 & 7.63 \\ +\CFA @waitfor@, 2 @monitor@ & 491.4 & 492.0 & 13.31 \\ +\CFA @waitfor@, 4 @monitor@ & 681.0 & 681.7 & 19.10 \\ +\uC @_Accept@ & 331.1 & 331.4 & 2.66 \end{tabular} \end{multicols} @@ -2810,149 +2961,10 @@ \begin{tabular}{@{}r*{3}{D{.}{.}{5.2}}@{}} \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ -\CFA @signal@, 1 @monitor@ & 367.0 & 371.5 & 17.34 \\ -\CFA @signal@, 2 @monitor@ & 477.2 & 478.6 & 8.31 \\ -\CFA @signal@, 4 @monitor@ & 725.8 & 734.0 & 17.98 \\ -\uC @signal@ & 322.8 & 323.0 & 3.64 \\ -Java @notify@ & 16520.0 & 20096.7 & 9378.53 \\ -Pthreads Cond. Variable & 4931.3 & 5057.0 & 326.80 -\end{tabular} -\end{multicols} - - -\paragraph{External Scheduling} - -External scheduling is measured using a cycle of two threads calling and accepting the call using the @waitfor@ statement. -Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}. -Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. - -\begin{multicols}{2} -\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} -\vspace*{-16pt} -\begin{cfa} -volatile int go = 0; -@monitor@ M {} m; -thread T {}; -void __attribute__((noinline)) -do_call( M & @mutex@ ) {} -void main( T & ) { - while ( go == 0 ) { yield(); } - while ( go == 1 ) { do_call( m ); } -} -int __attribute__((noinline)) -do_wait( M & @mutex@ m ) { - go = 1; // continue other thread - BENCH( for ( N ) { @waitfor( do_call, m );@ } ) - go = 0; // stop other thread - sout | result`ns; -} -int main() { - T t; - do_wait( m ); -} -\end{cfa} -\captionof{figure}{\CFA external-scheduling benchmark} -\label{f:ext-sched} - -\columnbreak - -\vspace*{-16pt} -\captionof{table}{External-scheduling comparison (nanoseconds)} -\label{tab:ext-sched} -\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} -\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ -\CFA @waitfor@, 1 @monitor@ & 366.7 & 369.5 & 7.52 \\ -\CFA @waitfor@, 2 @monitor@ & 453.6 & 455.8 & 12.38 \\ -\CFA @waitfor@, 4 @monitor@ & 671.6 & 672.4 & 14.16 \\ -\uC @_Accept@ & 336.0 & 335.8 & 3.22 -\end{tabular} -\end{multicols} - - -\paragraph{Context-Switching} - -In procedural programming, the cost of a function call is important as modularization (refactoring) increases. -(In many cases, a compiler inlines function calls to eliminate this cost.) -Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor. -The coroutine test is from resumer to suspender and from suspender to resumer, which is two context switches. -The thread test is using yield to enter and return from the runtime kernel, which is two context switches. -The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling. -Figure~\ref{f:ctx-switch} only shows the \CFA code for coroutines/threads (other systems are similar) with all results in Table~\ref{tab:ctx-switch}. - -\begin{multicols}{2} -\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} -\begin{cfa}[aboveskip=0pt,belowskip=0pt] -@coroutine@ C {} c; -void main( C & ) { for ( ;; ) { @suspend;@ } } -int main() { // coroutine test - BENCH( for ( N ) { @resume( c );@ } ) - sout | result`ns; -} -int main() { // task test - BENCH( for ( N ) { @yield();@ } ) - sout | result`ns; -} -\end{cfa} -\captionof{figure}{\CFA context-switch benchmark} -\label{f:ctx-switch} - -\columnbreak - -\vspace*{-16pt} -\captionof{table}{Context switch comparison (nanoseconds)} -\label{tab:ctx-switch} -\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} -\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ -C function & 1.8 & 1.8 & 0 \\ -\CFA generator & 2.7 & 2.4 & 0.27 \\ -\CFA Coroutine & 37.8 & 37.7 & 0.22 \\ -\CFA Thread & 93.6 & 93.8 & 1.46 \\ -\uC Coroutine & 52.7 & 52.8 & 0.28 \\ -\uC Thread & 93.4 & 93.7 & 1.04 \\ -Goroutine & 140.0 & 139.7 & 2.93 \\ -Java Thread & 374.0 & 375.8 & 10.38 \\ -% Qthreads Thread & 159.5 & 159.3 & 0.71 \\ -Pthreads Thread & 334.4 & 335.0 & 1.95 \\ -\end{tabular} -\end{multicols} - - -\paragraph{Mutual-Exclusion} - -Uncontented mutual exclusion, which frequently occurs, is measured by entering/leaving a critical section. -For monitors, entering and leaving a monitor function is measured. -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. -Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}. -Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. - -\begin{multicols}{2} -\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} -\begin{cfa} -@monitor@ M {} m1/*, m2, m3, m4*/; -void __attribute__((noinline)) -do_call( M & @mutex m/*, m2, m3, m4*/@ ) {} -int main() { - BENCH( - for( N ) do_call( m1/*, m2, m3, m4*/ ); - ) - sout | result`ns; -} -\end{cfa} -\captionof{figure}{\CFA acquire/release mutex benchmark} -\label{f:mutex} - -\columnbreak - -\vspace*{-16pt} -\captionof{table}{Mutex comparison (nanoseconds)} -\label{tab:mutex} -\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} -\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ -test and test-and-test lock & 19.1 & 19.0 & 0.36 \\ -\CFA @mutex@ function, 1 arg. & 46.6 & 46.8 & 0.86 \\ -\CFA @mutex@ function, 2 arg. & 84.1 & 85.3 & 1.86 \\ -\CFA @mutex@ function, 4 arg. & 158.6 & 160.7 & 3.07 \\ -\uC @monitor@ member rtn. & 54.0 & 53.7 & 0.83 \\ -Java synchronized method & 27.0 & 27.1 & 0.25 \\ -Pthreads Mutex Lock & 33.6 & 32.7 & 1.12 +\CFA @signal@, 1 @monitor@ & 372.6 & 374.3 & 14.17 \\ +\CFA @signal@, 2 @monitor@ & 492.7 & 494.1 & 12.99 \\ +\CFA @signal@, 4 @monitor@ & 749.4 & 750.4 & 24.74 \\ +\uC @signal@ & 320.5 & 321.0 & 3.36 \\ +Java @notify@ & 10160.5 & 10169.4 & 267.71 \\ +Pthreads Cond. Variable & 4949.6 & 5065.2 & 363 \end{tabular} \end{multicols} Index: doc/proposals/operator-defaults.md =================================================================== --- doc/proposals/operator-defaults.md (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) +++ doc/proposals/operator-defaults.md (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -0,0 +1,281 @@ +Operator Defaults +================= + +This proposal introduces a new syntax for requesting a default implementation +of an operator and the rules for generating them. + +This is to build on the implied relationships between operators. Most default +operators will be implemented in terms of other operators. As a fall-back +operators can try to figure out an intuitive definition from inspection of the +type's sue declaration. + +Syntax +------ + +The syntax for requesting a default implementation is part of function +definition. After the function signature (after the parameter list) instead +of putting the function body you declare it to be equal to default. + + box ?+?(box const & left, box const & right) = default; + +These can exist along side any forward definitions of the function, but would +conflict with any other complete definitions or deletions of the function. + +It could be valid syntax on any function, but possibly all non-operators would +report that no default implementation available. + +If default implementations are really popular and we don't need additional +information about the signature a more compact syntax could be added. + + default box( ?(), ?=?, ?!=?, ??, ?<=?, ?>=? ); + +Generation Strategies +--------------------- + +There exists a system around the default generation that selects how to +generate a given function if one can be generated at all. This section +describes that system and some of the logic behind it. + +There are two main strategies for generating an operator implementation. + +The first is to mimic the relationship between operators on the primitive +types by defining a new operator in terms of an existing operator on the same +type. For instance `++i` is equivalent to `i += 1`, so the generated +implementation will "look like" that. + +The second is to inspect the structure of the declaration to guess at what +the default implementation would be. Because of that it is dependent on the +kind of declaration, a structure doesn't have the same rules as an +enumeration. Also it is similar to the implicate definitions currently created +by the compiler and the generation methods for many are carried over. + +From these strategies a method of generation (a particular set of rules that +define an implementation from the type and existing functions) has to be +picked, but often there is more than on reasonable choice. In these cases they +are ordered and the first (best) one whose requirements is met is then used. +See "Circular Requirements" below for some exceptions and extensions to this +pattern. + +Generally the methods based on operators come first as they propagate any +unusual implementations from the explicate operators to the ones being +generated. If all of those fail then the intuitive definition based on the +declaration's shape is used. The general patterns in this area for the +different sue types follow. + +### Structures +Structures will usually apply the operation to each field, or when there are +two parameters the matching pairs of fields from each, and then combine the +results. + +This does require that the fields have certain operators defined on them. +In this respect it is still operator based generation, but we use inspection +on the structure to find out which operators to use. + +Also, for the purposes of default generation types declared with the +concurrency modifiers (coroutine, monitor and thread) are considered structs. +The default implementations should be the same as if you had written out the +extra field and functions by hand. + +### Enumerations +The two ways of using enumerations are considered. First as "one of" the +list options as in normal use, the second is as a set of flags where each +option represents a flag that may or may not be set. + +Currently there is no way to specify which nor does the system attempt to +guess by checking assigned values. There is one case where an operator could +have a meaningful default in both versions. If both are included then we can +try to pick one by scanning the enumeration to see what values its options +are given (a linear series or powers of 2) could be used. In all other cases +the definition that makes sense can be assumed. + +### Unions +Unions are the hardest to deal with because the instance does not show which +field in the union is being used. Because of that there are very few intuitive +definitions to use and the ones that do depend on bit-wise operations and only +if the union is made of primitive types. + +### Traits +Default operations are not supported on traits. A function implemented by the +default generation may be used to satisfy an assertion. However a default +implementation may not be requested on a polymorphic function. + +It could in theory, limiting to operation based generation and using the +operations available in the assertion list. There are a few problems: ++ Knowing the entire set of functions being generated is very useful in some + cases and this information is quickly lost with polymorphic functions. ++ The rules for choosing a generation method do not match how a polymorphic + function is selected so the results can be inconsistent. ++ It is easily to mimic with a polymorphic function already, writing out one + generic function and including it. + +Default Generation +------------------ + +Here are the generation methods. Unless otherwise stated they are listed in +priority order. That is the first one mentioned that a type fits (has all the +required operators or its form matches) will be used. + +The operator based constructions can be used on any sue type, those that +require a particular kind mention that. + +### Constructor: ?{} +Note that requesting any constructor to be generated counts as defining a +constructor for purposes of disabling the implicate constructors. There are +no operator based methods for generating constructors. + +For structures: For the zero argument constructor (aka the default constructor, +which takes just a reference to the value to construct) each field is +constructed with its zero argument constructor. For the copy constructor each +field is copy constructed from the same field in the copied structure. For +zero_t and one_t each field is also constructed from zero_t or one_t. + +For enumerations: For the zero argument constructor the value is set to 0 if +one of the enumeration options is 0 (or set to the first value in the enum). +For the zero_t constructor it is the same except the check is skipped (and no +or). The copy constructor is the same as memcpy. + +For unions: For the zero argument constructor of a union that is constructed +entirely of primitive types (or other types that zero argument construct to +all 0s) the union filled with 0s. For the copy constructor of a union of types +that all have trivial copy constructors memcpy is used. + +### Destructor: ^?{} +Requesting the default destructor should be the same as having it implicitly +defined. Destructors only have one signature and the intuitive definition for +that is the same as without the signature. + +Still it should be allowed for consistency. It also allows it to be forward +declared and then generated in a .cfa file. + +### Assignment: ?=? +Default assignment is only supported between two objects of the same type. +For structures it is field to field assignment. For enumerations and unions +of primitives or trivially copiable types it the same as memcpy. + +### Equality: ?==? ?!=? +Both equality operations can be implemented by negating the result of the +other operations. + +For structures: Equality can be implement by checking equality on each pair of +matching fields and taking the logical and of the results. Inequality can be +implemented by checking inequality on each pair of matching fields and taking +the logical or of the results. + +Both logical operations could be short circuiting. Without side effects it is +purely an optimization. + +For enumerations: Both operations are the same as on the underlying integral. + +For unions: If it is assumed that the different branches represent different +views of the same data and this data is primitive, than bit-wise comparisons +can be used. + +### Comparison: ?? ?<=? ?>=? +Less than can be implemented by flipping the arguments on greater than. +Greater than can be implemented by flipping less then. Less than or equal to +can be implemented by flipping greater than or equal to. Greater than or equal +to can be implemented by flipping less than or equal to. + +Less than or equal to can be implemented by using less than, equals and taking +the or of the results. Greater than or equal to can be implemented by using +greater than, equals and taking the or of the results. + +> The trick of negating comparisons is not used. As an example ? (boolean) not ?>=? unless the type is strictly ordered. For operator based +> overloads that might not be true in very reasonable implementations so it is +> not assumed. + +Opposite less than can be implemented as less than or equal to and not equal +to. Greater than can be implemented as greater than or equal to and not equal +to. + +For enumerations: Enumerations that represent one of all operations are the +same as on the underlying integral. Enumerations that represent a set of +options could replace less then with subset of and greator than with superset +of and use bit-wise masking to implement those operations. + +### Binary & Relative Assignment Operators: ?_? ?_=? +This applies to each operator in the form of `T ?_?(T, T);` for some type T +and has a matching relative assignment operator `T& ?_=?(T&, T)` where the +`_` in both is replaced by some string of operator characters. + +The binary operator can be created by copying the left argument, using the +relative assignment with the right argument and returning the updated copy. + +The relative assignment operator can be implemented by using the binary +operation to create a copy, then assigning the result to the left argument. +The left argument should then be returned. For the signature above it would +return by reference. The signature `T ?_=?(T&, T)` could also be supported in +which case it would return by copy. + +### Minus: -? ?-? +Unary minus can be implemented by subtracting argument from the value created +from zero_t. + +Binary minus can be implemented by negating (with unary minus) the right +argument and adding the result to the left argument. + +### Increment & Decrement: ++? ?++ --? ?-- +Either pre- operation can implemented by applying the post- operation and then +returning a reference to, or copy of, the updated value. Either post- +operation can be implemented by copying the argument, applying the pre- +operation to the original and returning the copy. + +Pre-increment can be implemented by using addition assignment by the value +constructed from one_t. Pre-decrement can be implemented by using subtraction +assignment by the value from one_t. + +Because many of the operations used have there own default implementations +(for example: ?+=? from ?+? or field-wise one_t construction) this list could +be expanded by replacing a function call with the default implementation for +that function. This might work for the post- operations generated from +relative assignment, the one_t constructed object and copying, but the logical +connection becomes weaker and weaker as that process continues. + +### Bit Manipulation: ?|? ?&? ~? ?<>? +No operation based construction is provided for bit manipulation operators. + +For enumerations that are considered sets of flags: And returns a set with all +flags set in both operand sets, or returns a set with all flags set that are +set in either operand sets and not returns a set with all flags set that are +not set in the operand set. + +> And it would be possible to actually implement this for any sized type and +> just do the bitwise operation and trust the user that it makes sense if they +> request it. + +Also for set enumerations, the signature `T ?< @@ -264,14 +264,23 @@ for (auto cvq : qualifiersPair) { for (auto is_vol : { " ", "volatile" }) { - cout << "forall(dtype DT) void ?{}(" << cvq.first << type << " * " << is_vol << " &, " << cvq.second << "DT *);" << endl; + cout << "forall(dtype DT) void ?{}(" << cvq.first << type << " * " << is_vol << " &, " << cvq.second << "DT *);" << endl; } } - for (auto cvq : qualifiersSingle) { - for (auto is_vol : { " ", "volatile" }) { - cout << "forall(dtype DT) void ?{}(" << cvq << type << " * " << is_vol << " &);" << endl; - } - for (auto is_vol : { " ", "volatile" }) { - cout << "forall(dtype DT) void ^?{}(" << cvq << type << " * " << is_vol << " &);" << endl; - } + } + for (auto cvq : qualifiersSingle) { + for (auto is_vol : { " ", "volatile" }) { + cout << "void ?{}(" << cvq << "void" << " * " << is_vol << " &);" << endl; + } + for (auto is_vol : { " ", "volatile" }) { + cout << "void ^?{}(" << cvq << "void" << " * " << is_vol << " &);" << endl; + } + } + + for (auto cvq : qualifiersSingle) { + for (auto is_vol : { " ", "volatile" }) { + cout << "forall(dtype DT) void ?{}(" << cvq << " DT" << " * " << is_vol << " &);" << endl; + } + for (auto is_vol : { " ", "volatile" }) { + cout << "forall(dtype DT) void ^?{}(" << cvq << " DT" << " * " << is_vol << " &);" << endl; } } @@ -288,5 +297,5 @@ cout << endl; - cout << "forall(ftype FT) void ?{}( FT * &, zero_t ); " << endl; + cout << "forall(ftype FT) void ?{}( FT * &, zero_t );" << endl; cout << "forall(ftype FT) FT * ?=?( FT * &, zero_t );" << endl; cout << "forall(ftype FT) FT * ?=?( FT * volatile &, zero_t );" << endl; Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ libcfa/src/heap.cfa (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Tue Dec 19 21:58:35 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Jul 19 16:07:46 2019 -// Update Count : 548 +// Last Modified On : Wed Jul 24 13:12:45 2019 +// Update Count : 550 // @@ -248,6 +248,5 @@ #ifdef FASTLOOKUP -static_assert( 16 == sizeof(HeapManager.Storage), "size of HeapManager Storage wrong" ); // FIX ME -enum { LookupSizes = 65_536 + 16 }; // number of fast lookup sizes +enum { LookupSizes = 65_536 + sizeof(HeapManager.Storage) }; // number of fast lookup sizes static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes #endif // FASTLOOKUP @@ -869,5 +868,5 @@ void * area; if ( unlikely( alignment != 0 ) ) { // previous request memalign? - area = memalign( alignment, size ); // create new area + area = memalign( alignment, size ); // create new aligned area } else { area = mallocNoStats( size ); // create new area Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ libcfa/src/stdlib.hfa (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Apr 24 17:35:43 2019 -// Update Count : 352 +// Last Modified On : Tue Jul 23 14:14:59 2019 +// Update Count : 373 // @@ -17,6 +17,8 @@ #include "bits/defs.hfa" +#include "bits/align.hfa" #include // *alloc, strto*, ato* + extern "C" { void * memalign( size_t align, size_t size ); // malloc.h @@ -39,12 +41,15 @@ T * malloc( void ) { - return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + if ( _Alignof(T) <= libAlign() ) return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + else return (T *)memalign( _Alignof(T), sizeof(T) ); } // malloc T * calloc( size_t dim ) { - return (T *)(void *)calloc( dim, sizeof(T) ); // C calloc + if ( _Alignof(T) <= libAlign() )return (T *)(void *)calloc( dim, sizeof(T) ); // C calloc + else return (T *)cmemalign( _Alignof(T), dim, sizeof(T) ); } // calloc T * realloc( T * ptr, size_t size ) { + if ( unlikely( ptr == 0 ) ) return malloc(); return (T *)(void *)realloc( (void *)ptr, size ); } // realloc @@ -66,28 +71,27 @@ T * alloc( void ) { - return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + return malloc(); } // alloc T * alloc( char fill ) { - T * ptr = (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + T * ptr; + if ( _Alignof(T) <= libAlign() ) ptr = (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + else ptr = (T *)memalign( _Alignof(T), sizeof(T) ); return (T *)memset( ptr, (int)fill, sizeof(T) ); // initialize with fill value } // alloc T * alloc( size_t dim ) { - return (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C malloc + if ( _Alignof(T) <= libAlign() ) return (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C malloc + else return (T *)memalign( _Alignof(T), dim * sizeof(T) ); } // alloc T * alloc( size_t dim, char fill ) { - T * ptr = (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C calloc - return (T *)memset( ptr, (int)fill, dim * sizeof(T) ); // initialize with fill value + return (T *)memset( (T *)alloc( dim ), (int)fill, dim * sizeof(T) ); // initialize with fill value } // alloc T * alloc( T ptr[], size_t dim ) { - return (T *)(void *)realloc( (void *)ptr, dim * (size_t)sizeof(T) ); // C realloc - } // alloc -} // distribution - - -forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim, char fill ); + return realloc( ptr, dim * sizeof(T) ); + } // alloc +} // distribution @@ -107,14 +111,13 @@ T * align_alloc( size_t align, size_t dim, char fill ) { - T * ptr; if ( fill == '\0' ) { - ptr = (T *)cmemalign( align, dim, sizeof(T) ); + return (T *)cmemalign( align, dim, sizeof(T) ); } else { - ptr = (T *)memalign( align, dim * sizeof(T) ); - return (T *)memset( ptr, (int)fill, dim * sizeof(T) ); + return (T *)memset( (T *)memalign( align, dim * sizeof(T) ), (int)fill, dim * sizeof(T) ); } // if - return ptr; - } // align_alloc -} // distribution + } // align_alloc +} // distribution + +forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim, char fill ); Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/AST/Convert.cpp (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Thierry Delisle // Created On : Thu May 09 15::37::05 2019 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Jun 17 16:44:00 2019 -// Update Count : 12 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jul 25 22:21:46 2019 +// Update Count : 13 // @@ -2676,8 +2676,4 @@ ); } - - virtual void visit( const AttrExpr * ) override final { - assertf( false, "AttrExpr deprecated in new AST." ); - } }; Index: src/AST/porting.md =================================================================== --- src/AST/porting.md (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/AST/porting.md (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -171,7 +171,4 @@ * all existing uses assume `type` set if true and don't use `expr` -`AttrExpr` -* did not port due to feature deprecation (e.g. `expr@attribute`) - `LogicalExpr` * un-defaulted constructor parameter determining `&&` or `||` Index: src/Common/Eval.cc =================================================================== --- src/Common/Eval.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Common/Eval.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun May 6 22:24:16 2018 -// Update Count : 40 +// Last Modified On : Wed Jul 24 15:09:06 2019 +// Update Count : 64 // @@ -27,12 +27,15 @@ bool valid = true; - void previsit( BaseSyntaxNode * ) { visit_children = false; } - void postvisit( BaseSyntaxNode * ) { valid = false; } + void previsit( const BaseSyntaxNode * ) { visit_children = false; } + void postvisit( const BaseSyntaxNode * ) { valid = false; } - void postvisit( ConstantExpr * expr ) { + void postvisit( const SizeofExpr * ) { + } + + void postvisit( const ConstantExpr * expr ) { value = expr->intValue(); } - void postvisit( CastExpr * expr ) { + void postvisit( const CastExpr * expr ) { auto arg = eval(expr->arg); valid = arg.second; @@ -41,5 +44,5 @@ } - void postvisit( VariableExpr * expr ) { + void postvisit( const VariableExpr * const expr ) { if ( EnumInstType * inst = dynamic_cast(expr->result) ) { if ( EnumDecl * decl = inst->baseEnum ) { @@ -52,6 +55,6 @@ } - void postvisit( ApplicationExpr * expr ) { - DeclarationWithType * function = InitTweak::getFunction(expr); + void postvisit( const ApplicationExpr * expr ) { + DeclarationWithType * function = InitTweak::getFunction(const_cast(expr)); if ( ! function || function->linkage != LinkageSpec::Intrinsic ) { valid = false; return; } const std::string & fname = function->name; @@ -94,4 +97,10 @@ void postvisit( const ast::ConstantExpr * expr ) { value = expr->intValue(); + } + + void postvisit( const ast::SizeofExpr * expr ) { + if ( expr->expr ) value = eval(expr->expr).first; + else if ( expr->type ) value = eval(expr->expr).first; + else SemanticError( expr->location, ::toString( "Internal error: SizeofExpr has no expression or type value" ) ); } @@ -145,5 +154,5 @@ }; -std::pair eval(Expression * expr) { +std::pair eval( const Expression * expr) { PassVisitor ev; if (expr) { Index: src/Common/PassVisitor.h =================================================================== --- src/Common/PassVisitor.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Common/PassVisitor.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -155,6 +155,4 @@ virtual void visit( OffsetPackExpr * offsetPackExpr ) override final; virtual void visit( const OffsetPackExpr * offsetPackExpr ) override final; - virtual void visit( AttrExpr * attrExpr ) override final; - virtual void visit( const AttrExpr * attrExpr ) override final; virtual void visit( LogicalExpr * logicalExpr ) override final; virtual void visit( const LogicalExpr * logicalExpr ) override final; @@ -301,5 +299,4 @@ virtual Expression * mutate( OffsetofExpr * offsetofExpr ) override final; virtual Expression * mutate( OffsetPackExpr * offsetPackExpr ) override final; - virtual Expression * mutate( AttrExpr * attrExpr ) override final; virtual Expression * mutate( LogicalExpr * logicalExpr ) override final; virtual Expression * mutate( ConditionalExpr * conditionalExpr ) override final; Index: src/Common/PassVisitor.impl.h =================================================================== --- src/Common/PassVisitor.impl.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Common/PassVisitor.impl.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -2302,49 +2302,4 @@ //-------------------------------------------------------------------------- -// AttrExpr -template< typename pass_type > -void PassVisitor< pass_type >::visit( AttrExpr * node ) { - VISIT_START( node ); - - indexerScopedAccept( node->result, *this ); - if ( node->get_isType() ) { - maybeAccept_impl( node->type, *this ); - } else { - maybeAccept_impl( node->expr, *this ); - } - - VISIT_END( node ); -} - -template< typename pass_type > -void PassVisitor< pass_type >::visit( const AttrExpr * node ) { - VISIT_START( node ); - - indexerScopedAccept( node->result, *this ); - if ( node->get_isType() ) { - maybeAccept_impl( node->type, *this ); - } else { - maybeAccept_impl( node->expr, *this ); - } - - VISIT_END( node ); -} - -template< typename pass_type > -Expression * PassVisitor< pass_type >::mutate( AttrExpr * node ) { - MUTATE_START( node ); - - indexerScopedMutate( node->env , *this ); - indexerScopedMutate( node->result, *this ); - if ( node->get_isType() ) { - maybeMutate_impl( node->type, *this ); - } else { - maybeMutate_impl( node->expr, *this ); - } - - MUTATE_END( Expression, node ); -} - -//-------------------------------------------------------------------------- // LogicalExpr template< typename pass_type > Index: src/Common/utility.h =================================================================== --- src/Common/utility.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Common/utility.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun May 6 22:24:16 2018 -// Update Count : 40 +// Last Modified On : Wed Jul 24 14:28:19 2019 +// Update Count : 41 // @@ -483,5 +483,5 @@ // ----------------------------------------------------------------------------- /// evaluates expr as a long long int. If second is false, expr could not be evaluated -std::pair eval(Expression * expr); +std::pair eval(const Expression * expr); namespace ast { Index: src/InitTweak/InitTweak.cc =================================================================== --- src/InitTweak/InitTweak.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/InitTweak/InitTweak.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Rob Schluntz // Created On : Fri May 13 11:26:36 2016 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jun 19 14:34:00 2019 -// Update Count : 6 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jul 25 22:21:48 2019 +// Update Count : 7 // @@ -957,5 +957,4 @@ void previsit( OffsetofExpr * ) {} void previsit( OffsetPackExpr * ) {} - void previsit( AttrExpr * ) {} void previsit( CommaExpr * ) {} void previsit( LogicalExpr * ) {} Index: src/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Parser/DeclarationNode.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Sat May 16 12:34:05 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Feb 1 16:49:17 2019 -// Update Count : 1113 +// Last Modified On : Thu Jul 25 22:17:10 2019 +// Update Count : 1116 // @@ -49,5 +49,5 @@ const char * DeclarationNode::aggregateNames[] = { "struct", "union", "trait", "coroutine", "monitor", "thread", "NoAggregateNames" }; const char * DeclarationNode::typeClassNames[] = { "otype", "dtype", "ftype", "NoTypeClassNames" }; -const char * DeclarationNode::builtinTypeNames[] = { "__builtin_va_list", "zero_t", "one_t", "NoBuiltinTypeNames" }; +const char * DeclarationNode::builtinTypeNames[] = { "__builtin_va_list", "__auto_type", "zero_t", "one_t", "NoBuiltinTypeNames" }; UniqueName DeclarationNode::anonymous( "__anonymous" ); @@ -418,22 +418,4 @@ return newnode; } // DeclarationNode::newBuiltinType - -DeclarationNode * DeclarationNode::newAttr( const string * name, ExpressionNode * expr ) { - DeclarationNode * newnode = new DeclarationNode; - newnode->type = nullptr; -// newnode->attr.name = name; - newnode->name = name; - newnode->attr.expr = expr; - return newnode; -} - -DeclarationNode * DeclarationNode::newAttr( const string * name, DeclarationNode * type ) { - DeclarationNode * newnode = new DeclarationNode; - newnode->type = nullptr; -// newnode->attr.name = name; - newnode->name = name; - newnode->attr.type = type; - return newnode; -} DeclarationNode * DeclarationNode::newAttribute( const string * name, ExpressionNode * expr ) { Index: src/Parser/ParseNode.h =================================================================== --- src/Parser/ParseNode.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Parser/ParseNode.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Sat May 16 13:28:16 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Apr 15 14:22:39 2019 -// Update Count : 874 +// Last Modified On : Thu Jul 25 22:17:10 2019 +// Update Count : 876 // @@ -221,5 +221,5 @@ enum TypeClass { Otype, Dtype, Ftype, Ttype, NoTypeClass }; static const char * typeClassNames[]; - enum BuiltinType { Valist, Zero, One, NoBuiltinType }; + enum BuiltinType { Valist, AutoType, Zero, One, NoBuiltinType }; static const char * builtinTypeNames[]; @@ -252,6 +252,4 @@ static DeclarationNode * newTuple( DeclarationNode * members ); static DeclarationNode * newTypeof( ExpressionNode * expr, bool basetypeof = false ); - static DeclarationNode * newAttr( const std::string *, ExpressionNode * expr ); // @ attributes - static DeclarationNode * newAttr( const std::string *, DeclarationNode * type ); // @ attributes static DeclarationNode * newAttribute( const std::string *, ExpressionNode * expr = nullptr ); // gcc attributes static DeclarationNode * newAsmStmt( StatementNode * stmt ); // gcc external asm statement Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Parser/lex.ll (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Wed May 15 21:25:27 2019 - * Update Count : 708 + * Last Modified On : Thu Jul 25 22:08:32 2019 + * Update Count : 716 */ @@ -59,5 +59,4 @@ #define QKEYWORD_RETURN(x) RETURN_VAL(x); // quasi-keyword #define IDENTIFIER_RETURN() RETURN_VAL( typedefTable.isKind( yytext ) ) -#define ATTRIBUTE_RETURN() RETURN_VAL( ATTR_IDENTIFIER ) #ifdef HAVE_KEYWORDS_FLOATXX // GCC >= 7 => keyword, otherwise typedef @@ -92,7 +91,4 @@ // identifier, GCC: $ in identifier identifier ([a-zA-Z_$]|{universal_char})([0-9a-zA-Z_$]|{universal_char})* - - // attribute identifier, GCC: $ in identifier -attr_identifier "@"{identifier} // numeric constants, CFA: '_' in constant @@ -218,4 +214,5 @@ __attribute__ { KEYWORD_RETURN(ATTRIBUTE); } // GCC auto { KEYWORD_RETURN(AUTO); } +__auto_type { KEYWORD_RETURN(AUTO_TYPE); } basetypeof { KEYWORD_RETURN(BASETYPEOF); } // CFA _Bool { KEYWORD_RETURN(BOOL); } // C99 @@ -292,4 +289,5 @@ __restrict__ { KEYWORD_RETURN(RESTRICT); } // GCC return { KEYWORD_RETURN(RETURN); } + /* resume { KEYWORD_RETURN(RESUME); } // CFA */ short { KEYWORD_RETURN(SHORT); } signed { KEYWORD_RETURN(SIGNED); } @@ -300,4 +298,5 @@ _Static_assert { KEYWORD_RETURN(STATICASSERT); } // C11 struct { KEYWORD_RETURN(STRUCT); } + /* suspend { KEYWORD_RETURN(SUSPEND); } // CFA */ switch { KEYWORD_RETURN(SWITCH); } thread { KEYWORD_RETURN(THREAD); } // C11 @@ -333,5 +332,4 @@ IDENTIFIER_RETURN(); } -{attr_identifier} { ATTRIBUTE_RETURN(); } /* numeric constants */ Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/Parser/parser.yy (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Jul 14 07:54:30 2019 -// Update Count : 4355 +// Last Modified On : Thu Jul 25 22:31:38 2019 +// Update Count : 4359 // @@ -272,4 +272,5 @@ %token ZERO_T ONE_T // CFA %token VALIST // GCC +%token AUTO_TYPE // GCC %token TYPEOF BASETYPEOF LABEL // GCC %token ENUM STRUCT UNION @@ -288,5 +289,4 @@ %token IDENTIFIER QUOTED_IDENTIFIER TYPEDEFname TYPEGENname %token TIMEOUT WOR -%token ATTR_IDENTIFIER ATTR_TYPEDEFname ATTR_TYPEGENname %token INTEGERconstant CHARACTERconstant STRINGliteral %token DIRECTIVE @@ -312,6 +312,6 @@ %token ATassign // @= -%type identifier no_attr_identifier -%type identifier_or_type_name no_attr_identifier_or_type_name attr_name +%type identifier +%type identifier_or_type_name attr_name %type quasi_keyword %type string_literal @@ -546,14 +546,9 @@ ; -no_attr_identifier: +identifier: IDENTIFIER | quasi_keyword | '@' // CFA { Token tok = { new string( DeclarationNode::anonymous.newName() ), yylval.tok.loc }; $$ = tok; } - ; - -identifier: - no_attr_identifier - | ATTR_IDENTIFIER // CFA ; @@ -594,5 +589,5 @@ | '(' comma_expression ')' '`' IDENTIFIER // CFA, postfix call { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $5 ) ), $2 ) ); } - | type_name '.' no_attr_identifier // CFA, nested type + | type_name '.' identifier // CFA, nested type { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; } | type_name '.' '[' field_name_list ']' // CFA, nested type / tuple field selector @@ -647,5 +642,5 @@ | postfix_expression '(' argument_expression_list ')' { $$ = new ExpressionNode( build_func( $1, $3 ) ); } - | postfix_expression '.' no_attr_identifier + | postfix_expression '.' identifier { $$ = new ExpressionNode( build_fieldSel( $1, build_varref( $3 ) ) ); } | postfix_expression '.' INTEGERconstant // CFA, tuple index @@ -655,5 +650,5 @@ | postfix_expression '.' '[' field_name_list ']' // CFA, tuple field selector { $$ = new ExpressionNode( build_fieldSel( $1, build_tuple( $4 ) ) ); } - | postfix_expression ARROW no_attr_identifier + | postfix_expression ARROW identifier { $$ = new ExpressionNode( build_pfieldSel( $1, build_varref( $3 ) ) ); } | postfix_expression ARROW INTEGERconstant // CFA, tuple index @@ -718,5 +713,5 @@ | FLOATINGconstant fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_field_name_FLOATINGconstant( *$1 ), $2 ) ); } - | no_attr_identifier fraction_constants_opt + | identifier fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_varref( $1 ), $2 ) ); @@ -776,12 +771,6 @@ | ALIGNOF '(' type_no_function ')' // GCC, type alignment { $$ = new ExpressionNode( new AlignofExpr( maybeMoveBuildType( $3 ) ) ); } - | OFFSETOF '(' type_no_function ',' no_attr_identifier ')' + | OFFSETOF '(' type_no_function ',' identifier ')' { $$ = new ExpressionNode( build_offsetOf( $3, build_varref( $5 ) ) ); } - | ATTR_IDENTIFIER - { $$ = new ExpressionNode( new AttrExpr( build_varref( $1 ), maybeMoveBuild< Expression >( (ExpressionNode *)nullptr ) ) ); } - | ATTR_IDENTIFIER '(' argument_expression ')' - { $$ = new ExpressionNode( new AttrExpr( build_varref( $1 ), maybeMoveBuild< Expression >( $3 ) ) ); } - | ATTR_IDENTIFIER '(' type ')' - { $$ = new ExpressionNode( new AttrExpr( build_varref( $1 ), maybeMoveBuildType( $3 ) ) ); } ; @@ -1018,5 +1007,5 @@ labeled_statement: - // labels cannot be identifiers 0 or 1 or ATTR_IDENTIFIER + // labels cannot be identifiers 0 or 1 identifier_or_type_name ':' attribute_list_opt statement { $$ = $4->add_label( $1, $3 ); } @@ -1386,5 +1375,5 @@ | type_specifier_nobody variable_abstract_declarator { $$ = $2->addType( $1 ); } - | cfa_abstract_declarator_tuple no_attr_identifier // CFA + | cfa_abstract_declarator_tuple identifier // CFA { $$ = $1->addName( $2 ); } | cfa_abstract_declarator_tuple // CFA @@ -1450,10 +1439,10 @@ label_list: - no_attr_identifier + identifier { $$ = new LabelNode(); $$->labels.push_back( *$1 ); delete $1; // allocated by lexer } - | label_list ',' no_attr_identifier + | label_list ',' identifier { $$ = $1; $1->labels.push_back( *$3 ); @@ -1500,6 +1489,6 @@ local_label_list: // GCC, local label - no_attr_identifier_or_type_name - | local_label_list ',' no_attr_identifier_or_type_name + identifier_or_type_name + | local_label_list ',' identifier_or_type_name ; @@ -1623,5 +1612,5 @@ $$ = $2->addTypedef(); } - | cfa_typedef_declaration pop ',' push no_attr_identifier + | cfa_typedef_declaration pop ',' push identifier { typedefTable.addToEnclosingScope( *$5, TYPEDEFname, "3" ); @@ -1663,10 +1652,10 @@ typedef_expression: // GCC, naming expression type: typedef name = exp; gives a name to the type of an expression - TYPEDEF no_attr_identifier '=' assignment_expression + TYPEDEF identifier '=' assignment_expression { // $$ = DeclarationNode::newName( 0 ); // unimplemented SemanticError( yylloc, "Typedef expression is currently unimplemented." ); $$ = nullptr; } - | typedef_expression pop ',' push no_attr_identifier '=' assignment_expression + | typedef_expression pop ',' push identifier '=' assignment_expression { // $$ = DeclarationNode::newName( 0 ); // unimplemented @@ -1871,4 +1860,6 @@ | VALIST // GCC, __builtin_va_list { $$ = DeclarationNode::newBuiltinType( DeclarationNode::Valist ); } + | AUTO_TYPE + { $$ = DeclarationNode::newBuiltinType( DeclarationNode::AutoType ); } ; @@ -1912,8 +1903,4 @@ | BASETYPEOF '(' comma_expression ')' // CFA: basetypeof( a+b ) y; { $$ = DeclarationNode::newTypeof( $3, true ); } - | ATTR_TYPEGENname '(' type ')' // CFA: e.g., @type( x ) y; - { $$ = DeclarationNode::newAttr( $1, $3 ); } - | ATTR_TYPEGENname '(' comma_expression ')' // CFA: e.g., @type( a+b ) y; - { $$ = DeclarationNode::newAttr( $1, $3 ); } | ZERO_T // CFA { $$ = DeclarationNode::newBuiltinType( DeclarationNode::Zero ); } @@ -2024,5 +2011,5 @@ '{' field_declaration_list_opt '}' type_parameters_opt { $$ = DeclarationNode::newAggregate( $1, nullptr, $7, $5, true )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt no_attr_identifier fred + | aggregate_key attribute_list_opt identifier fred { typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname ); // create typedef @@ -2050,5 +2037,5 @@ aggregate_type_nobody: // struct, union - {...} - aggregate_key attribute_list_opt no_attr_identifier fred + aggregate_key attribute_list_opt identifier fred { typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname ); @@ -2151,7 +2138,7 @@ cfa_field_declaring_list: // CFA, new style field declaration // bit-fields are handled by C declarations - cfa_abstract_declarator_tuple no_attr_identifier_or_type_name + cfa_abstract_declarator_tuple identifier_or_type_name { $$ = $1->addName( $2 ); } - | cfa_field_declaring_list ',' no_attr_identifier_or_type_name + | cfa_field_declaring_list ',' identifier_or_type_name { $$ = $1->appendList( $1->cloneType( $3 ) ); } ; @@ -2178,5 +2165,5 @@ ENUM attribute_list_opt '{' enumerator_list comma_opt '}' { $$ = DeclarationNode::newEnum( nullptr, $4, true )->addQualifiers( $2 ); } - | ENUM attribute_list_opt no_attr_identifier + | ENUM attribute_list_opt identifier { typedefTable.makeTypedef( *$3 ); } '{' enumerator_list comma_opt '}' @@ -2189,5 +2176,5 @@ enum_type_nobody: // enum - {...} - ENUM attribute_list_opt no_attr_identifier + ENUM attribute_list_opt identifier { typedefTable.makeTypedef( *$3 ); @@ -2202,7 +2189,7 @@ enumerator_list: - no_attr_identifier_or_type_name enumerator_value_opt + identifier_or_type_name enumerator_value_opt { $$ = DeclarationNode::newEnumConstant( $1, $2 ); } - | enumerator_list ',' no_attr_identifier_or_type_name enumerator_value_opt + | enumerator_list ',' identifier_or_type_name enumerator_value_opt { $$ = $1->appendList( DeclarationNode::newEnumConstant( $3, $4 ) ); } ; @@ -2312,7 +2299,7 @@ identifier_list: // K&R-style parameter list => no types - no_attr_identifier + identifier { $$ = DeclarationNode::newName( $1 ); } - | identifier_list ',' no_attr_identifier + | identifier_list ',' identifier { $$ = $1->appendList( DeclarationNode::newName( $3 ) ); } ; @@ -2320,10 +2307,4 @@ identifier_or_type_name: identifier - | TYPEDEFname - | TYPEGENname - ; - -no_attr_identifier_or_type_name: - no_attr_identifier | TYPEDEFname | TYPEGENname @@ -2380,5 +2361,5 @@ designation: designator_list ':' // C99, CFA uses ":" instead of "=" - | no_attr_identifier ':' // GCC, field name + | identifier ':' // GCC, field name { $$ = new ExpressionNode( build_varref( $1 ) ); } ; @@ -2392,5 +2373,5 @@ designator: - '.' no_attr_identifier // C99, field name + '.' identifier // C99, field name { $$ = new ExpressionNode( build_varref( $2 ) ); } | '[' push assignment_expression pop ']' // C99, single array element @@ -2437,5 +2418,5 @@ type_parameter: // CFA - type_class no_attr_identifier_or_type_name + type_class identifier_or_type_name { typedefTable.addToScope( *$2, TYPEDEFname, "9" ); } type_initializer_opt assertion_list_opt @@ -2470,5 +2451,5 @@ assertion: // CFA - '|' no_attr_identifier_or_type_name '(' type_list ')' + '|' identifier_or_type_name '(' type_list ')' { $$ = DeclarationNode::newTraitUse( $2, $4 ); } | '|' '{' push trait_declaration_list pop '}' @@ -2507,10 +2488,10 @@ type_declarator_name: // CFA - no_attr_identifier_or_type_name + identifier_or_type_name { typedefTable.addToEnclosingScope( *$1, TYPEDEFname, "10" ); $$ = DeclarationNode::newTypeDecl( $1, 0 ); } - | no_attr_identifier_or_type_name '(' type_parameter_list ')' + | identifier_or_type_name '(' type_parameter_list ')' { typedefTable.addToEnclosingScope( *$1, TYPEGENname, "11" ); @@ -2520,7 +2501,7 @@ trait_specifier: // CFA - TRAIT no_attr_identifier_or_type_name '(' type_parameter_list ')' '{' '}' + TRAIT identifier_or_type_name '(' type_parameter_list ')' '{' '}' { $$ = DeclarationNode::newTrait( $2, $4, 0 ); } - | TRAIT no_attr_identifier_or_type_name '(' type_parameter_list ')' '{' push trait_declaration_list pop '}' + | TRAIT identifier_or_type_name '(' type_parameter_list ')' '{' push trait_declaration_list pop '}' { $$ = DeclarationNode::newTrait( $2, $4, $8 ); } ; Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/ResolvExpr/AlternativeFinder.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Sat May 16 23:52:08 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Nov 1 21:00:56 2018 -// Update Count : 35 +// Last Modified On : Thu Jul 25 22:37:46 2019 +// Update Count : 37 // @@ -79,5 +79,4 @@ void postvisit( OffsetofExpr * offsetofExpr ); void postvisit( OffsetPackExpr * offsetPackExpr ); - void postvisit( AttrExpr * attrExpr ); void postvisit( LogicalExpr * logicalExpr ); void postvisit( ConditionalExpr * conditionalExpr ); @@ -1404,69 +1403,4 @@ } - namespace { - void resolveAttr( SymTab::Indexer::IdData data, const FunctionType * function, Type * argType, const TypeEnvironment &env, AlternativeFinder & finder ) { - // assume no polymorphism - // assume no implicit conversions - assert( function->parameters.size() == 1 ); - PRINT( - std::cerr << "resolvAttr: funcDecl is "; - data.id->print( std::cerr ); - std::cerr << " argType is "; - argType->print( std::cerr ); - std::cerr << std::endl; - ) - const SymTab::Indexer & indexer = finder.get_indexer(); - AltList & alternatives = finder.get_alternatives(); - if ( typesCompatibleIgnoreQualifiers( argType, function->parameters.front()->get_type(), indexer, env ) ) { - Cost cost = Cost::zero; - Expression * newExpr = data.combine( cost ); - alternatives.push_back( Alternative{ - new AttrExpr{ newExpr, argType->clone() }, env, OpenVarSet{}, - AssertionList{}, Cost::zero, cost } ); - for ( DeclarationWithType * retVal : function->returnVals ) { - alternatives.back().expr->result = retVal->get_type()->clone(); - } // for - } // if - } - } - - void AlternativeFinder::Finder::postvisit( AttrExpr * attrExpr ) { - // assume no 'pointer-to-attribute' - NameExpr * nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() ); - assert( nameExpr ); - std::list< SymTab::Indexer::IdData > attrList; - indexer.lookupId( nameExpr->get_name(), attrList ); - if ( attrExpr->get_isType() || attrExpr->get_expr() ) { - for ( auto & data : attrList ) { - const DeclarationWithType * id = data.id; - // check if the type is function - if ( const FunctionType * function = dynamic_cast< const FunctionType * >( id->get_type() ) ) { - // assume exactly one parameter - if ( function->parameters.size() == 1 ) { - if ( attrExpr->get_isType() ) { - resolveAttr( data, function, attrExpr->get_type(), env, altFinder); - } else { - AlternativeFinder finder( indexer, env ); - finder.find( attrExpr->get_expr() ); - for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) { - if ( choice->expr->get_result()->size() == 1 ) { - resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder ); - } // fi - } // for - } // if - } // if - } // if - } // for - } else { - for ( auto & data : attrList ) { - Cost cost = Cost::zero; - Expression * newExpr = data.combine( cost ); - alternatives.push_back( Alternative{ - newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost } ); - renameTypes( alternatives.back().expr ); - } // for - } // if - } - void AlternativeFinder::Finder::postvisit( LogicalExpr * logicalExpr ) { AlternativeFinder firstFinder( indexer, env ); Index: src/SymTab/Demangle.cc =================================================================== --- src/SymTab/Demangle.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SymTab/Demangle.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Rob Schluntz // Created On : Thu Jul 19 12:52:41 2018 -// Last Modified By : Rob Schluntz -// Last Modified On : Thu Jul 19 12:54:35 2018 -// Update Count : 2 +// Last Modified By : Peter A. Buhr +// Last Modified On : Tue Jul 30 13:46:33 2019 +// Update Count : 3 // @@ -313,8 +313,4 @@ typeString = "_Atomic " + typeString; } // if - if ( type->get_lvalue() ) { - // when not generating C code, print lvalue for debugging. - typeString = "lvalue " + typeString; - } } } Index: src/SymTab/Mangler.cc =================================================================== --- src/SymTab/Mangler.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SymTab/Mangler.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Sun May 17 21:40:29 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Sep 25 15:49:26 2017 -// Update Count : 23 +// Last Modified On : Tue Jul 30 13:46:10 2019 +// Update Count : 26 // #include "Mangler.h" @@ -377,9 +377,4 @@ mangleName << Encoding::qualifiers.at(Type::Mutex); } // if - if ( type->get_lvalue() ) { - // mangle based on whether the type is lvalue, so that the resolver can differentiate lvalues and rvalues - mangleName << Encoding::qualifiers.at(Type::Lvalue); - } - if ( inFunctionType ) { // turn off inFunctionType so that types can be differentiated for nested qualifiers @@ -724,9 +719,4 @@ mangleName << Encoding::qualifiers.at(Type::Mutex); } // if - if ( type->is_lvalue() ) { - // mangle based on whether the type is lvalue, so that the resolver can differentiate lvalues and rvalues - mangleName << Encoding::qualifiers.at(Type::Lvalue); - } - if ( inFunctionType ) { // turn off inFunctionType so that types can be differentiated for nested qualifiers Index: src/SynTree/Expression.cc =================================================================== --- src/SynTree/Expression.cc (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SynTree/Expression.cc (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Feb 19 18:10:55 2019 -// Update Count : 60 +// Last Modified On : Thu Jul 25 22:21:48 2019 +// Update Count : 61 // @@ -249,33 +249,4 @@ os << "Offset pack expression on "; type->print(os, indent+1); - Expression::print( os, indent ); -} - -AttrExpr::AttrExpr( Expression * attr, Expression * expr_ ) : - Expression(), attr( attr ), expr(expr_), type(0), isType(false) { -} - -AttrExpr::AttrExpr( Expression * attr, Type * type_ ) : - Expression(), attr( attr ), expr(0), type(type_), isType(true) { -} - -AttrExpr::AttrExpr( const AttrExpr & other ) : - Expression( other ), attr( maybeClone( other.attr ) ), expr( maybeClone( other.expr ) ), type( maybeClone( other.type ) ), isType( other.isType ) { -} - -AttrExpr::~AttrExpr() { - delete attr; - delete expr; - delete type; -} - -void AttrExpr::print( std::ostream & os, Indenter indent) const { - os << "Attr "; - attr->print( os, indent+1); - if ( isType || expr ) { - os << "applied to: "; - if (isType) type->print(os, indent+1); - else expr->print(os, indent+1); - } // if Expression::print( os, indent ); } Index: src/SynTree/Expression.h =================================================================== --- src/SynTree/Expression.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SynTree/Expression.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Feb 18 18:29:51 2019 -// Update Count : 49 +// Last Modified On : Thu Jul 25 22:21:44 2019 +// Update Count : 50 // @@ -463,33 +463,4 @@ }; -/// AttrExpr represents an @attribute expression (like sizeof, but user-defined) -class AttrExpr : public Expression { - public: - Expression * attr; - Expression * expr; - Type * type; - bool isType; - - AttrExpr(Expression * attr, Expression * expr ); - AttrExpr( const AttrExpr & other ); - AttrExpr( Expression * attr, Type * type ); - virtual ~AttrExpr(); - - Expression * get_attr() const { return attr; } - void set_attr( Expression * newValue ) { attr = newValue; } - Expression * get_expr() const { return expr; } - void set_expr( Expression * newValue ) { expr = newValue; } - Type * get_type() const { return type; } - void set_type( Type * newValue ) { type = newValue; } - bool get_isType() const { return isType; } - void set_isType( bool newValue ) { isType = newValue; } - - virtual AttrExpr * clone() const override { return new AttrExpr( * this ); } - virtual void accept( Visitor & v ) override { v.visit( this ); } - virtual void accept( Visitor & v ) const override { v.visit( this ); } - virtual Expression * acceptMutator( Mutator & m ) override { return m.mutate( this ); } - virtual void print( std::ostream & os, Indenter indent = {} ) const override; -}; - /// LogicalExpr represents a short-circuit boolean expression (&& or ||) class LogicalExpr : public Expression { Index: src/SynTree/Mutator.h =================================================================== --- src/SynTree/Mutator.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SynTree/Mutator.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Jul 24 16:31:00 2017 -// Update Count : 16 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jul 25 22:37:46 2019 +// Update Count : 17 // #pragma once @@ -74,5 +74,4 @@ virtual Expression * mutate( OffsetofExpr * offsetofExpr ) = 0; virtual Expression * mutate( OffsetPackExpr * offsetPackExpr ) = 0; - virtual Expression * mutate( AttrExpr * attrExpr ) = 0; virtual Expression * mutate( LogicalExpr * logicalExpr ) = 0; virtual Expression * mutate( ConditionalExpr * conditionalExpr ) = 0; Index: src/SynTree/SynTree.h =================================================================== --- src/SynTree/SynTree.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SynTree/SynTree.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Jul 24 16:54:00 2017 -// Update Count : 11 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jul 25 22:37:45 2019 +// Update Count : 12 // @@ -79,5 +79,4 @@ class OffsetofExpr; class OffsetPackExpr; -class AttrExpr; class LogicalExpr; class ConditionalExpr; Index: src/SynTree/Visitor.h =================================================================== --- src/SynTree/Visitor.h (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ src/SynTree/Visitor.h (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Mon Jul 24 16:28:00 2017 -// Update Count : 13 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jul 25 22:21:49 2019 +// Update Count : 14 // @@ -123,6 +123,4 @@ virtual void visit( OffsetPackExpr * node ) { visit( const_cast(node) ); } virtual void visit( const OffsetPackExpr * offsetPackExpr ) = 0; - virtual void visit( AttrExpr * node ) { visit( const_cast(node) ); } - virtual void visit( const AttrExpr * attrExpr ) = 0; virtual void visit( LogicalExpr * node ) { visit( const_cast(node) ); } virtual void visit( const LogicalExpr * logicalExpr ) = 0; Index: tests/pybin/settings.py =================================================================== --- tests/pybin/settings.py (revision c60a664fdbecd8c57b45864b650e615f9927c95b) +++ tests/pybin/settings.py (revision 99cadc602bbd3d6068509ad13a17cbc5e1a52a8e) @@ -22,4 +22,5 @@ 'x86-64' : 'x64', 'x86_64' : 'x64', + 'aarch64' : 'x64', 'x86' : 'x86', 'i386' : 'x86', @@ -40,5 +41,5 @@ canonical_host = Architecture.make_canonical( config.HOSTARCH ) except KeyError: - print("Unkown host architecture %s" % config.HOSTARCH, file=sys.stderr) + print("Unknown host architecture %s" % config.HOSTARCH, file=sys.stderr) sys.exit(1) @@ -47,5 +48,5 @@ arch = Architecture.make_canonical( arch ) except KeyError: - print("Unkown architecture %s" % arch, file=sys.stderr) + print("Unknown architecture %s" % arch, file=sys.stderr) sys.exit(1)