Index: doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -26,5 +26,5 @@ This thesis designs and examines a new set of micro-benchmarks for memory allocators that test a variety of allocation patterns, each with multiple tuning parameters. -The aim of the 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). +The aim of the micro-benchmark suite is to create a set of programs that can evaluate a memory allocator based on the key performance matrices such as speed, memory overhead, and cache performance. % 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 certain allocation patterns. Index: doc/theses/mubeen_zulfiqar_MMath/conclusion.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/conclusion.tex (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ doc/theses/mubeen_zulfiqar_MMath/conclusion.tex (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -36,5 +36,5 @@ Starting a micro-benchmark test-suite for comparing allocators, rather than relying on a suite of arbitrary programs, has been an interesting challenge. -The current micro-benchmark allows some understand of allocator implementation properties without actually looking at the implementation. +The current micro-benchmarks allow some understand of allocator implementation properties without actually looking at the implementation. For example, the memory micro-benchmark quickly identified how several of the allocators work at the global level. It was not possible to show how the micro-benchmarks adjustment knobs were used to tune to an interesting test point. @@ -52,2 +52,3 @@ After llheap is made available on gitHub, interacting with its users to locate problems and improvements, will make llbench a more robust memory allocator. +As well, feedback from the \uC and \CFA projects, which have adopted llheap for their memory allocator, will provide additional feedback. Index: c/theses/mubeen_zulfiqar_MMath/dofree.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/dofree.tex (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ (revision ) @@ -1,34 +1,0 @@ -Algorithm~\ref{alg:heapObjectFreeOwn} shows how a free request is fulfilled if object ownership is turned on. Algorithm~\ref{alg:heapObjectFreeNoOwn} shows how the same free request is fulfilled without object ownership. - -\begin{algorithm} -\caption{Dynamic object free at address A with object ownership}\label{alg:heapObjectFreeOwn} -\begin{algorithmic}[1] -\If {$\textit{A was mmap-ed}$} - \State $\text{return A's dynamic memory to system using system call munmap}$ -\Else - \State $\text{B} \gets \textit{O's owner}$ - \If {$\textit{B is thread-local heap's bucket}$} - \State $\text{push A to B's free-list}$ - \Else - \State $\text{push A to B's away-list}$ - \EndIf -\EndIf -\end{algorithmic} -\end{algorithm} - -\begin{algorithm} -\caption{Dynamic object free at address A without object ownership}\label{alg:heapObjectFreeNoOwn} -\begin{algorithmic}[1] -\If {$\textit{A was mmap-ed}$} - \State $\text{return A's dynamic memory to system using system call munmap}$ -\Else - \State $\text{B} \gets \textit{O's owner}$ - \If {$\textit{B is thread-local heap's bucket}$} - \State $\text{push A to B's free-list}$ - \Else - \State $\text{C} \gets \textit{thread local heap's bucket with same size as B}$ - \State $\text{push A to C's free-list}$ - \EndIf -\EndIf -\end{algorithmic} -\end{algorithm} Index: doc/theses/mubeen_zulfiqar_MMath/performance.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -92,4 +92,5 @@ The each micro-benchmark is configured and run with each of the allocators, The less time an allocator takes to complete a benchmark the better, so lower in the graphs is better. +All graphs use log scale on the Y-axis, except for the Memory micro-benchmark (see \VRef{s:MemoryMicroBenchmark}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -103,5 +104,5 @@ \begin{description}[itemsep=0pt,parsep=0pt] \item[thread:] -1, 2, 4, 8, 16 +1, 2, 4, 8, 16, 32, 48 \item[spots:] 16 @@ -139,8 +140,10 @@ \end{figure} +\paragraph{Assessment} All allocators did well in this micro-benchmark, except for \textsf{dl} on the ARM. -llheap is slightly slower because it uses ownership, where many of the allocations have remote frees, which requires locking. -When llheap is compiled without ownership, its performance is the same as the other allocators (not shown). - +\textsf{dl}'s is the slowest, indicating some small bottleneck with respect to the other allocators. +\textsf{je} is the fastest, with only a small benefit over the other allocators. +% llheap is slightly slower because it uses ownership, where many of the allocations have remote frees, which requires locking. +% When llheap is compiled without ownership, its performance is the same as the other allocators (not shown). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -149,4 +152,5 @@ \subsection{Cache Thrash} +\label{sec:cache-thrash-perf} Thrash tests memory allocators for active false sharing (see \VRef{sec:benchThrashSec}). @@ -154,5 +158,5 @@ \begin{description}[itemsep=0pt,parsep=0pt] \item[threads:] -1, 2, 4, 8, 16 +1, 2, 4, 8, 16, 32, 48 \item[iterations:] 1,000 @@ -179,6 +183,10 @@ \end{figure} -All allocators did well in this micro-benchmark, except for \textsf{dl} and \textsf{pt3} on the x64. -Either the memory allocators generate little active false-sharing or the micro-benchmark is not generating scenarios that cause active false-sharing. +\paragraph{Assessment} +All allocators did well in this micro-benchmark, except for \textsf{dl} and \textsf{pt3}. +\textsf{dl} uses a single heap for all threads so it is understandable that it generates so much active false-sharing. +Requests from different threads are dealt with sequentially by the single heap (using a single lock), which can allocate objects to different threads on the same cache line. +\textsf{pt3} uses the T:H model, so multiple threads can use one heap, but the active false-sharing is less than \textsf{dl}. +The rest of the memory allocators generate little or no active false-sharing. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -192,5 +200,5 @@ \begin{description}[itemsep=0pt,parsep=0pt] \item[threads:] -1, 2, 4, 8, 16 +1, 2, 4, 8, 16, 32, 48 \item[iterations:] 1,000 @@ -217,6 +225,15 @@ \end{figure} -All allocators did well in this micro-benchmark on the ARM. -Allocators \textsf{llh}, \textsf{je}, and \textsf{rp} did well on the x64, while the remaining allocators experienced significant slowdowns from the false sharing. +\paragraph{Assessment} +This micro-benchmark divides the allocators into two groups. +First is the high-performer group: \textsf{llh}, \textsf{je}, and \textsf{rp}. +These memory allocators generate little or no passive false-sharing and their performance difference is negligible. +Second is the low-performer group, which includes the rest of the memory allocators. +These memory allocators have significant program-induced passive false-sharing, where \textsf{hrd}'s is the worst performing allocator. +All of the allocator's in this group are sharing heaps among threads at some level. + +Interestingly, allocators such as \textsf{hrd} and \textsf{glc} performed well in micro-benchmark cache thrash (see \VRef{sec:cache-thrash-perf}). +But, these allocators are among the low performers in the cache scratch. +It suggests these allocators do not actively produce false-sharing but preserve program-induced passive false sharing. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -238,7 +255,7 @@ fisher \item[objects:] -1,000,000 +100,000 \item[workers:] -1, 2, 4, 8, 16 +1, 2, 4, 8, 16, 32, 48 \end{description} @@ -273,5 +290,14 @@ \end{itemize} -All allocators did well in this micro-benchmark across all allocation chains, except for \textsf{dl} and \textsf{pt3}. +\paragraph{Assessment} +This micro-benchmark divides the allocators into two groups: with and without @calloc@. +@calloc@ uses @memset@ to set the allocated memory to zero, which dominates the cost of the allocation chain (large performance increase) and levels performance across the allocators. +But the difference among the allocators in a @calloc@ chain still gives an idea of their relative performance. + +All allocators did well in this micro-benchmark across all allocation chains, except for \textsf{dl}, \textsf{pt3}, and \textsf{hrd}. +Again, the low-performing allocators are sharing heaps among threads, so the contention causes performance increases with increasing numbers of threads. +Furthermore, chains with @free@ can trigger coalescing, which slows the fast path. +The high-performing allocators all illustrate low latency across the allocation chains, \ie there are no performance spikes as the chain lengths, that might be caused by contention and/or coalescing. +Low latency is important for applications that are sensitive to unknown execution delays. %speed-3-malloc.eps @@ -389,4 +415,5 @@ \newpage \subsection{Memory Micro-Benchmark} +\label{s:MemoryMicroBenchmark} This experiment is run with the following two configurations for each allocator. @@ -497,14 +524,21 @@ The Y-axis shows the memory usage in bytes. -For the experiment, at a certain time in the program's life, the difference between the memory requested by the benchmark (\textit{current\_req\_mem(B)}) and the memory that the process has received from system (\textit{heap}, \textit{mmap}) should be minimum. +For this experiment, the difference between the memory requested by the benchmark (\textit{current\_req\_mem(B)}) and the memory that the process has received from system (\textit{heap}, \textit{mmap}) should be minimum. This difference is the memory overhead caused by the allocator and shows the level of fragmentation in the allocator. +\paragraph{Assessment} First, the differences in the shape of the curves between architectures (top ARM, bottom x64) is small, where the differences are in the amount of memory used. Hence, it is possible to focus on either the top or bottom graph. -The heap curve It is possible glib, hoard, jemalloc, ptmalloc3, rpmalloc do not use the sbrk area => only uses mmap. - -hoard, tbbmalloc uses more total memory - -ptmalloc3 gives memory back to operating system + +Second, the heap curve is 0 for four memory allocators: \textsf{hrd}, \textsf{je}, \textsf{pt3}, and \textsf{rp}, indicating these memory allocators only use @mmap@ to get memory from the system and ignore the @sbrk@ area. + +The total dynamic memory is higher for \textsf{hrd} and \textsf{tbb} than the other allocators. +The main reason is the use of superblocks (see \VRef{s:ObjectContainers}) containing objects of the same size. +These superblocks are maintained throughout the life of the program. + +\textsf{pt3} is the only memory allocator where the total dynamic memory goes down in the second half of the program lifetime when the memory is freed by the benchmark program. +It makes pt3 the only memory allocator that gives memory back to the operating system as it is freed by the program. + +% FOR 1 THREAD %mem-1-prod-1-cons-100-llh.eps @@ -513,7 +547,72 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-llh} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-llh} } -\caption{Memory benchmark results with 1 producer for llh memory allocator} +\caption{Memory benchmark results with Configuration-1 for llh memory allocator} \label{fig:mem-1-prod-1-cons-100-llh} \end{figure} + +%mem-1-prod-1-cons-100-dl.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-dl} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-dl} } +\caption{Memory benchmark results with Configuration-1 for dl memory allocator} +\label{fig:mem-1-prod-1-cons-100-dl} +\end{figure} + +%mem-1-prod-1-cons-100-glc.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-glc} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-glc} } +\caption{Memory benchmark results with Configuration-1 for glibc memory allocator} +\label{fig:mem-1-prod-1-cons-100-glc} +\end{figure} + +%mem-1-prod-1-cons-100-hrd.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-hrd} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-hrd} } +\caption{Memory benchmark results with Configuration-1 for hoard memory allocator} +\label{fig:mem-1-prod-1-cons-100-hrd} +\end{figure} + +%mem-1-prod-1-cons-100-je.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-je} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-je} } +\caption{Memory benchmark results with Configuration-1 for je memory allocator} +\label{fig:mem-1-prod-1-cons-100-je} +\end{figure} + +%mem-1-prod-1-cons-100-pt3.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-pt3} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-pt3} } +\caption{Memory benchmark results with Configuration-1 for pt3 memory allocator} +\label{fig:mem-1-prod-1-cons-100-pt3} +\end{figure} + +%mem-1-prod-1-cons-100-rp.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-rp} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-rp} } +\caption{Memory benchmark results with Configuration-1 for rp memory allocator} +\label{fig:mem-1-prod-1-cons-100-rp} +\end{figure} + +%mem-1-prod-1-cons-100-tbb.eps +\begin{figure} +\centering + \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-tbb} } + \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-tbb} } +\caption{Memory benchmark results with Configuration-1 for tbb memory allocator} +\label{fig:mem-1-prod-1-cons-100-tbb} +\end{figure} + +% FOR 4 THREADS %mem-4-prod-4-cons-100-llh.eps @@ -522,15 +621,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-llh} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-llh} } -\caption{Memory benchmark results with 4 producers for llh memory allocator} +\caption{Memory benchmark results with Configuration-2 for llh memory allocator} \label{fig:mem-4-prod-4-cons-100-llh} -\end{figure} - -%mem-1-prod-1-cons-100-dl.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-dl} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-dl} } -\caption{Memory benchmark results with 1 producer for dl memory allocator} -\label{fig:mem-1-prod-1-cons-100-dl} \end{figure} @@ -540,15 +630,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-dl} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-dl} } -\caption{Memory benchmark results with 4 producers for dl memory allocator} +\caption{Memory benchmark results with Configuration-2 for dl memory allocator} \label{fig:mem-4-prod-4-cons-100-dl} -\end{figure} - -%mem-1-prod-1-cons-100-glc.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-glc} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-glc} } -\caption{Memory benchmark results with 1 producer for glibc memory allocator} -\label{fig:mem-1-prod-1-cons-100-glc} \end{figure} @@ -558,15 +639,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-glc} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-glc} } -\caption{Memory benchmark results with 4 producers for glibc memory allocator} +\caption{Memory benchmark results with Configuration-2 for glibc memory allocator} \label{fig:mem-4-prod-4-cons-100-glc} -\end{figure} - -%mem-1-prod-1-cons-100-hrd.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-hrd} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-hrd} } -\caption{Memory benchmark results with 1 producer for hoard memory allocator} -\label{fig:mem-1-prod-1-cons-100-hrd} \end{figure} @@ -576,15 +648,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-hrd} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-hrd} } -\caption{Memory benchmark results with 4 producers for hoard memory allocator} +\caption{Memory benchmark results with Configuration-2 for hoard memory allocator} \label{fig:mem-4-prod-4-cons-100-hrd} -\end{figure} - -%mem-1-prod-1-cons-100-je.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-je} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-je} } -\caption{Memory benchmark results with 1 producer for je memory allocator} -\label{fig:mem-1-prod-1-cons-100-je} \end{figure} @@ -594,15 +657,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-je} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-je} } -\caption{Memory benchmark results with 4 producers for je memory allocator} +\caption{Memory benchmark results with Configuration-2 for je memory allocator} \label{fig:mem-4-prod-4-cons-100-je} -\end{figure} - -%mem-1-prod-1-cons-100-pt3.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-pt3} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-pt3} } -\caption{Memory benchmark results with 1 producer for pt3 memory allocator} -\label{fig:mem-1-prod-1-cons-100-pt3} \end{figure} @@ -612,15 +666,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-pt3} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-pt3} } -\caption{Memory benchmark results with 4 producers for pt3 memory allocator} +\caption{Memory benchmark results with Configuration-2 for pt3 memory allocator} \label{fig:mem-4-prod-4-cons-100-pt3} -\end{figure} - -%mem-1-prod-1-cons-100-rp.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-rp} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-rp} } -\caption{Memory benchmark results with 1 producer for rp memory allocator} -\label{fig:mem-1-prod-1-cons-100-rp} \end{figure} @@ -630,15 +675,6 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-rp} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-rp} } -\caption{Memory benchmark results with 4 producers for rp memory allocator} +\caption{Memory benchmark results with Configuration-2 for rp memory allocator} \label{fig:mem-4-prod-4-cons-100-rp} -\end{figure} - -%mem-1-prod-1-cons-100-tbb.eps -\begin{figure} -\centering - \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-tbb} } - \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-tbb} } -\caption{Memory benchmark results with 1 producer for tbb memory allocator} -\label{fig:mem-1-prod-1-cons-100-tbb} \end{figure} @@ -648,9 +684,5 @@ \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-tbb} } \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-tbb} } -\caption{Memory benchmark results with 4 producers for tbb memory allocator} +\caption{Memory benchmark results with Configuration-2 for tbb memory allocator} \label{fig:mem-4-prod-4-cons-100-tbb} \end{figure} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% ANALYSIS -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Index: doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -129,6 +129,27 @@ \begin{center}\textbf{Abstract}\end{center} -This is the abstract. - +Memory management takes a sequence of program generated allocation/deallocation requests and attempts to satisfy them within a fixed-sized block of memory while minimizing the total amount of memory used. +A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal. +However, memory allocators do take advantage of regularities in allocation patterns for typical programs to produce excellent results, both in time and space (similar to LRU paging). +In general, allocators use a number of similar techniques, each optimizing specific allocation patterns. +Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns. + +The goal of this thesis is to build a low-latency memory allocator for both kernel and user multi-threaded systems, which is competitive with the best current memory allocators, while extending the feature set of existing and new allocator routines. +A new llheap memory-allocator is created that achieves all of these goals, while maintaining and managing sticky allocation properties for zero-fill and alignment allocations without a performance loss. +Hence, it becomes possible to use @realloc@ frequently as a safe operation, rather than just occasionally, because it preserves sticky properties when enlarging storage requests. +Furthermore, the ability to query sticky properties and information allows programmers to write safer programs, as it is possible to dynamically match allocation styles from unknown library routines that return allocations. +The C allocation API is also extended with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ so programmers do not make mistakes writing theses useful allocation operations. +llheap is embedded into the \uC and \CFA runtime systems, both of which have user-level threading. +The ability to use \CFA's advanced type-system (and possibly \CC's too) to have one allocation routine with completely orthogonal sticky properties shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation. + +The llheap allocator also provides comprehensive statistics for all allocation operations, which are invaluable in understanding and debugging a program's dynamic behaviour. +No other memory allocator examined in the thesis provides comprehensive statistics gathering. +As well, llheap provides a debugging mode where allocations are checked, along with internal pre/post conditions and invariants, is extremely useful, especially for students. +While not as powerful as the @valgrind@ interpreter, a large number of allocations mistakes are detected. +Finally, contention-free statistics gathering and debugging have a low enough cost to be used in production code. + +A micro-benchmark test-suite is started for comparing allocators, rather than relying on a suite of arbitrary programs, has been an interesting challenge. +These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs. +Existing memory allocators, glibc, dlmalloc, hoard, jemalloc, ptmalloc3, rpmalloc, tbmalloc and the new allocator llheap are all compared using the new micro-benchmark test-suite. \cleardoublepage @@ -136,7 +157,14 @@ % ------------------------------- -\begin{center}\textbf{Acknowledgements}\end{center} - -I would like to thank all the little people who made this thesis possible. +\begin{center} +\textbf{Acknowledgements} + +I would like to thank all the people who made this thesis possible. + +I would like to acknowledge Peter A. Buhr for his assistance and support throughtout the process. +It would have been impossible without him. + +Also, I would say thanks to my team members at PLG especially Thierry, Michael, and Andrew for their input. +\end{center} \cleardoublepage Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/AST/Convert.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -2729,5 +2729,6 @@ ty->forall.emplace_back(new ast::TypeInstType(param)); for (auto asst : param->assertions) { - ty->assertions.emplace_back(new ast::VariableExpr({}, asst)); + ty->assertions.emplace_back( + new ast::VariableExpr(param->location, asst)); } } Index: src/Common/utility.h =================================================================== --- src/Common/utility.h (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/Common/utility.h (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Feb 11 13:00:36 2020 -// Update Count : 50 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Apr 25 14:26:00 2022 +// Update Count : 51 // @@ -230,4 +230,10 @@ } +template +void erase_if( Container & cont, Pred && pred ) { + auto keep_end = std::remove_if( cont.begin(), cont.end(), pred ); + cont.erase( keep_end, cont.end() ); +} + template< typename... Args > auto zip(Args&&... args) -> decltype(zipWith(std::forward(args)..., std::make_pair)) { Index: src/SymTab/Validate.cc =================================================================== --- src/SymTab/Validate.cc (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/SymTab/Validate.cc (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -10,6 +10,6 @@ // Created On : Sun May 17 21:50:04 2015 // Last Modified By : Andrew Beach -// Last Modified On : Fri Nov 12 11:00:00 2021 -// Update Count : 364 +// Last Modified On : Fri Apr 29 9:45:00 2022 +// Update Count : 365 // @@ -143,4 +143,5 @@ struct LinkReferenceToTypes_old final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting { LinkReferenceToTypes_old( const Indexer * indexer ); + void postvisit( TypeInstType * typeInst ); @@ -370,11 +371,15 @@ } + void linkReferenceToTypes( std::list< Declaration * > & translationUnit ) { + PassVisitor lrt( nullptr ); + acceptAll( translationUnit, lrt ); // must happen before autogen, because sized flag needs to propagate to generated functions + } + void validate_B( std::list< Declaration * > & translationUnit ) { - PassVisitor lrt( nullptr ); PassVisitor fixQual; { Stats::Heap::newPass("validate-B"); Stats::Time::BlockGuard guard("validate-B"); - acceptAll( translationUnit, lrt ); // must happen before autogen, because sized flag needs to propagate to generated functions + //linkReferenceToTypes( translationUnit ); mutateAll( translationUnit, fixQual ); // must happen after LinkReferenceToTypes_old, because aggregate members are accessed HoistStruct::hoistStruct( translationUnit ); Index: src/SymTab/Validate.h =================================================================== --- src/SymTab/Validate.h (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/SymTab/Validate.h (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -42,4 +42,5 @@ void validate_E( std::list< Declaration * > &translationUnit ); void validate_F( std::list< Declaration * > &translationUnit ); + void linkReferenceToTypes( std::list< Declaration * > &translationUnit ); const ast::Type * validateType( Index: src/Validate/EliminateTypedef.cpp =================================================================== --- src/Validate/EliminateTypedef.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/EliminateTypedef.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,79 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// EliminateTypedef.cpp -- Removes TypedefDecl nodes from the AST. +// +// Author : Andrew Beach +// Created On : Wed Apr 20 16:37:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Apr 25 14:26:00 2022 +// Update Count : 0 +// + +#include "Validate/EliminateTypedef.hpp" + +#include + +#include "AST/Decl.hpp" +#include "AST/Pass.hpp" +#include "AST/Stmt.hpp" +#include "Common/utility.h" + +namespace Validate { + +namespace { + +struct EliminateTypedefCore { + ast::StructDecl const * previsit( ast::StructDecl const * decl ); + ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); + ast::CompoundStmt const * previsit( ast::CompoundStmt const * stmt ); +}; + +bool isTypedef( ast::ptr const & decl ) { + return (nullptr != decl.as()); +} + +bool isTypedefStmt( ast::ptr const & stmt ) { + if ( auto declStmt = stmt.as() ) { + return isTypedef( declStmt->decl ); + } + return false; +} + +template +node_t const * field_erase_if( node_t const * node, field_t super_t::*field, pred_t && pred) { + node_t * mut = ast::mutate( node ); + erase_if( mut->*field, pred ); + return mut; +} + +ast::StructDecl const * EliminateTypedefCore::previsit( ast::StructDecl const * decl ) { + return field_erase_if( decl, &ast::StructDecl::members, isTypedef ); +} + +ast::UnionDecl const * EliminateTypedefCore::previsit( ast::UnionDecl const * decl ) { + return field_erase_if( decl, &ast::UnionDecl::members, isTypedef ); +} + +ast::CompoundStmt const * EliminateTypedefCore::previsit( ast::CompoundStmt const * stmt ) { + return field_erase_if( stmt, &ast::CompoundStmt::kids, isTypedefStmt ); +} + +} // namespace + +/// Removes TypedefDecl nodes from the AST. +void eliminateTypedef( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); + erase_if( translationUnit.decls, isTypedef ); +} + +} // namespace Validate + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/EliminateTypedef.hpp =================================================================== --- src/Validate/EliminateTypedef.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/EliminateTypedef.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,33 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// EliminateTypedef.hpp -- Removes TypedefDecl nodes from the AST. +// +// Author : Andrew Beach +// Created On : Wed Apr 20 16:35:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Wed Apr 20 16:38:00 2022 +// Update Count : 0 +// + +#pragma once + +namespace ast { + class TranslationUnit; +} + +namespace Validate { + +/// Removes TypedefDecl nodes from the AST. +void eliminateTypedef( ast::TranslationUnit & translationUnit ); + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/FixQualifiedTypes.cpp =================================================================== --- src/Validate/FixQualifiedTypes.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/FixQualifiedTypes.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,106 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// FixQualifiedTypes.cpp -- +// +// Author : Andrew Beach +// Created On : Thr Apr 21 11:13:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Apr 22 11:36:00 2022 +// Update Count : 0 +// + +#include "Validate/FixQualifiedTypes.hpp" + +#include "AST/Pass.hpp" +#include "AST/TranslationUnit.hpp" +#include "Validate/NoIdSymbolTable.hpp" + +namespace Validate { + +namespace { + +struct FixQualifiedTypesCore : + public WithNoIdSymbolTable, public ast::WithGuards { + CodeLocation const * location = nullptr; + + void previsit( ast::ParseNode const * node ) { + GuardValue( location ) = &node->location; + } + + ast::Type const * postvisit( ast::QualifiedType const * type ) { + assert( location ); + + ast::ptr const & parent = type->parent; + ast::ptr const & child = type->child; + if ( parent.as() ) { + // .T => lookup T at global scope. + if ( auto inst = child.as() ) { + auto td = symtab.globalLookupType( inst->name ); + if ( !td ) { + SemanticError( *location, toString("Use of undefined global type ", inst->name) ); + } + auto base = td->base; + assert( base ); + ast::Type * ret = ast::deepCopy( base ); + ret->qualifiers = type->qualifiers; + return ret; + } else { + // .T => T is not a type name. + assertf( false, "unhandled global qualified child type: %s", toCString(child) ); + } + } else { + // S.T => S must be an aggregate type, find the declaration for T in S. + ast::AggregateDecl const * aggr = nullptr; + ast::BaseInstType const * instp = nullptr; + if ( auto inst = parent.as() ) { + aggr = inst->base; + instp = inst; + } else if ( auto inst = parent.as() ) { + aggr = inst->base; + instp = inst; + } else { + SemanticError( *location, toString("Qualified type requires an aggregate on the left, but has: ", parent) ); + } + // TODO: Need to handle forward declarations. + assert( aggr ); + for ( ast::ptr const & member : aggr->members ) { + if ( auto inst = child.as() ) { + if ( auto decl = member.as() ) { + if ( decl->name == inst->name ) { + assert( decl->base ); + ast::Type * ret = ast::deepCopy( decl->base ); + ret->qualifiers = type->qualifiers; + ast::TypeSubstitution sub( aggr->params, instp->params ); + // = parent->genericSubstitution(); + auto result = sub.apply(ret); + return result.node.release(); + } + } + } else { + // S.T - S is not an aggregate => error. + assertf( false, "unhandled qualified child type: %s", toCString(type) ); + } + } + // failed to find a satisfying definition of type + SemanticError( *location, toString("Undefined type in qualified type: ", type) ); + } + } +}; + +} // namespace + +void fixQualifiedTypes( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); +} + +} // namespace Validate + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/FixQualifiedTypes.hpp =================================================================== --- src/Validate/FixQualifiedTypes.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/FixQualifiedTypes.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,32 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// FixQualifiedTypes.hpp -- +// +// Author : Andrew Beach +// Created On : Thr Apr 21 11:11:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Thr Apr 21 11:11:00 2022 +// Update Count : 0 +// + +#pragma once + +namespace ast { + class TranslationUnit; +} + +namespace Validate { + +void fixQualifiedTypes( ast::TranslationUnit & translationUnit ); + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/ForallPointerDecay.cpp =================================================================== --- src/Validate/ForallPointerDecay.cpp (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/Validate/ForallPointerDecay.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -10,6 +10,6 @@ // Created On : Tue Dec 7 16:15:00 2021 // Last Modified By : Andrew Beach -// Last Modified On : Fri Feb 11 10:59:00 2022 -// Update Count : 0 +// Last Modified On : Sat Apr 23 13:10:00 2022 +// Update Count : 1 // @@ -237,4 +237,9 @@ } +std::vector> expandAssertions( + std::vector> const & old ) { + return TraitExpander::expandAssertions( old ); +} + } // namespace Validate Index: src/Validate/ForallPointerDecay.hpp =================================================================== --- src/Validate/ForallPointerDecay.hpp (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/Validate/ForallPointerDecay.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -10,11 +10,15 @@ // Created On : Tue Dec 7 16:15:00 2021 // Last Modified By : Andrew Beach -// Last Modified On : Tue Dec 8 11:50:00 2021 -// Update Count : 0 +// Last Modified On : Sat Apr 23 13:13:00 2022 +// Update Count : 1 // #pragma once +#include +#include "AST/Node.hpp" + namespace ast { + class DeclWithType; class TranslationUnit; } @@ -27,4 +31,8 @@ void decayForallPointers( ast::TranslationUnit & transUnit ); +/// Expand all traits in an assertion list. +std::vector> expandAssertions( + std::vector> const & ); + } Index: src/Validate/GenericParameter.cpp =================================================================== --- src/Validate/GenericParameter.cpp (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/Validate/GenericParameter.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -10,6 +10,6 @@ // Created On : Fri Mar 21 10:02:00 2022 // Last Modified By : Andrew Beach -// Last Modified On : Wed Apr 13 10:09:00 2022 -// Update Count : 0 +// Last Modified On : Fri Apr 22 16:43:00 2022 +// Update Count : 1 // @@ -22,4 +22,5 @@ #include "AST/TranslationUnit.hpp" #include "AST/Type.hpp" +#include "Validate/NoIdSymbolTable.hpp" namespace Validate { @@ -138,31 +139,6 @@ // -------------------------------------------------------------------------- -// A SymbolTable that only has the operations used in the Translate Dimension -// pass. More importantly, it doesn't have some methods that should no be -// called by the Pass template (lookupId and addId). -class NoIdSymbolTable { - ast::SymbolTable base; -public: -# define FORWARD_X( func, types_and_names, just_names ) \ - inline auto func types_and_names -> decltype( base.func just_names ) { \ - return base.func just_names ; \ - } -# define FORWARD_0( func ) FORWARD_X( func, (), () ) -# define FORWARD_1( func, type ) FORWARD_X( func, (type arg), (arg) ) -# define FORWARD_2( func, t0, t1 ) FORWARD_X( func, (t0 a0, t1 a1), (a0, a1) ) - - FORWARD_0( enterScope ) - FORWARD_0( leaveScope ) - FORWARD_1( lookupType, const std::string & ) - FORWARD_1( addType , const ast::NamedTypeDecl * ) - FORWARD_1( addStruct , const ast::StructDecl * ) - FORWARD_1( addEnum , const ast::EnumDecl * ) - FORWARD_1( addUnion , const ast::UnionDecl * ) - FORWARD_1( addTrait , const ast::TraitDecl * ) - FORWARD_2( addWith , const std::vector< ast::ptr > &, const ast::Decl * ) -}; - -struct TranslateDimensionCore : public ast::WithGuards { - NoIdSymbolTable symtab; +struct TranslateDimensionCore : + public WithNoIdSymbolTable, public ast::WithGuards { // SUIT: Struct- or Union- InstType Index: src/Validate/HoistStruct.cpp =================================================================== --- src/Validate/HoistStruct.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/HoistStruct.cpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,145 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// HoistStruct.cpp -- Flattens nested type declarations. +// +// Author : Andrew Beach +// Created On : Thr Apr 21 10:34:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Thr Apr 21 10:34:00 2022 +// Update Count : 0 +// + +#include "Validate/HoistStruct.hpp" + +#include "AST/Pass.hpp" +#include "AST/TranslationUnit.hpp" +#include "Common/utility.h" + +namespace Validate { + +namespace { + +bool shouldHoist( ast::Decl const * decl ) { + return dynamic_cast< ast::StructDecl const * >( decl ) + || dynamic_cast< ast::UnionDecl const * >( decl ) + || dynamic_cast< ast::StaticAssertDecl const * >( decl ); +} + +/* This pass also does some renaming and internal field alteration, but the + * complex part is the actual hoisting. Hoisted declarations should always + * appear before the declaration they are hoisted out of and if two types are + * nested in the same declaration their order should not change. + */ +struct HoistStructCore final : + public ast::WithDeclsToAdd<>, public ast::WithGuards { + ast::StructDecl const * previsit( ast::StructDecl const * decl ); + ast::StructDecl const * postvisit( ast::StructDecl const * decl ); + ast::UnionDecl const * previsit( ast::UnionDecl const * decl ); + ast::UnionDecl const * postvisit( ast::UnionDecl const * decl ); + ast::StructInstType const * previsit( ast::StructInstType const * type ); + ast::UnionInstType const * previsit( ast::UnionInstType const * type ); + ast::EnumInstType const * previsit( ast::EnumInstType const * type ); + +private: + template + AggrDecl const * preAggregate( AggrDecl const * ); + template + AggrDecl const * postAggregate( AggrDecl const * ); + + ast::AggregateDecl const * parent = nullptr; +}; + +void qualifiedName( ast::AggregateDecl const * decl, std::ostringstream & ss ) { + if ( decl->parent ) { + qualifiedName( decl->parent, ss ); + } + ss << "__" << decl->name; +} + +std::string qualifiedName( ast::AggregateDecl const * decl ) { + std::ostringstream ss; + qualifiedName( decl, ss ); + return ss.str(); +} + +template +AggrDecl const * HoistStructCore::preAggregate( AggrDecl const * decl ) { + if ( parent ) { + auto mut = ast::mutate( decl ); + mut->parent = parent; + mut->name = qualifiedName( mut ); + return mut; + } else { + GuardValue( parent ) = decl; + return decl; + } +} + +template +AggrDecl const * HoistStructCore::postAggregate( AggrDecl const * decl ) { + auto mut = ast::mutate( decl ); + for ( auto it = mut->members.begin() ; it != mut->members.end() ; ) { + if ( shouldHoist( *it ) ) { + // This is the place where the actual hoisting happens. + declsToAddBefore.push_back( it->get() ); + it = mut->members.erase( it ); + } else { + ++it; + } + } + return mut; +} + +ast::StructDecl const * HoistStructCore::previsit( ast::StructDecl const * decl ) { + return preAggregate( decl ); +} + +ast::StructDecl const * HoistStructCore::postvisit( ast::StructDecl const * decl ) { + return postAggregate( decl ); +} + +ast::UnionDecl const * HoistStructCore::previsit( ast::UnionDecl const * decl ) { + return preAggregate( decl ); +} + +ast::UnionDecl const * HoistStructCore::postvisit( ast::UnionDecl const * decl ) { + return postAggregate( decl ); +} + +template +InstType const * preInstType( InstType const * type ) { + assert( type->base ); + auto mut = ast::mutate( type ); + mut->name = mut->base->name; + return mut; +} + +ast::StructInstType const * HoistStructCore::previsit( ast::StructInstType const * type ) { + return preInstType( type ); +} + +ast::UnionInstType const * HoistStructCore::previsit( ast::UnionInstType const * type ) { + return preInstType( type ); +} + +ast::EnumInstType const * HoistStructCore::previsit( ast::EnumInstType const * type ) { + return preInstType( type ); +} + +} // namespace + +void hoistStruct( ast::TranslationUnit & translationUnit ) { + ast::Pass::run( translationUnit ); +} + +} // namespace Validate + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/HoistStruct.hpp =================================================================== --- src/Validate/HoistStruct.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/HoistStruct.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,33 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// HoistStruct.hpp -- Flattens nested type declarations. +// +// Author : Andrew Beach +// Created On : Thr Apr 21 10:33:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Thr Apr 21 10:39:00 2022 +// Update Count : 0 +// + +#pragma once + +namespace ast { + class TranslationUnit; +} + +namespace Validate { + +/// Flattens nested type declarations. +void hoistStruct( ast::TranslationUnit & translationUnit ); + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/NoIdSymbolTable.hpp =================================================================== --- src/Validate/NoIdSymbolTable.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ src/Validate/NoIdSymbolTable.hpp (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,70 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// NoIdSymbolTable.hpp -- Special WithSymbolTable variant ast::Pass helper. +// +// Author : Andrew Beach +// Created On : Thr Apr 21 11:57:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Thr Apr 21 11:57:00 2022 +// Update Count : 0 +// + +#pragma once + +#include "AST/SymbolTable.hpp" + +namespace Validate { + +// A SymbolTable that only has the operations used in the Translate Dimension +// pass. More importantly, it doesn't have some methods that should no be +// called by the Pass template (lookupId and addId). +class NoIdSymbolTable { + ast::SymbolTable base; +public: +# define FORWARD_X( func, types_and_names, just_names ) \ + inline auto func types_and_names -> decltype( base.func just_names ) { \ + return base.func just_names ; \ + } +# define FORWARD_0( func ) FORWARD_X( func, (), () ) +# define FORWARD_1( func, type ) FORWARD_X( func, (type arg), (arg) ) +# define FORWARD_2( func, t0, t1 ) FORWARD_X( func, (t0 a0, t1 a1), (a0, a1) ) + + FORWARD_0( enterScope ) + FORWARD_0( leaveScope ) + FORWARD_1( lookupType , const std::string & ) + FORWARD_1( lookupStruct, const std::string & ) + FORWARD_1( lookupEnum , const std::string & ) + FORWARD_1( lookupUnion , const std::string & ) + FORWARD_1( lookupTrait , const std::string & ) + FORWARD_1( addType , const ast::NamedTypeDecl * ) + FORWARD_1( addStruct, const ast::StructDecl * ) + FORWARD_1( addEnum , const ast::EnumDecl * ) + FORWARD_1( addUnion , const ast::UnionDecl * ) + FORWARD_1( addTrait , const ast::TraitDecl * ) + FORWARD_1( addStruct, const std::string & ) + FORWARD_1( addUnion , const std::string & ) + FORWARD_2( addWith , const std::vector< ast::ptr > &, const ast::Decl * ) + + FORWARD_1( globalLookupType, const std::string & ) + +# undef FORWARD_2 +# undef FORWARD_1 +# undef FORWARD_0 +# undef FORWARD_X +}; + +struct WithNoIdSymbolTable { + NoIdSymbolTable symtab; +}; + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/module.mk =================================================================== --- src/Validate/module.mk (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/Validate/module.mk (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -20,4 +20,8 @@ Validate/CompoundLiteral.cpp \ Validate/CompoundLiteral.hpp \ + Validate/EliminateTypedef.cpp \ + Validate/EliminateTypedef.hpp \ + Validate/FixQualifiedTypes.cpp \ + Validate/FixQualifiedTypes.hpp \ Validate/ForallPointerDecay.cpp \ Validate/ForallPointerDecay.hpp \ @@ -26,8 +30,11 @@ Validate/HandleAttributes.cc \ Validate/HandleAttributes.h \ + Validate/HoistStruct.cpp \ + Validate/HoistStruct.hpp \ Validate/InitializerLength.cpp \ Validate/InitializerLength.hpp \ Validate/LabelAddressFixer.cpp \ Validate/LabelAddressFixer.hpp \ + Validate/NoIdSymbolTable.hpp \ Validate/ReturnCheck.cpp \ Validate/ReturnCheck.hpp \ Index: src/main.cc =================================================================== --- src/main.cc (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ src/main.cc (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -10,6 +10,6 @@ // Created On : Fri May 15 23:12:02 2015 // Last Modified By : Andrew Beach -// Last Modified On : Wed Apr 13 11:11:00 2022 -// Update Count : 672 +// Last Modified On : Fri Apr 29 9:52:00 2022 +// Update Count : 673 // @@ -75,10 +75,14 @@ #include "Tuples/Tuples.h" // for expandMemberTuples, expan... #include "Validate/Autogen.hpp" // for autogenerateRoutines +#include "Validate/CompoundLiteral.hpp" // for handleCompoundLiterals +#include "Validate/EliminateTypedef.hpp" // for eliminateTypedef +#include "Validate/FindSpecialDecls.h" // for findGlobalDecls +#include "Validate/FixQualifiedTypes.hpp" // for fixQualifiedTypes +#include "Validate/ForallPointerDecay.hpp" // for decayForallPointers #include "Validate/GenericParameter.hpp" // for fillGenericParameters, tr... -#include "Validate/FindSpecialDecls.h" // for findGlobalDecls -#include "Validate/ForallPointerDecay.hpp" // for decayForallPointers -#include "Validate/CompoundLiteral.hpp" // for handleCompoundLiterals +#include "Validate/HoistStruct.hpp" // for hoistStruct #include "Validate/InitializerLength.hpp" // for setLengthFromInitializer #include "Validate/LabelAddressFixer.hpp" // for fixLabelAddresses +#include "Validate/LinkReferenceToTypes.hpp"// for linkReferenceToTypes #include "Validate/ReturnCheck.hpp" // for checkReturnStatements #include "Virtual/ExpandCasts.h" // for expandCasts @@ -328,5 +332,7 @@ // add the assignment statement after the initialization of a type parameter PASS( "Validate-A", SymTab::validate_A( translationUnit ) ); - PASS( "Validate-B", SymTab::validate_B( translationUnit ) ); + + // Must happen before auto-gen, because it uses the sized flag. + PASS( "Link Reference To Types", SymTab::linkReferenceToTypes( translationUnit ) ); CodeTools::fillLocations( translationUnit ); @@ -342,4 +348,11 @@ forceFillCodeLocations( transUnit ); + + // Must happen after Link References To Types, + // because aggregate members are accessed. + PASS( "Fix Qualified Types", Validate::fixQualifiedTypes( transUnit ) ); + + PASS( "Hoist Struct", Validate::hoistStruct( transUnit ) ); + PASS( "Eliminate Typedef", Validate::eliminateTypedef( transUnit ) ); // Check as early as possible. Can't happen before @@ -438,4 +451,5 @@ translationUnit = convert( move( transUnit ) ); } else { + PASS( "Validate-B", SymTab::validate_B( translationUnit ) ); PASS( "Validate-C", SymTab::validate_C( translationUnit ) ); PASS( "Validate-D", SymTab::validate_D( translationUnit ) ); Index: tests/.expect/nested-types-ERR2.nast.txt =================================================================== --- tests/.expect/nested-types-ERR2.nast.txt (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ tests/.expect/nested-types-ERR2.nast.txt (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,7 @@ +nested-types.cfa:100:25: warning: Compiled +nested-types.cfa:86:1 error: Use of undefined global type Z +nested-types.cfa:87:1 error: Qualified type requires an aggregate on the left, but has: signed int +nested-types.cfa:88:1 error: Undefined type in qualified type: Qualified Type: + instance of struct S with body + instance of type Z (not function type) + Index: tests/.expect/nested-types-ERR2.oast.txt =================================================================== --- tests/.expect/nested-types-ERR2.oast.txt (revision 4cb1a24ff34151243be29586e1465c43d098a106) +++ tests/.expect/nested-types-ERR2.oast.txt (revision 4cb1a24ff34151243be29586e1465c43d098a106) @@ -0,0 +1,7 @@ +nested-types.cfa:100:25: warning: Compiled +nested-types.cfa:86:1 error: Use of undefined global type Z +nested-types.cfa:87:1 error: Qualified type requires an aggregate on the left, but has: signed int +nested-types.cfa:88:1 error: Undefined type in qualified type: Qualified Type: + instance of struct S with body 1 + instance of type Z (not function type) + Index: sts/.expect/nested-types-ERR2.txt =================================================================== --- tests/.expect/nested-types-ERR2.txt (revision 111a2ab3e38e9a482e065aa6feb44c420adb6b6f) +++ (revision ) @@ -1,7 +1,0 @@ -nested-types.cfa:100:25: warning: Compiled -nested-types.cfa:86:1 error: Use of undefined global type Z -nested-types.cfa:87:1 error: Qualified type requires an aggregate on the left, but has: signed int -nested-types.cfa:88:1 error: Undefined type in qualified type: Qualified Type: - instance of struct S with body 1 - instance of type Z (not function type) -