Index: doc/theses/mubeen_zulfiqar_MMath/allocator.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/allocator.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/allocator.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -24,6 +24,7 @@ \end{itemize} -The new features added to uHeapLmmm (incl. @malloc_size@ routine) +The new features added to uHeapLmmm (incl. @malloc\_size@ routine) \CFA alloc interface with examples. + \begin{itemize} \item @@ -117,8 +118,9 @@ We added a few more features and routines to the allocator's C interface that can make the allocator more usable to the programmers. THese features will programmer more control on the dynamic memory allocation. -\subsubsection void * aalloc( size_t dim, size_t elemSize ) +\subsubsection void * aalloc( size\_t dim, size\_t elemSize ) aalloc is an extension of malloc. It allows programmer to allocate a dynamic array of objects without calculating the total size of array explicitly. The only alternate of this routine in the other allocators is calloc but calloc also fills the dynamic memory with 0 which makes it slower for a programmer who only wants to dynamically allocate an array of objects without filling it with 0. \paragraph{Usage} aalloc takes two parameters. + \begin{itemize} \item @@ -129,8 +131,9 @@ It returns address of dynamic object allocatoed on heap that can contain dim number of objects of the size elemSize. On failure, it returns NULL pointer. -\subsubsection void * resize( void * oaddr, size_t size ) +\subsubsection void * resize( void * oaddr, size\_t size ) resize is an extension of relloc. It allows programmer to reuse a cuurently allocated dynamic object with a new size requirement. Its alternate in the other allocators is realloc but relloc also copy the data in old object to the new object which makes it slower for the programmer who only wants to reuse an old dynamic object for a new size requirement but does not want to preserve the data in the old object to the new object. \paragraph{Usage} resize takes two parameters. + \begin{itemize} \item @@ -141,8 +144,9 @@ It returns an object that is of the size given but it does not preserve the data in the old object. On failure, it returns NULL pointer. -\subsubsection void * resize( void * oaddr, size_t nalign, size_t size ) +\subsubsection void * resize( void * oaddr, size\_t nalign, size\_t size ) This resize is an extension of the above resize (FIX ME: cite above resize). In addition to resizing the size of of an old object, it can also realign the old object to a new alignment requirement. \paragraph{Usage} This resize takes three parameters. It takes an additional parameter of nalign as compared to the above resize (FIX ME: cite above resize). + \begin{itemize} \item @@ -155,8 +159,9 @@ It returns an object with the size and alignment given in the parameters. On failure, it returns a NULL pointer. -\subsubsection void * amemalign( size_t alignment, size_t dim, size_t elemSize ) +\subsubsection void * amemalign( size\_t alignment, size\_t dim, size\_t elemSize ) amemalign is a hybrid of memalign and aalloc. It allows programmer to allocate an aligned dynamic array of objects without calculating the total size of the array explicitly. It frees the programmer from calculating the total size of the array. \paragraph{Usage} amemalign takes three parameters. + \begin{itemize} \item @@ -169,8 +174,9 @@ It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment. On failure, it returns NULL pointer. -\subsubsection void * cmemalign( size_t alignment, size_t dim, size_t elemSize ) +\subsubsection void * cmemalign( size\_t alignment, size\_t dim, size\_t elemSize ) cmemalign is a hybrid of amemalign and calloc. It allows programmer to allocate an aligned dynamic array of objects that is 0 filled. The current way to do this in other allocators is to allocate an aligned object with memalign and then fill it with 0 explicitly. This routine provides both features of aligning and 0 filling, implicitly. \paragraph{Usage} cmemalign takes three parameters. + \begin{itemize} \item @@ -183,38 +189,42 @@ It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment and is 0 filled. On failure, it returns NULL pointer. -\subsubsection size_t malloc_alignment( void * addr ) -malloc_alignment returns the alignment of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment. -\paragraph{Usage} -malloc_alignment takes one parameters. +\subsubsection size\_t malloc\_alignment( void * addr ) +malloc\_alignment returns the alignment of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment. +\paragraph{Usage} +malloc\_alignment takes one parameters. + \begin{itemize} \item addr: the address of the currently allocated dynamic object. \end{itemize} -malloc_alignment returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator. - -\subsubsection bool malloc_zero_fill( void * addr ) -malloc_zero_fill returns whether a currently allocated dynamic object was initially zero filled at the time of allocation. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation. -\paragraph{Usage} -malloc_zero_fill takes one parameters. +malloc\_alignment returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator. + +\subsubsection bool malloc\_zero\_fill( void * addr ) +malloc\_zero\_fill returns whether a currently allocated dynamic object was initially zero filled at the time of allocation. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation. +\paragraph{Usage} +malloc\_zero\_fill takes one parameters. + \begin{itemize} \item addr: the address of the currently allocated dynamic object. \end{itemize} -malloc_zero_fill returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false. - -\subsubsection size_t malloc_size( void * addr ) -malloc_size returns the allocation size of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size. Its current alternate in the other allocators is malloc_usable_size. But, malloc_size is different from malloc_usable_size as malloc_usabe_size returns the total data capacity of dynamic object including the extra space at the end of the dynamic object. On the other hand, malloc_size returns the size that was given to the allocator at the allocation of the dynamic object. This size is updated when an object is realloced, resized, or passed through a similar allocator routine. -\paragraph{Usage} -malloc_size takes one parameters. +malloc\_zero\_fill returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false. + +\subsubsection size\_t malloc\_size( void * addr ) +malloc\_size returns the allocation size of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size. Its current alternate in the other allocators is malloc\_usable\_size. But, malloc\_size is different from malloc\_usable\_size as malloc\_usabe\_size returns the total data capacity of dynamic object including the extra space at the end of the dynamic object. On the other hand, malloc\_size returns the size that was given to the allocator at the allocation of the dynamic object. This size is updated when an object is realloced, resized, or passed through a similar allocator routine. +\paragraph{Usage} +malloc\_size takes one parameters. + \begin{itemize} \item addr: the address of the currently allocated dynamic object. \end{itemize} -malloc_size returns the allocation size of the given dynamic object. On failure, it return zero. - -\subsubsection void * realloc( void * oaddr, size_t nalign, size_t size ) +malloc\_size returns the allocation size of the given dynamic object. On failure, it return zero. + +\subsubsection void * realloc( void * oaddr, size\_t nalign, size\_t size ) This realloc is an extension of the default realloc (FIX ME: cite default realloc). In addition to reallocating an old object and preserving the data in old object, it can also realign the old object to a new alignment requirement. \paragraph{Usage} This realloc takes three parameters. It takes an additional parameter of nalign as compared to the default realloc. + \begin{itemize} \item @@ -237,8 +247,9 @@ It returns a dynamic object of the size of type T. On failure, it return NULL pointer. -\subsubsection T * aalloc( size_t dim ) +\subsubsection T * aalloc( size\_t dim ) This aalloc is a simplified polymorphic form of above aalloc (FIX ME: cite aalloc). It takes one parameter as compared to the above aalloc that takes two parameters. \paragraph{Usage} aalloc takes one parameters. + \begin{itemize} \item @@ -247,8 +258,9 @@ It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer. -\subsubsection T * calloc( size_t dim ) +\subsubsection T * calloc( size\_t dim ) This calloc is a simplified polymorphic form of defualt calloc (FIX ME: cite calloc). It takes one parameter as compared to the default calloc that takes two parameters. \paragraph{Usage} This calloc takes one parameter. + \begin{itemize} \item @@ -257,8 +269,9 @@ It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer. -\subsubsection T * resize( T * ptr, size_t size ) +\subsubsection T * resize( T * ptr, size\_t size ) This resize is a simplified polymorphic form of above resize (FIX ME: cite resize with alignment). It takes two parameters as compared to the above resize that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type. \paragraph{Usage} This resize takes two parameters. + \begin{itemize} \item @@ -269,8 +282,9 @@ It returns a dynamic object of the size given in paramters. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer. -\subsubsection T * realloc( T * ptr, size_t size ) +\subsubsection T * realloc( T * ptr, size\_t size ) This realloc is a simplified polymorphic form of defualt realloc (FIX ME: cite realloc with align). It takes two parameters as compared to the above realloc that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type. \paragraph{Usage} This realloc takes two parameters. + \begin{itemize} \item @@ -281,8 +295,9 @@ It returns a dynamic object of the size given in paramters that preserves the data in the given object. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer. -\subsubsection T * memalign( size_t align ) +\subsubsection T * memalign( size\_t align ) This memalign is a simplified polymorphic form of defualt memalign (FIX ME: cite memalign). It takes one parameters as compared to the default memalign that takes two parameters. \paragraph{Usage} memalign takes one parameters. + \begin{itemize} \item @@ -291,8 +306,9 @@ It returns a dynamic object of the size of type T that is aligned to given parameter align. On failure, it return NULL pointer. -\subsubsection T * amemalign( size_t align, size_t dim ) +\subsubsection T * amemalign( size\_t align, size\_t dim ) This amemalign is a simplified polymorphic form of above amemalign (FIX ME: cite amemalign). It takes two parameter as compared to the above amemalign that takes three parameters. \paragraph{Usage} amemalign takes two parameters. + \begin{itemize} \item @@ -303,8 +319,9 @@ It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align. On failure, it return NULL pointer. -\subsubsection T * cmemalign( size_t align, size_t dim ) +\subsubsection T * cmemalign( size\_t align, size\_t dim ) This cmemalign is a simplified polymorphic form of above cmemalign (FIX ME: cite cmemalign). It takes two parameter as compared to the above cmemalign that takes three parameters. \paragraph{Usage} cmemalign takes two parameters. + \begin{itemize} \item @@ -315,8 +332,9 @@ It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align and is zero filled. On failure, it return NULL pointer. -\subsubsection T * aligned_alloc( size_t align ) -This aligned_alloc is a simplified polymorphic form of defualt aligned_alloc (FIX ME: cite aligned_alloc). It takes one parameter as compared to the default aligned_alloc that takes two parameters. -\paragraph{Usage} -This aligned_alloc takes one parameter. +\subsubsection T * aligned\_alloc( size\_t align ) +This aligned\_alloc is a simplified polymorphic form of defualt aligned\_alloc (FIX ME: cite aligned\_alloc). It takes one parameter as compared to the default aligned\_alloc that takes two parameters. +\paragraph{Usage} +This aligned\_alloc takes one parameter. + \begin{itemize} \item @@ -325,8 +343,9 @@ It returns a dynamic object of the size of type T that is aligned to the given parameter. On failure, it return NULL pointer. -\subsubsection int posix_memalign( T ** ptr, size_t align ) -This posix_memalign is a simplified polymorphic form of defualt posix_memalign (FIX ME: cite posix_memalign). It takes two parameters as compared to the default posix_memalign that takes three parameters. -\paragraph{Usage} -This posix_memalign takes two parameter. +\subsubsection int posix\_memalign( T ** ptr, size\_t align ) +This posix\_memalign is a simplified polymorphic form of defualt posix\_memalign (FIX ME: cite posix\_memalign). It takes two parameters as compared to the default posix\_memalign that takes three parameters. +\paragraph{Usage} +This posix\_memalign takes two parameter. + \begin{itemize} \item @@ -335,4 +354,5 @@ align: required alignment of the dynamic object. \end{itemize} + It stores address of the dynamic object of the size of type T in given parameter ptr. This object is aligned to the given parameter. On failure, it return NULL pointer. @@ -349,7 +369,8 @@ It returns a dynamic object of the size that is calcutaed by rouding the size of type T. The returned object is also aligned to the page size. On failure, it return NULL pointer. -\subsection{Alloc Interface} +\subsection Alloc Interface In addition to improve allocator interface both for CFA and our standalone allocator uHeapLmmm in C. We also added a new alloc interface in CFA that increases usability of dynamic memory allocation. This interface helps programmers in three major ways. + \begin{itemize} \item @@ -371,5 +392,5 @@ This is the only parameter in the alloc routine that has a fixed-position and it is also the only parameter that does not use a backtick function. It has to be passed at the first position to alloc call in-case of an array allocation of objects of type T. It represents the required number of members in the array allocation as in CFA's aalloc (FIX ME: cite aalloc). -This parameter should be of type size_t. +This parameter should be of type size\_t. Example: int a = alloc( 5 ) @@ -377,5 +398,5 @@ \paragraph{Align} -This parameter is position-free and uses a backtick routine align (`align). The parameter passed with `align should be of type size_t. If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in CFA) then the passed alignment parameter will be rejected and the default alignment will be used. +This parameter is position-free and uses a backtick routine align (`align). The parameter passed with `align should be of type size\_t. If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in CFA) then the passed alignment parameter will be rejected and the default alignment will be used. Example: int b = alloc( 5 , 64`align ) @@ -385,4 +406,5 @@ This parameter is position-free and uses a backtick routine fill (`fill). In case of realloc, only the extra space after copying the data in the old object will be filled with given parameter. Three types of parameters can be passed using `fill. + \begin{itemize} \item Index: doc/theses/mubeen_zulfiqar_MMath/background.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/background.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/background.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -23,3 +23,42 @@ ==================== -\cite{Wasik08} +\section{Background} + +% FIXME: cite wasik +\cite{wasik.thesis} + +\subsection{Memory Allocation} +With dynamic allocation being an important feature of C, there are many standalone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators. + +\paragraph{dlmalloc} +dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik) + +\paragraph{hoard} +Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thred heaps that have thread-local free-lists, and a gloabl shared heap. (FIX ME: cite wasik) + +\paragraph{jemalloc} +jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes. + +\paragraph{ptmalloc} +ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap. + +\paragraph{rpmalloc} +rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-calss contains memory regions of the relevant size. + +\paragraph{tbb malloc} +tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size. + +\paragraph{tc malloc} +tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty. + +\subsection{Benchmarks} +There are multiple benchmarks that are built individually and evaluate different aspects of a memory allocator. But, there is not standard set of benchamrks that can be used to evaluate multiple aspects of memory allocators. + +\paragraph{threadtest} +(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency. + +\paragraph{shbench} +(FIX ME: cite benchmark and hoard) Each thread allocates and randomly frees a number of random-sized objects. It is a stress test that also uses runtime to determine efficiency of the allocator. + +\paragraph{larson} +(FIX ME: cite benchmark and hoard) Larson simulates a server environment. Multiple threads are created where each thread allocator and free a number of objects within a size range. Some objects are passed from threads to the child threads to free. It caluculates memory operations per second as an indicator of memory allocator's performance. Index: doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -149,5 +149,5 @@ *** FIX ME: Insert a figure of above benchmark with description -\paragrpah{Relevant Knobs} +\paragraph{Relevant Knobs} *** FIX ME: Insert Relevant Knobs Index: doc/theses/mubeen_zulfiqar_MMath/intro.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/intro.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/intro.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -47,11 +47,11 @@ \begin{itemize} \item -aligned_alloc +aligned\_alloc \item -malloc_usable_size +malloc\_usable\_size \item memalign \item -posix_memalign +posix\_memalign \item pvalloc @@ -61,42 +61,4 @@ With the rise of concurrent applications, memory allocators should be able to fulfill dynamic memory requests from multiple threads in parallel without causing contention on shared resources. There needs to be a set of a standard benchmarks that can be used to evaluate an allocator's performance in different scenerios. - -\section{Background} - -\subsection{Memory Allocation} -With dynamic allocation being an important feature of C, there are many standalone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators. - -\paragraph{dlmalloc} -dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik) - -\paragraph{hoard} -Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thred heaps that have thread-local free-lists, and a gloabl shared heap. (FIX ME: cite wasik) - -\paragraph{jemalloc} -jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes. - -\paragraph{ptmalloc} -ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap. - -\paragraph{rpmalloc} -rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-calss contains memory regions of the relevant size. - -\paragraph{tbb malloc} -tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size. - -\paragraph{tc malloc} -tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty. - -\subsection{Benchmarks} -There are multiple benchmarks that are built individually and evaluate different aspects of a memory allocator. But, there is not standard set of benchamrks that can be used to evaluate multiple aspects of memory allocators. - -\paragraph{threadtest} -(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency. - -\paragraph{shbench} -(FIX ME: cite benchmark and hoard) Each thread allocates and randomly frees a number of random-sized objects. It is a stress test that also uses runtime to determine efficiency of the allocator. - -\paragraph{larson} -(FIX ME: cite benchmark and hoard) Larson simulates a server environment. Multiple threads are created where each thread allocator and free a number of objects within a size range. Some objects are passed from threads to the child threads to free. It caluculates memory operations per second as an indicator of memory allocator's performance. \section{Research Objectives} Index: doc/theses/mubeen_zulfiqar_MMath/performance.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -44,5 +44,6 @@ tc & & \\ \end{tabularx} -(FIX ME: complete table) + +%(FIX ME: complete table) \section{Experiment Environment} Index: c/theses/mubeen_zulfiqar_MMath/thesis.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/thesis.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ (revision ) @@ -1,12 +1,0 @@ -\documentclass[letterpaper,12pt,titlepage,oneside,final]{book} - -\usepackage{amsmath,amssymb,amsfonts} - -\begin{document} - -\section{Benchmark Suite} - -\section{Memory Allocator} - -\end{document} - Index: doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.bib =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.bib (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.bib (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -27,2 +27,9 @@ address = "Reading, Massachusetts" } + +@article{wasik.thesis, + author = "Ayelet Wasik", + title = "Features of A Multi-Threaded Memory Alloator", + publisher = "University of Waterloo", + year = "2008" +} Index: doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -84,4 +84,5 @@ \usepackage{graphicx} \usepackage{comment} % Removes large sections of the document. +\usepackage{tabularx} % Hyperlinks make it very easy to navigate an electronic document. @@ -191,4 +192,6 @@ % Tip: Putting each sentence on a new line is a way to simplify later editing. %---------------------------------------------------------------------- +\begin{sloppypar} + \input{intro} \input{background} @@ -197,4 +200,6 @@ \input{performance} \input{conclusion} + +\end{sloppypar} %---------------------------------------------------------------------- Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision a51a02de31d78381190b6b5aafa5260020147369) +++ doc/user/user.tex (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Mon May 31 09:03:34 2021 -%% Update Count : 5071 +%% Last Modified On : Sun Oct 10 12:45:00 2021 +%% Update Count : 5095 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -4444,8 +4444,8 @@ \CFA provides a fine-grained solution where a \Index{recursive lock} is acquired and released indirectly via a manipulator ©acquire© or instantiating an \Index{RAII} type specific for the kind of stream: ©osacquire©\index{ostream@©ostream©!osacquire@©osacquire©} for output streams and ©isacquire©\index{isacquire@©isacquire©}\index{istream@©istream©!isacquire@©isacquire©} for input streams. -The common usage is manipulator ©acquire©\index{ostream@©ostream©!acquire@©acquire©} to lock a stream during a single cascaded I/O expression, with the manipulator appearing as the first item in a cascade list, \eg: -\begin{cfa} -$\emph{thread\(_1\)}$ : sout | ®acquire® | "abc " | "def "; // manipulator -$\emph{thread\(_2\)}$ : sout | ®acquire® | "uvw " | "xyz "; +The common usage is the short form of the mutex statement\index{ostream@©ostream©!mutex@©mutex©} to lock a stream during a single cascaded I/O expression, \eg: +\begin{cfa} +$\emph{thread\(_1\)}$ : ®mutex()® sout | "abc " | "def "; +$\emph{thread\(_2\)}$ : ®mutex()® sout | "uvw " | "xyz "; \end{cfa} Now, the order of the thread execution is still non-deterministic, but the output is constrained to two possible lines in either order. @@ -4466,25 +4466,23 @@ In summary, the stream lock is acquired by the ©acquire© manipulator and implicitly released at the end of the cascaded I/O expression ensuring all operations in the expression occur atomically. -To lock a stream across multiple I/O operations, an object of type ©osacquire© or ©isacquire© is declared to implicitly acquire/release the stream lock providing mutual exclusion for the object's duration, \eg: -\begin{cfa} -{ // acquire sout for block duration - ®osacquire® acq = { sout }; $\C{// named stream locker}$ +To lock a stream across multiple I/O operations, he long form of the mutex statement is used, \eg: +\begin{cfa} +®mutex( sout )® { sout | 1; - sout | ®acquire® | 2 | 3; $\C{// unnecessary, but ok to acquire and release again}$ + ®mutex() sout® | 2 | 3; $\C{// unnecessary, but ok because of recursive lock}$ sout | 4; -} // implicitly release the lock when "acq" is deallocated -\end{cfa} -Note, the unnecessary ©acquire© manipulator works because the recursive stream-lock can be acquired/released multiple times by the owner thread. +} // implicitly release sout lock +\end{cfa} +Note, the unnecessary ©mutex© in the middle of the mutex statement, works because the recursive stream-lock can be acquired/released multiple times by the owner thread. Hence, calls to functions that also acquire a stream lock for their output do not result in \Index{deadlock}. The previous values written by threads 1 and 2 can be read in concurrently: \begin{cfa} -{ // acquire sin lock for block duration - ®isacquire acq = { sin };® $\C{// named stream locker}$ +®mutex( sin )® { int x, y, z, w; sin | x; - sin | ®acquire® | y | z; $\C{// unnecessary, but ok to acquire and release again}$ + ®mutex() sin® | y | z; $\C{// unnecessary, but ok because of recursive lock}$ sin | w; -} // implicitly release the lock when "acq" is deallocated +} // implicitly release sin lock \end{cfa} Again, the order of the reading threads is non-deterministic. @@ -4493,5 +4491,5 @@ \Textbf{WARNING:} The general problem of \Index{nested locking} can occur if routines are called in an I/O sequence that block, \eg: \begin{cfa} -sout | ®acquire® | "data:" | rtn( mon ); $\C{// mutex call on monitor}$ +®mutex() sout® | "data:" | rtn( mon ); $\C{// mutex call on monitor}$ \end{cfa} If the thread executing the I/O expression blocks in the monitor with the ©sout© lock, other threads writing to ©sout© also block until the thread holding the lock is unblocked and releases it. @@ -4500,5 +4498,5 @@ \begin{cfa} int ®data® = rtn( mon ); -sout | acquire | "data:" | ®data®; +mutex() sout | "data:" | ®data®; \end{cfa} @@ -4506,6 +4504,22 @@ \section{String Stream} -All the stream formatting capabilities are available to format text to/from a C string rather than to a stream file. -\VRef[Figure]{f:StringStreamProcessing} shows writing (output) and reading (input) from a C string. +The stream types ©ostrstream© and ©istrstream© provide all the stream formatting capabilities to/from a C string rather than a stream file. +\VRef[Figure]{f:StringStreamProcessing} shows writing (output) to and reading (input) from a C string. +The only string stream operations different from a file stream are: +\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt] +\item +constructors to create a stream that writes to a write buffer (©ostrstream©) of ©size©, or reads from a read buffer (©istrstream©) containing a C string terminated with ©'\0'©. +\begin{cfa} +void ?{}( ostrstream &, char buf[], size_t size ); +void ?{}( istrstream & is, char buf[] ); +\end{cfa} +\item +\Indexc{write} (©ostrstream© only) writes all the buffered characters to the specified stream (©stdout© default). +\begin{cfa} +ostrstream & write( ostrstream & os, FILE * stream = stdout ); +\end{cfa} +There is no ©read© for ©istrstream©. +\end{itemize} + \begin{figure} \begin{cfa} @@ -4520,46 +4534,24 @@ double x = 12345678.9, y = 98765.4321e-11; - osstr | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y)); $\C{// same lines of output}$ - write( osstr ); - printf( "%s", buf ); - sout | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y)); - - char buf2[] = "12 14 15 3.5 7e4"; $\C{// input buffer}$ + osstr | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y)) | "abc"; + write( osstr ); $\C{// write string to stdout}$ + printf( "%s", buf ); $\C{// same lines of output}$ + sout | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y)) | "abc"; + + char buf2[] = "12 14 15 3.5 7e4 abc"; $\C{// input buffer}$ ®istrstream isstr = { buf2 };® - isstr | i | j | k | x | y; - sout | i | j | k | x | y; -} + char s[10]; + isstr | i | j | k | x | y | s; + sout | i | j | k | x | y | s; +} + +3 0x5 7 1.234568e+07 987.654n abc +3 0x5 7 1.234568e+07 987.654n abc +3 0x5 7 1.234568e+07 987.654n abc +12 14 15 3.5 70000. abc \end{cfa} \caption{String Stream Processing} \label{f:StringStreamProcessing} \end{figure} - -\VRef[Figure]{f:StringStreamFunctions} shows the string stream operations. -\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt] -\item -\Indexc{write} (©ostrstream© only) writes all the buffered characters to the specified stream (©stdout© default). -\end{itemize} -The constructor functions: -\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt] -\item -create a bound stream to a write buffer (©ostrstream©) of ©size© or a read buffer (©istrstream©) containing a C string terminated with ©'\0'©. -\end{itemize} - -\begin{figure} -\begin{cfa} -// *********************************** ostrstream *********************************** - -ostrstream & write( ostrstream & os, FILE * stream = stdout ); - -void ?{}( ostrstream &, char buf[], size_t size ); - -// *********************************** istrstream *********************************** - -void ?{}( istrstream & is, char buf[] ); -\end{cfa} -\caption{String Stream Functions} -\label{f:StringStreamFunctions} -\end{figure} - \begin{comment} Index: libcfa/src/fstream.cfa =================================================================== --- libcfa/src/fstream.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/fstream.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Sep 21 21:51:38 2021 -// Update Count : 460 +// Last Modified On : Sun Oct 10 11:23:05 2021 +// Update Count : 512 // @@ -28,5 +28,6 @@ #define IO_MSG "I/O error: " -void ?{}( ofstream & os, void * file ) with(os) { +// private +void ?{}( ofstream & os, void * file ) with( os ) { file$ = file; sepDefault$ = true; @@ -35,5 +36,4 @@ prt$ = false; sawNL$ = false; - acquired$ = false; sepSetCur$( os, sepGet( os ) ); sepSet( os, " " ); @@ -41,30 +41,23 @@ } // ?{} -// private -bool sepPrt$( ofstream & os ) { setNL$( os, false ); return os.sepOnOff$; } -void sepReset$( ofstream & os ) { os.sepOnOff$ = os.sepDefault$; } -void sepReset$( ofstream & os, bool reset ) { os.sepDefault$ = reset; os.sepOnOff$ = os.sepDefault$; } -const char * sepGetCur$( ofstream & os ) { return os.sepCur$; } -void sepSetCur$( ofstream & os, const char sepCur[] ) { os.sepCur$ = sepCur; } -bool getNL$( ofstream & os ) { return os.sawNL$; } -void setNL$( ofstream & os, bool state ) { os.sawNL$ = state; } -bool getANL$( ofstream & os ) { return os.nlOnOff$; } -bool getPrt$( ofstream & os ) { return os.prt$; } -void setPrt$( ofstream & os, bool state ) { os.prt$ = state; } +inline bool sepPrt$( ofstream & os ) { setNL$( os, false ); return os.sepOnOff$; } +inline void sepReset$( ofstream & os ) { os.sepOnOff$ = os.sepDefault$; } +inline void sepReset$( ofstream & os, bool reset ) { os.sepDefault$ = reset; os.sepOnOff$ = os.sepDefault$; } +inline const char * sepGetCur$( ofstream & os ) { return os.sepCur$; } +inline void sepSetCur$( ofstream & os, const char sepCur[] ) { os.sepCur$ = sepCur; } +inline bool getNL$( ofstream & os ) { return os.sawNL$; } +inline void setNL$( ofstream & os, bool state ) { os.sawNL$ = state; } +inline bool getANL$( ofstream & os ) { return os.nlOnOff$; } +inline bool getPrt$( ofstream & os ) { return os.prt$; } +inline void setPrt$( ofstream & os, bool state ) { os.prt$ = state; } + +inline void lock( ofstream & os ) with( os ) { lock( os.lock$ ); } +inline void unlock( ofstream & os ) { unlock( os.lock$ ); } // public void ?{}( ofstream & os ) { os.file$ = 0p; } - -void ?{}( ofstream & os, const char name[], const char mode[] ) { - open( os, name, mode ); -} // ?{} - -void ?{}( ofstream & os, const char name[] ) { - open( os, name, "w" ); -} // ?{} - -void ^?{}( ofstream & os ) { - close( os ); -} // ^?{} +void ?{}( ofstream & os, const char name[], const char mode[] ) { open( os, name, mode ); } +void ?{}( ofstream & os, const char name[] ) { open( os, name, "w" ); } +void ^?{}( ofstream & os ) { close( os ); } void sepOn( ofstream & os ) { os.sepOnOff$ = ! getNL$( os ); } @@ -107,21 +100,18 @@ if ( &os == &exit ) exit( EXIT_FAILURE ); if ( &os == &abort ) abort(); - if ( os.acquired$ ) { os.acquired$ = false; release( os ); } } // ends -bool fail( ofstream & os ) { - return os.file$ == 0 || ferror( (FILE *)(os.file$) ); -} // fail - -void clear( ofstream & os ) { - clearerr( (FILE *)(os.file$) ); -} // clear - -int flush( ofstream & os ) { - return fflush( (FILE *)(os.file$) ); -} // flush +bool fail( ofstream & os ) { return os.file$ == 0 || ferror( (FILE *)(os.file$) ); } +void clear( ofstream & os ) { clearerr( (FILE *)(os.file$) ); } +int flush( ofstream & os ) { return fflush( (FILE *)(os.file$) ); } void open( ofstream & os, const char name[], const char mode[] ) { - FILE * file = fopen( name, mode ); + FILE * file; + for ( cnt; 10 ) { + errno = 0; + file = fopen( name, mode ); + if ( file != 0p || errno != EINTR ) break; // timer interrupt ? + if ( cnt == 9 ) abort( "ofstream open EINTR spinning exceeded" ); + } // for if ( file == 0p ) { throw (Open_Failure){ os }; @@ -131,17 +121,22 @@ } // open -void open( ofstream & os, const char name[] ) { - open( os, name, "w" ); -} // open - -void close( ofstream & os ) with(os) { +void open( ofstream & os, const char name[] ) { open( os, name, "w" ); } + +void close( ofstream & os ) with( os ) { if ( (FILE *)(file$) == 0p ) return; if ( (FILE *)(file$) == (FILE *)stdout || (FILE *)(file$) == (FILE *)stderr ) return; - if ( fclose( (FILE *)(file$) ) == EOF ) { + int ret; + for ( cnt; 10 ) { + errno = 0; + ret = fclose( (FILE *)(file$) ); + if ( ret != EOF || errno != EINTR ) break; // timer interrupt ? + if ( cnt == 9 ) abort( "ofstream open EINTR spinning exceeded" ); + } // for + if ( ret == EOF ) { throw (Close_Failure){ os }; // abort | IO_MSG "close output" | nl | strerror( errno ); } // if - file$ = 0p; + file$ = 0p; // safety after close } // close @@ -162,5 +157,12 @@ va_list args; va_start( args, format ); - int len = vfprintf( (FILE *)(os.file$), format, args ); + + int len; + for ( cnt; 10 ) { + errno = 0; + len = vfprintf( (FILE *)(os.file$), format, args ); + if ( len != EOF || errno != EINTR ) break; // timer interrupt ? + if ( cnt == 9 ) abort( "ofstream fmt EINTR spinning exceeded" ); + } // for if ( len == EOF ) { if ( ferror( (FILE *)(os.file$) ) ) { @@ -175,4 +177,5 @@ } // fmt +<<<<<<< HEAD inline void acquire( ofstream & os ) with(os) { lock( lock$ ); // may increase recursive lock @@ -191,4 +194,6 @@ void ^?{}( osacquire & acq ) { release( acq.os ); } +======= +>>>>>>> 15885de998d9500373efda8e609b893c87e6363a static ofstream soutFile = { (FILE *)stdout }; ofstream & sout = soutFile, & stdout = soutFile; @@ -208,9 +213,4 @@ flush( os ); return os; - // (ofstream &)(os | '\n'); - // setPrt$( os, false ); // turn off - // setNL$( os, true ); - // flush( os ); - // return sepOff( os ); // prepare for next line } // nl @@ -220,47 +220,38 @@ // private -void ?{}( ifstream & is, void * file ) with(is) { +void ?{}( ifstream & is, void * file ) with( is ) { file$ = file; nlOnOff$ = false; - acquired$ = false; -} // ?{} +} // ?{} + +bool getANL$( ifstream & os ) { return os.nlOnOff$; } + +inline void lock( ifstream & os ) with( os ) { lock( os.lock$ ); } +inline void unlock( ifstream & os ) { unlock( os.lock$ ); } // public void ?{}( ifstream & is ) { is.file$ = 0p; } - -void ?{}( ifstream & is, const char name[], const char mode[] ) { - open( is, name, mode ); -} // ?{} - -void ?{}( ifstream & is, const char name[] ) { - open( is, name, "r" ); -} // ?{} - -void ^?{}( ifstream & is ) { - close( is ); -} // ^?{} +void ?{}( ifstream & is, const char name[], const char mode[] ) { open( is, name, mode ); } +void ?{}( ifstream & is, const char name[] ) { open( is, name, "r" ); } +void ^?{}( ifstream & is ) { close( is ); } + +bool fail( ifstream & is ) { return is.file$ == 0p || ferror( (FILE *)(is.file$) ); } +void clear( ifstream & is ) { clearerr( (FILE *)(is.file$) ); } void nlOn( ifstream & os ) { os.nlOnOff$ = true; } void nlOff( ifstream & os ) { os.nlOnOff$ = false; } -bool getANL( ifstream & os ) { return os.nlOnOff$; } - -bool fail( ifstream & is ) { - return is.file$ == 0p || ferror( (FILE *)(is.file$) ); -} // fail - -void clear( ifstream & is ) { - clearerr( (FILE *)(is.file$) ); -} // clear - -void ends( ifstream & is ) { - if ( is.acquired$ ) { is.acquired$ = false; release( is ); } -} // ends - -bool eof( ifstream & is ) { - return feof( (FILE *)(is.file$) ); -} // eof + +void ends( ifstream & is ) {} + +bool eof( ifstream & is ) { return feof( (FILE *)(is.file$) ) != 0; } void open( ifstream & is, const char name[], const char mode[] ) { - FILE * file = fopen( name, mode ); + FILE * file; + for ( cnt; 10 ) { + errno = 0; + file = fopen( name, mode ); + if ( file != 0p || errno != EINTR ) break; // timer interrupt ? + if ( cnt == 9 ) abort( "ifstream open EINTR spinning exceeded" ); + } // for if ( file == 0p ) { throw (Open_Failure){ is }; @@ -270,17 +261,22 @@ } // open -void open( ifstream & is, const char name[] ) { - open( is, name, "r" ); -} // open - -void close( ifstream & is ) with(is) { +void open( ifstream & is, const char name[] ) { open( is, name, "r" ); } + +void close( ifstream & is ) with( is ) { if ( (FILE *)(file$) == 0p ) return; if ( (FILE *)(file$) == (FILE *)stdin ) return; - if ( fclose( (FILE *)(file$) ) == EOF ) { + int ret; + for ( cnt; 10 ) { + errno = 0; + ret = fclose( (FILE *)(file$) ); + if ( ret != EOF || errno != EINTR ) break; // timer interrupt ? + if ( cnt == 9 ) abort( "ifstream close EINTR spinning exceeded" ); + } // for + if ( ret == EOF ) { throw (Close_Failure){ is }; // abort | IO_MSG "close input" | nl | strerror( errno ); } // if - file$ = 0p; + file$ = 0p; // safety after close } // close @@ -311,7 +307,12 @@ int fmt( ifstream & is, const char format[], ... ) { va_list args; - va_start( args, format ); - int len = vfscanf( (FILE *)(is.file$), format, args ); + + int len; + for () { // no check for EINTR limit waiting for keyboard input + errno = 0; + len = vfscanf( (FILE *)(is.file$), format, args ); + if ( len != EOF || errno != EINTR ) break; // timer interrupt ? + } // for if ( len == EOF ) { if ( ferror( (FILE *)(is.file$) ) ) { @@ -322,17 +323,4 @@ return len; } // fmt - -inline void acquire( ifstream & is ) with(is) { - lock( lock$ ); // may increase recursive lock - if ( ! acquired$ ) acquired$ = true; // not locked ? - else unlock( lock$ ); // unwind recursive lock at start -} // acquire - -inline void release( ifstream & is ) { - unlock( is.lock$ ); -} // release - -void ?{}( isacquire & acq, ifstream & is ) { lock( is.lock$ ); &acq.is = &is; } -void ^?{}( isacquire & acq ) { release( acq.is ); } static ifstream sinFile = { (FILE *)stdin }; Index: libcfa/src/fstream.hfa =================================================================== --- libcfa/src/fstream.hfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/fstream.hfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Jul 28 07:35:50 2021 -// Update Count : 234 +// Last Modified On : Sun Oct 10 09:37:32 2021 +// Update Count : 243 // @@ -36,5 +36,4 @@ char tupleSeparator$[ofstream_sepSize]; multiple_acquisition_lock lock$; - bool acquired$; }; // ofstream @@ -52,4 +51,7 @@ bool getPrt$( ofstream & ); void setPrt$( ofstream &, bool ); + +void lock( ofstream & ); +void unlock( ofstream & ); // public @@ -75,17 +77,6 @@ void open( ofstream &, const char name[] ); void close( ofstream & ); + ofstream & write( ofstream &, const char data[], size_t size ); - -void acquire( ofstream & ); -void release( ofstream & ); - -void lock( ofstream & ); -void unlock( ofstream & ); - -struct osacquire { - ofstream & os; -}; -void ?{}( osacquire & acq, ofstream & ); -void ^?{}( osacquire & acq ); void ?{}( ofstream & ); @@ -110,13 +101,17 @@ bool nlOnOff$; multiple_acquisition_lock lock$; - bool acquired$; }; // ifstream // Satisfies istream +// private +bool getANL$( ifstream & ); + +void lock( ifstream & ); +void unlock( ifstream & ); + // public void nlOn( ifstream & ); void nlOff( ifstream & ); -bool getANL( ifstream & ); void ends( ifstream & ); int fmt( ifstream &, const char format[], ... ) __attribute__(( format(scanf, 2, 3) )); @@ -128,15 +123,7 @@ void open( ifstream & is, const char name[] ); void close( ifstream & is ); + ifstream & read( ifstream & is, char data[], size_t size ); ifstream & ungetc( ifstream & is, char c ); - -void acquire( ifstream & is ); -void release( ifstream & is ); - -struct isacquire { - ifstream & is; -}; -void ?{}( isacquire & acq, ifstream & is ); -void ^?{}( isacquire & acq ); void ?{}( ifstream & is ); Index: libcfa/src/iostream.cfa =================================================================== --- libcfa/src/iostream.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/iostream.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat May 15 09:39:21 2021 -// Update Count : 1342 +// Last Modified On : Sun Oct 10 09:28:17 2021 +// Update Count : 1345 // @@ -398,11 +398,4 @@ return os; } // nlOff -} // distribution - -forall( ostype & | ostream( ostype ) ) { - ostype & acquire( ostype & os ) { - acquire( os ); // call void returning - return os; - } // acquire } // distribution @@ -829,5 +822,5 @@ fmt( is, "%c", &temp ); // must pass pointer through varg to fmt // do not overwrite parameter with newline unless appropriate - if ( temp != '\n' || getANL( is ) ) { c = temp; break; } + if ( temp != '\n' || getANL$( is ) ) { c = temp; break; } if ( eof( is ) ) break; } // for @@ -1035,11 +1028,4 @@ return is; } // nlOff -} // distribution - -forall( istype & | istream( istype ) ) { - istype & acquire( istype & is ) { - acquire( is ); // call void returning - return is; - } // acquire } // distribution Index: libcfa/src/iostream.hfa =================================================================== --- libcfa/src/iostream.hfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/iostream.hfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Apr 28 20:37:56 2021 -// Update Count : 401 +// Last Modified On : Sun Oct 10 10:02:07 2021 +// Update Count : 407 // @@ -58,5 +58,4 @@ void close( ostype & ); ostype & write( ostype &, const char [], size_t ); - void acquire( ostype & ); // concurrent access }; // ostream @@ -142,8 +141,4 @@ ostype & nlOn( ostype & ); ostype & nlOff( ostype & ); -} // distribution - -forall( ostype & | ostream( ostype ) ) { - ostype & acquire( ostype & ); } // distribution @@ -296,8 +291,9 @@ trait basic_istream( istype & ) { - bool getANL( istype & ); // get scan newline (on/off) + // private + bool getANL$( istype & ); // get scan newline (on/off) + // public void nlOn( istype & ); // read newline void nlOff( istype & ); // scan newline - void ends( istype & os ); // end of output statement int fmt( istype &, const char format[], ... ) __attribute__(( format(scanf, 2, 3) )); @@ -312,5 +308,4 @@ void close( istype & is ); istype & read( istype &, char [], size_t ); - void acquire( istype & ); // concurrent access }; // istream @@ -379,8 +374,4 @@ } // distribution -forall( istype & | istream( istype ) ) { - istype & acquire( istype & ); -} // distribution - // *********************************** manipulators *********************************** Index: libcfa/src/strstream.cfa =================================================================== --- libcfa/src/strstream.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/strstream.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,9 +10,10 @@ // Created On : Thu Apr 22 22:24:35 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 27 20:59:53 2021 -// Update Count : 78 +// Last Modified On : Sun Oct 10 16:13:20 2021 +// Update Count : 101 // #include "strstream.hfa" +#include "fstream.hfa" // abort #include // vsnprintf @@ -30,14 +31,14 @@ // private -bool sepPrt$( ostrstream & os ) { setNL$( os, false ); return os.sepOnOff$; } -void sepReset$( ostrstream & os ) { os.sepOnOff$ = os.sepDefault$; } -void sepReset$( ostrstream & os, bool reset ) { os.sepDefault$ = reset; os.sepOnOff$ = os.sepDefault$; } -const char * sepGetCur$( ostrstream & os ) { return os.sepCur$; } -void sepSetCur$( ostrstream & os, const char sepCur[] ) { os.sepCur$ = sepCur; } -bool getNL$( ostrstream & os ) { return os.sawNL$; } -void setNL$( ostrstream & os, bool state ) { os.sawNL$ = state; } -bool getANL$( ostrstream & os ) { return os.nlOnOff$; } -bool getPrt$( ostrstream & os ) { return os.prt$; } -void setPrt$( ostrstream & os, bool state ) { os.prt$ = state; } +inline bool sepPrt$( ostrstream & os ) { setNL$( os, false ); return os.sepOnOff$; } +inline void sepReset$( ostrstream & os ) { os.sepOnOff$ = os.sepDefault$; } +inline void sepReset$( ostrstream & os, bool reset ) { os.sepDefault$ = reset; os.sepOnOff$ = os.sepDefault$; } +inline const char * sepGetCur$( ostrstream & os ) { return os.sepCur$; } +inline void sepSetCur$( ostrstream & os, const char sepCur[] ) { os.sepCur$ = sepCur; } +inline bool getNL$( ostrstream & os ) { return os.sawNL$; } +inline void setNL$( ostrstream & os, bool state ) { os.sawNL$ = state; } +inline bool getANL$( ostrstream & os ) { return os.nlOnOff$; } +inline bool getPrt$( ostrstream & os ) { return os.prt$; } +inline void setPrt$( ostrstream & os, bool state ) { os.prt$ = state; } // public @@ -128,4 +129,6 @@ // *********************************** istrstream *********************************** +// private +bool getANL$( istrstream & is ) { return is.nlOnOff$; } // public @@ -136,14 +139,27 @@ } // ?{} -bool getANL( istrstream & is ) { return is.nlOnOff$; } void nlOn( istrstream & is ) { is.nlOnOff$ = true; } void nlOff( istrstream & is ) { is.nlOnOff$ = false; } -void ends( istrstream & is ) { -} // ends +void ends( istrstream & is ) {} +bool eof( istrstream & is ) { return false; } -int eof( istrstream & is ) { - return 0; -} // eof +int fmt( istrstream & is, const char format[], ... ) with(is) { + va_list args; + va_start( args, format ); + // THIS DOES NOT WORK BECAUSE VSSCANF RETURNS NUMBER OF VALUES READ VERSUS BUFFER POSITION SCANNED. + int len = vsscanf( buf$ + cursor$, format, args ); + va_end( args ); + if ( len == EOF ) { + abort | IO_MSG "invalid read"; + } // if + // SKULLDUGGERY: This hack skips over characters read by vsscanf by moving to the next whitespace but it does not + // handle C reads with wdi manipulators that leave the cursor at a non-whitespace character. + for ( ; buf$[cursor$] != ' ' && buf$[cursor$] != '\t' && buf$[cursor$] != '\0'; cursor$ += 1 ) { + //printf( "X \'%c\'\n", buf$[cursor$] ); + } // for + if ( buf$[cursor$] != '\0' ) cursor$ += 1; // advance to whitespace + return len; +} // fmt istrstream &ungetc( istrstream & is, char c ) { @@ -154,18 +170,4 @@ } // ungetc -int fmt( istrstream & is, const char format[], ... ) { - va_list args; - va_start( args, format ); - // This does not work because vsscanf does not return buffer position. - int len = vsscanf( is.buf$ + is.cursor$, format, args ); - va_end( args ); - if ( len == EOF ) { - int j; - printf( "X %d%n\n", len, &j ); - } // if - is.cursor$ += len; - return len; -} // fmt - // Local Variables: // // tab-width: 4 // Index: libcfa/src/strstream.hfa =================================================================== --- libcfa/src/strstream.hfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ libcfa/src/strstream.hfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Thu Apr 22 22:20:59 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 27 20:58:50 2021 -// Update Count : 41 +// Last Modified On : Sun Oct 10 10:14:22 2021 +// Update Count : 47 // @@ -85,14 +85,17 @@ // Satisfies basic_istream +// private +bool getANL$( istrstream & ); + // public -bool getANL( istrstream & ); void nlOn( istrstream & ); void nlOff( istrstream & ); void ends( istrstream & ); + int fmt( istrstream &, const char format[], ... ) __attribute__(( format(scanf, 2, 3) )); -istrstream & ungetc( istrstream & is, char c ); -int eof( istrstream & is ); +istrstream & ungetc( istrstream &, char ); +bool eof( istrstream & ); -void ?{}( istrstream & is, char buf[] ); +void ?{}( istrstream &, char buf[] ); // Local Variables: // Index: src/AST/Pass.hpp =================================================================== --- src/AST/Pass.hpp (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/AST/Pass.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -348,9 +348,11 @@ /// When this node is finished being visited, restore the value of a variable + /// You may assign to the return value to set the new value in the same statement. template< typename T > - void GuardValue( T& val ) { + T& GuardValue( T& val ) { at_cleanup( [ val ]( void * newVal ) { * static_cast< T * >( newVal ) = val; }, static_cast< void * >( & val ) ); + return val; } @@ -394,4 +396,14 @@ }; +/// Used to get a pointer to the wrapping TranslationUnit. +struct WithConstTranslationUnit { + const TranslationUnit * translationUnit = nullptr; + + const TranslationUnit & transUnit() const { + assertf( translationUnit, "WithConstTranslationUnit not set-up." ); + return *translationUnit; + } +}; + } Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/AST/Pass.impl.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -420,5 +420,11 @@ template< typename core_t > inline void ast::accept_all( ast::TranslationUnit & unit, ast::Pass< core_t > & visitor ) { - return ast::accept_all( unit.decls, visitor ); + if ( auto ptr = __pass::translation_unit::get_cptr( visitor.core, 0 ) ) { + ValueGuard guard( *ptr ); + *ptr = &unit; + return ast::accept_all( unit.decls, visitor ); + } else { + return ast::accept_all( unit.decls, visitor ); + } } Index: src/AST/Pass.proto.hpp =================================================================== --- src/AST/Pass.proto.hpp (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/AST/Pass.proto.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -426,4 +426,18 @@ } // namespace forall + // For passes that need access to the global context. Sreaches `translationUnit` + namespace translation_unit { + template + static inline auto get_cptr( core_t & core, int ) + -> decltype( &core.translationUnit ) { + return &core.translationUnit; + } + + template + static inline const TranslationUnit ** get_cptr( core_t &, long ) { + return nullptr; + } + } + template static inline auto get_result( core_t & core, char ) -> decltype( core.result() ) { Index: src/AST/TranslationUnit.hpp =================================================================== --- src/AST/TranslationUnit.hpp (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/AST/TranslationUnit.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -26,8 +26,8 @@ std::list< ptr< Decl > > decls; - struct Globals { + struct Global { std::map< UniqueId, Decl * > idMap; - const Type * sizeType; + ptr sizeType; const FunctionDecl * dereference; const StructDecl * dtorStruct; Index: src/AST/porting.md =================================================================== --- src/AST/porting.md (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/AST/porting.md (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -98,4 +98,5 @@ * `Initializer` => `ast::Init` * `Statement` => `ast::Stmt` + * `ReferenceToType` => `ast::BaseInstType` * any field names should follow a similar renaming * because they don't really belong to `Type` (and for consistency with `Linkage::Spec`): Index: src/CodeTools/DeclStats.cc =================================================================== --- src/CodeTools/DeclStats.cc (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/CodeTools/DeclStats.cc (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -156,6 +156,17 @@ /// number of counting bins for linkages static const unsigned n_named_specs = 8; - /// map from total number of specs to bins - static const unsigned ind_for_linkage[16]; + /// Mapping function from linkage to bin. + static unsigned linkage_index( LinkageSpec::Spec spec ) { + switch ( spec ) { + case LinkageSpec::Intrinsic: return 0; + case LinkageSpec::C: return 1; + case LinkageSpec::Cforall: return 2; + case LinkageSpec::AutoGen: return 3; + case LinkageSpec::Compiler: return 4; + case LinkageSpec::BuiltinCFA: return 5; + case LinkageSpec::BuiltinC: return 6; + default: return 7; + } + } Stats for_linkage[n_named_specs]; ///< Stores separate stats per linkage @@ -366,5 +377,5 @@ const std::string& mangleName = decl->get_mangleName().empty() ? decl->name : decl->get_mangleName(); if ( seen_names.insert( mangleName ).second ) { - Stats& stats = for_linkage[ ind_for_linkage[ decl->linkage ] ]; + Stats& stats = for_linkage[ linkage_index( decl->linkage ) ]; ++stats.n_decls; @@ -527,7 +538,4 @@ }; - const unsigned DeclStats::ind_for_linkage[] - = { 7, 7, 2, 1, 7, 7, 7, 3, 4, 7, 6, 5, 7, 7, 7, 0 }; - void printDeclStats( std::list< Declaration * > &translationUnit ) { PassVisitor stats; Index: src/Common/DeclStats.cpp =================================================================== --- src/Common/DeclStats.cpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) +++ src/Common/DeclStats.cpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -0,0 +1,575 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// DeclStats.cpp -- Print statistics about a translation unit's declarations. +// +// Author : Andrew Beach +// Created On : Fri Oct 1 14:26:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Wed Oct 8 11:24:00 2021 +// Update Count : 0 +// + +#include "DeclStats.hpp" + +#include "AST/LinkageSpec.hpp" +#include "AST/Pass.hpp" +#include "AST/Print.hpp" +#include "Common/VectorMap.h" + +#include +#include +#include +#include + +// Everything but printDeclStats at the bottom is hidden. +namespace { + +template +void sum( T & l, const T & r ) { l += r; } + +void sum( VectorMap & l, const VectorMap & r ) { + l.reserve( r.size() ); + for ( unsigned i = 0 ; i < r.size() ; ++i ) { + l[i] += r[i]; + } +} + +template +void sum( std::map & l, const std::map & r ) { + for ( const auto & entry : r ) { + l[ entry.first ] += entry.second; + } +} + +template +void sum( std::unordered_map & l, + const std::unordered_map & r ) { + for ( const auto & entry : r ) { + l[ entry.first ] += entry.second; + } +} + +/// Stores statistics on a single group of arguments or return values. +struct ArgPackStats { + /// Count of decls with each number of elements. + VectorMap n; + /// Count of decls with each number of basic type elements. + VectorMap n_basic; + /// Count of decls with each number of generic type elements. + VectorMap n_generic; + /// Count of decls with each number of polymorphic elements. + VectorMap n_poly; + /// Count of decls with each number of non-generic compound types. + VectorMap n_compound; + /// Count of decls with each percentage of basic type elements. + std::map p_basic; + /// Count of decls with each percentage of generic type elements. + std::map p_generic; + /// Count of decls with each percentage of polymorphic elements. + std::map p_poly; + /// Count of decls with each percentage of non-generic compound type elements. + std::map p_compound; + /// Count of decls with each number of distinct types in the pack. + VectorMap n_types; + /// Count of decls with each percentage of new types in lists. + /// Types used in the parameter list that recur in the return list are not considered to be new. + std::map p_new; + + ArgPackStats& operator+=( const ArgPackStats& other ) { + sum(n, other.n); + sum(n_basic, other.n_basic); + sum(n_generic, other.n_generic); + sum(n_poly, other.n_poly); + sum(n_compound, other.n_compound); + sum(p_basic, other.p_basic); + sum(p_generic, other.p_generic); + sum(p_poly, other.p_poly); + sum(p_compound, other.p_compound); + sum(n_types, other.n_types); + sum(p_new, other.p_new); + + return *this; + } +}; + +/// Collected statistics on a group of declarations. +struct Stats { + /// Total number of declarations in these statistics. + unsigned n_decls; + /// Count of declarations with each number of assertion parameters. + VectorMap n_type_params; + /// Count of generic types with each number of type parameters. + VectorMap n_generic_params; + /// Count of maximum nesting depth of types. + VectorMap n_generic_nesting; + /// Count of declarations with each name. + std::unordered_map by_name; + /// Count of uses of each basic type. + std::unordered_map basic_type_names; + /// Count of uses of each generic type name (includes "*", "[]", "(*)", "[,]"). + std::unordered_map generic_type_names; + /// Count of uses of each non-generic aggregate type. + std::unordered_map compound_type_names; + /// Count of decls using each basic type. + std::unordered_map basic_type_decls; + /// Count of decls using each generic type (includes "*", "[]", "(*)", "[,]"). + std::unordered_map generic_type_decls; + /// Count of decls using each compound type. + std::unordered_map compound_type_decls; + /// Stats for the parameter lists. + ArgPackStats params; + /// Stats for the return lists. + ArgPackStats returns; + + /// Count of declarations with each number of assertions. + std::map n_assns; + /// Stats for the assertions' parameters. + ArgPackStats assn_params; + /// Stats for the assertions' return types. + ArgPackStats assn_returns; + + Stats& operator+=( const Stats& other ) { + sum( n_decls, other.n_decls ); + sum( n_type_params, other.n_type_params ); + sum( n_generic_params, other.n_generic_params ); + sum( n_generic_nesting, other.n_generic_nesting ); + sum( by_name, other.by_name ); + sum( basic_type_names, other.basic_type_names ); + sum( generic_type_names, other.generic_type_names ); + sum( compound_type_names, other.compound_type_names ); + sum( basic_type_decls, other.basic_type_decls ); + sum( generic_type_decls, other.generic_type_decls ); + sum( compound_type_decls, other.compound_type_decls ); + sum( params, other.params ); + sum( returns, other.returns ); + sum( n_assns, other.n_assns ); + sum( assn_params, other.assn_params ); + sum( assn_returns, other.assn_returns ); + + return *this; + } + +}; + +void update_max( unsigned & max, unsigned value ) { + if ( max < value ) max = value; +} + +// Where all unnamed specs are counted as one named spec group. +constexpr unsigned num_named_specs = 8; + +unsigned linkage_index( ast::Linkage::Spec spec ) { + switch ( spec.val ) { + case ast::Linkage::Intrinsic.val: return 0; + case ast::Linkage::C.val: return 1; + case ast::Linkage::Cforall.val: return 2; + case ast::Linkage::AutoGen.val: return 3; + case ast::Linkage::Compiler.val: return 4; + case ast::Linkage::BuiltinCFA.val: return 5; + case ast::Linkage::BuiltinC.val: return 6; + default: return 7; + } +} + +struct DeclStats : public ast::WithShortCircuiting { + /// Stores separate stats per linkage. + Stats by_linkage[num_named_specs]; + /// Stores manglenames already seen to avoid double-counting. + std::unordered_set seen_names; + /// Overall stats. + Stats total; + /// Count of expressions with (depth, fanout) + std::map, unsigned> exprs_by_fanout_at_depth; + + /// Count that we have seen a named type. + void countType( + const std::string & name, unsigned & n, + std::unordered_map & names, + std::unordered_map & decls, + std::unordered_set & elSeen ) { + ++n; + ++names[ name ]; + if ( elSeen.insert( name ).second ) { + ++decls[ name ]; + } + } + + /// Perform type analysis on a subtype. + void analyzeSubtype( const ast::Type * type, Stats & stats, + std::unordered_set & elSeen, unsigned & n_poly, + bool & seen_poly, unsigned & max_depth, unsigned depth ) { + // This kind of gets in the way of grouping arguments. + unsigned ignored = 0; + analyzeType( + type, stats, elSeen, ignored, ignored, n_poly, ignored, + seen_poly, max_depth, depth + 1 ); + } + + /// Perform type analysis on each subtype. + void analyzeSubtypes( + const std::vector> & types, Stats & stats, + std::unordered_set & elSeen, unsigned & n_poly, + bool & seen_poly, unsigned & max_depth, unsigned depth ) { + for ( const auto & type : types ) { + analyzeSubtype( type, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + } + } + + /// Perform sub-type analysis on each subtype in an argument pack. + void analyzeSubPack( + const std::vector> & types, Stats & stats, + std::unordered_set & elSeen, unsigned & n_poly, + bool & seen_poly, unsigned & max_depth, unsigned depth, + unsigned & n_subs ) { + // ... and count voids? + for ( const auto & type : types ) { + if ( type.as() ) { + ++n_subs; + } + // Could this be in `else`? + analyzeSubtype( type, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + } + } + + /// Analyze and gather stats from a single type. + void analyzeType( const ast::ptr & type, Stats & stats, + std::unordered_set & elSeen, + unsigned & n_basic, unsigned & n_generic, unsigned & n_poly, + unsigned & n_agg, bool & seen_poly, + unsigned & max_depth, unsigned depth ) { + // Almost a visit, except it is only types. + if ( const ast::BasicType * t = type.as() ) { + const std::string name = ast::BasicType::typeNames[ t->kind ]; + countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen ); + update_max( max_depth, depth ); + } else if ( auto t = type.as() ) { + static const std::string name = "*"; + countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen ); + analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + ++stats.n_generic_params.at( 1 ); + } else if ( auto t = type.as() ) { + static const std::string name = "[]"; + countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen ); + analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + ++stats.n_generic_params.at( 1 ); + } else if ( auto t = type.as() ) { + static const std::string name = "&"; + countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen ); + analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + ++stats.n_generic_params.at( 1 ); + } else if ( auto t = type.as() ) { + static const std::string name = "(*)"; + countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen ); + unsigned n_subs = 0; + analyzeSubPack( t->returns, stats, elSeen, n_poly, seen_poly, max_depth, depth, n_subs ); + analyzeSubPack( t->params, stats, elSeen, n_poly, seen_poly, max_depth, depth, n_subs ); + ++stats.n_generic_params.at( n_subs ); + } else if ( auto t = type.as() ) { + if ( !seen_poly ) { + ++n_poly; + seen_poly = true; + } + countType( t->name, n_agg, stats.compound_type_names, + stats.compound_type_decls, elSeen ); + update_max( max_depth, depth ); + } else if ( auto t = type.as() ) { + auto & params = t->params; + if ( params.empty() ) { + countType( t->name, n_agg, stats.compound_type_names, + stats.compound_type_decls, elSeen ); + update_max( max_depth, depth ); + } else { + countType( t->name, n_generic, stats.generic_type_names, + stats.generic_type_decls, elSeen ); + ++stats.n_generic_params.at( params.size() ); + } + } else if ( auto t = type.as() ) { + static const std::string name = "[,]"; + countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen); + analyzeSubtypes( t->types, stats, elSeen, n_poly, seen_poly, max_depth, depth ); + ++stats.n_generic_params.at( t->size() ); + } else if ( type.as() ) { + static const std::string name = "..."; + countType( name, n_agg, stats.compound_type_names, stats.compound_type_decls, elSeen ); + update_max( max_depth, depth ); + } else if ( type.as() ) { + static const std::string name = "0"; + countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen ); + update_max( max_depth, depth ); + } else if ( type.as() ) { + static const std::string name = "1"; + countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen ); + update_max( max_depth, depth ); + } + } + + /// Update an ArgPackStats based on the list of types it repersents. + void analyzeArgPack( + const std::vector> & types, + Stats & stats, + ArgPackStats & packStats, + // What are these two used for? + std::unordered_set & seen, + std::unordered_set & elSeen ) { + std::unordered_set type_names; + unsigned n = 0; + unsigned n_basic = 0; + unsigned n_generic = 0; + unsigned n_poly = 0; + unsigned n_compound = 0; + unsigned n_new = 0; + + for ( auto & type : types ) { + n += type->size(); + + std::stringstream ss; + ast::print( ss, type ); + type_names.insert( ss.str() ); + if ( seen.insert( ss.str() ).second ) { + ++n_new; + } + + bool seen_poly = false; + unsigned max_depth = 0; + analyzeType( + type, stats, elSeen, n_basic, n_generic, n_poly, n_compound, + seen_poly, max_depth, 0 + ); + ++stats.n_generic_nesting.at( max_depth ); + } + + ++packStats.n.at( n ); + ++packStats.n_basic.at( n_basic ); + ++packStats.n_generic.at( n_generic ); + ++packStats.n_poly.at( n_poly ); + ++packStats.n_compound.at( n_compound ); + if ( n > 0 ) { + ++packStats.p_basic[ n_basic * 100 / n ]; + ++packStats.p_generic[ n_generic * 100 / n ]; + ++packStats.p_poly[ n_poly * 100 / n ]; + ++packStats.p_compound[ n_compound * 100 / n ]; + if ( n > 1 ) { + ++packStats.p_new[ (n_new - 1) * 100 / (n - 1) ]; + } + } + ++packStats.n_types.at( types.size() ); + } + + /// Perform type analysis on a function type, storing information in the + /// given ArgPackStats. + void analyzeFunctionType( const ast::FunctionType * type, Stats& stats, + ArgPackStats Stats::* param_pack, + ArgPackStats Stats::* return_pack ) { + // I still don't know what these are for. + std::unordered_set seen; + std::unordered_set elSeen; + analyzeArgPack( type->params, stats, stats.*param_pack, seen, elSeen ); + analyzeArgPack( type->returns, stats, stats.*return_pack, seen, elSeen ); + } + + /// If the assertion is a function, return the function type. + static const ast::FunctionType * getAssertionFunctionType( + const ast::ptr & assertion ) { + if ( auto * assertionObject = assertion.as() ) { + if ( auto * ptrTy = assertionObject->type.as() ) { + return ptrTy->base.as(); + } else { + return assertionObject->type.as(); + } + } else if ( auto * assertionDecl = assertion.as() ) { + return assertionDecl->type; + } + return nullptr; + } + + void analyzeFunctionDecl( const ast::FunctionDecl * decl ) { + Stats & stats = by_linkage[ linkage_index( decl->linkage ) ]; + + ++stats.n_decls; + const ast::FunctionType * type = decl->type.get(); + const ast::FunctionType::ForallList & forall = type->forall; + ++stats.n_type_params.at( forall.size() ); + unsigned num_assertions = 0; + for ( const ast::ptr & instType : forall ) { + num_assertions += instType->base->assertions.size(); + for ( const auto & assertion : instType->base->assertions ) { + if ( auto assertionType = getAssertionFunctionType( assertion ) ) { + analyzeFunctionType( assertionType, stats, + &Stats::assn_params, &Stats::assn_returns ); + } + } + } + ++stats.n_assns[ num_assertions ]; + ++stats.by_name[ decl->name ]; + analyzeFunctionType( type, stats, &Stats::params, &Stats::returns ); + } + + void analyzeUntypedExpr( const ast::UntypedExpr * expr, unsigned depth ) { + unsigned fanout = expr->args.size(); + ++exprs_by_fanout_at_depth[ std::make_pair( depth, fanout ) ]; + + for ( const ast::ptr & arg : expr->args ) { + if ( const auto * untyped = arg.as() ) { + analyzeUntypedExpr( untyped, depth + 1 ); + } + } + } + +public: + void previsit( const ast::UntypedExpr * expr ) { + visit_children = false; + analyzeUntypedExpr( expr, 0 ); + } + + void previsit( const ast::FunctionDecl * decl ) { + const std::string & mangleName = decl->mangleName; + const std::string & indexName = mangleName.empty() ? decl->name : mangleName; + if ( seen_names.insert( indexName ).second ) { + analyzeFunctionDecl( decl ); + } + } + +private: + + // Trying to avoid duplication by templates. + // I couldn't do it in all cases. + template + using getter = std::function; + + /// Print a single role, for every linkage and the totals. + void printRow( const std::string & name, getter extract ) { + std::cout << "\"" << name << "\","; + for ( const Stats & stats : by_linkage ) { + std::cout << "," << extract( stats ); + } + std::cout << "," << extract( total ) << std::endl; + } + + /// Print every row in a group of maps. + template + void printAllMap( const std::string & name, Func && extract ) { + // Get all rows from the total stats. + for ( auto & entry : extract( total ) ) { + auto & key = entry.first; + std::cout << "\"" << name << "\"," << key; + for ( const auto & stats : by_linkage ) { + const auto & map = extract( stats ); + auto it = map.find( key ); + if ( map.end() == it ) { + std::cout << ",0"; + } else { + std::cout << "," << it->second; + } + } + std::cout << "," << entry.second << std::endl; + } + } + + /// Accumalate information, then print every row in the remaining maps. + template + void printAllSparseHisto( const std::string & name, Func && extract ) { + std::map histos[num_named_specs]; + std::map histo_total; + + // Collect all data into the histograms. + for ( const auto & entry : extract( total ) ) { + ++histo_total[ entry.second ]; + } + + for ( unsigned i = 0 ; i < num_named_specs ; ++i ) { + for ( const auto & entry : extract( by_linkage[i] ) ) { + ++histos[ i ][ entry.second ]; + } + } + + // Get all rows from the total stats. + for ( const auto & entry : histo_total ) { + const unsigned & key = entry.first; + std::cout << "\"" << name << "\"," << key; + for ( unsigned i = 0 ; i < num_named_specs ; ++i ) { + auto it = histos[i].find( key ); + if ( histos[i].end() == it ) { + std::cout << ",0"; + } else { + std::cout << "," << it->second; + } + } + std::cout << "," << entry.second << std::endl; + } + } + + void printAllPack( const std::string & name, ArgPackStats Stats::* field ) { + printAllMap("n_basic_" + name, [&field](const Stats& stats) { return (stats.*field).n_basic; }); + printAllMap("n_generic_" + name, [&field](const Stats& stats) { return (stats.*field).n_generic; }); + printAllMap("n_poly_" + name, [&field](const Stats& stats) { return (stats.*field).n_poly; }); + printAllMap("n_compound_" + name, [&field](const Stats& stats) { return (stats.*field).n_compound; }); + printAllMap("n_" + name, [&field](const Stats& stats) { return (stats.*field).n; }); + printAllMap("%_basic_" + name, [&field](const Stats& stats) { return (stats.*field).p_basic; }); + printAllMap("%_generic_" + name, [&field](const Stats& stats) { return (stats.*field).p_generic; }); + printAllMap("%_poly_" + name, [&field](const Stats& stats) { return (stats.*field).p_poly; }); + printAllMap("%_compound_" + name, [&field](const Stats& stats) { return (stats.*field).p_compound; }); + printAllMap("n_distinct_types_" + name, [&field](const Stats& stats) { return (stats.*field).n_types; }); + printAllMap("%_new_types_in_" + name, [&field](const Stats& stats) { return (stats.*field).p_new; }); + } + + static void printPairMap ( + const std::string & name, + const std::map, unsigned> & map ) { + for ( const auto & entry : map ) { + const auto & key = entry.first; + std::cout << "\"" << name << "\"," << key.first << ',' + << key.second << ',' << entry.second << std::endl; + } + } + +public: + void print() { + for ( auto & stats : by_linkage ) { + total += stats; + } + + std::cout << ",,\"intrinsic\",\"Cforall\",\"C\",\"autogen\",\"compiler\",\"builtinCFA\",\"builtinC\",\"other\",\"TOTAL\"" << std::endl; + + printAllMap("n_type_params", [](const Stats& stats) { return stats.n_type_params; }); + printAllMap("n_generic_params", [](const Stats& stats) { return stats.n_generic_params; }); + printAllMap("n_generic_nesting", [](const Stats& stats) { return stats.n_generic_nesting; }); + printRow("n_decls", [](const Stats& stats) { return stats.n_decls; }); + printRow("unique_names", [](const Stats& stats) { return stats.by_name.size(); }); + printAllSparseHisto("overloads", [](const Stats& stats) { return stats.by_name; }); + printRow("basic_type_names", [](const Stats& stats) { return stats.basic_type_names.size(); }); + printAllSparseHisto("basic_type_uses", [](const Stats& stats) { return stats.basic_type_names; }); + printAllSparseHisto("decls_using_basic_type", [](const Stats& stats) { return stats.basic_type_decls; }); + printRow("generic_type_names", [](const Stats& stats) { return stats.generic_type_names.size(); }); + printAllSparseHisto("generic_type_uses", [](const Stats& stats) { return stats.generic_type_names; }); + printAllSparseHisto("decls_using_generic_type", [](const Stats& stats) { return stats.generic_type_decls; }); + printRow("compound_type_names", [](const Stats& stats) { return stats.compound_type_names.size(); }); + printAllSparseHisto("compound_type_uses", [](const Stats& stats) { return stats.compound_type_names; }); + printAllSparseHisto("decls_using_compound_type", [](const Stats& stats) { return stats.compound_type_decls; }); + printAllPack("params", &Stats::params); + printAllPack("returns", &Stats::returns); + printAllMap("n_assns", [](const Stats& stats) { return stats.n_assns; }); + printAllPack("assn_params", &Stats::assn_params); + printAllPack("assn_returns", &Stats::assn_returns); + std::cout << std::endl; + + printPairMap( "exprs by depth+fanout", exprs_by_fanout_at_depth ); + } +}; + +} // namespace + +void printDeclStats( ast::TranslationUnit & translationUnit ) { + ast::Pass stats; + accept_all( translationUnit, stats ); + stats.core.print(); +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/DeclStats.hpp =================================================================== --- src/Common/DeclStats.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) +++ src/Common/DeclStats.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -0,0 +1,29 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// DeclStats.hpp -- Print statistics about a translation unit's declarations. +// +// Author : Andrew Beach +// Created On : Fri Oct 1 14:20:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Oct 1 14:28:00 2021 +// Update Count : 0 +// + +#pragma once + +namespace ast { + class TranslationUnit; +} + +/// Print statistics about a translation unit's declarations. +void printDeclStats( ast::TranslationUnit &translationUnit ); + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/ResolvProtoDump.cpp =================================================================== --- src/Common/ResolvProtoDump.cpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) +++ src/Common/ResolvProtoDump.cpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -0,0 +1,808 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ResolvProtoDump.cpp -- Prints AST as instances for resolv-proto. +// +// Author : Andrew Beach +// Created On : Wed Oct 6 14:10:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Tue Oct 18 11:23:00 2021 +// Update Count : 0 +// + +#include "ResolvProtoDump.hpp" + +#include +#include +#include +#include + +#include "AST/Copy.hpp" +#include "AST/Pass.hpp" +#include "AST/TranslationUnit.hpp" +#include "AST/Type.hpp" +#include "CodeGen/OperatorTable.h" +#include "Common/utility.h" + +namespace { + +/// Add a prefix to an existing name. +std::string add_prefix( const std::string & prefix, const char * added ) { + if ( prefix.empty() ) { + return std::string("$") + added; + } else { + return prefix + added; + } +} + +/// Shortens operator names. +std::string op_name( const std::string & name ) { + if ( name.compare( 0, 10, "_operator_" ) == 0 ) { + return name.substr( 10 ); + } else if ( name.compare( "_constructor" ) == 0 + || name.compare( "_destructor" ) == 0 ) { + return name.substr( 1 ); + } else if ( name.compare( 0, 11, "__operator_" ) == 0 ) { + return name.substr( 11 ); + } else { + return name; + } +} + +/// Get the resolv-proto names for operators. +std::string rp_name( const std::string & name, std::string && pre = "" ) { + // Check for anonymous names. + if ( name.empty() ) { + return add_prefix( pre, "anon" ); + } + + // Replace operator names. + const CodeGen::OperatorInfo * opInfo = CodeGen::operatorLookup( name ); + if ( nullptr != opInfo ) { + return add_prefix( pre, "" ) + op_name( opInfo->outputName ); + } + + // Replace return value prefix. + if ( name.compare( 0, 8, "_retval_" ) == 0 ) { + return add_prefix( pre, "rtn_" ) + op_name( name.substr( 8 ) ); + } + + // Default to just name, with first character in lowercase. + if ( std::isupper( name[0] ) ) { + std::string copy = name; + copy[0] = std::tolower( copy[0] ); + return pre + copy; + } + return pre + name; +} + +/// Normalise a type instance name. +std::string ti_name( const std::string & name ) { + // Replace built-in names + if ( name == "char16_t" || name == "char32_t" || name == "wchar_t" ) { + return std::string("#") + name; + } + + // Strip leadng underscores. + unsigned i = 0; + while ( i < name.size() && name[i] == '_' ) { ++i; } + if ( i == name.size() ) { + return "Anon"; + } + + std::string stripped = name.substr( i ); + // Strip trailing generic from autogen names () + static char generic[] = "_generic_"; + static size_t n_generic = sizeof(generic) - 1; + if ( stripped.size() >= n_generic + && stripped.substr( stripped.size() - n_generic ) == generic ) { + stripped.resize( stripped.size() - n_generic ); + } + + // Uppercase first character. + stripped[0] = std::toupper( stripped[0] ); + return stripped; +} + +std::vector> to_types( + const std::vector> & data ) { + std::vector> ret_val; + ret_val.reserve( data.size() ); + for ( auto entry : data ) { + if ( auto * typeExpr = entry.as() ) { + ret_val.emplace_back( typeExpr->type ); + } + } + return ret_val; +} + +enum class septype { separated, terminated, preceded }; + +template +void build( + V & visitor, + const std::vector> & types, + std::stringstream & ss, + septype mode ); + +template +void buildAsTuple( + V & visitor, const std::vector> & types, + std::stringstream & ss ); + +struct TypePrinter : public ast::WithShortCircuiting, ast::WithVisitorRef { + /// Accumulator for the printed type. + std::stringstream ss; + /// Closed type variables. + const std::unordered_set & closed; + /// Depth of nesting from root type. + unsigned depth; + + TypePrinter( const std::unordered_set & closed ) : + ss(), closed(closed), depth(0) + {} + + std::string result() const { + return ss.str(); + } + + // Basic type represented as an integer type. + // TODO: Maybe hard-code conversion graph and make named type. + void previsit( const ast::BasicType * type ) { + ss << (int)type->kind; + } + + // Pointers (except function pointers) are represented as generic type. + void previsit( const ast::PointerType * type ) { + if ( nullptr == type->base.as() ) { + ss << "#$ptr<"; + ++depth; + } + } + void postvisit( const ast::PointerType * type ) { + if ( nullptr == type->base.as() ) { + --depth; + ss << '>'; + } + } + + // Arrays repersented as pointers. + void previsit( const ast::ArrayType * type ) { + ss << "#$ptr<"; + ++depth; + type->base->accept( *visitor ); + --depth; + ss << '>'; + visit_children = false; + } + + // Ignore top-level references as they are mostly transparent to resolution. + void previsit( const ast::ReferenceType * ) { + if ( !atTopLevel() ) { ss << "#$ref<"; } + ++depth; + } + void postvisit( const ast::ReferenceType * ) { + --depth; + if ( !atTopLevel() ) { ss << '>'; } + } + + void previsit( const ast::FunctionType * type ) { + ss << '['; + ++depth; + build( *visitor, type->returns, ss, septype::preceded ); + ss << " : "; + build( *visitor, type->params, ss, septype::terminated ); + --depth; + ss << ']'; + visit_children = false; + } + +private: + bool atTopLevel() const { + return 0 == depth; + } + + void handleAggregate( const ast::BaseInstType * type ) { + ss << '#' << type->name; + if ( !type->params.empty() ) { + ss << '<'; + ++depth; + build( *visitor, to_types( type->params ), ss, septype::separated ); + --depth; + ss << '>'; + } + visit_children = false; + } +public: + + void previsit( const ast::StructInstType * type ) { + handleAggregate( type ); + } + + void previsit( const ast::UnionInstType * type ) { + handleAggregate( type ); + } + + void previsit( const ast::EnumInstType * ) { + ss << (int)ast::BasicType::SignedInt; + } + + void previsit( const ast::TypeInstType * type ) { + // Print closed variables as named types. + if ( closed.count( type->name ) ) { + ss << '#' << type->name; + // Otherwise normalize the name. + } else { + ss << ti_name( type->name ); + } + } + + void previsit( const ast::TupleType * tupleType ) { + ++depth; + buildAsTuple( *visitor, tupleType->types, ss ); + --depth; + visit_children = false; + } + + void previsit( const ast::VarArgsType * ) { + if ( atTopLevel() ) ss << "#$varargs"; + } + + // TODO: Support 0 and 1 with their type names and conversions. + void previsit( const ast::ZeroType * ) { + ss << (int)ast::BasicType::SignedInt; + } + + void previsit( const ast::OneType * ) { + ss << (int)ast::BasicType::SignedInt; + } + + void previsit( const ast::VoidType * ) { + if ( !atTopLevel() ) { + ss << "#void"; + } + } +}; + +struct ExprPrinter : public ast::WithShortCircuiting, ast::WithVisitorRef { + // TODO: Change interface to generate multiple expression canditates. + /// Accumulator of the printed expression. + std::stringstream ss; + /// Set of closed type variables. + const std::unordered_set & closed; + + ExprPrinter( const std::unordered_set & closed ) : + ss(), closed( closed ) + {} + + std::string result() const { + return ss.str(); + } + + void previsit( const ast::NameExpr * expr ) { + ss << '&' << rp_name( expr->name ); + } + + /// Handle already resolved variables as type constants. + void previsit( const ast::VariableExpr * expr ) { + ss << ast::Pass::read( expr->var->get_type(), closed ); + visit_children = false; + } + + void previsit( const ast::UntypedExpr * expr ) { + // TODO: Handle name extraction more generally. + const ast::NameExpr * name = expr->func.as(); + + // TODO: Incorporate function type into resolv-proto. + if ( !name ) { + expr->func->accept( *visitor ); + visit_children = false; + return; + } + + ss << rp_name( name->name ); + if ( expr->args.empty() ) { + ss << "()"; + } else { + ss << "( "; + auto it = expr->args.begin(); + while (true) { + (*it)->accept( *visitor ); + if ( ++it == expr->args.end() ) break; + ss << ' '; + } + ss << " )"; + } + visit_children = false; + } + + void previsit( const ast::ApplicationExpr * expr ) { + ss << ast::Pass::read( static_cast( expr ), closed ); + visit_children = false; + } + + void previsit( const ast::AddressExpr * expr ) { + ss << "$addr( "; + expr->arg->accept( *visitor ); + ss << " )"; + visit_children = false; + } + + void previsit( const ast::CastExpr * expr ) { + ss << ast::Pass::read( expr->result.get(), closed ); + visit_children = false; + } + + /// Member access handled as function from aggregate to member. + void previsit( const ast::UntypedMemberExpr * expr ) { + // TODO: Handle name extraction more generally. + const ast::NameExpr * name = expr->member.as(); + + // TODO: Incorporate function type into resolve-proto. + if ( !name ) { + expr->member->accept( *visitor ); + visit_children = false; + return; + } + + ss << rp_name( name->name, "$field_" ); + ss << "( "; + expr->aggregate->accept( *visitor ); + ss << " )"; + visit_children = false; + } + + /// Constant expression replaced by its type. + void previsit( const ast::ConstantExpr * expr ) { + ss << ast::Pass::read( static_cast( expr ), closed ); + visit_children = false; + } + + /// sizeof, alignof, & offsetof are replaced by constant type. + // TODO: Extra expression to resolve argument. + void previsit( const ast::SizeofExpr * ) { + ss << (int)ast::BasicType::LongUnsignedInt; + visit_children = false; + } + void previsit( const ast::AlignofExpr * ) { + ss << (int)ast::BasicType::LongUnsignedInt; + visit_children = false; + } + void previsit( const ast::UntypedOffsetofExpr * ) { + ss << (int)ast::BasicType::LongUnsignedInt; + visit_children = false; + } + + /// Logical expressions represented as operators. + void previsit( const ast::LogicalExpr * expr ) { + ss << ( (ast::AndExpr == expr->isAnd) ? "$and( " : "$or( " ); + expr->arg1->accept( *visitor ); + ss << ' '; + expr->arg2->accept( *visitor ); + ss << " )"; + visit_children = false; + } + + /// Conditional expression represented as an operator. + void previsit( const ast::ConditionalExpr * expr ) { + ss << "$if( "; + expr->arg1->accept( *visitor ); + ss << ' '; + expr->arg2->accept( *visitor ); + ss << ' '; + expr->arg3->accept( *visitor ); + ss << " )"; + visit_children = false; + } + + /// Comma expression represented as on operator. + void previsit( const ast::CommaExpr * expr ) { + ss << "$seq( "; + expr->arg1->accept( *visitor ); + ss << ' '; + expr->arg2->accept( *visitor ); + ss << " )"; + visit_children = false; + } + + // TODO: Handle ignored ImplicitCopyCtorExpr and below. +}; + +template +void build( + V & visitor, + const std::vector> & types, + std::stringstream & ss, + septype mode ) { + if ( types.empty() ) return; + + if ( septype::preceded == mode ) { ss << ' '; } + + auto it = types.begin(); + (*it)->accept( visitor ); + + while ( ++it != types.end() ) { + ss << ' '; + (*it)->accept( visitor ); + } + + if ( septype::terminated == mode ) { ss << ' '; } +} + +std::string buildType( + const std::string & name, const ast::Type * type, + const std::unordered_set & closed ); + +/// Build a string representing a function type. +std::string buildFunctionType( + const std::string & name, const ast::FunctionType * type, + const std::unordered_set & closed ) { + ast::Pass printer( closed ); + std::stringstream & ss = printer.core.ss; + + build( printer, type->returns, ss, septype::terminated ); + ss << rp_name( name ); + build( printer, type->params, ss, septype::preceded ); + for ( const auto & assertion : type->assertions ) { + auto var = assertion->var; + ss << " | " << buildType( var->name, var->get_type(), closed ); + } + return ss.str(); +} + +/// Build a description of a type. +std::string buildType( + const std::string & name, const ast::Type * type, + const std::unordered_set & closed ) { + const ast::Type * norefs = type->stripReferences(); + + if ( const auto & ptrType = dynamic_cast( norefs ) ) { + if ( const auto & funcType = ptrType->base.as() ) { + return buildFunctionType( name, funcType, closed ); + } + } else if ( const auto & funcType = dynamic_cast( norefs ) ) { + return buildFunctionType( name, funcType, closed ); + } + + std::stringstream ss; + ss << ast::Pass::read( norefs, closed ); + ss << " &" << rp_name( name ); + return ss.str(); +} + +/// Builds description of a field access. +std::string buildAggregateDecl( const std::string & name, + const ast::AggregateDecl * agg, const ast::Type * type, + const std::unordered_set & closed ) { + const ast::Type * norefs = type->stripReferences(); + std::stringstream ss; + + ss << ast::Pass::read( norefs, closed ) << ' '; + ss << rp_name( name, "$field_" ); + ss << " #" << agg->name; + if ( !agg->params.empty() ) { + ss << '<'; + auto it = agg->params.begin(); + while (true) { + ss << ti_name( (*it)->name ); + if ( ++it == agg->params.end() ) break; + ss << ' '; + } + ss << '>'; + } + return ss.str(); +} + +template +void buildAsTuple( + V & visitor, const std::vector> & types, + std::stringstream & ss ) { + switch ( types.size() ) { + case 0: + ss << "#void"; + break; + case 1: + types.front()->accept( visitor ); + break; + default: + ss << "#$" << types.size() << '<'; + build( visitor, types, ss, septype::separated ); + ss << '>'; + break; + } +} + +/// Adds a return +std::string buildReturn( + const ast::Type * returnType, + const ast::Expr * expr, + const std::unordered_set & closed ) { + std::stringstream ss; + ss << "$constructor( "; + ss << ast::Pass::read( returnType, closed ); + ss << ' '; + ss << ast::Pass::read( expr, closed ); + ss << " )"; + return ss.str(); +} + +void buildInitComponent( + std::stringstream & out, const ast::Init * init, + const std::unordered_set & closed ) { + if ( const auto * s = dynamic_cast( init ) ) { + out << ast::Pass::read( s->value.get(), closed ) << ' '; + } else if ( const auto * l = dynamic_cast( init ) ) { + for ( const auto & it : l->initializers ) { + buildInitComponent( out, it, closed ); + } + } +} + +/// Build a representation of an initializer. +std::string buildInitializer( + const std::string & name, const ast::Init * init, + const std::unordered_set & closed ) { + std::stringstream ss; + ss << "$constructor( &"; + ss << rp_name( name ); + ss << ' '; + buildInitComponent( ss, init, closed ); + ss << ')'; + return ss.str(); +} + +/// Visitor for collecting and printing resolver prototype output. +class ProtoDump : public ast::WithShortCircuiting, ast::WithVisitorRef { + /// Declarations in this scope. + // Set is used for ordering of printing. + std::set decls; + /// Expressions in this scope. + std::vector exprs; + /// Sub-scopes + std::vector subs; + /// Closed type variables + std::unordered_set closed; + /// Outer lexical scope + const ProtoDump * parent; + /// Return type for this scope + ast::ptr returnType; + + /// Is the declaration in this scope or a parent scope? + bool hasDecl( const std::string & decl ) const { + return decls.count( decl ) || (parent && parent->hasDecl( decl )); + } + + /// Adds a declaration to this scope if it is new. + void addDecl( const std::string & decl ) { + if ( !hasDecl( decl ) ) decls.insert( decl ); + } + + /// Adds a new expression to this scope. + void addExpr( const std::string & expr ) { + if ( !expr.empty() ) exprs.emplace_back( expr ); + } + + /// Adds a new scope as a child scope. + void addSub( ast::Pass && pass ) { + subs.emplace_back( std::move( pass.core ) ); + } + + /// Adds all named declaration in a list to the local scope. + void addAll( const std::vector> & decls ) { + for ( auto decl : decls ) { + // Skip anonymous decls. + if ( decl->name.empty() ) continue; + + if ( const auto & obj = decl.as() ) { + previsit( obj ); + } + } + } + +public: + ProtoDump() : + parent( nullptr ), returnType( nullptr ) + {} + + ProtoDump( const ProtoDump * parent, const ast::Type * returnType ) : + closed( parent->closed ), parent( parent ), returnType( returnType ) + {} + + ProtoDump( const ProtoDump & other ) : + decls( other.decls ), exprs( other.exprs ), subs( other.subs ), + closed( other.closed ), parent( other.parent ), + returnType( other.returnType ) + {} + + ProtoDump( ProtoDump && ) = default; + + ProtoDump & operator=( const ProtoDump & ) = delete; + ProtoDump & operator=( ProtoDump && ) = delete; + + void previsit( const ast::ObjectDecl * decl ) { + // Add variable as declaration. + addDecl( buildType( decl->name, decl->type, closed ) ); + + // Add initializer as expression if applicable. + if ( decl->init ) { + addExpr( buildInitializer( decl->name, decl->init, closed ) ); + } + } + + void previsit( const ast::FunctionDecl * decl ) { + visit_children = false; + + // Skips declarations with ftype parameters. + for ( const auto & typeDecl : decl->type->forall ) { + if ( ast::TypeDecl::Ftype == typeDecl->kind ) { + return; + } + } + + // Add function as declaration. + // NOTE: I'm not sure why the assertions are only present on the + // declaration and not the function type. Is that an error? + ast::FunctionType * new_type = ast::shallowCopy( decl->type.get() ); + for ( const ast::ptr & assertion : decl->assertions ) { + new_type->assertions.push_back( + new ast::VariableExpr( assertion->location , assertion ) + ); + } + addDecl( buildFunctionType( decl->name, new_type, closed ) ); + delete new_type; + + // Add information body if available. + if ( !decl->stmts ) return; + const std::vector> & returns = + decl->type->returns; + + // Add the return statement. + ast::ptr retType = nullptr; + if ( 1 == returns.size() ) { + if ( !returns.front().as() ) { + retType = returns.front(); + } + } else if ( 1 < returns.size() ) { + retType = new ast::TupleType( copy( returns ) ); + } + ast::Pass body( this, retType.get() ); + + // Handle the forall clause (type parameters and assertions). + for ( const ast::ptr & typeDecl : decl->type_params ) { + // Add set of "closed" types to body so that it can print them as NamedType. + body.core.closed.insert( typeDecl->name ); + + // Add assertions to local scope as declarations as well. + for ( const ast::DeclWithType * assertion : typeDecl->assertions ) { + assertion->accept( body ); + } + } + + // NOTE: Related to the last NOTE; this is where the assertions are now. + for ( const ast::ptr & assertion : decl->assertions ) { + assertion->accept( body ); + } + + // Add named parameters and returns to local scope. + body.core.addAll( decl->returns ); + body.core.addAll( decl->params ); + + // Add contents of the function to a new scope. + decl->stmts->accept( body ); + + // Store sub-scope + addSub( std::move( body ) ); + } + +private: + void addAggregateFields( const ast::AggregateDecl * agg ) { + for ( const auto & member : agg->members ) { + if ( const ast::ObjectDecl * obj = member.as() ) { + addDecl( buildAggregateDecl( obj->name, agg, obj->type, closed ) ); + } + } + visit_children = false; + } + +public: + + void previsit( const ast::StructDecl * decl ) { + addAggregateFields( decl ); + } + + void previsit( const ast::UnionDecl * decl ) { + addAggregateFields( decl ); + } + + void previsit( const ast::EnumDecl * decl ) { + for ( const auto & member : decl->members ) { + if ( const auto * obj = member.as() ) { + previsit( obj ); + } + } + + visit_children = false; + } + + void previsit( const ast::ReturnStmt * stmt ) { + // Do nothing for void-returning functions or statements returning nothing. + if ( !returnType || !stmt->expr ) return; + + // Otherwise constuct the return type from the expression. + addExpr( buildReturn( returnType.get(), stmt->expr, closed ) ); + visit_children = false; + } + + void previsit( const ast::AsmStmt * ) { + // Skip asm statements. + visit_children = false; + } + + void previsit( const ast::Expr * expr ) { + addExpr( ast::Pass::read( expr, closed ) ); + visit_children = false; + } + +private: + /// Print the pesudo-declarations not in any scope. + void printGlobal( std::ostream & out ) const { + // &? Address of operator. + out << "#$ptr $addr T" << std::endl; + const int intId = (int)ast::BasicType::SignedInt; + // ?&&? ?||? ?: Logical operators. + out << intId << " $and " << intId << ' ' << intId << std::endl; + out << intId << " $or " << intId << ' ' << intId << std::endl; + out << "T $if " << intId << " T T" << std::endl; + // ?,? Sequencing. + out << "T $seq X T" << std::endl; + } + + /// Print everything in this scope and its child scopes. + void printLocal( std::ostream & out, unsigned indent ) const { + const std::string tab( indent, '\t' ); + + // Print Declarations: + for ( const std::string & decl : decls ) { + out << tab << decl << std::endl; + } + + // Print Divider: + out << '\n' << tab << "%%\n" << std::endl; + + // Print Top-Level Expressions: + for ( const std::string & expr : exprs ) { + out << tab << expr << std::endl; + } + + // Print Children Scopes: + ++indent; + for ( const ProtoDump & sub : subs ) { + out << tab << '{' << std::endl; + sub.printLocal( out, indent ); + out << tab << '}' << std::endl; + } + } +public: + /// Start printing, the collected information. + void print( std::ostream & out ) const { + printGlobal( out ); + printLocal( out, 0 ); + } +}; + +} // namespace + +void dumpAsResolverProto( ast::TranslationUnit & transUnit ) { + ast::Pass dump; + accept_all( transUnit, dump ); + dump.core.print( std::cout ); +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/ResolvProtoDump.hpp =================================================================== --- src/Common/ResolvProtoDump.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) +++ src/Common/ResolvProtoDump.hpp (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -0,0 +1,29 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ResolvProtoDump.hpp -- Prints AST as instances for resolv-proto. +// +// Author : Andrew Beach +// Created On : Wed Oct 6 14:05:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Wed Oct 6 14:29:00 2021 +// Update Count : 0 +// + +#pragma once + +namespace ast { + struct TranslationUnit; +} + +/// Prints AST as instances for resolv-proto. +void dumpAsResolverProto( ast::TranslationUnit & transUnit ); + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/module.mk =================================================================== --- src/Common/module.mk (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/Common/module.mk (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -22,4 +22,6 @@ Common/CompilerError.h \ Common/Debug.h \ + Common/DeclStats.hpp \ + Common/DeclStats.cpp \ Common/ErrorObjects.h \ Common/Eval.cc \ @@ -33,4 +35,6 @@ Common/PassVisitor.proto.h \ Common/PersistentMap.h \ + Common/ResolvProtoDump.hpp \ + Common/ResolvProtoDump.cpp \ Common/ScopedMap.h \ Common/SemanticError.cc \ Index: src/InitTweak/GenInit.cc =================================================================== --- src/InitTweak/GenInit.cc (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/InitTweak/GenInit.cc (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -9,7 +9,7 @@ // Author : Rob Schluntz // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Fri Dec 13 23:15:10 2019 -// Update Count : 184 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Oct 25 13:53:00 2021 +// Update Count : 186 // #include "GenInit.h" @@ -24,4 +24,5 @@ #include "AST/Decl.hpp" #include "AST/Init.hpp" +#include "AST/Pass.hpp" #include "AST/Node.hpp" #include "AST/Stmt.hpp" @@ -294,4 +295,133 @@ } +namespace { + +# warning Remove the _New suffix after the conversion is complete. + struct HoistArrayDimension_NoResolve_New final : + public ast::WithDeclsToAdd<>, public ast::WithShortCircuiting, + public ast::WithGuards, public ast::WithConstTranslationUnit, + public ast::WithVisitorRef { + void previsit( const ast::ObjectDecl * decl ); + const ast::DeclWithType * postvisit( const ast::ObjectDecl * decl ); + // Do not look for objects inside there declarations (and type). + void previsit( const ast::AggregateDecl * ) { visit_children = false; } + void previsit( const ast::NamedTypeDecl * ) { visit_children = false; } + void previsit( const ast::FunctionType * ) { visit_children = false; } + + const ast::Type * hoist( const ast::Type * type ); + + ast::Storage::Classes storageClasses; + }; + + void HoistArrayDimension_NoResolve_New::previsit( + const ast::ObjectDecl * decl ) { + GuardValue( storageClasses ) = decl->storage; + } + + const ast::DeclWithType * HoistArrayDimension_NoResolve_New::postvisit( + const ast::ObjectDecl * objectDecl ) { + return mutate_field( objectDecl, &ast::ObjectDecl::type, + hoist( objectDecl->type ) ); + } + + const ast::Type * HoistArrayDimension_NoResolve_New::hoist( + const ast::Type * type ) { + static UniqueName dimensionName( "_array_dim" ); + + if ( !isInFunction() || storageClasses.is_static ) { + return type; + } + + if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) { + if ( nullptr == arrayType->dimension ) { + return type; + } + + if ( !Tuples::maybeImpure( arrayType->dimension ) ) { + return type; + } + + ast::ptr dimType = transUnit().global.sizeType; + assert( dimType ); + add_qualifiers( dimType, ast::CV::Qualifiers( ast::CV::Const ) ); + + ast::ObjectDecl * arrayDimension = new ast::ObjectDecl( + arrayType->dimension->location, + dimensionName.newName(), + dimType, + new ast::SingleInit( + arrayType->dimension->location, + arrayType->dimension + ) + ); + + ast::ArrayType * mutType = ast::mutate( arrayType ); + mutType->dimension = new ast::VariableExpr( + arrayDimension->location, arrayDimension ); + declsToAddBefore.push_back( arrayDimension ); + + mutType->base = hoist( mutType->base ); + return mutType; + } + return type; + } + + struct ReturnFixer_New final : + public ast::WithStmtsToAdd<>, ast::WithGuards { + void previsit( const ast::FunctionDecl * decl ); + const ast::ReturnStmt * previsit( const ast::ReturnStmt * stmt ); + private: + const ast::FunctionDecl * funcDecl = nullptr; + }; + + void ReturnFixer_New::previsit( const ast::FunctionDecl * decl ) { + GuardValue( funcDecl ) = decl; + } + + const ast::ReturnStmt * ReturnFixer_New::previsit( + const ast::ReturnStmt * stmt ) { + auto & returns = funcDecl->returns; + assert( returns.size() < 2 ); + // Hands off if the function returns a reference. + // Don't allocate a temporary if the address is returned. + if ( stmt->expr && 1 == returns.size() ) { + ast::ptr retDecl = returns.front(); + if ( isConstructable( retDecl->get_type() ) ) { + // Explicitly construct the return value using the return + // expression and the retVal object. + assertf( "" != retDecl->name, + "Function %s has unnamed return value.\n", + funcDecl->name.c_str() ); + + auto retVal = retDecl.strict_as(); + if ( auto varExpr = stmt->expr.as() ) { + // Check if the return statement is already set up. + if ( varExpr->var == retVal ) return stmt; + } + ast::ptr ctorStmt = genCtorDtor( + retVal->location, "?{}", retVal, stmt->expr ); + assertf( ctorStmt, + "ReturnFixer: genCtorDtor returned nllptr: %s / %s", + toString( retVal ).c_str(), + toString( stmt->expr ).c_str() ); + stmtsToAddBefore.push_back( ctorStmt ); + + // Return the retVal object. + ast::ReturnStmt * mutStmt = ast::mutate( stmt ); + mutStmt->expr = new ast::VariableExpr( + stmt->location, retDecl ); + return mutStmt; + } + } + return stmt; + } + +} // namespace + + void genInit( ast::TranslationUnit & transUnit ) { + ast::Pass::run( transUnit ); + ast::Pass::run( transUnit ); + } + void CtorDtor::generateCtorDtor( std::list< Declaration * > & translationUnit ) { PassVisitor ctordtor; Index: src/InitTweak/GenInit.h =================================================================== --- src/InitTweak/GenInit.h (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/InitTweak/GenInit.h (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -9,7 +9,7 @@ // Author : Rodolfo G. Esteves // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:31:19 2017 -// Update Count : 4 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Oct 22 16:08:00 2021 +// Update Count : 6 // @@ -27,4 +27,5 @@ /// Adds return value temporaries and wraps Initializers in ConstructorInit nodes void genInit( std::list< Declaration * > & translationUnit ); + void genInit( ast::TranslationUnit & translationUnit ); /// Converts return statements into copy constructor calls on the hidden return variable Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/Parser/parser.yy (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Sep 11 08:20:44 2021 -// Update Count : 5040 +// Last Modified On : Fri Oct 15 09:20:17 2021 +// Update Count : 5163 // @@ -31,5 +31,5 @@ // from ANSI90 to ANSI11 C are marked with the comment "C99/C11". -// This grammar also has two levels of extensions. The first extensions cover most of the GCC C extensions All of the +// This grammar also has two levels of extensions. The first extensions cover most of the GCC C extensions. All of the // syntactic extensions for GCC C are marked with the comment "GCC". The second extensions are for Cforall (CFA), which // fixes several of C's outstanding problems and extends C with many modern language concepts. All of the syntactic @@ -69,5 +69,5 @@ // 2. String encodings are transformed into canonical form (one encoding at start) so the encoding can be found // without searching the string, e.g.: "abc" L"def" L"ghi" => L"abc" "def" "ghi". Multiple encodings must match, - // i.e., u"a" U"b" L"c" is disallowed. + // e.g., u"a" U"b" L"c" is disallowed. if ( from[0] != '"' ) { // encoding ? @@ -310,6 +310,5 @@ %token ATassign // @= -%type identifier -%type identifier_or_type_name attr_name +%type identifier identifier_at identifier_or_type_name attr_name %type quasi_keyword %type string_literal @@ -327,5 +326,5 @@ %type conditional_expression constant_expression assignment_expression assignment_expression_opt %type comma_expression comma_expression_opt -%type argument_expression_list_opt argument_expression default_initializer_opt +%type argument_expression_list_opt argument_expression_list argument_expression default_initializer_opt %type if_control_expression %type for_control_expression for_control_expression_list @@ -559,4 +558,8 @@ IDENTIFIER | quasi_keyword + ; + +identifier_at: + identifier | '@' // CFA { Token tok = { new string( DeclarationNode::anonymous.newName() ), yylval.tok.loc }; $$ = tok; } @@ -693,5 +696,9 @@ // empty { $$ = nullptr; } - | argument_expression + | argument_expression_list + ; + +argument_expression_list: + argument_expression | argument_expression_list_opt ',' argument_expression { $$ = (ExpressionNode *)($1->set_last( $3 )); } @@ -731,5 +738,5 @@ | FLOATINGconstant fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_field_name_FLOATINGconstant( *$1 ), $2 ) ); } - | identifier fraction_constants_opt + | identifier_at fraction_constants_opt // CFA, allow anonymous fields { $$ = new ExpressionNode( build_field_name_fraction_constants( build_varref( $1 ), $2 ) ); @@ -1084,4 +1091,7 @@ comma_expression_opt ';' { $$ = new StatementNode( build_expr( $1 ) ); } + | MUTEX '(' ')' comma_expression ';' + { $$ = new StatementNode( build_mutex( nullptr, new StatementNode( build_expr( $4 ) ) ) ); } + // { SemanticError( yylloc, "Mutex expression is currently unimplemented." ); $$ = nullptr; } ; @@ -1182,16 +1192,22 @@ iteration_statement: - WHILE '(' push if_control_expression ')' statement pop - { $$ = new StatementNode( build_while( $4, maybe_build_compound( $6 ) ) ); } - | WHILE '(' ')' statement // CFA => while ( 1 ) + WHILE '(' ')' statement // CFA => while ( 1 ) { $$ = new StatementNode( build_while( new IfCtrl( nullptr, new ExpressionNode( build_constantInteger( *new string( "1" ) ) ) ), maybe_build_compound( $4 ) ) ); } - | DO statement WHILE '(' comma_expression ')' ';' - { $$ = new StatementNode( build_do_while( $5, maybe_build_compound( $2 ) ) ); } + | WHILE '(' if_control_expression ')' statement %prec THEN + { $$ = new StatementNode( build_while( $3, maybe_build_compound( $5 ) ) ); } + | WHILE '(' if_control_expression ')' statement ELSE statement // CFA + { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; } | DO statement WHILE '(' ')' ';' // CFA => do while( 1 ) { $$ = new StatementNode( build_do_while( new ExpressionNode( build_constantInteger( *new string( "1" ) ) ), maybe_build_compound( $2 ) ) ); } - | FOR '(' push for_control_expression_list ')' statement pop - { $$ = new StatementNode( build_for( $4, maybe_build_compound( $6 ) ) ); } + | DO statement WHILE '(' comma_expression ')' ';' %prec THEN + { $$ = new StatementNode( build_do_while( $5, maybe_build_compound( $2 ) ) ); } + | DO statement WHILE '(' comma_expression ')' ELSE statement // CFA + { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; } | FOR '(' ')' statement // CFA => for ( ;; ) { $$ = new StatementNode( build_for( new ForCtrl( (ExpressionNode * )nullptr, (ExpressionNode * )nullptr, (ExpressionNode * )nullptr ), maybe_build_compound( $4 ) ) ); } + | FOR '(' for_control_expression_list ')' statement %prec THEN + { $$ = new StatementNode( build_for( $3, maybe_build_compound( $5 ) ) ); } + | FOR '(' for_control_expression_list ')' statement ELSE statement // CFA + { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; } ; @@ -1339,12 +1355,10 @@ with_statement: WITH '(' tuple_expression_list ')' statement - { - $$ = new StatementNode( build_with( $3, $5 ) ); - } + { $$ = new StatementNode( build_with( $3, $5 ) ); } ; // If MUTEX becomes a general qualifier, there are shift/reduce conflicts, so change syntax to "with mutex". mutex_statement: - MUTEX '(' argument_expression_list_opt ')' statement + MUTEX '(' argument_expression_list ')' statement { $$ = new StatementNode( build_mutex( $3, $5 ) ); } ; @@ -2475,5 +2489,5 @@ designation: designator_list ':' // C99, CFA uses ":" instead of "=" - | identifier ':' // GCC, field name + | identifier_at ':' // GCC, field name { $$ = new ExpressionNode( build_varref( $1 ) ); } ; @@ -2487,5 +2501,5 @@ designator: - '.' identifier // C99, field name + '.' identifier_at // C99, field name { $$ = new ExpressionNode( build_varref( $2 ) ); } | '[' push assignment_expression pop ']' // C99, single array element @@ -2919,5 +2933,5 @@ paren_identifier: - identifier + identifier_at { $$ = DeclarationNode::newName( $1 ); } | '(' paren_identifier ')' // redundant parenthesis Index: src/main.cc =================================================================== --- src/main.cc (revision a51a02de31d78381190b6b5aafa5260020147369) +++ src/main.cc (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -9,7 +9,7 @@ // Author : Peter Buhr and Rob Schluntz // Created On : Fri May 15 23:12:02 2015 -// Last Modified By : Henry Xue -// Last Modified On : Mon Aug 23 15:42:08 2021 -// Update Count : 650 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Oct 22 16:06:00 2021 +// Update Count : 653 // @@ -43,4 +43,6 @@ #include "Common/CodeLocationTools.hpp" // for forceFillCodeLocations #include "Common/CompilerError.h" // for CompilerError +#include "Common/DeclStats.hpp" // for printDeclStats +#include "Common/ResolvProtoDump.hpp" // for dumpAsResolverProto #include "Common/Stats.h" #include "Common/PassVisitor.h" @@ -334,28 +336,6 @@ PASS( "Fix Labels", ControlStruct::fixLabels( translationUnit ) ); PASS( "Fix Names", CodeGen::fixNames( translationUnit ) ); - PASS( "Gen Init", InitTweak::genInit( translationUnit ) ); - - if ( libcfap ) { - // generate the bodies of cfa library functions - LibCfa::makeLibCfa( translationUnit ); - } // if - - if ( declstatsp ) { - CodeTools::printDeclStats( translationUnit ); - deleteAll( translationUnit ); - return EXIT_SUCCESS; - } // if - - if ( bresolvep ) { - dump( translationUnit ); - return EXIT_SUCCESS; - } // if CodeTools::fillLocations( translationUnit ); - - if ( resolvprotop ) { - CodeTools::dumpAsResolvProto( translationUnit ); - return EXIT_SUCCESS; - } // if if( useNewAST ) { @@ -366,6 +346,29 @@ auto transUnit = convert( move( translationUnit ) ); + forceFillCodeLocations( transUnit ); + + PASS( "Gen Init", InitTweak::genInit( transUnit ) ); PASS( "Expand Member Tuples" , Tuples::expandMemberTuples( transUnit ) ); - + + if ( libcfap ) { + // Generate the bodies of cfa library functions. + LibCfa::makeLibCfa( transUnit ); + } // if + + if ( declstatsp ) { + printDeclStats( transUnit ); + return EXIT_SUCCESS; + } // if + + if ( bresolvep ) { + dump( move( transUnit ) ); + return EXIT_SUCCESS; + } // if + + if ( resolvprotop ) { + dumpAsResolverProto( transUnit ); + return EXIT_SUCCESS; + } // if + PASS( "Resolve", ResolvExpr::resolve( transUnit ) ); if ( exprp ) { @@ -377,7 +380,32 @@ PASS( "Fix Init", InitTweak::fix(transUnit, buildingLibrary())); + translationUnit = convert( move( transUnit ) ); } else { + PASS( "Gen Init", InitTweak::genInit( translationUnit ) ); PASS( "Expand Member Tuples" , Tuples::expandMemberTuples( translationUnit ) ); + + if ( libcfap ) { + // Generate the bodies of cfa library functions. + LibCfa::makeLibCfa( translationUnit ); + } // if + + if ( declstatsp ) { + CodeTools::printDeclStats( translationUnit ); + deleteAll( translationUnit ); + return EXIT_SUCCESS; + } // if + + if ( bresolvep ) { + dump( translationUnit ); + return EXIT_SUCCESS; + } // if + + CodeTools::fillLocations( translationUnit ); + + if ( resolvprotop ) { + CodeTools::dumpAsResolvProto( translationUnit ); + return EXIT_SUCCESS; + } // if PASS( "Resolve", ResolvExpr::resolve( translationUnit ) ); Index: tests/concurrent/semaphore.cfa =================================================================== --- tests/concurrent/semaphore.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/concurrent/semaphore.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -2,4 +2,5 @@ #include #include +#include enum { num_blockers = 17, num_unblockers = 13 }; @@ -28,5 +29,5 @@ thrash(); P(ben); - if(((thread&)this).seqable.next != 0p) sout | acquire |"Link not invalidated"; + if(((thread&)this).seqable.next != 0p) mutex(sout) sout | "Link not invalidated"; thrash(); } Index: tests/concurrent/sleep.cfa =================================================================== --- tests/concurrent/sleep.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/concurrent/sleep.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -1,4 +1,5 @@ #include #include +#include #include @@ -29,5 +30,5 @@ int main() { - sout | acquire | "start"; + mutex( sout ) sout | "start"; { slow_sleeper slow; @@ -36,5 +37,5 @@ yield(); } - sout | acquire | "done"; + mutex( sout ) sout | "done"; } Index: tests/io/io-acquire.cfa =================================================================== --- tests/io/io-acquire.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/io/io-acquire.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -10,10 +10,11 @@ // Created On : Mon Mar 1 18:40:09 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 27 11:49:34 2021 -// Update Count : 18 +// Last Modified On : Wed Oct 6 18:04:58 2021 +// Update Count : 72 // #include #include +#include thread T {}; @@ -21,9 +22,8 @@ // output from parallel threads should not be scrambled - for ( 100 ) { // local protection - sout | acquire | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + for ( 100 ) { // expression protection + mutex(sout) sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; } - { // global protection (RAII) - osacquire acq = { sout }; + mutex( sout ) { // statement protection for ( 100 ) { sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; @@ -31,9 +31,17 @@ } { // duplicate protection demonstrating recursive lock - osacquire acq = { sout }; - for ( 100 ) { - osacquire acq = { sout }; - sout | acquire | 1 | 2 | 3 | 4 | 5 | acquire | 6 | 7 | 8 | 9; - sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + ofstream & h1( ofstream & os ) { // helper + mutex( os ) return os | 1 | 2 | 3 | 4; // unnecessary mutex + } + ofstream & h2( ofstream & os ) { // helper + mutex( os ) return os | 6 | 7 | 8 | 9; // unnecessary mutex + } + mutex( sout ) { // unnecessary mutex + for ( 100 ) { + mutex( sout ) { + sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + sout | h1 | 5 | h2; // refactored code + } + } } } @@ -42,9 +50,8 @@ int a, b, c, d, e, f, g, h, i; - for ( 100 ) { // local protection - sin | acquire | a | b | c | d | e | f | g | h | i; + for ( 100 ) { // expression protection + mutex(sin) sin | a | b | c | d | e | f | g | h | i; } - { // global protection (RAII) - isacquire acq = { sin }; + mutex( sin ) { // statement protection for ( 100 ) { sin | a | b | c | d | e | f | g | h | i; @@ -52,9 +59,17 @@ } { // duplicate protection demonstrating recursive lock - isacquire acq = { sin }; - for ( 100 ) { - isacquire acq = { sin }; - sin | acquire | a | b | c | d | e | acquire | f | g | h | i; - sin | a | b | c | d | e | f | g | h | i; + ifstream & h1( ifstream & is ) { // helper + mutex( is ) return is | a | b | c | d; // unnecessary mutex + } + ifstream & h2( ifstream & is ) { // helper + mutex( is ) return is | f | g | h | i; // unnecessary mutex + } + mutex( sin ) { // unnecessary mutex + for ( 5 ) { + mutex( sin ) { + sin | a | b | c | d | e | f | g | h | i; + sin | h1 | e | h2; // refactored code + } + } } } Index: tests/linking/io-acquire.cfa =================================================================== --- tests/linking/io-acquire.cfa (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/linking/io-acquire.cfa (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -17,12 +17,13 @@ #include #include +#include int main() { int i; if(threading_enabled()) { - stdout | acquire | "YES"; + mutex( stdout ) stdout | "YES"; stdin | i; } else { - stdout | acquire | "NO"; + mutex( stdout ) stdout | "NO"; stdin | i; } Index: tests/pybin/test_run.py =================================================================== --- tests/pybin/test_run.py (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/pybin/test_run.py (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -65,12 +65,12 @@ def toString( cls, retcode, duration ): if settings.generating : - if retcode == TestResult.SUCCESS: text = "Done " - elif retcode == TestResult.TIMEOUT: text = "TIMEOUT" - else : text = "ERROR code %d" % retcode + if retcode == TestResult.SUCCESS: key = 'pass'; text = "Done " + elif retcode == TestResult.TIMEOUT: key = 'time'; text = "TIMEOUT" + else : key = 'fail'; text = "ERROR code %d" % retcode else : - if retcode == TestResult.SUCCESS: text = "PASSED " - elif retcode == TestResult.TIMEOUT: text = "TIMEOUT" - else : text = "FAILED with code %d" % retcode + if retcode == TestResult.SUCCESS: key = 'pass'; text = "PASSED " + elif retcode == TestResult.TIMEOUT: key = 'time'; text = "TIMEOUT" + else : key = 'fail'; text = "FAILED with code %d" % retcode text += " C%s - R%s" % (fmtDur(duration[0]), fmtDur(duration[1])) - return text + return key, text Index: tests/test.py =================================================================== --- tests/test.py (revision a51a02de31d78381190b6b5aafa5260020147369) +++ tests/test.py (revision a2e4b0cd8f28d66ff183eebe6d8cf6d6d3858dd9) @@ -257,5 +257,5 @@ # update output based on current action - result_txt = TestResult.toString( retcode, duration ) + result_key, result_txt = TestResult.toString( retcode, duration ) #print result with error if needed @@ -265,7 +265,7 @@ text = text + '\n' + error - return retcode == TestResult.SUCCESS, text + return retcode == TestResult.SUCCESS, result_key, text except KeyboardInterrupt: - return False, "" + return False, 'keybrd', "" # except Exception as ex: # print("Unexpected error in worker thread running {}: {}".format(t.target(), ex), file=sys.stderr) @@ -283,4 +283,6 @@ failed = False + rescnts = { 'pass': 0, 'fail': 0, 'time': 0, 'keybrd': 0 } + other = 0 # for each test to run @@ -294,5 +296,10 @@ ) - for i, (succ, txt) in enumerate(timed(results, timeout = settings.timeout.total), 1) : + for i, (succ, code, txt) in enumerate(timed(results, timeout = settings.timeout.total), 1) : + if code in rescnts.keys(): + rescnts[code] += 1 + else: + other += 1 + if not succ : failed = True @@ -319,4 +326,6 @@ # clean the workspace make('clean', output_file=subprocess.DEVNULL, error=subprocess.DEVNULL) + + print("{} passes, {} failures, {} timeouts, {} cancelled, {} other".format(rescnts['pass'], rescnts['fail'], rescnts['time'], rescnts['keybrd'], other)) return failed @@ -443,5 +452,4 @@ failed = run_tests(local_tests, options.jobs) if failed: - result = 1 if not settings.continue_: break