Changeset 35ea4f3


Ignore:
Timestamp:
Jan 16, 2021, 4:48:06 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
b57db73
Parents:
0edd11a (diff), 02b73ea (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/features.tex

    r0edd11a r35ea4f3  
    1010of they virtual system was designed and implemented.
    1111
    12 Virtual types are organizied in simple hierarchies. Each virtual type may have
     12Virtual types are organized in simple hierarchies. Each virtual type may have
    1313a parent and can have any number of children. A type's descendants are its
    1414children and its children's descendants. A type may not be its own descendant.
    … …  
    1717structure that has fields for all the virtual members of a type. A virtual
    1818type has all the virtual members of its parent and can add more. It may also
    19 update the values of the virtual members.
     19update the values of the virtual members and should in many cases.
    2020
    2121Except for virtual casts, this is only used internally in the exception
    … …  
    2727\end{lstlisting}
    2828
    29 This has the same precidence as a traditional C-cast and can be used in the
     29This has the same precedence as a traditional C-cast and can be used in the
    3030same places. This will convert the result of EXPRESSION to the type TYPE. Both
    3131the type of EXPRESSION and TYPE must be pointers to virtual types.
    … …  
    4141% features all exceptions support.
    4242
     43\subsection{Exception Traits}
     44Exceptions are defined by the trait system; there are a series of traits and
     45if a type satisfies them then they can be used as exceptions.
     46
     47\begin{lstlisting}
     48trait is_exception(dtype exceptT, dtype virtualT) {
     49    virtualT const & get_exception_vtable(exceptT *);
     50};
     51\end{lstlisting}
     52This is the base trait that all exceptions need to match.
     53The single function takes any pointer (including the null pointer) and
     54returns a reference to the virtual table instance. Defining this function
     55also establishes the virtual type and virtual table pair to the resolver
     56and promises that \codeCFA{exceptT} is a virtual type and a child of the
     57base exception type.
     58
     59One odd thing about \codeCFA{get_exception_vtable} is that it should always
     60be a constant function, returning the same value regardless of its argument.
     61A pointer or reference to the virtual table instance could be used instead,
     62however using a function has some ease of implementation advantages and
     63allows for easier disambiguation because the virtual type name (or the
     64address of an instance that is in scope) can be used instead of the mangled
     65virtual table name.
     66
     67Also note the use of the word ``promise" in the trait description. \CFA
     68cannot currently check to see if either \codeCFA{exceptT} or
     69\codeCFA{virtualT} match the layout requirements. Currently this is
     70considered part of \codeCFA{get_exception_vtable}'s correct implementation.
     71
     72\begin{lstlisting}
     73trait is_termination_exception(
     74        dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
     75    void defaultTerminationHandler(exceptT &);
     76};
     77\end{lstlisting}
     78The only additional function required to make the exception usable with
     79termination is a default handler. This function is called whenever a
     80termination throw on an exception of this type is preformed and no handler
     81is found.
     82
     83\begin{lstlisting}
     84trait is_resumption_exception(
     85        dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
     86    void defaultResumptionHandler(exceptT &);
     87};
     88\end{lstlisting}
     89Creating a resumption exception is exactly the same except for resumption.
     90The name change reflects that and the function is called when a resumption
     91throw on an exception of this type is preformed and no handler is found.
     92
     93Finally there are three additional macros that can be used to refer to the
     94these traits. They are \codeCFA{IS_EXCEPTION},
     95\codeCFA{IS_TERMINATION_EXCEPTION} and \codeCFA{IS_RESUMPTION_EXCEPTION}.
     96Each takes the virtual type's name and, for polymorphic types only, the
     97parenthesized list of polymorphic arguments. These do the name mangling to
     98get the virtual table name and provide the arguments to both sides.
     99
    43100\section{Termination}
    44101
    45 Termination exception throws are likely the most framilar kind, as they are
     102Termination exception throws are likely the most familiar kind, as they are
    46103used in several popular programming languages. A termination will throw an
    47104exception, search the stack for a handler, unwind the stack to where the
    … …  
    66123
    67124Then the exception system will search the stack starting from the throw and
    68 proceding towards the base of the stack, from callee to caller. As it goes
     125proceeding towards the base of the stack, from callee to caller. As it goes
    69126it will check any termination handlers it finds:
    70127
    … …  
    111168\paragraph{Re-Throwing}
    112169
    113 You can also rethrow the most recent termination exception with
     170You can also re-throw the most recent termination exception with
    114171\codeCFA{throw;}. % This is terrible and you should never do it.
    115172This can be done in a handler or any function that could be called from a
    … …  
    135192\end{lstlisting}
    136193The result of EXPRESSION must be a resumption exception type. A resumption
    137 exception type is any type that satifies the assertion
     194exception type is any type that satisfies the assertion
    138195\codeCFA{void defaultResumptionHandler(T &);} (the default handler). When the
    139196statement is executed the expression is evaluated and the result is thrown.
    … …  
    159216continues from the throw statement.
    160217
    161 If no approprate handler is found then the default handler is called. The
     218If no appropriate handler is found then the default handler is called. The
    162219throw statement acts as a regular function call passing the exception to
    163220the default handler and after the handler finishes executing control continues
    … …  
    174231which is what most users expect.
    175232
    176 % This might need a diagram. But it is an important part of the justifaction
     233% This might need a diagram. But it is an important part of the justification
    177234% of the design of the traversal order.
    178235It also avoids the recursive resumption problem. If the entire stack is
    … …  
    184241system an A resumed from the top of the stack will be handled by the first
    185242handler. A B resumed from the top or from the first handler it will be handled
    186 by the second hander. The only difference is when A is thrown from the second
     243by the second handler. The only difference is when A is thrown from the second
    187244handler. The entire stack search will call the first handler again, creating a
    188245loop. Starting from the position in the stack though will break this loop.
    … …  
    198255It also has the same behaviour, after the exception type has been matched
    199256with the EXCEPTION\_TYPE the CONDITION is evaluated with NAME in scope. If
    200 the result is true then the hander is run, otherwise the search continues
     257the result is true then the handler is run, otherwise the search continues
    201258just as if there had been a type mismatch.
    202259
    … …  
    241298the finally block. Other ways to leave the finally block - such as a long
    242299jump or termination - are much harder to check, at best requiring additional
    243 runtime overhead, and so are merely discouraged.
     300run-time overhead, and so are merely discouraged.
    244301
    245302\section{Cancellation}
    … …  
    250307
    251308There is no special statement for starting a cancellation, instead you call
    252 the standard libary function \codeCFA{cancel\_stack} which takes an exception.
     309the standard library function \codeCFA{cancel\_stack} which takes an exception.
    253310Unlike in a throw this exception is not used in control flow but is just there
    254311to pass information about why the cancellation happened.
    255312
    256 The handler is decided entirely by which stack is being cancelled. There are
     313The handler is decided entirely by which stack is being canceled. There are
    257314three handlers that apply to three different groups of stacks:
    258315\begin{itemize}
    … …  
    266323
    267324\item Thread Stack:
    268 Thread stacks are those created \codeCFA{thread} or otherwise satify the
     325Thread stacks are those created \codeCFA{thread} or otherwise satisfy the
    269326\codeCFA{is\_thread} trait.
    270327
    … …  
    288345context required for the other. This can happen with join but as the
    289346destructors will always be run when the stack is being unwound and one
    290 termination/cancellation is already active. Also since they are implicite they
     347termination/cancellation is already active. Also since they are implicit they
    291348are easier to forget about.
    292349
    293350\item Coroutine Stack:
    294351Coroutine stacks are those created with \codeCFA{coroutine} or otherwise
    295 satify the \codeCFA{is\_coroutine} trait.
     352satisfy the \codeCFA{is\_coroutine} trait.
    296353
    297354A coroutine knows of two other coroutines, its starter and its last resumer.
    … …  
    301358Resume will resume throw a \codeCFA{CoroutineCancelled} exception, which is
    302359polymorphic over the coroutine type and has a pointer to the coroutine being
    303 cancelled and the cancelling exception. The resume function also has an
     360canceled and the canceling exception. The resume function also has an
    304361assertion that the \codeCFA{defaultResumptionHandler} for the exception. So it
    305362will use the default handler like a regular throw.

  • doc/theses/andrew_beach_MMath/future.tex

    r0edd11a r35ea4f3  
    88parts of the exception system that use the current version.
    99
    10 For instance a full virtual system would probably allow for several
    11 improvements to the exception traits. Although they do currently work they
    12 could be made easier to use by making the virtual table type implitate in the
    13 trait (which would remove the need for those wrapper marcos) or allowing
    14 for assertions that give the layout of a virtual table for safety.
     10There are several improvements to the virtual system that would improve
     11the exception traits. The biggest one is an assertion that checks that one
     12virtual type is a child of another virtual type. This would capture many of
     13the requirements much more precisely.
     14
     15The full virtual system might also include other improvement like associated
     16types. This is a proposed feature that would allow traits to refer to types
     17not listed in their header. This would allow the exception traits to not
     18refer to the virtual table type explicatly which would remove the need for
     19the interface macros.
    1520
    1621\section{Additional Throws}
    … …  
    6570
    6671Also new techniques to skip previously searched parts of the stack will have
    67 to be developed.
     72to be developed. The recursive resume problem still remains and ideally the
     73same pattern of ignoring sections of the stack.
    6874
    69 \section{Support for More Platforms}
    70 Termination is not portable because it is implemented with inline assembly.
    71 Those sections will have to be rewritten to support different architectures
     75\section{Signal Exceptions}
     76Exception Handling: Issues and a Proposed Notation suggests there are three
     77types of exceptions: escape, notify and signal.
     78Escape exceptions are our termination exceptions, notify exceptions are
     79resumption exceptions and that leaves signal exception unimplemented.
    7280
    73 \section{Quality-of-Life Improvements}
    74 Finally come various improvements to the usability of \CFA. Most of these
    75 would just require time. Time that would not lead to interesting research so
    76 it has been left aside for now. A few examples are included here but there
    77 are more:
     81Signal exceptions allow either behaviour, that is after the exception is
     82handled control can either return to the throw or from where the handler is
     83defined.
     84
     85The design should be rexamined and be updated for \CFA. A very direct
     86translation would perhaps have a new throw and catch pair and a statement
     87(or statements) could be used to decide if the handler returns to the throw
     88or continues where it is, but there are other options.
     89
     90For instance resumption could be extended to cover this use by allowing
     91local control flow out of it. This would require an unwind as part of the
     92transition as there are stack frames that have to be removed.
     93This would mean there is no notify like throw but because \CFA does not have
     94exception signatures a termination can be thrown from any resumption handler
     95already so there are already ways one could try to do this in existing \CFA.
     96
     97% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
     98% if we could choose if _Unwind_Resume proceeded to the clean-up stage this
     99% would be much easier to implement.
     100
     101\section{Language Improvements}
     102There is also a lot of work that are not follow ups to this work in terms of
     103research, some have no interesting research to be done at all, but would
     104improve \CFA as a programming language. The full list of these would
     105naturally be quite extensive but here are a few examples that involve
     106exceptions:
    78107
    79108\begin{itemize}
     109\item The implementation of termination is not portable because it includes
     110some assembly statements. These sections will have to be re-written to so
     111\CFA has full support on more machines.
    80112\item Allowing exception handler to bind the exception to a reference instead
    81113of a pointer. This should actually result in no change in behaviour so there
    … …  
    88120much easier. (To do the same for try blocks would probably wait for zero-cost
    89121exceptions, which would allow the try block to be inlined as well.)
    90 \item Enabling local control flow out of a resumption handler. This would be
    91 a weighty operation, causing a stack unwind like a termination, so there might
    92 be a different statement or a statement modifier to make sure the user does
    93 this purposefully.
    94 
    95 However this would require the more complex system as they cannot be inlined
    96 into the original function as they can be run at a different place on the
    97 stack. So instead the unwinding will have to carry with it information on
    98 which one of these points to continue at and possibly also the return value
    99 for the function if a \codeCFA{return} statement was used.
    100122\end{itemize}

  • doc/theses/fangren_yu_COOP_F20/Report.tex

    r0edd11a r35ea4f3  
    8787
    8888\begin{abstract}
     89
     90\CFA is an evolutionary extension to the C programming language, featuring a parametric type system, and is currently under active development. The reference compiler for \CFA language, @cfa-cc@, has some of its major components dated back to early 2000s, and is based on inefficient data structures and algorithms. Some improvements targeting the expression resolution algorithm, suggested by a recent prototype experiment on a simplified model, are implemented in @cfa-cc@ to support the full \CFA language. These optimizations speed up the compiler significantly by a factor of 20 across the existing \CFA codebase, bringing the compilation time of a mid-sized \CFA source file down to 10-second level. A few cases derived from realistic code examples that causes trouble to the compiler are analyzed in detail, with proposed solutions. This step of \CFA project development is critical to its eventual goal to be used alongside C for large software systems.
     91
    8992\end{abstract}
    9093
    9194\section{Introduction}
     95
     96\CFA language, developed by the Programming Language Group at University of Waterloo, has a long history, with the first proof-of-concept compiler built in 2003 by Richard Bilson~\cite{Bilson03}. Many new features are added to the language over time, but the core of \CFA, parametric functions introduced by the @forall@ clause (hence the name of the language), with the type system supporting parametric overloading, remains mostly unchanged.
     97
     98The current \CFA reference compiler @cfa-cc@ still includes many parts taken directly from the original Bilson's implementation, and serves as a starting point for the enhancement work to the type system. Unfortunately, it does not provide the efficiency required for the language to be used practically: a \CFA source file of approximately 1000 lines of code can take a few minutes to compile. The cause of the problem is that the old compiler used inefficient data structures and algorithms for expression resolution, which involved a lot of copying and redundant work.
     99
     100This paper presents a series of optimizations to the performance-critical parts of the resolver, with a major rework of the data structure used by the compiler, using a functional programming approach to reduce memory complexity. Subsequent improvements are mostly suggested by running the compiler builds with a performance profiler against the \CFA standard library source code and a test suite to find the most underperforming components in the compiler algorithm.
     101
     102The \CFA team endorses a pragmatic philosophy in work that mostly focuses on practical implications of language design and implementation, rather than the theoretical limits. In particular, the compiler is designed to work on production \CFA code efficiently and keep type safety, while sometimes making compromises to expressiveness in extreme corner cases. However, when these corner cases do appear in actual usage, they need to be thoroughly investigated. Analysis presented in this paper, therefore, are conducted on a case-by-case basis. Some of them eventually point to certain weaknesses in the language design and solutions are proposed based on experimental results.
    92103
    93104\section{Completed work}
    … …  
    444455\section{Timing results}
    445456
    446 For the timing results presented here, the \CFA compiler is built with gcc 9.3.0, and tested on a server machine running Ubuntu 20.04, 64GB RAM and 32-core 2.2 GHz CPU, results reported by the time command, and using only 8 cores in parallel such that the time is close to the case with 100% CPU utilization on a single thread.
     457For the timing results presented here, the \CFA compiler is built with gcc 9.3.0, and tested on a server machine running Ubuntu 20.04, 64GB RAM and 32-core 2.2 GHz CPU, results reported by the time command, and using only 8 cores in parallel such that the time is close to the case with 100\% CPU utilization on a single thread.
    447458
    448459On the most recent build, the \CFA standard library (~1.3 MB of source code) compiles in 4 minutes 47 seconds total processor time (single thread equivalent), with the slowest file taking 13 seconds. The test suite (178 test cases, ~2.2MB of source code) completes within 25 minutes total processor time,\footnote{Including a few runtime tests; total time spent in compilation is approximately 21 minutes.} with the slowest file taking 23 seconds. In contrast, the library build on old compiler takes 85 minutes total, 5 minutes for the slowest file. Full test suite takes too long with old compiler build and is therefore not run, but the slowest test cases take approximately 5 minutes. Overall, the most recent build compared to old build in April 2020, before the project started, is consistently faster by a factor of 20.

  • libcfa/src/stdlib.hfa

    r0edd11a r35ea4f3  
    191191                } else if(Fill.tag == 't') {
    192192                        for ( int i = copy_end; i < Dim * size; i += size ) {
     193#pragma GCC diagnostic push
     194#pragma GCC diagnostic ignored "-Warray-bounds"
     195#pragma GCC diagnostic push
     196#pragma GCC diagnostic ignored "-Wstringop-overflow="
    193197                                memcpy( (char *)ptr + i, &Fill.t, size );
     198#pragma GCC diagnostic pop
     199#pragma GCC diagnostic pop
    194200                        }
    195201                } else if(Fill.tag == 'a') {
Note: See TracChangeset for help on using the changeset viewer.