Index: Jenkins/FullBuild =================================================================== --- Jenkins/FullBuild (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ Jenkins/FullBuild (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -18,13 +18,13 @@ parallel ( - gcc_8_x86_new: { trigger_build( 'gcc-8', 'x86' ) }, - gcc_7_x86_new: { trigger_build( 'gcc-7', 'x86' ) }, - gcc_6_x86_new: { trigger_build( 'gcc-6', 'x86' ) }, - gcc_9_x64_new: { trigger_build( 'gcc-9', 'x64' ) }, - gcc_8_x64_new: { trigger_build( 'gcc-8', 'x64' ) }, - gcc_7_x64_new: { trigger_build( 'gcc-7', 'x64' ) }, - gcc_6_x64_new: { trigger_build( 'gcc-6', 'x64' ) }, - gcc_5_x64_new: { trigger_build( 'gcc-5', 'x64' ) }, - clang_x64_new: { trigger_build( 'clang', 'x64' ) }, + gcc_08_x86_new: { trigger_build( 'gcc-8', 'x86' ) }, + gcc_07_x86_new: { trigger_build( 'gcc-7', 'x86' ) }, + gcc_06_x86_new: { trigger_build( 'gcc-6', 'x86' ) }, + gcc_10_x64_new: { trigger_build( 'gcc-10', 'x64' ) }, + gcc_09_x64_new: { trigger_build( 'gcc-9', 'x64' ) }, + gcc_08_x64_new: { trigger_build( 'gcc-8', 'x64' ) }, + gcc_07_x64_new: { trigger_build( 'gcc-7', 'x64' ) }, + gcc_06_x64_new: { trigger_build( 'gcc-6', 'x64' ) }, + clang_x64_new: { trigger_build( 'clang', 'x64' ) }, ) } Index: Jenkinsfile =================================================================== --- Jenkinsfile (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ Jenkinsfile (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -305,4 +305,10 @@ BuildSettings(java.util.Collections$UnmodifiableMap param, String branch) { switch( param.Compiler ) { + case 'gcc-11': + this.Compiler = new CC_Desc('gcc-11', 'g++-11', 'gcc-11', '-flto=auto') + break + case 'gcc-10': + this.Compiler = new CC_Desc('gcc-10', 'g++-10', 'gcc-10', '-flto=auto') + break case 'gcc-9': this.Compiler = new CC_Desc('gcc-9', 'g++-9', 'gcc-9', '-flto=auto') @@ -324,5 +330,5 @@ break case 'clang': - this.Compiler = new CC_Desc('clang', 'clang++-10', 'gcc-9', '-flto=thin -flto-jobs=0') + this.Compiler = new CC_Desc('clang', 'clang++-10', 'gcc-10', '-flto=thin -flto-jobs=0') break default : Index: benchmark/io/io_uring.h =================================================================== --- benchmark/io/io_uring.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ benchmark/io/io_uring.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1,6 +1,3 @@ extern "C" { - #ifndef _GNU_SOURCE /* See feature_test_macros(7) */ - #define _GNU_SOURCE /* See feature_test_macros(7) */ - #endif #include #include Index: doc/theses/mubeen_zulfiqar_MMath/.gitignore =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/.gitignore (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ doc/theses/mubeen_zulfiqar_MMath/.gitignore (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1,4 +1,4 @@ # Intermediate Results: -out/ +build/ # Final Files: Index: doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -35,77 +35,88 @@ ==================== -\section Performance Matrices of Memory Allocators +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Performance Matrices +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\section{Performance Matrices of Memory Allocators} When it comes to memory allocators, there are no set standards of performance. Performance of a memory allocator depends highly on the usage pattern of the application. A memory allocator that is the best performer for a certain application X might be the worst for some other application which has completely different memory usage pattern compared to the application X. It is extremely difficult to make one universally best memory allocator which will outperform every other memory allocator for every usage pattern. So, there is a lack of a set of standard benchmarks that are used to evaluate a memory allocators's performance. If we breakdown the goals of a memory allocator, there are two basic matrices on which a memory allocator's performance is evaluated. - -1. Memory Overhead -2. Speed - - /subsection Memory Overhead - Memory overhead is the extra memory that a memory allocator takes from OS which is not requested by the application. Ideally, an allocator should get just enough memory from OS that can fulfill application's request and should return this memory to OS as soon as applications frees it. But, allocators retain more memory compared to what application has asked for which causes memory overhead. Memory overhead can happen for various reasons. - - /subsubsection Fragmentation - Fragmentation is one of the major reasons behind memory overhead. Fragmentation happens because of situations that are either necassary for proper functioning of the allocator such as internal memory management and book-keeping or are out of allocator's control such as application's usage pattern. - - /subsubsubsection Internal Fragmentation - For internal book-keeping, allocators divide raw memory given by OS into chunks, blocks, or lists that can fulfill application's requested size. Allocators use memory given by OS for creating headers, footers etc. to store information about these chunks, blocks, or lists. This increases usage of memory in-addition to the memory requested by application as the allocators need to store their book-keeping information. This extra usage of memory for allocator's own book-keeping is called Internal Fragmentation. Although it cases memory overhead but this overhead is necassary for an allocator's proper funtioning. - +\begin{enumerate} +\item +Memory Overhead +\item +Speed +\end{enumerate} + +\subsection{Memory Overhead} +Memory overhead is the extra memory that a memory allocator takes from OS which is not requested by the application. Ideally, an allocator should get just enough memory from OS that can fulfill application's request and should return this memory to OS as soon as applications frees it. But, allocators retain more memory compared to what application has asked for which causes memory overhead. Memory overhead can happen for various reasons. + +\subsubsection{Fragmentation} +Fragmentation is one of the major reasons behind memory overhead. Fragmentation happens because of situations that are either necassary for proper functioning of the allocator such as internal memory management and book-keeping or are out of allocator's control such as application's usage pattern. + +\paragraph{Internal Fragmentation} +For internal book-keeping, allocators divide raw memory given by OS into chunks, blocks, or lists that can fulfill application's requested size. Allocators use memory given by OS for creating headers, footers etc. to store information about these chunks, blocks, or lists. This increases usage of memory in-addition to the memory requested by application as the allocators need to store their book-keeping information. This extra usage of memory for allocator's own book-keeping is called Internal Fragmentation. Although it cases memory overhead but this overhead is necassary for an allocator's proper funtioning. *** FIX ME: Insert a figure of internal fragmentation with explanation - /subsubsubsection External Fragmentation - External fragmentation is the free bits of memory between or around chunks of memory that are currently in-use of the application. Segmentation in memory due to application's usage pattern causes external fragmentation. The memory which is part of external fragmentation is completely free as it is neither used by allocator's internal book-keeping nor by the application. Ideally, an allocator should return a segment of memory back to the OS as soon as application frees it. But, this is not always the case. Allocators get memory from OS in one of the two ways. - - \begin{itemize} - \item - MMap: an allocator can ask OS for whole pages in mmap area. Then, the allocator segments the page internally and fulfills application's request. - \item - Heap: an allocator can ask OS for memory in heap area using system calls such as sbrk. Heap are grows downwards and shrinks upwards. - \begin{itemize} - - If an allocator uses mmap area, it can only return extra memory back to OS if the whole page is free i.e. no chunk on the page is in-use of the application. Even if one chunk on the whole page is currently in-use of the application, the allocator has to retain the whole page. - - If an allocator uses the heap area, it can only return the continous free memory at the end of the heap area that is currently in allocator's possession as heap area shrinks upwards. If there are free bits of memory in-between chunks of memory that are currently in-use of the application, the allocator can not return these free bits. - -*** FIX ME: Insert a figure of above scenrio with explanation - - Even if the entire heap area is free except one small chunk at the end of heap area that is being used by the application, the allocator cannot return the free heap area back to the OS as it is not a continous region at the end of heap area. - -*** FIX ME: Insert a figure of above scenrio with explanation - - Such scenerios cause external fragmentation but it is out of the allocator's control and depend on application's usage pattern. - - /subsubsection Internal Memory Management - Allocators such as je-malloc (FIX ME: insert reference) pro-actively get some memory from the OS and divide it into chunks of certain sizes that can be used in-future to fulfill application's request. This causes memory overhead as these chunks are made before application's request. There is also the possibility that an application may not even request memory of these sizes during their whole life-time. - -*** FIX ME: Insert a figure of above scenrio with explanation - - Allocators such as rp-malloc (FIX ME: insert reference) maintain lists or blocks of sized memory segments that is freed by the application for future use. These lists are maintained without any guarantee that application will even request these sizes again. - - Such tactics are usually used to gain speed as allocator will not have to get raw memory from OS and manage it at the time of application's request but they do cause memory overhead. - - Fragmentation and managed sized chunks of free memory can lead to Heap Blowup as the allocator may not be able to use the fragments or sized free chunks of free memory to fulfill application's requests of other sizes. - - /subsection Speed - When it comes to performance evaluation of any piece of software, its runtime is usually the first thing that is evaluated. The same is true for memory allocators but, in case of memory allocators, speed does not only mean the runtime of memory allocator's routines but there are other factors too. - - /subsubsection Runtime Speed - Low runtime is the main goal of a memory allocator when it comes it proving its speed. Runtime is the time that it takes for a routine of memory allocator to complete its execution. As mentioned in (FIX ME: refernce to routines' list), there four basic routines that are used in memory allocation. Ideally, each routine of a memory allocator should be fast. Some memory allocator designs use pro-active measures (FIX ME: local refernce) to gain speed when allocating some memory to the application. Some memory allocators do memory allocation faster than memory freeing (FIX ME: graph refernce) while others show similar speed whether memory is allocated or freed. - - /subsubsection Memory Access Speed - Runtime speed is not the only speed matrix in memory allocators. The memory that a memory allocator has allocated to the application also needs to be accessible as quick as possible. The application should be able to read/write allocated memory quickly. The allocation method of a memory allocator may introduce some delays when it comes to memory access speed, which is specially important in concurrent applications. Ideally, a memory allocator should allocate all memory on a cache-line to only one thread and no cache-line should be shared among multiple threads. If a memory allocator allocates memory to multple threads on a same cache line, then cache may get invalidated more frequesntly when two different threads running on two different processes will try to read/write the same memory region. On the other hand, if one cache-line is used by only one thread then the cache may get invalidated less frequently. This sharing of one cache-line among multiple threads is called false sharing (FIX ME: cite wasik). - - /subsubsubsection Active False Sharing - Active false sharing is the sharing of one cache-line among multiple threads that is caused by memory allocator. It happens when two threads request memory from memory allocator and the allocator allocates memory to both of them on the same cache-line. After that, if the threads are running on different processes who have their own caches and both threads start reading/writing the allocated memory simultanously, their caches will start getting invalidated every time the other thread writes something to the memory. This will cause the application to slow down as the process has to load cache much more frequently. - -*** FIX ME: Insert a figure of above scenrio with explanation - - /subsubsubsection Passive False Sharing - Passive false sharing is the kind of false sharing which is caused by the application and not the memory allocator. The memory allocator may preservce passive false sharing in future instead of eradicating it. But, passive false sharing is initiated by the application. - - /subsubsubsubsection Program Induced Passive False Sharing - Program induced false sharing is completely out of memory allocator's control and is purely caused by the application. When a thread in the application creates multiple objects in the dynamic area and allocator allocates memory for these objects on the same cache-line as the objects are created by the same thread. Passive false sharing will occur if this thread passes one of these objects to another thread but it retains the rest of these objects or it passes some/all of the remaining objects to some third thread(s). Now, one cache-line is shared among multiple threads but it is caused by the application and not the allocator. It is out of allocator's control and has the similar performance impact as Active False Sharing (FIX ME: cite local) if these threads, who are sharing the same cache-line, start reading/writing the given objects simultanously. +\paragraph{External Fragmentation} +External fragmentation is the free bits of memory between or around chunks of memory that are currently in-use of the application. Segmentation in memory due to application's usage pattern causes external fragmentation. The memory which is part of external fragmentation is completely free as it is neither used by allocator's internal book-keeping nor by the application. Ideally, an allocator should return a segment of memory back to the OS as soon as application frees it. But, this is not always the case. Allocators get memory from OS in one of the two ways. + +\begin{itemize} +\item +MMap: an allocator can ask OS for whole pages in mmap area. Then, the allocator segments the page internally and fulfills application's request. +\item +Heap: an allocator can ask OS for memory in heap area using system calls such as sbrk. Heap are grows downwards and shrinks upwards. +\begin{itemize} +\item +If an allocator uses mmap area, it can only return extra memory back to OS if the whole page is free i.e. no chunk on the page is in-use of the application. Even if one chunk on the whole page is currently in-use of the application, the allocator has to retain the whole page. +\item +If an allocator uses the heap area, it can only return the continous free memory at the end of the heap area that is currently in allocator's possession as heap area shrinks upwards. If there are free bits of memory in-between chunks of memory that are currently in-use of the application, the allocator can not return these free bits. + +*** FIX ME: Insert a figure of above scenrio with explanation +\item +Even if the entire heap area is free except one small chunk at the end of heap area that is being used by the application, the allocator cannot return the free heap area back to the OS as it is not a continous region at the end of heap area. + +*** FIX ME: Insert a figure of above scenrio with explanation + +\item +Such scenerios cause external fragmentation but it is out of the allocator's control and depend on application's usage pattern. +\end{itemize} +\end{itemize} + +\subsubsection{Internal Memory Management} +Allocators such as je-malloc (FIX ME: insert reference) pro-actively get some memory from the OS and divide it into chunks of certain sizes that can be used in-future to fulfill application's request. This causes memory overhead as these chunks are made before application's request. There is also the possibility that an application may not even request memory of these sizes during their whole life-time. + +*** FIX ME: Insert a figure of above scenrio with explanation + +Allocators such as rp-malloc (FIX ME: insert reference) maintain lists or blocks of sized memory segments that is freed by the application for future use. These lists are maintained without any guarantee that application will even request these sizes again. + +Such tactics are usually used to gain speed as allocator will not have to get raw memory from OS and manage it at the time of application's request but they do cause memory overhead. + +Fragmentation and managed sized chunks of free memory can lead to Heap Blowup as the allocator may not be able to use the fragments or sized free chunks of free memory to fulfill application's requests of other sizes. + +\subsection{Speed} +When it comes to performance evaluation of any piece of software, its runtime is usually the first thing that is evaluated. The same is true for memory allocators but, in case of memory allocators, speed does not only mean the runtime of memory allocator's routines but there are other factors too. + +\subsubsection{Runtime Speed} +Low runtime is the main goal of a memory allocator when it comes it proving its speed. Runtime is the time that it takes for a routine of memory allocator to complete its execution. As mentioned in (FIX ME: refernce to routines' list), there four basic routines that are used in memory allocation. Ideally, each routine of a memory allocator should be fast. Some memory allocator designs use pro-active measures (FIX ME: local refernce) to gain speed when allocating some memory to the application. Some memory allocators do memory allocation faster than memory freeing (FIX ME: graph refernce) while others show similar speed whether memory is allocated or freed. + +\subsubsection{Memory Access Speed} +Runtime speed is not the only speed matrix in memory allocators. The memory that a memory allocator has allocated to the application also needs to be accessible as quick as possible. The application should be able to read/write allocated memory quickly. The allocation method of a memory allocator may introduce some delays when it comes to memory access speed, which is specially important in concurrent applications. Ideally, a memory allocator should allocate all memory on a cache-line to only one thread and no cache-line should be shared among multiple threads. If a memory allocator allocates memory to multple threads on a same cache line, then cache may get invalidated more frequesntly when two different threads running on two different processes will try to read/write the same memory region. On the other hand, if one cache-line is used by only one thread then the cache may get invalidated less frequently. This sharing of one cache-line among multiple threads is called false sharing (FIX ME: cite wasik). + +\paragraph{Active False Sharing} +Active false sharing is the sharing of one cache-line among multiple threads that is caused by memory allocator. It happens when two threads request memory from memory allocator and the allocator allocates memory to both of them on the same cache-line. After that, if the threads are running on different processes who have their own caches and both threads start reading/writing the allocated memory simultanously, their caches will start getting invalidated every time the other thread writes something to the memory. This will cause the application to slow down as the process has to load cache much more frequently. + +*** FIX ME: Insert a figure of above scenrio with explanation + +\paragraph{Passive False Sharing} +Passive false sharing is the kind of false sharing which is caused by the application and not the memory allocator. The memory allocator may preservce passive false sharing in future instead of eradicating it. But, passive false sharing is initiated by the application. + +\subparagraph{Program Induced Passive False Sharing} +Program induced false sharing is completely out of memory allocator's control and is purely caused by the application. When a thread in the application creates multiple objects in the dynamic area and allocator allocates memory for these objects on the same cache-line as the objects are created by the same thread. Passive false sharing will occur if this thread passes one of these objects to another thread but it retains the rest of these objects or it passes some/all of the remaining objects to some third thread(s). Now, one cache-line is shared among multiple threads but it is caused by the application and not the allocator. It is out of allocator's control and has the similar performance impact as Active False Sharing (FIX ME: cite local) if these threads, who are sharing the same cache-line, start reading/writing the given objects simultanously. *** FIX ME: Insert a figure of above scenrio 1 with explanation @@ -113,6 +124,117 @@ *** FIX ME: Insert a figure of above scenrio 2 with explanation - /subsubsubsubsection Program Induced Allocator Preserved Passive False Sharing - Program induced allocator preserved passive false sharing is another interesting case of passive false sharing. Both the application and the allocator are partially responsible for it. It starts the same as Program Induced False Sharing (FIX ME: cite local). Once, an application thread has created multiple dynamic objects on the same cache-line and ditributed these objects among multiple threads causing sharing of one cache-line among multiple threads (Program Induced Passive False Sharing). This kind of false sharing occurs when one of these threads, which got the object on the shared cache-line, frees the passed object then re-allocates another object but the allocator returns the same object (on the shared cache-line) that this thread just freed. Although, the application caused the false sharing to happen in the frst place however, to prevent furthur false sharing, the allocator should have returned the new object on some other cache-line which is only shared by the allocating thread. When it comes to performnce impact, this passive false sharing will slow down the application just like any other kind of false sharing if the threads sharing the cache-line start reading/writing the objects simultanously. - -*** FIX ME: Insert a figure of above scenrio with explanation +\subparagraph{Program Induced Allocator Preserved Passive False Sharing} +Program induced allocator preserved passive false sharing is another interesting case of passive false sharing. Both the application and the allocator are partially responsible for it. It starts the same as Program Induced False Sharing (FIX ME: cite local). Once, an application thread has created multiple dynamic objects on the same cache-line and ditributed these objects among multiple threads causing sharing of one cache-line among multiple threads (Program Induced Passive False Sharing). This kind of false sharing occurs when one of these threads, which got the object on the shared cache-line, frees the passed object then re-allocates another object but the allocator returns the same object (on the shared cache-line) that this thread just freed. Although, the application caused the false sharing to happen in the frst place however, to prevent furthur false sharing, the allocator should have returned the new object on some other cache-line which is only shared by the allocating thread. When it comes to performnce impact, this passive false sharing will slow down the application just like any other kind of false sharing if the threads sharing the cache-line start reading/writing the objects simultanously. + + +*** FIX ME: Insert a figure of above scenrio with explanation + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Micro Benchmark Suite +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\section{Micro Benchmark Suite} +The aim of micro benchmark suite is to create a set of programs that can evaluate a memory allocator based on the performance matrices described in (FIX ME: local cite). These programs can be taken as a standard to benchmark an allocator's basic goals. These programs give details of an allocator's memory overhead and speed under a certain allocation pattern. The speed of the allocator is benchmarked in different ways. Similarly, false sharing happening in an allocator is also measured in multiple ways. These benchmarks evalute the allocator under a certain allocation pattern which is configurable and can be changed using a few knobs to benchmark observe an allocator's performance under a desired allocation pattern. + +Micro Benchmark Suite benchmarks an allocator's performance by allocating dynamic objects and, then, measuring specifc matrices. The benchmark suite evaluates an allocator with a certain allocation pattern. Bnechmarks have different knobs that can be used to change allocation pattern and evaluate an allocator under desired conditions. These can be set by giving commandline arguments to the benchmark on execution. + +Following is the list of avalable knobs. + +*** FIX ME: Add knobs items after finalize + +\subsection{Memory Benchmark} +Memory benchmark measures memory overhead of an allocator. It allocates a number of dynamic objects. Then, by reading /self/proc/maps, gets the total memory that the allocator has reuested from the OS. Finally, it calculates the memory head by taking the difference between the memory the allocator has requested from the OS and the memory that program has allocated. +*** FIX ME: Insert a figure of above benchmark with description + +\subsubsection{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsection{Speed Benchmark} +Speed benchmark calculates the runtime speed of an allocator's functions (FIX ME: cite allocator routines). It does by measuring the runtime of allocator routines in two different ways. + +\subsubsection{Speed Time} +The time method does a certain amount of work by calling each routine of the allocator (FIX ME: cite allocator routines) a specific time. It calculates the total time it took to perform this workload. Then, it divides the time it took by the workload and calculates the average time taken by the allocator's routine. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsubsection{Speed Workload} +The worload method uses the opposite approach. It calls the allocator's routines for a specific amount of time and measures how much work was done during that time. Then, similar to the time method, it divides the time by the workload done during that time and calculates the average time taken by the allocator's routine. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsection{Cache Scratch} +Cache Scratch benchmark measures program induced allocator preserved passive false sharing (FIX ME CITE) in an allocator. It does so in two ways. + +\subsubsection{Cache Scratch Time} +Cache Scratch Time allocates dynamic objects. Then, it benchmarks program induced allocator preserved passive false sharing (FIX ME CITE) in an allocator by measuring the time it takes to read/write these objects. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsubsection{Cache Scratch Layout} +Cache Scratch Layout also allocates dynamic objects. Then, it benchmarks program induced allocator preserved passive false sharing (FIX ME CITE) by using heap addresses returned by the allocator. It calculates how many objects were allocated to different threads on the same cache line. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsection{Cache Thrash} +Cache Thrash benchmark measures allocator induced passive false sharing (FIX ME CITE) in an allocator. It also does so in two ways. + +\subsubsection{Cache Thrash Time} +Cache Thrash Time allocates dynamic objects. Then, it benchmarks allocator induced false sharing (FIX ME CITE) in an allocator by measuring the time it takes to read/write these objects. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\subsubsection{Cache Thrash Layout} +Cache Thrash Layout also allocates dynamic objects. Then, it benchmarks allocator induced false sharing (FIX ME CITE) by using heap addresses returned by the allocator. It calculates how many objects were allocated to different threads on the same cache line. +*** FIX ME: Insert a figure of above benchmark with description + +\paragraph{Relevant Knobs} +*** FIX ME: Insert Relevant Knobs + +\section{Results} +*** FIX ME: add configuration details of memory allocators + +\subsection{Memory Benchmark} + +\subsubsection{Relevant Knobs} + +\subsection{Speed Benchmark} + +\subsubsection{Speed Time} + +\paragraph{Relevant Knobs} + +\subsubsection{Speed Workload} + +\paragraph{Relevant Knobs} + +\subsection{Cache Scratch} + +\subsubsection{Cache Scratch Time} + +\paragraph{Relevant Knobs} + +\subsubsection{Cache Scratch Layout} + +\paragraph{Relevant Knobs} + +\subsection{Cache Thrash} + +\subsubsection{Cache Thrash Time} + +\paragraph{Relevant Knobs} + +\subsubsection{Cache Thrash Layout} + +\paragraph{Relevant Knobs} Index: doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -165,6 +165,7 @@ % cfa macros used in the document \input{common} +%\usepackageinput{common} \CFAStyle % CFA code-style for all languages -\lstset{language=CFA,basicstyle=\linespread{0.9}\tt} % CFA default language +\lstset{basicstyle=\linespread{0.9}\tt} % CFA typewriter font \newcommand{\PAB}[1]{{\color{red}PAB: #1}} Index: libcfa/prelude/defines.hfa.in =================================================================== --- libcfa/prelude/defines.hfa.in (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/prelude/defines.hfa.in (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -171,4 +171,10 @@ #undef CFA_HAVE_LINUX_IO_URING_H +/* Defined if librseq support is present when compiling libcfathread. */ +#undef CFA_HAVE_LINUX_LIBRSEQ + +/* Defined if rseq support is present when compiling libcfathread. */ +#undef CFA_HAVE_LINUX_RSEQ_H + /* Defined if openat2 support is present when compiling libcfathread. */ #undef CFA_HAVE_OPENAT2 @@ -205,4 +211,7 @@ #undef HAVE_LINUX_IO_URING_H +/* Define to 1 if you have the header file. */ +#undef HAVE_LINUX_RSEQ_H + /* Define to 1 if you have the header file. */ #undef HAVE_MEMORY_H Index: libcfa/src/bits/signal.hfa =================================================================== --- libcfa/src/bits/signal.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/bits/signal.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -20,7 +20,5 @@ #include -#define __USE_GNU #include -#undef __USE_GNU #include #include Index: libcfa/src/concurrency/coroutine.cfa =================================================================== --- libcfa/src/concurrency/coroutine.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/coroutine.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #include "coroutine.hfa" Index: libcfa/src/concurrency/io.cfa =================================================================== --- libcfa/src/concurrency/io.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/io.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #if defined(__CFA_DEBUG__) @@ -23,5 +24,4 @@ #if defined(CFA_HAVE_LINUX_IO_URING_H) - #define _GNU_SOURCE /* See feature_test_macros(7) */ #include #include Index: libcfa/src/concurrency/io/setup.cfa =================================================================== --- libcfa/src/concurrency/io/setup.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/io/setup.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,5 +15,5 @@ #define __cforall_thread__ -#define _GNU_SOURCE /* See feature_test_macros(7) */ +#define _GNU_SOURCE #if defined(__CFA_DEBUG__) Index: libcfa/src/concurrency/kernel.cfa =================================================================== --- libcfa/src/concurrency/kernel.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/kernel.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,6 @@ #define __cforall_thread__ +#define _GNU_SOURCE + // #define __CFA_DEBUG_PRINT_RUNTIME_CORE__ @@ -278,5 +280,5 @@ // Spin a little on I/O, just in case - for(5) { + for(5) { __maybe_io_drain( this ); readyThread = pop_fast( this->cltr ); @@ -285,5 +287,5 @@ // no luck, try stealing a few times - for(5) { + for(5) { if( __maybe_io_drain( this ) ) { readyThread = pop_fast( this->cltr ); Index: libcfa/src/concurrency/kernel.hfa =================================================================== --- libcfa/src/concurrency/kernel.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/kernel.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -66,4 +66,5 @@ unsigned id; unsigned target; + unsigned last; unsigned long long int cutoff; } rdq; Index: libcfa/src/concurrency/kernel/startup.cfa =================================================================== --- libcfa/src/concurrency/kernel/startup.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/kernel/startup.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,11 +15,15 @@ #define __cforall_thread__ +#define _GNU_SOURCE // C Includes #include // errno +#include #include // strerror #include // sysconf + extern "C" { #include // PTHREAD_STACK_MIN + #include // syscall #include // eventfd #include // mprotect @@ -136,4 +140,16 @@ }; +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + // No data needed +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + extern "Cforall" { + __attribute__((aligned(128))) thread_local volatile struct rseq __cfaabi_rseq @= { + .cpu_id : RSEQ_CPU_ID_UNINITIALIZED, + }; + } +#else + // No data needed +#endif + //----------------------------------------------------------------------------- // Struct to steal stack @@ -468,5 +484,5 @@ self_mon_p = &self_mon; link.next = 0p; - link.ts = 0; + link.ts = -1llu; preferred = -1u; last_proc = 0p; @@ -497,4 +513,5 @@ this.rdq.id = -1u; this.rdq.target = -1u; + this.rdq.last = -1u; this.rdq.cutoff = 0ull; do_terminate = false; Index: libcfa/src/concurrency/kernel_private.hfa =================================================================== --- libcfa/src/concurrency/kernel_private.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/kernel_private.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -16,4 +16,8 @@ #pragma once +#if !defined(__cforall_thread__) + #error kernel_private.hfa should only be included in libcfathread source +#endif + #include "kernel.hfa" #include "thread.hfa" @@ -22,8 +26,19 @@ #include "stats.hfa" +extern "C" { +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + #include +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + #include +#else + #ifndef _GNU_SOURCE + #error kernel_private requires gnu_source + #endif + #include +#endif +} + //----------------------------------------------------------------------------- // Scheduler - - extern "C" { void disable_interrupts() OPTIONAL_THREAD; @@ -39,4 +54,30 @@ //----------------------------------------------------------------------------- +// Hardware + +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + // No data needed +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + extern "Cforall" { + extern __attribute__((aligned(128))) thread_local volatile struct rseq __cfaabi_rseq; + } +#else + // No data needed +#endif + +static inline int __kernel_getcpu() { + /* paranoid */ verify( ! __preemption_enabled() ); +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + return rseq_current_cpu(); +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + int r = __cfaabi_rseq.cpu_id; + /* paranoid */ verify( r >= 0 ); + return r; +#else + return sched_getcpu(); +#endif +} + +//----------------------------------------------------------------------------- // Processor void main(processorCtx_t *); @@ -44,6 +85,4 @@ void * __create_pthread( pthread_t *, void * (*)(void *), void * ); void __destroy_pthread( pthread_t pthread, void * stack, void ** retval ); - - extern cluster * mainCluster; Index: libcfa/src/concurrency/locks.cfa =================================================================== --- libcfa/src/concurrency/locks.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/locks.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -16,4 +16,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #include "locks.hfa" Index: libcfa/src/concurrency/monitor.cfa =================================================================== --- libcfa/src/concurrency/monitor.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/monitor.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #include "monitor.hfa" Index: libcfa/src/concurrency/mutex.cfa =================================================================== --- libcfa/src/concurrency/mutex.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/mutex.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -17,4 +17,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #include "mutex.hfa" Index: libcfa/src/concurrency/preemption.cfa =================================================================== --- libcfa/src/concurrency/preemption.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/preemption.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,6 @@ #define __cforall_thread__ +#define _GNU_SOURCE + // #define __CFA_DEBUG_PRINT_PREEMPTION__ Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/ready_queue.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,18 +15,26 @@ #define __cforall_thread__ +#define _GNU_SOURCE + // #define __CFA_DEBUG_PRINT_READY_QUEUE__ -#define USE_RELAXED_FIFO +// #define USE_RELAXED_FIFO // #define USE_WORK_STEALING +#define USE_CPU_WORK_STEALING #include "bits/defs.hfa" +#include "device/cpu.hfa" #include "kernel_private.hfa" -#define _GNU_SOURCE #include "stdlib.hfa" #include "math.hfa" +#include #include + +extern "C" { + #include // __NR_xxx +} #include "ready_subqueue.hfa" @@ -46,5 +54,7 @@ #endif -#if defined(USE_RELAXED_FIFO) +#if defined(USE_CPU_WORK_STEALING) + #define READYQ_SHARD_FACTOR 2 +#elif defined(USE_RELAXED_FIFO) #define BIAS 4 #define READYQ_SHARD_FACTOR 4 @@ -85,4 +95,23 @@ } +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + // No forward declaration needed + #define __kernel_rseq_register rseq_register_current_thread + #define __kernel_rseq_unregister rseq_unregister_current_thread +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + void __kernel_raw_rseq_register (void); + void __kernel_raw_rseq_unregister(void); + + #define __kernel_rseq_register __kernel_raw_rseq_register + #define __kernel_rseq_unregister __kernel_raw_rseq_unregister +#else + // No forward declaration needed + // No initialization needed + static inline void noop(void) {} + + #define __kernel_rseq_register noop + #define __kernel_rseq_unregister noop +#endif + //======================================================================= // Cluster wide reader-writer lock @@ -107,4 +136,6 @@ // Lock-Free registering/unregistering of threads unsigned register_proc_id( void ) with(*__scheduler_lock) { + __kernel_rseq_register(); + __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc); bool * handle = (bool *)&kernelTLS().sched_lock; @@ -161,4 +192,6 @@ __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc); + + __kernel_rseq_unregister(); } @@ -214,11 +247,25 @@ //======================================================================= void ?{}(__ready_queue_t & this) with (this) { - lanes.data = 0p; - lanes.tscs = 0p; - lanes.count = 0; + #if defined(USE_CPU_WORK_STEALING) + lanes.count = cpu_info.hthrd_count * READYQ_SHARD_FACTOR; + lanes.data = alloc( lanes.count ); + lanes.tscs = alloc( lanes.count ); + + for( idx; (size_t)lanes.count ) { + (lanes.data[idx]){}; + lanes.tscs[idx].tv = rdtscl(); + } + #else + lanes.data = 0p; + lanes.tscs = 0p; + lanes.count = 0; + #endif } void ^?{}(__ready_queue_t & this) with (this) { - verify( SEQUENTIAL_SHARD == lanes.count ); + #if !defined(USE_CPU_WORK_STEALING) + verify( SEQUENTIAL_SHARD == lanes.count ); + #endif + free(lanes.data); free(lanes.tscs); @@ -226,4 +273,143 @@ //----------------------------------------------------------------------- +#if defined(USE_CPU_WORK_STEALING) + __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) with (cltr->ready_queue) { + __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr); + + processor * const proc = kernelTLS().this_processor; + const bool external = !push_local || (!proc) || (cltr != proc->cltr); + + const int cpu = __kernel_getcpu(); + /* paranoid */ verify(cpu >= 0); + /* paranoid */ verify(cpu < cpu_info.hthrd_count); + /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count); + + const cpu_map_entry_t & map = cpu_info.llc_map[cpu]; + /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count); + /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count); + /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR); + + const int start = map.self * READYQ_SHARD_FACTOR; + unsigned i; + do { + unsigned r; + if(unlikely(external)) { r = __tls_rand(); } + else { r = proc->rdq.its++; } + i = start + (r % READYQ_SHARD_FACTOR); + // If we can't lock it retry + } while( !__atomic_try_acquire( &lanes.data[i].lock ) ); + + // Actually push it + push(lanes.data[i], thrd); + + // Unlock and return + __atomic_unlock( &lanes.data[i].lock ); + + #if !defined(__CFA_NO_STATISTICS__) + if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED); + else __tls_stats()->ready.push.local.success++; + #endif + + __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first); + + } + + // Pop from the ready queue from a given cluster + __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) { + /* paranoid */ verify( lanes.count > 0 ); + /* paranoid */ verify( kernelTLS().this_processor ); + + const int cpu = __kernel_getcpu(); + /* paranoid */ verify(cpu >= 0); + /* paranoid */ verify(cpu < cpu_info.hthrd_count); + /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count); + + const cpu_map_entry_t & map = cpu_info.llc_map[cpu]; + /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count); + /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count); + /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR); + + processor * const proc = kernelTLS().this_processor; + const int start = map.self * READYQ_SHARD_FACTOR; + + // Did we already have a help target + if(proc->rdq.target == -1u) { + // if We don't have a + unsigned long long min = ts(lanes.data[start]); + for(i; READYQ_SHARD_FACTOR) { + unsigned long long tsc = ts(lanes.data[start + i]); + if(tsc < min) min = tsc; + } + proc->rdq.cutoff = min; + + /* paranoid */ verify(lanes.count < 65536); // The following code assumes max 65536 cores. + /* paranoid */ verify(map.count < 65536); // The following code assumes max 65536 cores. + uint64_t chaos = __tls_rand(); + uint64_t high_chaos = (chaos >> 32); + uint64_t mid_chaos = (chaos >> 16) & 0xffff; + uint64_t low_chaos = chaos & 0xffff; + + unsigned me = map.self; + unsigned cpu_chaos = map.start + (mid_chaos % map.count); + bool global = cpu_chaos == me; + + if(global) { + proc->rdq.target = high_chaos % lanes.count; + } else { + proc->rdq.target = (cpu_chaos * READYQ_SHARD_FACTOR) + (low_chaos % READYQ_SHARD_FACTOR); + /* paranoid */ verify(proc->rdq.target >= (map.start * READYQ_SHARD_FACTOR)); + /* paranoid */ verify(proc->rdq.target < ((map.start + map.count) * READYQ_SHARD_FACTOR)); + } + + /* paranoid */ verify(proc->rdq.target != -1u); + } + else { + const unsigned long long bias = 0; //2_500_000_000; + const unsigned long long cutoff = proc->rdq.cutoff > bias ? proc->rdq.cutoff - bias : proc->rdq.cutoff; + { + unsigned target = proc->rdq.target; + proc->rdq.target = -1u; + if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) { + $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help)); + proc->rdq.last = target; + if(t) return t; + } + } + + unsigned last = proc->rdq.last; + if(last != -1u && lanes.tscs[last].tv < cutoff && ts(lanes.data[last]) < cutoff) { + $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.help)); + if(t) return t; + } + else { + proc->rdq.last = -1u; + } + } + + for(READYQ_SHARD_FACTOR) { + unsigned i = start + (proc->rdq.itr++ % READYQ_SHARD_FACTOR); + if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t; + } + + // All lanes where empty return 0p + return 0p; + } + + __attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) { + processor * const proc = kernelTLS().this_processor; + unsigned last = proc->rdq.last; + if(last != -1u) { + struct $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.steal)); + if(t) return t; + proc->rdq.last = -1u; + } + + unsigned i = __tls_rand() % lanes.count; + return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal)); + } + __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) { + return search(cltr); + } +#endif #if defined(USE_RELAXED_FIFO) //----------------------------------------------------------------------- @@ -519,9 +705,9 @@ if(is_empty(sl)) { assert( sl.anchor.next == 0p ); - assert( sl.anchor.ts == 0 ); + assert( sl.anchor.ts == -1llu ); assert( mock_head(sl) == sl.prev ); } else { assert( sl.anchor.next != 0p ); - assert( sl.anchor.ts != 0 ); + assert( sl.anchor.ts != -1llu ); assert( mock_head(sl) != sl.prev ); } @@ -573,134 +759,141 @@ lanes.tscs = alloc(lanes.count, lanes.tscs`realloc); for(i; lanes.count) { - unsigned long long tsc = ts(lanes.data[i]); - lanes.tscs[i].tv = tsc != 0 ? tsc : rdtscl(); + unsigned long long tsc1 = ts(lanes.data[i]); + unsigned long long tsc2 = rdtscl() + lanes.tscs[i].tv = min(tsc1, tsc2); } #endif } -// Grow the ready queue -void ready_queue_grow(struct cluster * cltr) { - size_t ncount; - int target = cltr->procs.total; - - /* paranoid */ verify( ready_mutate_islocked() ); - __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n"); - - // Make sure that everything is consistent - /* paranoid */ check( cltr->ready_queue ); - - // grow the ready queue - with( cltr->ready_queue ) { - // Find new count - // Make sure we always have atleast 1 list - if(target >= 2) { - ncount = target * READYQ_SHARD_FACTOR; - } else { - ncount = SEQUENTIAL_SHARD; - } - - // Allocate new array (uses realloc and memcpies the data) - lanes.data = alloc( ncount, lanes.data`realloc ); - - // Fix the moved data - for( idx; (size_t)lanes.count ) { - fix(lanes.data[idx]); - } - - // Construct new data - for( idx; (size_t)lanes.count ~ ncount) { - (lanes.data[idx]){}; - } - - // Update original - lanes.count = ncount; - } - - fix_times(cltr); - - reassign_cltr_id(cltr); - - // Make sure that everything is consistent - /* paranoid */ check( cltr->ready_queue ); - - __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n"); - - /* paranoid */ verify( ready_mutate_islocked() ); -} - -// Shrink the ready queue -void ready_queue_shrink(struct cluster * cltr) { - /* paranoid */ verify( ready_mutate_islocked() ); - __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n"); - - // Make sure that everything is consistent - /* paranoid */ check( cltr->ready_queue ); - - int target = cltr->procs.total; - - with( cltr->ready_queue ) { - // Remember old count - size_t ocount = lanes.count; - - // Find new count - // Make sure we always have atleast 1 list - lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD; - /* paranoid */ verify( ocount >= lanes.count ); - /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 ); - - // for printing count the number of displaced threads - #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) - __attribute__((unused)) size_t displaced = 0; - #endif - - // redistribute old data - for( idx; (size_t)lanes.count ~ ocount) { - // Lock is not strictly needed but makes checking invariants much easier - __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock); - verify(locked); - - // As long as we can pop from this lane to push the threads somewhere else in the queue - while(!is_empty(lanes.data[idx])) { - struct $thread * thrd; - unsigned long long _; - [thrd, _] = pop(lanes.data[idx]); - - push(cltr, thrd, true); - - // for printing count the number of displaced threads - #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) - displaced++; - #endif - } - - // Unlock the lane - __atomic_unlock(&lanes.data[idx].lock); - - // TODO print the queue statistics here - - ^(lanes.data[idx]){}; - } - - __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced); - - // Allocate new array (uses realloc and memcpies the data) - lanes.data = alloc( lanes.count, lanes.data`realloc ); - - // Fix the moved data - for( idx; (size_t)lanes.count ) { - fix(lanes.data[idx]); - } - } - - fix_times(cltr); - - reassign_cltr_id(cltr); - - // Make sure that everything is consistent - /* paranoid */ check( cltr->ready_queue ); - - __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n"); - /* paranoid */ verify( ready_mutate_islocked() ); -} +#if defined(USE_CPU_WORK_STEALING) + // ready_queue size is fixed in this case + void ready_queue_grow(struct cluster * cltr) {} + void ready_queue_shrink(struct cluster * cltr) {} +#else + // Grow the ready queue + void ready_queue_grow(struct cluster * cltr) { + size_t ncount; + int target = cltr->procs.total; + + /* paranoid */ verify( ready_mutate_islocked() ); + __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n"); + + // Make sure that everything is consistent + /* paranoid */ check( cltr->ready_queue ); + + // grow the ready queue + with( cltr->ready_queue ) { + // Find new count + // Make sure we always have atleast 1 list + if(target >= 2) { + ncount = target * READYQ_SHARD_FACTOR; + } else { + ncount = SEQUENTIAL_SHARD; + } + + // Allocate new array (uses realloc and memcpies the data) + lanes.data = alloc( ncount, lanes.data`realloc ); + + // Fix the moved data + for( idx; (size_t)lanes.count ) { + fix(lanes.data[idx]); + } + + // Construct new data + for( idx; (size_t)lanes.count ~ ncount) { + (lanes.data[idx]){}; + } + + // Update original + lanes.count = ncount; + } + + fix_times(cltr); + + reassign_cltr_id(cltr); + + // Make sure that everything is consistent + /* paranoid */ check( cltr->ready_queue ); + + __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n"); + + /* paranoid */ verify( ready_mutate_islocked() ); + } + + // Shrink the ready queue + void ready_queue_shrink(struct cluster * cltr) { + /* paranoid */ verify( ready_mutate_islocked() ); + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n"); + + // Make sure that everything is consistent + /* paranoid */ check( cltr->ready_queue ); + + int target = cltr->procs.total; + + with( cltr->ready_queue ) { + // Remember old count + size_t ocount = lanes.count; + + // Find new count + // Make sure we always have atleast 1 list + lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD; + /* paranoid */ verify( ocount >= lanes.count ); + /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 ); + + // for printing count the number of displaced threads + #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) + __attribute__((unused)) size_t displaced = 0; + #endif + + // redistribute old data + for( idx; (size_t)lanes.count ~ ocount) { + // Lock is not strictly needed but makes checking invariants much easier + __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock); + verify(locked); + + // As long as we can pop from this lane to push the threads somewhere else in the queue + while(!is_empty(lanes.data[idx])) { + struct $thread * thrd; + unsigned long long _; + [thrd, _] = pop(lanes.data[idx]); + + push(cltr, thrd, true); + + // for printing count the number of displaced threads + #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) + displaced++; + #endif + } + + // Unlock the lane + __atomic_unlock(&lanes.data[idx].lock); + + // TODO print the queue statistics here + + ^(lanes.data[idx]){}; + } + + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced); + + // Allocate new array (uses realloc and memcpies the data) + lanes.data = alloc( lanes.count, lanes.data`realloc ); + + // Fix the moved data + for( idx; (size_t)lanes.count ) { + fix(lanes.data[idx]); + } + } + + fix_times(cltr); + + reassign_cltr_id(cltr); + + // Make sure that everything is consistent + /* paranoid */ check( cltr->ready_queue ); + + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n"); + /* paranoid */ verify( ready_mutate_islocked() ); + } +#endif #if !defined(__CFA_NO_STATISTICS__) @@ -710,2 +903,59 @@ } #endif + + +#if defined(CFA_HAVE_LINUX_LIBRSEQ) + // No definition needed +#elif defined(CFA_HAVE_LINUX_RSEQ_H) + + #if defined( __x86_64 ) || defined( __i386 ) + #define RSEQ_SIG 0x53053053 + #elif defined( __ARM_ARCH ) + #ifdef __ARMEB__ + #define RSEQ_SIG 0xf3def5e7 /* udf #24035 ; 0x5de3 (ARMv6+) */ + #else + #define RSEQ_SIG 0xe7f5def3 /* udf #24035 ; 0x5de3 */ + #endif + #endif + + extern void __disable_interrupts_hard(); + extern void __enable_interrupts_hard(); + + void __kernel_raw_rseq_register (void) { + /* paranoid */ verify( __cfaabi_rseq.cpu_id == RSEQ_CPU_ID_UNINITIALIZED ); + + // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, (sigset_t *)0p, _NSIG / 8); + int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, RSEQ_SIG); + if(ret != 0) { + int e = errno; + switch(e) { + case EINVAL: abort("KERNEL ERROR: rseq register invalid argument"); + case ENOSYS: abort("KERNEL ERROR: rseq register no supported"); + case EFAULT: abort("KERNEL ERROR: rseq register with invalid argument"); + case EBUSY : abort("KERNEL ERROR: rseq register already registered"); + case EPERM : abort("KERNEL ERROR: rseq register sig argument on unregistration does not match the signature received on registration"); + default: abort("KERNEL ERROR: rseq register unexpected return %d", e); + } + } + } + + void __kernel_raw_rseq_unregister(void) { + /* paranoid */ verify( __cfaabi_rseq.cpu_id >= 0 ); + + // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, (sigset_t *)0p, _NSIG / 8); + int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, RSEQ_SIG); + if(ret != 0) { + int e = errno; + switch(e) { + case EINVAL: abort("KERNEL ERROR: rseq unregister invalid argument"); + case ENOSYS: abort("KERNEL ERROR: rseq unregister no supported"); + case EFAULT: abort("KERNEL ERROR: rseq unregister with invalid argument"); + case EBUSY : abort("KERNEL ERROR: rseq unregister already registered"); + case EPERM : abort("KERNEL ERROR: rseq unregister sig argument on unregistration does not match the signature received on registration"); + default: abort("KERNEL ERROR: rseq unregisteunexpected return %d", e); + } + } + } +#else + // No definition needed +#endif Index: libcfa/src/concurrency/ready_subqueue.hfa =================================================================== --- libcfa/src/concurrency/ready_subqueue.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/ready_subqueue.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -32,5 +32,5 @@ this.prev = mock_head(this); this.anchor.next = 0p; - this.anchor.ts = 0; + this.anchor.ts = -1llu; #if !defined(__CFA_NO_STATISTICS__) this.cnt = 0; @@ -44,5 +44,5 @@ /* paranoid */ verify( &mock_head(this)->link.ts == &this.anchor.ts ); /* paranoid */ verify( mock_head(this)->link.next == 0p ); - /* paranoid */ verify( mock_head(this)->link.ts == 0 ); + /* paranoid */ verify( mock_head(this)->link.ts == -1llu ); /* paranoid */ verify( mock_head(this) == this.prev ); /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 ); @@ -55,5 +55,5 @@ // Make sure the list is empty /* paranoid */ verify( this.anchor.next == 0p ); - /* paranoid */ verify( this.anchor.ts == 0 ); + /* paranoid */ verify( this.anchor.ts == -1llu ); /* paranoid */ verify( mock_head(this) == this.prev ); } @@ -64,13 +64,15 @@ /* paranoid */ verify( this.lock ); /* paranoid */ verify( node->link.next == 0p ); - /* paranoid */ verify( node->link.ts == 0 ); + /* paranoid */ verify( node->link.ts == -1llu ); /* paranoid */ verify( this.prev->link.next == 0p ); - /* paranoid */ verify( this.prev->link.ts == 0 ); + /* paranoid */ verify( this.prev->link.ts == -1llu ); if( this.anchor.next == 0p ) { /* paranoid */ verify( this.anchor.next == 0p ); - /* paranoid */ verify( this.anchor.ts == 0 ); + /* paranoid */ verify( this.anchor.ts == -1llu ); + /* paranoid */ verify( this.anchor.ts != 0 ); /* paranoid */ verify( this.prev == mock_head( this ) ); } else { /* paranoid */ verify( this.anchor.next != 0p ); + /* paranoid */ verify( this.anchor.ts != -1llu ); /* paranoid */ verify( this.anchor.ts != 0 ); /* paranoid */ verify( this.prev != mock_head( this ) ); @@ -92,4 +94,5 @@ /* paranoid */ verify( this.lock ); /* paranoid */ verify( this.anchor.next != 0p ); + /* paranoid */ verify( this.anchor.ts != -1llu ); /* paranoid */ verify( this.anchor.ts != 0 ); @@ -99,7 +102,7 @@ this.anchor.next = node->link.next; this.anchor.ts = node->link.ts; - bool is_empty = this.anchor.ts == 0; + bool is_empty = this.anchor.next == 0p; node->link.next = 0p; - node->link.ts = 0; + node->link.ts = -1llu; #if !defined(__CFA_NO_STATISTICS__) this.cnt--; @@ -110,5 +113,7 @@ /* paranoid */ verify( node->link.next == 0p ); - /* paranoid */ verify( node->link.ts == 0 ); + /* paranoid */ verify( node->link.ts == -1llu ); + /* paranoid */ verify( node->link.ts != 0 ); + /* paranoid */ verify( this.anchor.ts != 0 ); return [node, ts]; } @@ -116,5 +121,5 @@ // Check whether or not list is empty static inline bool is_empty(__intrusive_lane_t & this) { - return this.anchor.ts == 0; + return this.anchor.next == 0p; } @@ -122,4 +127,5 @@ static inline unsigned long long ts(__intrusive_lane_t & this) { // Cannot verify here since it may not be locked + /* paranoid */ verify(this.anchor.ts != 0); return this.anchor.ts; } Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/concurrency/thread.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -15,4 +15,5 @@ #define __cforall_thread__ +#define _GNU_SOURCE #include "thread.hfa" @@ -39,5 +40,5 @@ curr_cluster = &cl; link.next = 0p; - link.ts = 0; + link.ts = -1llu; preferred = -1u; last_proc = 0p; Index: libcfa/src/containers/array.hfa =================================================================== --- libcfa/src/containers/array.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/containers/array.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1,13 +1,7 @@ -// a type whose size is n -#define Z(n) char[n] - -// the inverse of Z(-) -#define z(N) sizeof(N) - -forall( T & ) struct tag {}; +forall( __CFA_tysys_id_only_X & ) struct tag {}; #define ttag(T) ((tag(T)){}) -#define ztag(n) ttag(Z(n)) +#define ztag(n) ttag(n) @@ -18,5 +12,5 @@ forall( [N], S & | sized(S), Timmed &, Tbase & ) { struct arpk { - S strides[z(N)]; + S strides[N]; }; @@ -56,14 +50,14 @@ static inline size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) { - return z(N); + return N; } // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa) static inline void ?{}( arpk(N, S, Timmed, Tbase) & this ) { - void ?{}( S (&inner)[z(N)] ) {} + void ?{}( S (&inner)[N] ) {} ?{}(this.strides); } static inline void ^?{}( arpk(N, S, Timmed, Tbase) & this ) { - void ^?{}( S (&inner)[z(N)] ) {} + void ^?{}( S (&inner)[N] ) {} ^?{}(this.strides); } Index: libcfa/src/device/cpu.cfa =================================================================== --- libcfa/src/device/cpu.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/device/cpu.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -253,38 +253,39 @@ } - #if defined(__CFA_WITH_VERIFY__) - // Check widths are consistent - for(i; 1~cpus) { - for(j; cache_levels) { - verifyf(raw[0][j].width == raw[i][j].width, "Unexpected width %u for cpu %u, index %u. Expected %u.", raw[i][j].width, i, j, raw[0][j].width); - } - } - #endif - return raw; } +struct llc_map_t { + raw_cache_instance * raw; + unsigned count; + unsigned start; +}; + // returns an allocate list of all the different distinct last level caches -static [*idx_range_t, size_t cnt] distinct_llcs(unsigned cpus, unsigned llc_idx, raw_cache_instance ** raw) { +static [*llc_map_t, size_t cnt] distinct_llcs(unsigned cpus, unsigned llc_idx, raw_cache_instance ** raw) { // Allocate at least one element - idx_range_t * ranges = alloc(); + llc_map_t* ranges = alloc(); size_t range_cnt = 1; // Initialize with element 0 - *ranges = raw[0][llc_idx].range; + ranges->raw = &raw[0][llc_idx]; + ranges->count = 0; + ranges->start = -1u; // Go over all other cpus CPU_LOOP: for(i; 1~cpus) { // Check if the range is already there - idx_range_t candidate = raw[i][llc_idx].range; + raw_cache_instance * candidate = &raw[i][llc_idx]; for(j; range_cnt) { - idx_range_t exist = ranges[j]; + llc_map_t & exist = ranges[j]; // If the range is already there just jump to the next cpu - if(0 == strcmp(candidate, exist)) continue CPU_LOOP; + if(0 == strcmp(candidate->range, exist.raw->range)) continue CPU_LOOP; } // The range wasn't there, added to the list ranges = alloc(range_cnt + 1, ranges`realloc); - ranges[range_cnt] = candidate; + ranges[range_cnt].raw = candidate; + ranges[range_cnt].count = 0; + ranges[range_cnt].start = -1u; range_cnt++; } @@ -296,12 +297,12 @@ struct cpu_pairing_t { unsigned cpu; - unsigned llc_id; + unsigned id; }; int ?range)) continue MAP_LOOP; + + pairings[i].id = j; continue CPU_LOOP; } @@ -321,4 +322,6 @@ return pairings; } + +#include extern "C" { @@ -345,9 +348,22 @@ // Find number of distinct cache instances - idx_range_t * maps; + llc_map_t * maps; size_t map_cnt; [maps, map_cnt] = distinct_llcs(cpus, cache_levels - llc, raw); - /* paranoid */ verify((map_cnt * raw[0][cache_levels - llc].width) == cpus); + #if defined(__CFA_WITH_VERIFY__) + // Verify that the caches cover the all the cpus + { + unsigned width1 = 0; + unsigned width2 = 0; + for(i; map_cnt) { + const char * _; + width1 += read_width(maps[i].raw->range, strlen(maps[i].raw->range), &_); + width2 += maps[i].raw->width; + } + verify(width1 == cpus); + verify(width2 == cpus); + } + #endif // Get mappings from cpu to cache instance @@ -357,13 +373,31 @@ qsort(pairings, cpus); - unsigned llc_width = raw[0][cache_levels - llc].width; - - // From the mappins build the actual cpu map we want + { + unsigned it = 0; + for(i; cpus) { + unsigned llc_id = pairings[i].id; + if(maps[llc_id].start == -1u) { + maps[llc_id].start = it; + it += maps[llc_id].raw->width; + /* paranoid */ verify(maps[llc_id].start < it); + /* paranoid */ verify(it != -1u); + } + } + /* paranoid */ verify(it == cpus); + } + + // From the mappings build the actual cpu map we want struct cpu_map_entry_t * entries = alloc(cpus); for(i; cpus) { entries[i].count = 0; } for(i; cpus) { + /* paranoid */ verify(pairings[i].id < map_cnt); unsigned c = pairings[i].cpu; - entries[c].start = pairings[i].llc_id * llc_width; - entries[c].count = llc_width; + unsigned llc_id = pairings[i].id; + unsigned width = maps[llc_id].raw->width; + unsigned start = maps[llc_id].start; + unsigned self = start + (maps[llc_id].count++); + entries[c].count = width; + entries[c].start = start; + entries[c].self = self; } Index: libcfa/src/device/cpu.hfa =================================================================== --- libcfa/src/device/cpu.hfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/device/cpu.hfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -17,4 +17,5 @@ struct cpu_map_entry_t { + unsigned self; unsigned start; unsigned count; @@ -22,5 +23,8 @@ struct cpu_info_t { + // array of size [hthrd_count] const cpu_map_entry_t * llc_map; + + // Number of _hardware_ threads present in the system size_t hthrd_count; }; Index: libcfa/src/exception.c =================================================================== --- libcfa/src/exception.c (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ libcfa/src/exception.c (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -256,6 +256,12 @@ // the whole stack. +#if defined( __x86_64 ) || defined( __i386 ) // We did not simply reach the end of the stack without finding a handler. This is an error. if ( ret != _URC_END_OF_STACK ) { +#else // defined( __ARM_ARCH ) + // The return code from _Unwind_RaiseException seems to be corrupt on ARM at end of stack. + // This workaround tries to keep default exception handling working. + if ( ret == _URC_FATAL_PHASE1_ERROR || ret == _URC_FATAL_PHASE2_ERROR ) { +#endif printf("UNWIND ERROR %d after raise exception\n", ret); abort(); Index: libcfa/src/stdhdr/pthread.h =================================================================== --- libcfa/src/stdhdr/pthread.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ libcfa/src/stdhdr/pthread.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,24 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// pthread.h -- +// +// Author : Peter A. Buhr +// Created On : Wed Jun 16 13:39:06 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Jun 16 13:39:42 2021 +// Update Count : 1 +// + +extern "C" { +#include_next // has internal check for multiple expansion +} // extern "C" + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/AST/Convert.cpp (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -2415,4 +2415,15 @@ } + virtual void visit( const DimensionExpr * old ) override final { + // DimensionExpr gets desugared away in Validate. + // As long as new-AST passes don't use it, this cheap-cheerful error + // detection helps ensure that these occurrences have been compiled + // away, as expected. To move the DimensionExpr boundary downstream + // or move the new-AST translation boundary upstream, implement + // DimensionExpr in the new AST and implement a conversion. + (void) old; + assert(false && "DimensionExpr should not be present at new-AST boundary"); + } + virtual void visit( const AsmExpr * old ) override final { this->node = visitBaseExpr( old, Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/AST/Decl.cpp (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -78,5 +78,5 @@ const char * TypeDecl::typeString() const { - static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized array length type" }; + static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized length value" }; static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." ); assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." ); Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/AST/Decl.hpp (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -175,5 +175,5 @@ class TypeDecl final : public NamedTypeDecl { public: - enum Kind { Dtype, DStype, Otype, Ftype, Ttype, ALtype, NUMBER_OF_KINDS }; + enum Kind { Dtype, DStype, Otype, Ftype, Ttype, Dimension, NUMBER_OF_KINDS }; Kind kind; Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/AST/Pass.impl.hpp (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -479,5 +479,5 @@ guard_symtab guard { *this }; // implicit add __func__ identifier as specified in the C manual 6.4.2.2 - static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{ + static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{ CodeLocation{}, "__func__", new ast::ArrayType{ @@ -522,6 +522,7 @@ VISIT({ guard_symtab guard { * this }; - maybe_accept( node, &StructDecl::params ); - maybe_accept( node, &StructDecl::members ); + maybe_accept( node, &StructDecl::params ); + maybe_accept( node, &StructDecl::members ); + maybe_accept( node, &StructDecl::attributes ); }) @@ -543,6 +544,7 @@ VISIT({ guard_symtab guard { * this }; - maybe_accept( node, &UnionDecl::params ); - maybe_accept( node, &UnionDecl::members ); + maybe_accept( node, &UnionDecl::params ); + maybe_accept( node, &UnionDecl::members ); + maybe_accept( node, &UnionDecl::attributes ); }) @@ -562,6 +564,7 @@ VISIT( // unlike structs, traits, and unions, enums inject their members into the global scope - maybe_accept( node, &EnumDecl::params ); - maybe_accept( node, &EnumDecl::members ); + maybe_accept( node, &EnumDecl::params ); + maybe_accept( node, &EnumDecl::members ); + maybe_accept( node, &EnumDecl::attributes ); ) @@ -577,6 +580,7 @@ VISIT({ guard_symtab guard { *this }; - maybe_accept( node, &TraitDecl::params ); - maybe_accept( node, &TraitDecl::members ); + maybe_accept( node, &TraitDecl::params ); + maybe_accept( node, &TraitDecl::members ); + maybe_accept( node, &TraitDecl::attributes ); }) Index: src/CodeGen/CodeGenerator.cc =================================================================== --- src/CodeGen/CodeGenerator.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/CodeGen/CodeGenerator.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -589,4 +589,9 @@ output << nameExpr->get_name(); } // if + } + + void CodeGenerator::postvisit( DimensionExpr * dimensionExpr ) { + extension( dimensionExpr ); + output << "/*non-type*/" << dimensionExpr->get_name(); } Index: src/CodeGen/CodeGenerator.h =================================================================== --- src/CodeGen/CodeGenerator.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/CodeGen/CodeGenerator.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -92,4 +92,5 @@ void postvisit( TupleIndexExpr * tupleExpr ); void postvisit( TypeExpr *typeExpr ); + void postvisit( DimensionExpr *dimensionExpr ); void postvisit( AsmExpr * ); void postvisit( StmtExpr * ); Index: src/Common/PassVisitor.h =================================================================== --- src/Common/PassVisitor.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Common/PassVisitor.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -167,4 +167,6 @@ virtual void visit( TypeExpr * typeExpr ) override final; virtual void visit( const TypeExpr * typeExpr ) override final; + virtual void visit( DimensionExpr * dimensionExpr ) override final; + virtual void visit( const DimensionExpr * dimensionExpr ) override final; virtual void visit( AsmExpr * asmExpr ) override final; virtual void visit( const AsmExpr * asmExpr ) override final; @@ -309,4 +311,5 @@ virtual Expression * mutate( CommaExpr * commaExpr ) override final; virtual Expression * mutate( TypeExpr * typeExpr ) override final; + virtual Expression * mutate( DimensionExpr * dimensionExpr ) override final; virtual Expression * mutate( AsmExpr * asmExpr ) override final; virtual Expression * mutate( ImplicitCopyCtorExpr * impCpCtorExpr ) override final; @@ -542,5 +545,5 @@ class WithIndexer { protected: - WithIndexer() {} + WithIndexer( bool trackIdentifiers = true ) : indexer(trackIdentifiers) {} ~WithIndexer() {} Index: src/Common/PassVisitor.impl.h =================================================================== --- src/Common/PassVisitor.impl.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Common/PassVisitor.impl.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -636,4 +636,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -656,4 +657,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -676,4 +678,5 @@ maybeMutate_impl( node->parameters, *this ); maybeMutate_impl( node->members , *this ); + maybeMutate_impl( node->attributes, *this ); } @@ -697,4 +700,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -714,4 +718,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -732,4 +737,5 @@ maybeMutate_impl( node->parameters, *this ); maybeMutate_impl( node->members , *this ); + maybeMutate_impl( node->attributes, *this ); } @@ -750,4 +756,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); VISIT_END( node ); @@ -763,4 +770,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); VISIT_END( node ); @@ -776,4 +784,5 @@ maybeMutate_impl( node->parameters, *this ); maybeMutate_impl( node->members , *this ); + maybeMutate_impl( node->attributes, *this ); MUTATE_END( Declaration, node ); @@ -790,4 +799,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -805,4 +815,5 @@ maybeAccept_impl( node->parameters, *this ); maybeAccept_impl( node->members , *this ); + maybeAccept_impl( node->attributes, *this ); } @@ -820,4 +831,5 @@ maybeMutate_impl( node->parameters, *this ); maybeMutate_impl( node->members , *this ); + maybeMutate_impl( node->attributes, *this ); } @@ -2507,4 +2519,34 @@ //-------------------------------------------------------------------------- +// DimensionExpr +template< typename pass_type > +void PassVisitor< pass_type >::visit( DimensionExpr * node ) { + VISIT_START( node ); + + indexerScopedAccept( node->result, *this ); + + VISIT_END( node ); +} + +template< typename pass_type > +void PassVisitor< pass_type >::visit( const DimensionExpr * node ) { + VISIT_START( node ); + + indexerScopedAccept( node->result, *this ); + + VISIT_END( node ); +} + +template< typename pass_type > +Expression * PassVisitor< pass_type >::mutate( DimensionExpr * node ) { + MUTATE_START( node ); + + indexerScopedMutate( node->env , *this ); + indexerScopedMutate( node->result, *this ); + + MUTATE_END( Expression, node ); +} + +//-------------------------------------------------------------------------- // AsmExpr template< typename pass_type > @@ -3145,5 +3187,5 @@ maybeAccept_impl( node->forall, *this ); - // xxx - should PointerType visit/mutate dimension? + maybeAccept_impl( node->dimension, *this ); maybeAccept_impl( node->base, *this ); @@ -3156,5 +3198,5 @@ maybeAccept_impl( node->forall, *this ); - // xxx - should PointerType visit/mutate dimension? + maybeAccept_impl( node->dimension, *this ); maybeAccept_impl( node->base, *this ); @@ -3167,5 +3209,5 @@ maybeMutate_impl( node->forall, *this ); - // xxx - should PointerType visit/mutate dimension? + maybeMutate_impl( node->dimension, *this ); maybeMutate_impl( node->base, *this ); @@ -3856,5 +3898,5 @@ //-------------------------------------------------------------------------- -// Attribute +// Constant template< typename pass_type > void PassVisitor< pass_type >::visit( Constant * node ) { Index: src/InitTweak/InitTweak.cc =================================================================== --- src/InitTweak/InitTweak.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/InitTweak/InitTweak.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ // Created On : Fri May 13 11:26:36 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Dec 13 23:15:52 2019 -// Update Count : 8 +// Last Modified On : Wed Jun 16 20:57:22 2021 +// Update Count : 18 // @@ -1217,12 +1217,22 @@ void addDataSectonAttribute( ObjectDecl * objDecl ) { objDecl->attributes.push_back(new Attribute("section", { - new ConstantExpr( Constant::from_string(".data#") ), - })); + new ConstantExpr( Constant::from_string(".data" +#if defined( __x86_64 ) || defined( __i386 ) // assembler comment to prevent assembler warning message + "#" +#else // defined( __ARM_ARCH ) + "//" +#endif + ))})); } void addDataSectionAttribute( ast::ObjectDecl * objDecl ) { objDecl->attributes.push_back(new ast::Attribute("section", { - ast::ConstantExpr::from_string(objDecl->location, ".data#"), - })); + ast::ConstantExpr::from_string(objDecl->location, ".data" +#if defined( __x86_64 ) || defined( __i386 ) // assembler comment to prevent assembler warning message + "#" +#else // defined( __ARM_ARCH ) + "//" +#endif + )})); } Index: src/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/DeclarationNode.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1076,8 +1076,8 @@ if ( variable.tyClass != TypeDecl::NUMBER_OF_KINDS ) { // otype is internally converted to dtype + otype parameters - static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::DStype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype, TypeDecl::Dtype }; + static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::DStype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype, TypeDecl::Dimension }; static_assert( sizeof(kindMap) / sizeof(kindMap[0]) == TypeDecl::NUMBER_OF_KINDS, "DeclarationNode::build: kindMap is out of sync." ); assertf( variable.tyClass < sizeof(kindMap)/sizeof(kindMap[0]), "Variable's tyClass is out of bounds." ); - TypeDecl * ret = new TypeDecl( *name, Type::StorageClasses(), nullptr, kindMap[ variable.tyClass ], variable.tyClass == TypeDecl::Otype || variable.tyClass == TypeDecl::ALtype, variable.initializer ? variable.initializer->buildType() : nullptr ); + TypeDecl * ret = new TypeDecl( *name, Type::StorageClasses(), nullptr, kindMap[ variable.tyClass ], variable.tyClass == TypeDecl::Otype, variable.initializer ? variable.initializer->buildType() : nullptr ); buildList( variable.assertions, ret->get_assertions() ); return ret; Index: src/Parser/ExpressionNode.cc =================================================================== --- src/Parser/ExpressionNode.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/ExpressionNode.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -509,4 +509,9 @@ } // build_varref +DimensionExpr * build_dimensionref( const string * name ) { + DimensionExpr * expr = new DimensionExpr( *name ); + delete name; + return expr; +} // build_varref // TODO: get rid of this and OperKinds and reuse code from OperatorTable static const char * OperName[] = { // must harmonize with OperKinds Index: src/Parser/ParseNode.h =================================================================== --- src/Parser/ParseNode.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/ParseNode.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -183,4 +183,5 @@ NameExpr * build_varref( const std::string * name ); +DimensionExpr * build_dimensionref( const std::string * name ); Expression * build_cast( DeclarationNode * decl_node, ExpressionNode * expr_node ); Index: src/Parser/TypedefTable.cc =================================================================== --- src/Parser/TypedefTable.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/TypedefTable.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:20:13 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Mar 15 20:56:47 2021 -// Update Count : 260 +// Last Modified On : Wed May 19 08:30:14 2021 +// Update Count : 262 // @@ -31,4 +31,5 @@ switch ( kind ) { case IDENTIFIER: return "identifier"; + case TYPEDIMname: return "typedim"; case TYPEDEFname: return "typedef"; case TYPEGENname: return "typegen"; Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/lex.ll (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Thu Apr 1 13:22:31 2021 - * Update Count : 754 + * Last Modified On : Sun Jun 20 18:41:09 2021 + * Update Count : 759 */ @@ -117,10 +117,11 @@ hex_constant {hex_prefix}{hex_digits}{integer_suffix_opt} - // GCC: D (double) and iI (imaginary) suffixes, and DL (long double) + // GCC: floating D (double), imaginary iI, and decimal floating DF, DD, DL exponent "_"?[eE]"_"?[+-]?{decimal_digits} floating_size 16|32|32x|64|64x|80|128|128x floating_length ([fFdDlLwWqQ]|[fF]{floating_size}) floating_suffix ({floating_length}?[iI]?)|([iI]{floating_length}) -floating_suffix_opt ("_"?({floating_suffix}|"DL"))? +decimal_floating_suffix [dD][fFdDlL] +floating_suffix_opt ("_"?({floating_suffix}|{decimal_floating_suffix}))? decimal_digits ({decimal})|({decimal}({decimal}|"_")*{decimal}) floating_decimal {decimal_digits}"."{exponent}?{floating_suffix_opt} @@ -234,4 +235,7 @@ continue { KEYWORD_RETURN(CONTINUE); } coroutine { KEYWORD_RETURN(COROUTINE); } // CFA +_Decimal32 { KEYWORD_RETURN(DECIMAL32); } // GCC +_Decimal64 { KEYWORD_RETURN(DECIMAL64); } // GCC +_Decimal128 { KEYWORD_RETURN(DECIMAL128); } // GCC default { KEYWORD_RETURN(DEFAULT); } disable { KEYWORD_RETURN(DISABLE); } // CFA Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/Parser/parser.yy (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Apr 26 18:41:54 2021 -// Update Count : 4990 +// Last Modified On : Sun Jun 20 18:46:51 2021 +// Update Count : 5023 // @@ -269,4 +269,5 @@ %token INT128 UINT128 uuFLOAT80 uuFLOAT128 // GCC %token uFLOAT16 uFLOAT32 uFLOAT32X uFLOAT64 uFLOAT64X uFLOAT128 // GCC +%token DECIMAL32 DECIMAL64 DECIMAL128 // GCC %token ZERO_T ONE_T // CFA %token SIZEOF TYPEOF VALIST AUTO_TYPE // GCC @@ -287,5 +288,5 @@ // names and constants: lexer differentiates between identifier and typedef names -%token IDENTIFIER QUOTED_IDENTIFIER TYPEDEFname TYPEGENname +%token IDENTIFIER QUOTED_IDENTIFIER TYPEDIMname TYPEDEFname TYPEGENname %token TIMEOUT WOR CATCH RECOVER CATCHRESUME FIXUP FINALLY // CFA %token INTEGERconstant CHARACTERconstant STRINGliteral @@ -586,4 +587,8 @@ | quasi_keyword { $$ = new ExpressionNode( build_varref( $1 ) ); } + | TYPEDIMname // CFA, generic length argument + // { $$ = new ExpressionNode( new TypeExpr( maybeMoveBuildType( DeclarationNode::newFromTypedef( $1 ) ) ) ); } + // { $$ = new ExpressionNode( build_varref( $1 ) ); } + { $$ = new ExpressionNode( build_dimensionref( $1 ) ); } | tuple | '(' comma_expression ')' @@ -1887,4 +1892,10 @@ | uFLOAT128 { $$ = DeclarationNode::newBasicType( DeclarationNode::uFloat128 ); } + | DECIMAL32 + { SemanticError( yylloc, "_Decimal32 is currently unimplemented." ); $$ = nullptr; } + | DECIMAL64 + { SemanticError( yylloc, "_Decimal64 is currently unimplemented." ); $$ = nullptr; } + | DECIMAL128 + { SemanticError( yylloc, "_Decimal128 is currently unimplemented." ); $$ = nullptr; } | COMPLEX // C99 { $$ = DeclarationNode::newComplexType( DeclarationNode::Complex ); } @@ -2535,6 +2546,6 @@ | '[' identifier_or_type_name ']' { - typedefTable.addToScope( *$2, TYPEDEFname, "9" ); - $$ = DeclarationNode::newTypeParam( TypeDecl::ALtype, $2 ); + typedefTable.addToScope( *$2, TYPEDIMname, "9" ); + $$ = DeclarationNode::newTypeParam( TypeDecl::Dimension, $2 ); } // | type_specifier identifier_parameter_declarator @@ -2590,10 +2601,8 @@ { $$ = new ExpressionNode( new TypeExpr( maybeMoveBuildType( $1 ) ) ); } | assignment_expression - { SemanticError( yylloc, toString("Expression generic parameters are currently unimplemented: ", $1->build()) ); $$ = nullptr; } | type_list ',' type { $$ = (ExpressionNode *)($1->set_last( new ExpressionNode( new TypeExpr( maybeMoveBuildType( $3 ) ) ) )); } | type_list ',' assignment_expression - { SemanticError( yylloc, toString("Expression generic parameters are currently unimplemented: ", $3->build()) ); $$ = nullptr; } - // { $$ = (ExpressionNode *)( $1->set_last( $3 )); } + { $$ = (ExpressionNode *)( $1->set_last( $3 )); } ; Index: src/SymTab/Indexer.cc =================================================================== --- src/SymTab/Indexer.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SymTab/Indexer.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -74,7 +74,7 @@ } - Indexer::Indexer() + Indexer::Indexer( bool trackIdentifiers ) : idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(), - prevScope(), scope( 0 ), repScope( 0 ) { ++* stats().count; } + prevScope(), scope( 0 ), repScope( 0 ), trackIdentifiers( trackIdentifiers ) { ++* stats().count; } Indexer::~Indexer() { @@ -110,4 +110,6 @@ void Indexer::lookupId( const std::string & id, std::list< IdData > &out ) const { + assert( trackIdentifiers ); + ++* stats().lookup_calls; if ( ! idTable ) return; @@ -434,4 +436,5 @@ const Declaration * deleteStmt ) { ++* stats().add_calls; + if ( ! trackIdentifiers ) return; const std::string &name = decl->name; if ( name == "" ) return; Index: src/SymTab/Indexer.h =================================================================== --- src/SymTab/Indexer.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SymTab/Indexer.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -31,5 +31,5 @@ class Indexer : public std::enable_shared_from_this { public: - explicit Indexer(); + explicit Indexer( bool trackIdentifiers = true ); virtual ~Indexer(); @@ -180,4 +180,6 @@ /// returns true if there exists a declaration with C linkage and the given name with a different mangled name bool hasIncompatibleCDecl( const std::string & id, const std::string & mangleName ) const; + + bool trackIdentifiers; }; } // namespace SymTab Index: src/SymTab/Validate.cc =================================================================== --- src/SymTab/Validate.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SymTab/Validate.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -105,4 +105,5 @@ struct FixQualifiedTypes final : public WithIndexer { + FixQualifiedTypes() : WithIndexer(false) {} Type * postmutate( QualifiedType * ); }; @@ -174,4 +175,14 @@ }; + /// Does early resolution on the expressions that give enumeration constants their values + struct ResolveEnumInitializers final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting { + ResolveEnumInitializers( const Indexer * indexer ); + void postvisit( EnumDecl * enumDecl ); + + private: + const Indexer * local_indexer; + + }; + /// Replaces array and function types in forall lists by appropriate pointer type and assigns each Object and Function declaration a unique ID. struct ForallPointerDecay_old final { @@ -260,4 +271,23 @@ void previsit( StructInstType * inst ); void previsit( UnionInstType * inst ); + }; + + /// desugar declarations and uses of dimension paramaters like [N], + /// from type-system managed values, to tunnneling via ordinary types, + /// as char[-] in and sizeof(-) out + struct TranslateDimensionGenericParameters : public WithIndexer, public WithGuards { + static void translateDimensions( std::list< Declaration * > &translationUnit ); + TranslateDimensionGenericParameters(); + + bool nextVisitedNodeIsChildOfSUIT = false; // SUIT = Struct or Union -Inst Type + bool visitingChildOfSUIT = false; + void changeState_ChildOfSUIT( bool newVal ); + void premutate( StructInstType * sit ); + void premutate( UnionInstType * uit ); + void premutate( BaseSyntaxNode * node ); + + TypeDecl * postmutate( TypeDecl * td ); + Expression * postmutate( DimensionExpr * de ); + Expression * postmutate( Expression * e ); }; @@ -307,4 +337,5 @@ PassVisitor epc; PassVisitor lrt( nullptr ); + PassVisitor rei( nullptr ); PassVisitor fpd; PassVisitor compoundliteral; @@ -326,23 +357,27 @@ Stats::Heap::newPass("validate-B"); Stats::Time::BlockGuard guard("validate-B"); - Stats::Time::TimeBlock("Link Reference To Types", [&]() { - acceptAll( translationUnit, lrt ); // must happen before autogen, because sized flag needs to propagate to generated functions - }); - Stats::Time::TimeBlock("Fix Qualified Types", [&]() { - mutateAll( translationUnit, fixQual ); // must happen after LinkReferenceToTypes_old, because aggregate members are accessed - }); - Stats::Time::TimeBlock("Hoist Structs", [&]() { - HoistStruct::hoistStruct( translationUnit ); // must happen after EliminateTypedef, so that aggregate typedefs occur in the correct order - }); - Stats::Time::TimeBlock("Eliminate Typedefs", [&]() { - EliminateTypedef::eliminateTypedef( translationUnit ); // - }); + acceptAll( translationUnit, lrt ); // must happen before autogen, because sized flag needs to propagate to generated functions + mutateAll( translationUnit, fixQual ); // must happen after LinkReferenceToTypes_old, because aggregate members are accessed + HoistStruct::hoistStruct( translationUnit ); + EliminateTypedef::eliminateTypedef( translationUnit ); } { Stats::Heap::newPass("validate-C"); Stats::Time::BlockGuard guard("validate-C"); - acceptAll( translationUnit, genericParams ); // check as early as possible - can't happen before LinkReferenceToTypes_old - ReturnChecker::checkFunctionReturns( translationUnit ); - InitTweak::fixReturnStatements( translationUnit ); // must happen before autogen + Stats::Time::TimeBlock("Validate Generic Parameters", [&]() { + acceptAll( translationUnit, genericParams ); // check as early as possible - can't happen before LinkReferenceToTypes_old; observed failing when attempted before eliminateTypedef + }); + Stats::Time::TimeBlock("Translate Dimensions", [&]() { + TranslateDimensionGenericParameters::translateDimensions( translationUnit ); + }); + Stats::Time::TimeBlock("Resolve Enum Initializers", [&]() { + acceptAll( translationUnit, rei ); // must happen after translateDimensions because rei needs identifier lookup, which needs name mangling + }); + Stats::Time::TimeBlock("Check Function Returns", [&]() { + ReturnChecker::checkFunctionReturns( translationUnit ); + }); + Stats::Time::TimeBlock("Fix Return Statements", [&]() { + InitTweak::fixReturnStatements( translationUnit ); // must happen before autogen + }); } { @@ -644,5 +679,5 @@ } - LinkReferenceToTypes_old::LinkReferenceToTypes_old( const Indexer * other_indexer ) { + LinkReferenceToTypes_old::LinkReferenceToTypes_old( const Indexer * other_indexer ) : WithIndexer( false ) { if ( other_indexer ) { local_indexer = other_indexer; @@ -664,12 +699,4 @@ } - void checkGenericParameters( ReferenceToType * inst ) { - for ( Expression * param : inst->parameters ) { - if ( ! dynamic_cast< TypeExpr * >( param ) ) { - SemanticError( inst, "Expression parameters for generic types are currently unsupported: " ); - } - } - } - void LinkReferenceToTypes_old::postvisit( StructInstType * structInst ) { const StructDecl * st = local_indexer->lookupStruct( structInst->name ); @@ -682,5 +709,4 @@ forwardStructs[ structInst->name ].push_back( structInst ); } // if - checkGenericParameters( structInst ); } @@ -695,5 +721,4 @@ forwardUnions[ unionInst->name ].push_back( unionInst ); } // if - checkGenericParameters( unionInst ); } @@ -807,13 +832,4 @@ forwardEnums.erase( fwds ); } // if - - for ( Declaration * member : enumDecl->members ) { - ObjectDecl * field = strict_dynamic_cast( member ); - if ( field->init ) { - // need to resolve enumerator initializers early so that other passes that determine if an expression is constexpr have the appropriate information. - SingleInit * init = strict_dynamic_cast( field->init ); - ResolvExpr::findSingleExpression( init->value, new BasicType( Type::Qualifiers(), BasicType::SignedInt ), indexer ); - } - } } // if } @@ -878,4 +894,25 @@ typeInst->set_isFtype( typeDecl->kind == TypeDecl::Ftype ); } // if + } // if + } + + ResolveEnumInitializers::ResolveEnumInitializers( const Indexer * other_indexer ) : WithIndexer( true ) { + if ( other_indexer ) { + local_indexer = other_indexer; + } else { + local_indexer = &indexer; + } // if + } + + void ResolveEnumInitializers::postvisit( EnumDecl * enumDecl ) { + if ( enumDecl->body ) { + for ( Declaration * member : enumDecl->members ) { + ObjectDecl * field = strict_dynamic_cast( member ); + if ( field->init ) { + // need to resolve enumerator initializers early so that other passes that determine if an expression is constexpr have the appropriate information. + SingleInit * init = strict_dynamic_cast( field->init ); + ResolvExpr::findSingleExpression( init->value, new BasicType( Type::Qualifiers(), BasicType::SignedInt ), indexer ); + } + } } // if } @@ -1152,4 +1189,5 @@ GuardScope( typedeclNames ); mutateAll( aggr->parameters, * visitor ); + mutateAll( aggr->attributes, * visitor ); // unroll mutateAll for aggr->members so that implicit typedefs for nested types are added to the aggregate body. @@ -1220,4 +1258,22 @@ } } + } + + // Test for special name on a generic parameter. Special treatment for the + // special name is a bootstrapping hack. In most cases, the worlds of T's + // and of N's don't overlap (normal treamtemt). The foundations in + // array.hfa use tagging for both types and dimensions. Tagging treats + // its subject parameter even more opaquely than T&, which assumes it is + // possible to have a pointer/reference to such an object. Tagging only + // seeks to identify the type-system resident at compile time. Both N's + // and T's can make tags. The tag definition uses the special name, which + // is treated as "an N or a T." This feature is not inteded to be used + // outside of the definition and immediate uses of a tag. + static inline bool isReservedTysysIdOnlyName( const std::string & name ) { + // name's prefix was __CFA_tysys_id_only, before it got wrapped in __..._generic + int foundAt = name.find("__CFA_tysys_id_only"); + if (foundAt == 0) return true; + if (foundAt == 2 && name[0] == '_' && name[1] == '_') return true; + return false; } @@ -1238,19 +1294,35 @@ TypeSubstitution sub; auto paramIter = params->begin(); - for ( size_t i = 0; paramIter != params->end(); ++paramIter, ++i ) { - if ( i < args.size() ) { - TypeExpr * expr = strict_dynamic_cast< TypeExpr * >( * std::next( args.begin(), i ) ); - sub.add( (* paramIter)->get_name(), expr->get_type()->clone() ); - } else if ( i == args.size() ) { + auto argIter = args.begin(); + for ( ; paramIter != params->end(); ++paramIter, ++argIter ) { + if ( argIter != args.end() ) { + TypeExpr * expr = dynamic_cast< TypeExpr * >( * argIter ); + if ( expr ) { + sub.add( (* paramIter)->get_name(), expr->get_type()->clone() ); + } + } else { Type * defaultType = (* paramIter)->get_init(); if ( defaultType ) { args.push_back( new TypeExpr( defaultType->clone() ) ); sub.add( (* paramIter)->get_name(), defaultType->clone() ); + argIter = std::prev(args.end()); + } else { + SemanticError( inst, "Too few type arguments in generic type " ); } } + assert( argIter != args.end() ); + bool typeParamDeclared = (*paramIter)->kind != TypeDecl::Kind::Dimension; + bool typeArgGiven; + if ( isReservedTysysIdOnlyName( (*paramIter)->name ) ) { + // coerce a match when declaration is reserved name, which means "either" + typeArgGiven = typeParamDeclared; + } else { + typeArgGiven = dynamic_cast< TypeExpr * >( * argIter ); + } + if ( ! typeParamDeclared && typeArgGiven ) SemanticError( inst, "Type argument given for value parameter: " ); + if ( typeParamDeclared && ! typeArgGiven ) SemanticError( inst, "Expression argument given for type parameter: " ); } sub.apply( inst ); - if ( args.size() < params->size() ) SemanticError( inst, "Too few type arguments in generic type " ); if ( args.size() > params->size() ) SemanticError( inst, "Too many type arguments in generic type " ); } @@ -1263,4 +1335,104 @@ void ValidateGenericParameters::previsit( UnionInstType * inst ) { validateGeneric( inst ); + } + + void TranslateDimensionGenericParameters::translateDimensions( std::list< Declaration * > &translationUnit ) { + PassVisitor translator; + mutateAll( translationUnit, translator ); + } + + TranslateDimensionGenericParameters::TranslateDimensionGenericParameters() : WithIndexer( false ) {} + + // Declaration of type variable: forall( [N] ) -> forall( N & | sized( N ) ) + TypeDecl * TranslateDimensionGenericParameters::postmutate( TypeDecl * td ) { + if ( td->kind == TypeDecl::Dimension ) { + td->kind = TypeDecl::Dtype; + if ( ! isReservedTysysIdOnlyName( td->name ) ) { + td->sized = true; + } + } + return td; + } + + // Situational awareness: + // array( float, [[currentExpr]] ) has visitingChildOfSUIT == true + // array( float, [[currentExpr]] - 1 ) has visitingChildOfSUIT == false + // size_t x = [[currentExpr]] has visitingChildOfSUIT == false + void TranslateDimensionGenericParameters::changeState_ChildOfSUIT( bool newVal ) { + GuardValue( nextVisitedNodeIsChildOfSUIT ); + GuardValue( visitingChildOfSUIT ); + visitingChildOfSUIT = nextVisitedNodeIsChildOfSUIT; + nextVisitedNodeIsChildOfSUIT = newVal; + } + void TranslateDimensionGenericParameters::premutate( StructInstType * sit ) { + (void) sit; + changeState_ChildOfSUIT(true); + } + void TranslateDimensionGenericParameters::premutate( UnionInstType * uit ) { + (void) uit; + changeState_ChildOfSUIT(true); + } + void TranslateDimensionGenericParameters::premutate( BaseSyntaxNode * node ) { + (void) node; + changeState_ChildOfSUIT(false); + } + + // Passing values as dimension arguments: array( float, 7 ) -> array( float, char[ 7 ] ) + // Consuming dimension parameters: size_t x = N - 1 ; -> size_t x = sizeof(N) - 1 ; + // Intertwined reality: array( float, N ) -> array( float, N ) + // array( float, N - 1 ) -> array( float, char[ sizeof(N) - 1 ] ) + // Intertwined case 1 is not just an optimization. + // Avoiding char[sizeof(-)] is necessary to enable the call of f to bind the value of N, in: + // forall([N]) void f( array(float, N) & ); + // array(float, 7) a; + // f(a); + + Expression * TranslateDimensionGenericParameters::postmutate( DimensionExpr * de ) { + // Expression de is an occurrence of N in LHS of above examples. + // Look up the name that de references. + // If we are in a struct body, then this reference can be to an entry of the stuct's forall list. + // Whether or not we are in a struct body, this reference can be to an entry of a containing function's forall list. + // If we are in a struct body, then the stuct's forall declarations are innermost (functions don't occur in structs). + // Thus, a potential struct's declaration is highest priority. + // A struct's forall declarations are already renamed with _generic_ suffix. Try that name variant first. + + std::string useName = "__" + de->name + "_generic_"; + TypeDecl * namedParamDecl = const_cast( strict_dynamic_cast( indexer.lookupType( useName ) ) ); + + if ( ! namedParamDecl ) { + useName = de->name; + namedParamDecl = const_cast( strict_dynamic_cast( indexer.lookupType( useName ) ) ); + } + + // Expect to find it always. A misspelled name would have been parsed as an identifier. + assert( namedParamDecl && "Type-system-managed value name not found in symbol table" ); + + delete de; + + TypeInstType * refToDecl = new TypeInstType( 0, useName, namedParamDecl ); + + if ( visitingChildOfSUIT ) { + // As in postmutate( Expression * ), topmost expression needs a TypeExpr wrapper + // But avoid ArrayType-Sizeof + return new TypeExpr( refToDecl ); + } else { + // the N occurrence is being used directly as a runtime value, + // if we are in a type instantiation, then the N is within a bigger value computation + return new SizeofExpr( refToDecl ); + } + } + + Expression * TranslateDimensionGenericParameters::postmutate( Expression * e ) { + if ( visitingChildOfSUIT ) { + // e is an expression used as an argument to instantiate a type + if (! dynamic_cast< TypeExpr * >( e ) ) { + // e is a value expression + // but not a DimensionExpr, which has a distinct postmutate + Type * typeExprContent = new ArrayType( 0, new BasicType( 0, BasicType::Char ), e, true, false ); + TypeExpr * result = new TypeExpr( typeExprContent ); + return result; + } + } + return e; } Index: src/SynTree/Declaration.h =================================================================== --- src/SynTree/Declaration.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/Declaration.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -201,5 +201,5 @@ typedef NamedTypeDecl Parent; public: - enum Kind { Dtype, DStype, Otype, Ftype, Ttype, ALtype, NUMBER_OF_KINDS }; + enum Kind { Dtype, DStype, Otype, Ftype, Ttype, Dimension, NUMBER_OF_KINDS }; Kind kind; Index: src/SynTree/Expression.h =================================================================== --- src/SynTree/Expression.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/Expression.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -587,4 +587,23 @@ }; +/// DimensionExpr represents a type-system provided value used in an expression ( forrall([N]) ... N + 1 ) +class DimensionExpr : public Expression { + public: + std::string name; + + DimensionExpr( std::string name ); + DimensionExpr( const DimensionExpr & other ); + virtual ~DimensionExpr(); + + const std::string & get_name() const { return name; } + void set_name( std::string newValue ) { name = newValue; } + + virtual DimensionExpr * clone() const override { return new DimensionExpr( * 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; +}; + /// AsmExpr represents a GCC 'asm constraint operand' used in an asm statement: [output] "=f" (result) class AsmExpr : public Expression { Index: src/SynTree/Mutator.h =================================================================== --- src/SynTree/Mutator.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/Mutator.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -80,4 +80,5 @@ virtual Expression * mutate( CommaExpr * commaExpr ) = 0; virtual Expression * mutate( TypeExpr * typeExpr ) = 0; + virtual Expression * mutate( DimensionExpr * dimensionExpr ) = 0; virtual Expression * mutate( AsmExpr * asmExpr ) = 0; virtual Expression * mutate( ImplicitCopyCtorExpr * impCpCtorExpr ) = 0; Index: src/SynTree/SynTree.h =================================================================== --- src/SynTree/SynTree.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/SynTree.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -85,4 +85,5 @@ class CommaExpr; class TypeExpr; +class DimensionExpr; class AsmExpr; class ImplicitCopyCtorExpr; Index: src/SynTree/TypeDecl.cc =================================================================== --- src/SynTree/TypeDecl.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/TypeDecl.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -33,5 +33,5 @@ const char * TypeDecl::typeString() const { - static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized array length type" }; + static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized length value" }; static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." ); assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." ); Index: src/SynTree/TypeExpr.cc =================================================================== --- src/SynTree/TypeExpr.cc (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/TypeExpr.cc (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -35,4 +35,18 @@ } +DimensionExpr::DimensionExpr( std::string name ) : Expression(), name(name) { + assertf(name != "0", "Zero is not a valid name"); + assertf(name != "1", "One is not a valid name"); +} + +DimensionExpr::DimensionExpr( const DimensionExpr & other ) : Expression( other ), name( other.name ) { +} + +DimensionExpr::~DimensionExpr() {} + +void DimensionExpr::print( std::ostream & os, Indenter indent ) const { + os << "Type-Sys Value: " << get_name(); + Expression::print( os, indent ); +} // Local Variables: // // tab-width: 4 // Index: src/SynTree/Visitor.h =================================================================== --- src/SynTree/Visitor.h (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ src/SynTree/Visitor.h (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -135,4 +135,6 @@ virtual void visit( TypeExpr * node ) { visit( const_cast(node) ); } virtual void visit( const TypeExpr * typeExpr ) = 0; + virtual void visit( DimensionExpr * node ) { visit( const_cast(node) ); } + virtual void visit( const DimensionExpr * typeExpr ) = 0; virtual void visit( AsmExpr * node ) { visit( const_cast(node) ); } virtual void visit( const AsmExpr * asmExpr ) = 0; Index: tests/.expect/gmp.arm64.txt =================================================================== --- tests/.expect/gmp.arm64.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ tests/.expect/gmp.arm64.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,279 @@ +constructors +50000000000000000000 3 50000000000000000003 +x:50000000000000000000 y:3 z:50000000000000000003 +conversions +y:97 +y:12345678901234567890123456789 +y:200 +y:-400 +y:24691357802469135780246913578 +y:3 +y:-3 +y:4 +y:3 +y:3 b:3 si:3 +comparison +1 +0 +0 +1 +0 +1 +arithmetic +z:100000000000000000006 +z:50000000000000000000 +z:-3 +z:-450000000000000000000 +z:150000000000000000000 +z:150000000000000000000 +z:16666666666666666666 +16666666666666666666, 2 16666666666666666666, 2 +x:16666666666666666666 y:2 + +12345678901234567890123456789 12345678901234567890123456789 12345678901234567890123456789 + +Fibonacci Numbers +0 0 +1 1 +2 1 +3 2 +4 3 +5 5 +6 8 +7 13 +8 21 +9 34 +10 55 +11 89 +12 144 +13 233 +14 377 +15 610 +16 987 +17 1597 +18 2584 +19 4181 +20 6765 +21 10946 +22 17711 +23 28657 +24 46368 +25 75025 +26 121393 +27 196418 +28 317811 +29 514229 +30 832040 +31 1346269 +32 2178309 +33 3524578 +34 5702887 +35 9227465 +36 14930352 +37 24157817 +38 39088169 +39 63245986 +40 102334155 +41 165580141 +42 267914296 +43 433494437 +44 701408733 +45 1134903170 +46 1836311903 +47 2971215073 +48 4807526976 +49 7778742049 +50 12586269025 +51 20365011074 +52 32951280099 +53 53316291173 +54 86267571272 +55 139583862445 +56 225851433717 +57 365435296162 +58 591286729879 +59 956722026041 +60 1548008755920 +61 2504730781961 +62 4052739537881 +63 6557470319842 +64 10610209857723 +65 17167680177565 +66 27777890035288 +67 44945570212853 +68 72723460248141 +69 117669030460994 +70 190392490709135 +71 308061521170129 +72 498454011879264 +73 806515533049393 +74 1304969544928657 +75 2111485077978050 +76 3416454622906707 +77 5527939700884757 +78 8944394323791464 +79 14472334024676221 +80 23416728348467685 +81 37889062373143906 +82 61305790721611591 +83 99194853094755497 +84 160500643816367088 +85 259695496911122585 +86 420196140727489673 +87 679891637638612258 +88 1100087778366101931 +89 1779979416004714189 +90 2880067194370816120 +91 4660046610375530309 +92 7540113804746346429 +93 12200160415121876738 +94 19740274219868223167 +95 31940434634990099905 +96 51680708854858323072 +97 83621143489848422977 +98 135301852344706746049 +99 218922995834555169026 +100 354224848179261915075 +101 573147844013817084101 +102 927372692193078999176 +103 1500520536206896083277 +104 2427893228399975082453 +105 3928413764606871165730 +106 6356306993006846248183 +107 10284720757613717413913 +108 16641027750620563662096 +109 26925748508234281076009 +110 43566776258854844738105 +111 70492524767089125814114 +112 114059301025943970552219 +113 184551825793033096366333 +114 298611126818977066918552 +115 483162952612010163284885 +116 781774079430987230203437 +117 1264937032042997393488322 +118 2046711111473984623691759 +119 3311648143516982017180081 +120 5358359254990966640871840 +121 8670007398507948658051921 +122 14028366653498915298923761 +123 22698374052006863956975682 +124 36726740705505779255899443 +125 59425114757512643212875125 +126 96151855463018422468774568 +127 155576970220531065681649693 +128 251728825683549488150424261 +129 407305795904080553832073954 +130 659034621587630041982498215 +131 1066340417491710595814572169 +132 1725375039079340637797070384 +133 2791715456571051233611642553 +134 4517090495650391871408712937 +135 7308805952221443105020355490 +136 11825896447871834976429068427 +137 19134702400093278081449423917 +138 30960598847965113057878492344 +139 50095301248058391139327916261 +140 81055900096023504197206408605 +141 131151201344081895336534324866 +142 212207101440105399533740733471 +143 343358302784187294870275058337 +144 555565404224292694404015791808 +145 898923707008479989274290850145 +146 1454489111232772683678306641953 +147 2353412818241252672952597492098 +148 3807901929474025356630904134051 +149 6161314747715278029583501626149 +150 9969216677189303386214405760200 +151 16130531424904581415797907386349 +152 26099748102093884802012313146549 +153 42230279526998466217810220532898 +154 68330027629092351019822533679447 +155 110560307156090817237632754212345 +156 178890334785183168257455287891792 +157 289450641941273985495088042104137 +158 468340976726457153752543329995929 +159 757791618667731139247631372100066 +160 1226132595394188293000174702095995 +161 1983924214061919432247806074196061 +162 3210056809456107725247980776292056 +163 5193981023518027157495786850488117 +164 8404037832974134882743767626780173 +165 13598018856492162040239554477268290 +166 22002056689466296922983322104048463 +167 35600075545958458963222876581316753 +168 57602132235424755886206198685365216 +169 93202207781383214849429075266681969 +170 150804340016807970735635273952047185 +171 244006547798191185585064349218729154 +172 394810887814999156320699623170776339 +173 638817435613190341905763972389505493 +174 1033628323428189498226463595560281832 +175 1672445759041379840132227567949787325 +176 2706074082469569338358691163510069157 +177 4378519841510949178490918731459856482 +178 7084593923980518516849609894969925639 +179 11463113765491467695340528626429782121 +180 18547707689471986212190138521399707760 +181 30010821454963453907530667147829489881 +182 48558529144435440119720805669229197641 +183 78569350599398894027251472817058687522 +184 127127879743834334146972278486287885163 +185 205697230343233228174223751303346572685 +186 332825110087067562321196029789634457848 +187 538522340430300790495419781092981030533 +188 871347450517368352816615810882615488381 +189 1409869790947669143312035591975596518914 +190 2281217241465037496128651402858212007295 +191 3691087032412706639440686994833808526209 +192 5972304273877744135569338397692020533504 +193 9663391306290450775010025392525829059713 +194 15635695580168194910579363790217849593217 +195 25299086886458645685589389182743678652930 +196 40934782466626840596168752972961528246147 +197 66233869353085486281758142155705206899077 +198 107168651819712326877926895128666735145224 +199 173402521172797813159685037284371942044301 +200 280571172992510140037611932413038677189525 + +Factorial Numbers +0 1 +1 1 +2 2 +3 6 +4 24 +5 120 +6 720 +7 5040 +8 40320 +9 362880 +10 3628800 +11 39916800 +12 479001600 +13 6227020800 +14 87178291200 +15 1307674368000 +16 20922789888000 +17 355687428096000 +18 6402373705728000 +19 121645100408832000 +20 2432902008176640000 +21 51090942171709440000 +22 1124000727777607680000 +23 25852016738884976640000 +24 620448401733239439360000 +25 15511210043330985984000000 +26 403291461126605635584000000 +27 10888869450418352160768000000 +28 304888344611713860501504000000 +29 8841761993739701954543616000000 +30 265252859812191058636308480000000 +31 8222838654177922817725562880000000 +32 263130836933693530167218012160000000 +33 8683317618811886495518194401280000000 +34 295232799039604140847618609643520000000 +35 10333147966386144929666651337523200000000 +36 371993326789901217467999448150835200000000 +37 13763753091226345046315979581580902400000000 +38 523022617466601111760007224100074291200000000 +39 20397882081197443358640281739902897356800000000 +40 815915283247897734345611269596115894272000000000 Index: tests/.expect/typedefRedef-ERR1.txt =================================================================== --- tests/.expect/typedefRedef-ERR1.txt (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/.expect/typedefRedef-ERR1.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1,3 +1,3 @@ -typedefRedef.cfa:69:25: warning: Compiled +typedefRedef.cfa:75:25: warning: Compiled typedefRedef.cfa:4:1 error: Cannot redefine typedef: Foo -typedefRedef.cfa:59:1 error: Cannot redefine typedef: ARR +typedefRedef.cfa:65:1 error: Cannot redefine typedef: ARR Index: tests/.expect/typedefRedef.txt =================================================================== --- tests/.expect/typedefRedef.txt (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/.expect/typedefRedef.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -1,1 +1,1 @@ -typedefRedef.cfa:69:25: warning: Compiled +typedefRedef.cfa:75:25: warning: Compiled Index: tests/array-container/.expect/array-md-sbscr-cases.arm64.txt =================================================================== --- tests/array-container/.expect/array-md-sbscr-cases.arm64.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ tests/array-container/.expect/array-md-sbscr-cases.arm64.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,1 @@ +done Index: tests/array-container/.expect/array-md-sbscr-cases.x86.txt =================================================================== --- tests/array-container/.expect/array-md-sbscr-cases.x86.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ tests/array-container/.expect/array-md-sbscr-cases.x86.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,1 @@ +done Index: tests/array-container/.expect/language-dim-mismatch.txt =================================================================== --- tests/array-container/.expect/language-dim-mismatch.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ tests/array-container/.expect/language-dim-mismatch.txt (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,10 @@ +array-container/language-dim-mismatch.cfa:12:1 error: Type argument given for value parameter: instance of struct SN with body 1 +... with parameters + float + +array-container/language-dim-mismatch.cfa:13:1 error: Expression argument given for type parameter: instance of struct ST with body 1 +... with parameters + constant expression (42 42: signed int) + with resolved type: + signed int + Index: tests/array-container/array-basic.cfa =================================================================== --- tests/array-container/array-basic.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/array-container/array-basic.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -61,17 +61,17 @@ forall( [Nw], [Nx], [Ny], [Nz] ) void fillHelloData( array( float, Nw, Nx, Ny, Nz ) & wxyz ) { - for (w; z(Nw)) - for (x; z(Nx)) - for (y; z(Ny)) - for (z; z(Nz)) + for (w; Nw) + for (x; Nx) + for (y; Ny) + for (z; Nz) wxyz[w][x][y][z] = getMagicNumber(w, x, y, z); } -forall( [Zn] +forall( [N] , S & | sized(S) ) -float total1d_low( arpk(Zn, S, float, float ) & a ) { +float total1d_low( arpk(N, S, float, float ) & a ) { float total = 0.0f; - for (i; z(Zn)) + for (i; N) total += a[i]; return total; @@ -98,5 +98,5 @@ expect = 0; - for (i; z(Nw)) + for (i; Nw) expect += getMagicNumber( i, slice_ix, slice_ix, slice_ix ); printf("expect Ws = %f\n", expect); @@ -117,5 +117,5 @@ expect = 0; - for (i; z(Nx)) + for (i; Nx) expect += getMagicNumber( slice_ix, i, slice_ix, slice_ix ); printf("expect Xs = %f\n", expect); Index: tests/array-container/array-md-sbscr-cases.cfa =================================================================== --- tests/array-container/array-md-sbscr-cases.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/array-container/array-md-sbscr-cases.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -20,8 +20,8 @@ forall( [Nw], [Nx], [Ny], [Nz] ) void fillHelloData( array( float, Nw, Nx, Ny, Nz ) & wxyz ) { - for (w; z(Nw)) - for (x; z(Nx)) - for (y; z(Ny)) - for (z; z(Nz)) + for (w; Nw) + for (x; Nx) + for (y; Ny) + for (z; Nz) wxyz[w][x][y][z] = getMagicNumber(w, x, y, z); } @@ -246,25 +246,25 @@ assert(( wxyz[[2, 3, 4, 5]] == valExpected )); - for ( i; z(Nw) ) { + for ( i; Nw ) { assert(( wxyz[[ i, 3, 4, 5 ]] == getMagicNumber(i, 3, 4, 5) )); } - for ( i; z(Nx) ) { + for ( i; Nx ) { assert(( wxyz[[ 2, i, 4, 5 ]] == getMagicNumber(2, i, 4, 5) )); } - for ( i; z(Ny) ) { + for ( i; Ny ) { assert(( wxyz[[ 2, 3, i, 5 ]] == getMagicNumber(2, 3, i, 5) )); } - for ( i; z(Nz) ) { + for ( i; Nz ) { assert(( wxyz[[ 2, 3, 4, i ]] == getMagicNumber(2, 3, 4, i) )); } - for ( i; z(Nw) ) { + for ( i; Nw ) { assert(( wxyz[[ i, all, 4, 5 ]][3] == getMagicNumber(i, 3, 4, 5) )); } - for ( i; z(Nw) ) { + for ( i; Nw ) { assert(( wxyz[[ all, 3, 4, 5 ]][i] == getMagicNumber(i, 3, 4, 5) )); } Index: tests/array-container/language-dim-mismatch.cfa =================================================================== --- tests/array-container/language-dim-mismatch.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) +++ tests/array-container/language-dim-mismatch.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -0,0 +1,15 @@ +forall( [N] ) +struct SN {}; + +forall( T ) +struct ST {}; + +int main() { + + SN(42) good1; + ST(float) good2; + + SN(float) bad1; // first expected error: Type argument given for value parameter + ST(42) bad2; // second expected error: Expression argument given for type parameter + +} Index: tests/device/cpu.cfa =================================================================== --- tests/device/cpu.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/device/cpu.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -17,9 +17,129 @@ #include #include +#include + +#include +#include +#include +#include + extern "C" { + #include + #include + #include #include + #include +} + +// go through a directory calling fn on each file +static int iterate_dir( const char * path, void (*fn)(struct dirent * ent) ) { + // open the directory + DIR *dir = opendir(path); + if(dir == 0p) { return ENOTDIR; } + + // call fn for each + struct dirent * ent; + while ((ent = readdir(dir)) != 0p) { + fn( ent ); + } + + // no longer need this + closedir(dir); + return 0; +} + +// count the number of directories with the specified prefix +// the directories counted have the form '[prefix]N' where prefix is the parameter +// and N is an base 10 integer. +static int count_prefix_dirs(const char * path, const char * prefix) { + // read the directory and find the cpu count + // and make sure everything is as expected + int max = -1; + int count = 0; + void lambda(struct dirent * ent) { + // were are looking for prefixX, where X is a number + // check that it starts with 'cpu + char * s = strstr(ent->d_name, prefix); + if(s == 0p) { return; } + if(s != ent->d_name) { return; } + + // check that the next part is a number + s += strlen(prefix); + char * end; + long int val = strtol(s, &end, 10); + if(*end != '\0' || val < 0) { return; } + + // check that it's a directory + if(ent->d_type != DT_DIR) { return; } + + // it's a match! + max = max(val, max); + count++; + } + iterate_dir(path, lambda); + + /* paranoid */ verifyf(count == max + 1, "Inconsistent %s count, counted %d, but max %s was %d", prefix, count, prefix, (int)max); + + return count; +} + +// Count number of cache *indexes* in the system +// cache indexes are distinct from cache level as Data or Instruction cache +// can share a level but not an index +// PITFALL: assumes all cpus have the same indexes as cpu0 +static int count_cache_indexes(void) { + return count_prefix_dirs("/sys/devices/system/cpu/cpu0/cache", "index"); +} + +// read information about a spcficic cache index/cpu file into the output buffer +static size_t read_cpuidxinfo_into(unsigned cpu, unsigned idx, const char * file, char * out, size_t out_len) { + // Pick the file we want and read it + char buf[128]; + /* paranoid */ __attribute__((unused)) int len = + snprintf(buf, 128, "/sys/devices/system/cpu/cpu%u/cache/index%u/%s", cpu, idx, file); + /* paranoid */ verifyf(len > 0, "Could not generate '%s' filename for cpu %u, index %u", file, cpu, idx); + + int fd = open(buf, 0, O_RDONLY); + /* paranoid */ verifyf(fd > 0, "Could not open file '%s'", buf); + + ssize_t r = read(fd, out, out_len); + /* paranoid */ verifyf(r > 0, "Could not read file '%s'", buf); + + /* paranoid */ __attribute__((unused)) int ret = + close(fd); + /* paranoid */ verifyf(ret == 0, "Could not close file '%s'", buf); + + out[r-1] = '\0'; + return r-1; +} + +unsigned find_idx() { + int idxs = count_cache_indexes(); + + unsigned found_level = 0; + unsigned found = -1u; + for(i; idxs) { + unsigned idx = idxs - 1 - i; + char buf[32]; + + // Level is the cache level: higher means bigger and slower + read_cpuidxinfo_into(0, idx, "level", buf, 32); + char * end; + unsigned long level = strtoul(buf, &end, 10); + /* paranoid */ verifyf(level <= 250, "Cpu %u has more than 250 levels of cache, that doesn't sound right", 0); + /* paranoid */ verify(*end == '\0'); + + if(found_level < level) { + found_level = level; + found = idx; + } + } + + /* paranoid */ verify(found != -1u); + return found; } int main() { + //----------------------------------------------------------------------- int ret1 = get_nprocs(); int ret2 = cpu_info.hthrd_count; @@ -31,3 +151,48 @@ } + //----------------------------------------------------------------------- + // Make sure no one has the same self + for(ime; cpu_info.hthrd_count) { + unsigned me = cpu_info.llc_map[ime].self; + { + unsigned s = cpu_info.llc_map[ime].start; + unsigned e = s + cpu_info.llc_map[ime].count; + if(me < s || me >= e) { + sout | "CPU" | ime | "outside of it's own map: " | s | "<=" | me | "<" | e; + } + } + + + for(ithem; cpu_info.hthrd_count) { + if(ime == ithem) continue; + + unsigned them = cpu_info.llc_map[ithem].self; + if(me == them) { + sout | "CPU" | ime | "has conflicting self id with" | ithem | "(" | me | ")"; + } + } + } + + + //----------------------------------------------------------------------- + unsigned idx = find_idx(); + // For all procs check mapping is consistent + for(cpu_me; cpu_info.hthrd_count) { + char buf_me[32]; + size_t len_me = read_cpuidxinfo_into(cpu_me, idx, "shared_cpu_list", buf_me, 32); + for(cpu_them; cpu_info.hthrd_count) { + if(cpu_me == cpu_them) continue; + char buf_them[32]; + size_t len_them = read_cpuidxinfo_into(cpu_them, idx, "shared_cpu_list", buf_them, 32); + + bool match_file = len_them == len_me && 0 == strncmp(buf_them, buf_me, len_me); + bool match_info = cpu_info.llc_map[cpu_me].start == cpu_info.llc_map[cpu_them].start && cpu_info.llc_map[cpu_me].count == cpu_info.llc_map[cpu_them].count; + + if(match_file != match_info) { + sout | "CPU" | cpu_me | "and" | cpu_them | "have inconsitent file and cpu_info"; + sout | cpu_me | ": <" | cpu_info.llc_map[cpu_me ].start | "," | cpu_info.llc_map[cpu_me ].count | "> '" | buf_me | "'"; + sout | cpu_me | ": <" | cpu_info.llc_map[cpu_them].start | "," | cpu_info.llc_map[cpu_them].count | "> '" | buf_them | "'"; + } + } + } } Index: tests/literals.cfa =================================================================== --- tests/literals.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/literals.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ // Created On : Sat Sep 9 16:34:38 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Aug 29 10:57:56 2020 -// Update Count : 226 +// Last Modified On : Sat Jun 19 15:47:49 2021 +// Update Count : 237 // @@ -63,53 +63,105 @@ -0X0123456789ABCDEF; -0X0123456789ABCDEFu; -0X0123456789ABCDEFl; -0X0123456789ABCDEFll; -0X0123456789ABCDEFul; -0X0123456789ABCDEFlu; -0X0123456789ABCDEFull; -0X0123456789ABCDEFllu; +// floating literals + + 0123456789.; 0123456789.f; 0123456789.d; 0123456789.l; 0123456789.F; 0123456789.D; 0123456789.L; + +0123456789.; +0123456789.f; +0123456789.d; +0123456789.l; +0123456789.F; +0123456789.D; +0123456789.L; + -0123456789.; -0123456789.f; -0123456789.d; -0123456789.l; -0123456789.F; -0123456789.D; -0123456789.L; + + 0123456789.e09; 0123456789.e09f; 0123456789.e09d; 0123456789.e09l; 0123456789.e09F; 0123456789.e09D; 0123456789.e09L; + +0123456789.e09; +0123456789.e09f; +0123456789.e09d; +0123456789.e09l; +0123456789.e09F; +0123456789.e09D; +0123456789.e09L; + -0123456789.e09; -0123456789.e09f; -0123456789.e09d; -0123456789.e09l; -0123456789.e09F; -0123456789.e09D; -0123456789.e09L; + + 0123456789.e+09; 0123456789.e+09f; 0123456789.e+09d; 0123456789.e+09l; 0123456789.e+09F; 0123456789.e+09D; 0123456789.e+09L; + +0123456789.e+09; +0123456789.e+09f; +0123456789.e+09d; +0123456789.e+09l; +0123456789.e+09F; +0123456789.e+09D; +0123456789.e+09L; + -0123456789.e+09; -0123456789.e+09f; -0123456789.e+09d; -0123456789.e+09l; -0123456789.e+09F; -0123456789.e+09D; -0123456789.e+09L; + + 0123456789.e-09; 0123456789.e-09f; 0123456789.e-09d; 0123456789.e-09l; 0123456789.e-09F; 0123456789.e-09D; 0123456789.e-09L; + +0123456789.e-09; +0123456789.e-09f; +0123456789.e-09d; +0123456789.e-09l; +0123456789.e-09F; +0123456789.e-09D; +0123456789.e-09L; + -0123456789.e-09; -0123456789.e-09f; -0123456789.e-09d; -0123456789.e-09l; -0123456789.e-09F; -0123456789.e-09D; -0123456789.e-09L; + + .0123456789; .0123456789f; .0123456789d; .0123456789l; .0123456789F; .0123456789D; .0123456789L; + +.0123456789; +.0123456789f; +.0123456789d; +.0123456789l; +.0123456789F; +.0123456789D; +.0123456789L; + -.0123456789; -.0123456789f; -.0123456789d; -.0123456789l; -.0123456789F; -.0123456789D; -.0123456789L; + + .0123456789e09; .0123456789e09f; .0123456789e09d; .0123456789e09l; .0123456789e09F; .0123456789e09D; .0123456789e09L; + +.0123456789e09; +.0123456789e09f; +.0123456789e09d; +.0123456789e09l; +.0123456789e09F; +.0123456789e09D; +.0123456789e09L; + -.0123456789e09; -.0123456789e09f; -.0123456789e09d; -.0123456789e09l; -.0123456789e09F; -.0123456789e09D; -.0123456789e09L; + + .0123456789E+09; .0123456789E+09f; .0123456789E+09d; .0123456789E+09l; .0123456789E+09F; .0123456789E+09D; .0123456789E+09L; + +.0123456789E+09; +.0123456789E+09f; +.0123456789E+09d; +.0123456789E+09l; +.0123456789E+09F; +.0123456789E+09D; +.0123456789E+09L; + -.0123456789E+09; -.0123456789E+09f; -.0123456789E+09d; -.0123456789E+09l; -.0123456789E+09F; -.0123456789E+09D; -.0123456789E+09L; + + .0123456789E-09; .0123456789E-09f; .0123456789E-09d; .0123456789E-09l; .0123456789E-09F; .0123456789E-09D; .0123456789E-09L; + -.0123456789E-09; -.0123456789E-09f; -.0123456789E-09d; -.0123456789E-09l; -.0123456789E-09F; -.0123456789E-09D; -.0123456789E-09L; + -.0123456789E-09; -.0123456789E-09f; -.0123456789E-09d; -.0123456789E-09l; -.0123456789E-09F; -.0123456789E-09D; -.0123456789E-09L; + + 0123456789.0123456789; 0123456789.0123456789f; 0123456789.0123456789d; 0123456789.0123456789l; 0123456789.0123456789F; 0123456789.0123456789D; 0123456789.0123456789L; + +0123456789.0123456789; +0123456789.0123456789f; +0123456789.0123456789d; +0123456789.0123456789l; +0123456789.0123456789F; +0123456789.0123456789D; +0123456789.0123456789L; + -0123456789.0123456789; -0123456789.0123456789f; -0123456789.0123456789d; -0123456789.0123456789l; -0123456789.0123456789F; -0123456789.0123456789D; -0123456789.0123456789L; + + 0123456789.0123456789E09; 0123456789.0123456789E09f; 0123456789.0123456789E09d; 0123456789.0123456789E09l; 0123456789.0123456789E09F; 0123456789.0123456789E09D; 0123456789.0123456789E09L; + +0123456789.0123456789E09; +0123456789.0123456789E09f; +0123456789.0123456789E09d; +0123456789.0123456789E09l; +0123456789.0123456789E09F; +0123456789.0123456789E09D; +0123456789.0123456789E09L; + -0123456789.0123456789E09; -0123456789.0123456789E09f; -0123456789.0123456789E09d; -0123456789.0123456789E09l; -0123456789.0123456789E09F; -0123456789.0123456789E09D; -0123456789.0123456789E09L; + + 0123456789.0123456789E+09; 0123456789.0123456789E+09f; 0123456789.0123456789E+09d; 0123456789.0123456789E+09l; 0123456789.0123456789E+09F; 0123456789.0123456789E+09D; 0123456789.0123456789E+09L; + +0123456789.0123456789E+09; +0123456789.0123456789E+09f; +0123456789.0123456789E+09d; +0123456789.0123456789E+09l; +0123456789.0123456789E+09F; +0123456789.0123456789E+09D; +0123456789.0123456789E+09L; + -0123456789.0123456789E+09; -0123456789.0123456789E+09f; -0123456789.0123456789E+09d; -0123456789.0123456789E+09l; -0123456789.0123456789E+09F; -0123456789.0123456789E+09D; -0123456789.0123456789E+09L; + + 0123456789.0123456789E-09; 0123456789.0123456789E-09f; 0123456789.0123456789E-09d; 0123456789.0123456789E-09l; 0123456789.0123456789E-09F; 0123456789.0123456789E-09D; 0123456789.0123456789E-09L; + +0123456789.0123456789E-09; +0123456789.0123456789E-09f; +0123456789.0123456789E-09d; +0123456789.0123456789E-09l; +0123456789.0123456789E-09F; +0123456789.0123456789E-09D; +0123456789.0123456789E-09L; + -0123456789.0123456789E-09; -0123456789.0123456789E-09f; -0123456789.0123456789E-09d; -0123456789.0123456789E-09l; -0123456789.0123456789E-09F; -0123456789.0123456789E-09D; -0123456789.0123456789E-09L; + // decimal floating literals - 0123456789.; 0123456789.f; 0123456789.l; 0123456789.F; 0123456789.L; 0123456789.DL; - +0123456789.; +0123456789.f; +0123456789.l; +0123456789.F; +0123456789.L; +0123456789.DL; - -0123456789.; -0123456789.f; -0123456789.l; -0123456789.F; -0123456789.L; -0123456789.DL; - - 0123456789.e09; 0123456789.e09f; 0123456789.e09l; 0123456789.e09F; 0123456789.e09L; 0123456789.e09DL; - +0123456789.e09; +0123456789.e09f; +0123456789.e09l; +0123456789.e09F; +0123456789.e09L; +0123456789.e09DL; - -0123456789.e09; -0123456789.e09f; -0123456789.e09l; -0123456789.e09F; -0123456789.e09L; -0123456789.e09DL; - - 0123456789.e+09; 0123456789.e+09f; 0123456789.e+09l; 0123456789.e+09F; 0123456789.e+09L; 0123456789.e+09DL; - +0123456789.e+09; +0123456789.e+09f; +0123456789.e+09l; +0123456789.e+09F; +0123456789.e+09L; +0123456789.e+09DL; - -0123456789.e+09; -0123456789.e+09f; -0123456789.e+09l; -0123456789.e+09F; -0123456789.e+09L; -0123456789.e+09DL; - - 0123456789.e-09; 0123456789.e-09f; 0123456789.e-09l; 0123456789.e-09F; 0123456789.e-09L; 0123456789.e-09DL; - +0123456789.e-09; +0123456789.e-09f; +0123456789.e-09l; +0123456789.e-09F; +0123456789.e-09L; +0123456789.e-09DL; - -0123456789.e-09; -0123456789.e-09f; -0123456789.e-09l; -0123456789.e-09F; -0123456789.e-09L; -0123456789.e-09DL; - - .0123456789; .0123456789f; .0123456789l; .0123456789F; .0123456789L; .0123456789DL; - +.0123456789; +.0123456789f; +.0123456789l; +.0123456789F; +.0123456789L; +.0123456789DL; - -.0123456789; -.0123456789f; -.0123456789l; -.0123456789F; -.0123456789L; -.0123456789DL; - - .0123456789e09; .0123456789e09f; .0123456789e09l; .0123456789e09F; .0123456789e09L; .0123456789e09DL; - +.0123456789e09; +.0123456789e09f; +.0123456789e09l; +.0123456789e09F; +.0123456789e09L; +.0123456789e09DL; - -.0123456789e09; -.0123456789e09f; -.0123456789e09l; -.0123456789e09F; -.0123456789e09L; -.0123456789e09DL; - - .0123456789E+09; .0123456789E+09f; .0123456789E+09l; .0123456789E+09F; .0123456789E+09L; .0123456789E+09DL; - +.0123456789E+09; +.0123456789E+09f; +.0123456789E+09l; +.0123456789E+09F; +.0123456789E+09L; +.0123456789E+09DL; - -.0123456789E+09; -.0123456789E+09f; -.0123456789E+09l; -.0123456789E+09F; -.0123456789E+09L; -.0123456789E+09DL; - - .0123456789E-09; .0123456789E-09f; .0123456789E-09l; .0123456789E-09F; .0123456789E-09L; .0123456789E-09DL; - -.0123456789E-09; -.0123456789E-09f; -.0123456789E-09l; -.0123456789E-09F; -.0123456789E-09L; -.0123456789E-09DL; - -.0123456789E-09; -.0123456789E-09f; -.0123456789E-09l; -.0123456789E-09F; -.0123456789E-09L; -.0123456789E-09DL; - - 0123456789.0123456789; 0123456789.0123456789f; 0123456789.0123456789l; 0123456789.0123456789F; 0123456789.0123456789L; 0123456789.0123456789DL; - +0123456789.0123456789; +0123456789.0123456789f; +0123456789.0123456789l; +0123456789.0123456789F; +0123456789.0123456789L; +0123456789.0123456789DL; - -0123456789.0123456789; -0123456789.0123456789f; -0123456789.0123456789l; -0123456789.0123456789F; -0123456789.0123456789L; -0123456789.0123456789DL; - - 0123456789.0123456789E09; 0123456789.0123456789E09f; 0123456789.0123456789E09l; 0123456789.0123456789E09F; 0123456789.0123456789E09L; 0123456789.0123456789E09DL; - +0123456789.0123456789E09; +0123456789.0123456789E09f; +0123456789.0123456789E09l; +0123456789.0123456789E09F; +0123456789.0123456789E09L; +0123456789.0123456789E09DL; - -0123456789.0123456789E09; -0123456789.0123456789E09f; -0123456789.0123456789E09l; -0123456789.0123456789E09F; -0123456789.0123456789E09L; -0123456789.0123456789E09DL; - - 0123456789.0123456789E+09; 0123456789.0123456789E+09f; 0123456789.0123456789E+09l; 0123456789.0123456789E+09F; 0123456789.0123456789E+09L; 0123456789.0123456789E+09DL; - +0123456789.0123456789E+09; +0123456789.0123456789E+09f; +0123456789.0123456789E+09l; +0123456789.0123456789E+09F; +0123456789.0123456789E+09L; +0123456789.0123456789E+09DL; - -0123456789.0123456789E+09; -0123456789.0123456789E+09f; -0123456789.0123456789E+09l; -0123456789.0123456789E+09F; -0123456789.0123456789E+09L; -0123456789.0123456789E+09DL; - - 0123456789.0123456789E-09; 0123456789.0123456789E-09f; 0123456789.0123456789E-09l; 0123456789.0123456789E-09F; 0123456789.0123456789E-09L; 0123456789.0123456789E-09DL; - +0123456789.0123456789E-09; +0123456789.0123456789E-09f; +0123456789.0123456789E-09l; +0123456789.0123456789E-09F; +0123456789.0123456789E-09L; +0123456789.0123456789E-09DL; - -0123456789.0123456789E-09; -0123456789.0123456789E-09f; -0123456789.0123456789E-09l; -0123456789.0123456789E-09F; -0123456789.0123456789E-09L; -0123456789.0123456789E-09DL; +#if ! defined( __aarch64__ ) // unsupported on ARM after gcc-9 + 0123456789.df; 0123456789.dd; 0123456789.dl; 0123456789.DF; 0123456789.DD; 0123456789.DL; + +0123456789.df; +0123456789.dd; +0123456789.dl; +0123456789.DF; +0123456789.DD; +0123456789.DL; + -0123456789.df; -0123456789.dd; -0123456789.dl; -0123456789.DF; -0123456789.DD; -0123456789.DL; + + 0123456789.e09df; 0123456789.e09dd; 0123456789.e09dl; 0123456789.e09DF; 0123456789.e09DD; 0123456789.e09DL; + +0123456789.e09df; +0123456789.e09dd; +0123456789.e09dl; +0123456789.e09DF; +0123456789.e09DD; +0123456789.e09DL; + -0123456789.e09df; -0123456789.e09dd; -0123456789.e09dl; -0123456789.e09DF; -0123456789.e09DD; -0123456789.e09DL; + + 0123456789.e+09df; 0123456789.e+09dd; 0123456789.e+09dl; 0123456789.e+09DF; 0123456789.e+09DD; 0123456789.e+09DL; + +0123456789.e+09df; +0123456789.e+09dd; +0123456789.e+09dl; +0123456789.e+09DF; +0123456789.e+09DD; +0123456789.e+09DL; + -0123456789.e+09df; -0123456789.e+09dd; -0123456789.e+09dl; -0123456789.e+09DF; -0123456789.e+09DD; -0123456789.e+09DL; + + 0123456789.e-09df; 0123456789.e-09dd; 0123456789.e-09dl; 0123456789.e-09DF; 0123456789.e-09DD; 0123456789.e-09DL; + +0123456789.e-09df; +0123456789.e-09dd; +0123456789.e-09dl; +0123456789.e-09DF; +0123456789.e-09DD; +0123456789.e-09DL; + -0123456789.e-09df; -0123456789.e-09dd; -0123456789.e-09dl; -0123456789.e-09DF; -0123456789.e-09DD; -0123456789.e-09DL; + + .0123456789df; .0123456789dd; .0123456789dl; .0123456789DF; .0123456789DD; .0123456789DL; + +.0123456789df; +.0123456789dd; +.0123456789dl; +.0123456789DF; +.0123456789DD; +.0123456789DL; + -.0123456789df; -.0123456789dd; -.0123456789dl; -.0123456789DF; -.0123456789DD; -.0123456789DL; + + .0123456789e09df; .0123456789e09dd; .0123456789e09dl; .0123456789e09DF; .0123456789e09DD; .0123456789e09DL; + +.0123456789e09df; +.0123456789e09dd; +.0123456789e09dl; +.0123456789e09DF; +.0123456789e09DD; +.0123456789e09DL; + -.0123456789e09df; -.0123456789e09dd; -.0123456789e09dl; -.0123456789e09DF; -.0123456789e09DD; -.0123456789e09DL; + + .0123456789E+09df; .0123456789E+09dd; .0123456789E+09dl; .0123456789E+09DF; .0123456789E+09DD; .0123456789E+09DL; + +.0123456789E+09df; +.0123456789E+09dd; +.0123456789E+09dl; +.0123456789E+09DF; +.0123456789E+09DD; +.0123456789E+09DL; + -.0123456789E+09df; -.0123456789E+09dd; -.0123456789E+09dl; -.0123456789E+09DF; -.0123456789E+09DD; -.0123456789E+09DL; + + .0123456789E-09df; .0123456789E-09dd; .0123456789E-09dl; .0123456789E-09DF; .0123456789E-09DD; .0123456789E-09DL; + -.0123456789E-09df; -.0123456789E-09dd; -.0123456789E-09dl; -.0123456789E-09DF; -.0123456789E-09DD; -.0123456789E-09DL; + -.0123456789E-09df; -.0123456789E-09dd; -.0123456789E-09dl; -.0123456789E-09DF; -.0123456789E-09DD; -.0123456789E-09DL; + + 0123456789.0123456789df; 0123456789.0123456789dd; 0123456789.0123456789dl; 0123456789.0123456789DF; 0123456789.0123456789DD; 0123456789.0123456789DL; + +0123456789.0123456789df; +0123456789.0123456789dd; +0123456789.0123456789dl; +0123456789.0123456789DF; +0123456789.0123456789DD; +0123456789.0123456789DL; + -0123456789.0123456789df; -0123456789.0123456789dd; -0123456789.0123456789dl; -0123456789.0123456789DF; -0123456789.0123456789DD; -0123456789.0123456789DL; + + 0123456789.0123456789E09df; 0123456789.0123456789E09dd; 0123456789.0123456789E09dl; 0123456789.0123456789E09DF; 0123456789.0123456789E09DD; 0123456789.0123456789E09DL; + +0123456789.0123456789E09df; +0123456789.0123456789E09dd; +0123456789.0123456789E09dl; +0123456789.0123456789E09DF; +0123456789.0123456789E09DD; +0123456789.0123456789E09DL; + -0123456789.0123456789E09df; -0123456789.0123456789E09dd; -0123456789.0123456789E09dl; -0123456789.0123456789E09DF; -0123456789.0123456789E09DD; -0123456789.0123456789E09DL; + + 0123456789.0123456789E+09df; 0123456789.0123456789E+09dd; 0123456789.0123456789E+09dl; 0123456789.0123456789E+09DF; 0123456789.0123456789E+09DD; 0123456789.0123456789E+09DL; + +0123456789.0123456789E+09df; +0123456789.0123456789E+09dd; +0123456789.0123456789E+09dl; +0123456789.0123456789E+09DF; +0123456789.0123456789E+09DD; +0123456789.0123456789E+09DL; + -0123456789.0123456789E+09df; -0123456789.0123456789E+09dd; -0123456789.0123456789E+09dl; -0123456789.0123456789E+09DF; -0123456789.0123456789E+09DD; -0123456789.0123456789E+09DL; + + 0123456789.0123456789E-09df; 0123456789.0123456789E-09dd; 0123456789.0123456789E-09dl; 0123456789.0123456789E-09DF; 0123456789.0123456789E-09DD; 0123456789.0123456789E-09DL; + +0123456789.0123456789E-09df; +0123456789.0123456789E-09dd; +0123456789.0123456789E-09dl; +0123456789.0123456789E-09DF; +0123456789.0123456789E-09DD; +0123456789.0123456789E-09DL; + -0123456789.0123456789E-09df; -0123456789.0123456789E-09dd; -0123456789.0123456789E-09dl; -0123456789.0123456789E-09DF; -0123456789.0123456789E-09DD; -0123456789.0123456789E-09DL; +#endif // ! __aarch64__ // hexadecimal floating literals, must have exponent Index: tests/math.cfa =================================================================== --- tests/math.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/math.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -10,6 +10,6 @@ // Created On : Fri Apr 22 14:59:21 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 13 21:04:48 2021 -// Update Count : 123 +// Last Modified On : Fri Jun 18 17:02:44 2021 +// Update Count : 124 // @@ -40,9 +40,9 @@ sout | "exp:" | exp( 1.0F ) | exp( 1.0D ) | exp( 1.0L ) | nonl; - sout | exp( 1.0F+1.0FI ) | exp( 1.0D+1.0DI ) | exp( 1.0DL+1.0LI ); + sout | exp( 1.0F+1.0FI ) | exp( 1.0D+1.0DI ) | exp( 1.0L+1.0LI ); sout | "exp2:" | exp2( 1.0F ) | exp2( 1.0D ) | exp2( 1.0L ); sout | "expm1:" | expm1( 1.0F ) | expm1( 1.0D ) | expm1( 1.0L ); sout | "pow:" | pow( 1.0F, 1.0F ) | pow( 1.0D, 1.0D ) | pow( 1.0L, 1.0L ) | nonl; - sout | pow( 1.0F+1.0FI, 1.0F+1.0FI ) | pow( 1.0D+1.0DI, 1.0D+1.0DI ) | pow( 1.5DL+1.5LI, 1.5DL+1.5LI ); + sout | pow( 1.0F+1.0FI, 1.0F+1.0FI ) | pow( 1.0D+1.0DI, 1.0D+1.0DI ) | pow( 1.5L+1.5LI, 1.5L+1.5LI ); int b = 4; @@ -68,5 +68,5 @@ sout | "log:" | log( 1.0F ) | log( 1.0D ) | log( 1.0L ) | nonl; - sout | log( 1.0F+1.0FI ) | log( 1.0D+1.0DI ) | log( 1.0DL+1.0LI ); + sout | log( 1.0F+1.0FI ) | log( 1.0D+1.0DI ) | log( 1.0L+1.0LI ); sout | "log2:" | log2( 1024 ) | log2( 2 \ 17u ) | log2( 2 \ 23u ); sout | "log2:" | log2( 1024l ) | log2( 2l \ 17u ) | log2( 2l \ 23u ); @@ -82,5 +82,5 @@ sout | "sqrt:" | sqrt( 1.0F ) | sqrt( 1.0D ) | sqrt( 1.0L ) | nonl; - sout | sqrt( 1.0F+1.0FI ) | sqrt( 1.0D+1.0DI ) | sqrt( 1.0DL+1.0LI ); + sout | sqrt( 1.0F+1.0FI ) | sqrt( 1.0D+1.0DI ) | sqrt( 1.0L+1.0LI ); sout | "cbrt:" | cbrt( 27.0F ) | cbrt( 27.0D ) | cbrt( 27.0L ); sout | "hypot:" | hypot( 1.0F, -1.0F ) | hypot( 1.0D, -1.0D ) | hypot( 1.0L, -1.0L ); @@ -89,15 +89,15 @@ sout | "sin:" | sin( 1.0F ) | sin( 1.0D ) | sin( 1.0L ) | nonl; - sout | sin( 1.0F+1.0FI ) | sin( 1.0D+1.0DI ) | sin( 1.0DL+1.0LI ); + sout | sin( 1.0F+1.0FI ) | sin( 1.0D+1.0DI ) | sin( 1.0L+1.0LI ); sout | "cos:" | cos( 1.0F ) | cos( 1.0D ) | cos( 1.0L ) | nonl; - sout | cos( 1.0F+1.0FI ) | cos( 1.0D+1.0DI ) | cos( 1.0DL+1.0LI ); + sout | cos( 1.0F+1.0FI ) | cos( 1.0D+1.0DI ) | cos( 1.0L+1.0LI ); sout | "tan:" | tan( 1.0F ) | tan( 1.0D ) | tan( 1.0L ) | nonl; - sout | tan( 1.0F+1.0FI ) | tan( 1.0D+1.0DI ) | tan( 1.0DL+1.0LI ); + sout | tan( 1.0F+1.0FI ) | tan( 1.0D+1.0DI ) | tan( 1.0L+1.0LI ); sout | "asin:" | asin( 1.0F ) | asin( 1.0D ) | asin( 1.0L ) | nonl; - sout | asin( 1.0F+1.0FI ) | asin( 1.0D+1.0DI ) | asin( 1.0DL+1.0LI ); + sout | asin( 1.0F+1.0FI ) | asin( 1.0D+1.0DI ) | asin( 1.0L+1.0LI ); sout | "acos:" | acos( 1.0F ) | acos( 1.0D ) | acos( 1.0L ) | nonl; - sout | acos( 1.0F+1.0FI ) | acos( 1.0D+1.0DI ) | acos( 1.0DL+1.0LI ); + sout | acos( 1.0F+1.0FI ) | acos( 1.0D+1.0DI ) | acos( 1.0L+1.0LI ); sout | "atan:" | atan( 1.0F ) | atan( 1.0D ) | atan( 1.0L ) | nonl; - sout | atan( 1.0F+1.0FI ) | atan( 1.0D+1.0DI ) | atan( 1.0DL+1.0LI ); + sout | atan( 1.0F+1.0FI ) | atan( 1.0D+1.0DI ) | atan( 1.0L+1.0LI ); sout | "atan2:" | atan2( 1.0F, 1.0F ) | atan2( 1.0D, 1.0D ) | atan2( 1.0L, 1.0L ) | nonl; sout | "atan:" | atan( 1.0F, 1.0F ) | atan( 1.0D, 1.0D ) | atan( 1.0L, 1.0L ); @@ -106,15 +106,15 @@ sout | "sinh:" | sinh( 1.0F ) | sinh( 1.0D ) | sinh( 1.0L ) | nonl; - sout | sinh( 1.0F+1.0FI ) | sinh( 1.0D+1.0DI ) | sinh( 1.0DL+1.0LI ); + sout | sinh( 1.0F+1.0FI ) | sinh( 1.0D+1.0DI ) | sinh( 1.0L+1.0LI ); sout | "cosh:" | cosh( 1.0F ) | cosh( 1.0D ) | cosh( 1.0L ) | nonl; - sout | cosh( 1.0F+1.0FI ) | cosh( 1.0D+1.0DI ) | cosh( 1.0DL+1.0LI ); + sout | cosh( 1.0F+1.0FI ) | cosh( 1.0D+1.0DI ) | cosh( 1.0L+1.0LI ); sout | "tanh:" | tanh( 1.0F ) | tanh( 1.0D ) | tanh( 1.0L ) | nonl; - sout | tanh( 1.0F+1.0FI ) | tanh( 1.0D+1.0DI ) | tanh( 1.0DL+1.0LI ); + sout | tanh( 1.0F+1.0FI ) | tanh( 1.0D+1.0DI ) | tanh( 1.0L+1.0LI ); sout | "acosh:" | acosh( 1.0F ) | acosh( 1.0D ) | acosh( 1.0L ) | nonl; - sout | acosh( 1.0F+1.0FI ) | acosh( 1.0D+1.0DI ) | acosh( 1.0DL+1.0LI ); + sout | acosh( 1.0F+1.0FI ) | acosh( 1.0D+1.0DI ) | acosh( 1.0L+1.0LI ); sout | "asinh:" | asinh( 1.0F ) | asinh( 1.0D ) | asinh( 1.0L ) | nonl; - sout | asinh( 1.0F+1.0FI ) | asinh( 1.0D+1.0DI ) | asinh( 1.0DL+1.0LI ); + sout | asinh( 1.0F+1.0FI ) | asinh( 1.0D+1.0DI ) | asinh( 1.0L+1.0LI ); sout | "atanh:" | atanh( 1.0F ) | atanh( 1.0D ) | atanh( 1.0L ) | nonl; - sout | atanh( 1.0F+1.0FI ) | atanh( 1.0D+1.0DI ) | atanh( 1.0DL+1.0LI ); + sout | atanh( 1.0F+1.0FI ) | atanh( 1.0D+1.0DI ) | atanh( 1.0L+1.0LI ); //---------------------- Error / Gamma ---------------------- Index: tests/test.py =================================================================== --- tests/test.py (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/test.py (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -13,5 +13,4 @@ import os -import psutil import signal Index: tests/typedefRedef.cfa =================================================================== --- tests/typedefRedef.cfa (revision 33e1c91fee57e9c535b08ea125870ea6ae2422b4) +++ tests/typedefRedef.cfa (revision 929d925e53b2c137859d6e900557344a9a4953f6) @@ -45,4 +45,10 @@ typedef int X2; +X2 value __attribute__((aligned(4 * sizeof(X2)))); + +__attribute__((aligned(4 * sizeof(X2)))) struct rseq_cs { + int foo; +}; + // xxx - this doesn't work yet due to parsing problems with generic types // #ifdef __CFA__