Changes in / [f20dffa:6013bd7]


Ignore:
Files:
2 deleted
12 edited

Legend:

Unmodified
Added
Removed

  • doc/generic_types/.gitignore

    rf20dffa r6013bd7  
    1313*.ps
    1414*.toc
    15 *.lof
    16 *.lot
    1715*.synctex.gz

  • doc/generic_types/generic_types.bib

    rf20dffa r6013bd7  
    2020    note        = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}}
    2121}
    22 
    23 @mastersthesis{Schluntz17,
    24     author  = {Schluntz, Robert},
    25     title   = {Resource Management and Tuples in C$\mathbf{\forall}$},
    26     school      = {School of Computer Science, University of Waterloo},
    27     year        = 2017,
    28     address     = {Waterloo, Ontario, Canada, N2L 3G1},
    29     note    = {[[unpublished]]}
    30 }

  • doc/generic_types/generic_types.tex

    rf20dffa r6013bd7  
    2020        morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto,
    2121                _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__,
    22                 fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,sized,_Static_assert,
     22                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,_Static_assert,
    2323                _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t},
    2424}%
    … …  
    5757\acmJournal{PACMPL}
    5858
    59 \title{Generic and Tuple Types with Efficient Dynamic Layout in \CFA{}}
     59\title{Generic Types with Efficient Dynamic Layout in \CFA{}}
    6060
    6161\author{Aaron Moss}
    … …  
    9595\email{pabuhr@uwaterloo.ca}
    9696
    97 \terms{generic, tuple, types}
    98 \keywords{generic types, tuple types, polymorphic functions, C, Cforall}
     97\terms{generic, types}
     98\keywords{generic types, polymorphic functions, Cforall}
    9999
    100100\begin{CCSXML}
    … …  
    132132\section{Introduction \& Background}
    133133
    134 \CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or Cforall.} is an evolutionary extension of the C programming language which aims to add modern language features to C while maintaining both source compatibility with C and a familiar mental model for programmers. Four key design goals were set out in the original design of \CFA{} \citep{Bilson03}:
    135 \begin{enumerate}
    136 \item The behaviour of standard C code must remain the same when translated by a \CFA{} compiler as when translated by a C compiler.
    137 \item Standard C code must be as fast and as small when translated by a \CFA{} compiler as when translated by a C compiler.
    138 \item \CFA{} code must be at least as portable as standard C code.
    139 \item Extensions introduced by \CFA{} must be translated in the most efficient way possible.
    140 \end{enumerate}
    141 The purpose of these goals is to ensure that existing C codebases can be converted to \CFA{} incrementally and with minimal effort, and that programmers who already know C can productively produce \CFA{} code without extensive training beyond the extension features they wish to employ.
    142 
    143 \CFA{} has been previously extended with polymorphic functions and name overloading (including operator overloading) \citep{Bilson03}, and deterministically-executed constructors and destructors \citep{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA{} in accordance with both the backward compatibility goals and existing features described above.
     134\CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or Cforall.} is an evolutionary extension of the C programming language which aims to add modern language features to C while maintaining both source compatibility with C and a familiar mental model for programmers. This paper describes how generic types are designed and implemented in \CFA{}, and how they interact with \CFA{}'s polymorphic functions.
    144135
    145136\subsection{Polymorphic Functions}
    146 \label{sec:poly-fns}
    147137
    148138\CFA{}'s polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA{} is parametric-polymorphic functions; such functions are written using a @forall@ clause (which gives the language its name):
    … …  
    201191}
    202192\end{lstlisting}
    203 This capability allows specifying the same set of assertions in multiple locations, without the repetition and likelihood of mistakes that come with manually writing them out for each function declaration.
    204193
    205194@otype@ is essentially syntactic sugar for the following trait:
    … …  
    209198        void ?{}(T*);  // default constructor
    210199        void ?{}(T*, T);  // copy constructor
    211         void ?=?(T*, T);  // assignment operator
     200        T ?=?(T*, T);  // assignment operator
    212201        void ^?{}(T*);  // destructor
    213202};
    214 \end{lstlisting}
    215 Given this information, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @abs@ function above would produce generated code something like the following (simplified for clarity and brevity):
    216 \begin{lstlisting}
    217 void abs( size_t _sizeof_M, size_t _alignof_M,
    218                 void (*_ctor_M)(void*), void (*_copy_M)(void*, void*),
    219                 void (*_assign_M)(void*, void*), void (*_dtor_M)(void*),
    220                 bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*),
    221         void (*_ctor_M_zero)(void*, int),
    222                 void* m, void* _rtn ) {  // polymorphic parameter and return passed as void*
    223         // M zero = { 0 };
    224         void* zero = alloca(_sizeof_M);  // stack allocate 0 temporary
    225         _ctor_M_zero(zero, 0);  // initialize using zero_t constructor
    226         // return m < zero ? -m : m;
    227         void *_tmp = alloca(_sizeof_M)
    228         _copy_M( _rtn,  // copy-initialize return value
    229                 _lt_M( m, zero ) ?  // check condition
    230                  (_neg_M(m, _tmp), _tmp) :  // negate m
    231                  m);
    232         _dtor_M(_tmp); _dtor_M(zero);  // destroy temporaries
    233 }
    234203\end{lstlisting}
    235204
    … …  
    313282\end{lstlisting}
    314283
    315 Though \CFA{} implements concrete generic types efficiently, it also has a fully-general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also come with an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0.}. Access to members\footnote{The \lstinline@offsetof@ macro is implmented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where neccessary.
    316 
    317 \TODO{} Discuss caller-provided versus callee-provided offset arrays, layout functions.
    318 
    319 Whether a type is concrete, dtype-static, or dynamic is decided based solely on the type parameters and @forall@ clause on the struct declaration. This allows opaque forward declarations of generic types like @forall(otype T) struct Box;@ -- like in C, all uses of @Box(T)@ can be in a separately compiled translation unit, and callers from other translation units will know the proper calling conventions to use. If the definition of a struct type was included in the determination of dynamic or concrete, some further types may be recognized as dtype-static (\eg, @forall(otype T) struct unique_ptr { T* p };@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in this way is judged to be an appropriate trade-off.
    320 
    321 The re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers:
     284\TODO{} Maybe move this after the rest of the discussion.
     285This re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers:
    322286\begin{lstlisting}
    323287forall(dtype T)
    … …  
    347311scalar(metres) marathon = half_marathon + half_marathon;
    348312scalar(litres) two_pools = swimming_pool + swimming_pool;
    349 marathon + swimming_pool; // ERROR -- caught by compiler
     313marathon + swimming_pool; // ERRORv -- caught by compiler
    350314\end{lstlisting}
    351315@scalar@ is a dtype-static type, so all uses of it will use a single struct definition, containing only a single @unsigned long@, and can share the same implementations of common routines like @?+?@ -- these implementations may even be separately compiled, unlike \CC{} template functions. However, the \CFA{} type-checker will ensure that matching types are used by all calls to @?+?@, preventing nonsensical computations like adding the length of a marathon to the volume of an olympic pool.
    … …  
    359323\section{Related Work}
    360324
    361 \TODO{} Talk about \CC{}, Cyclone, maybe D, Rust, \etc{}
    362 
    363 A major difference between the approaches of \CC{} and \CFA{} to polymorphism is that the set of assumed properties for a type is \emph{explicit} in \CFA{}. One of the major limiting factors of \CC{}'s approach is that templates cannot be separately compiled. In contrast, the explicit nature of assertions allows \CFA{}'s polymorphic functions to be separately compiled.
    364 
    365 \section{Conclusion \& Future Work}
    366 
    367 \TODO{} Among future work, talk about ideas for selectively template-expanding code (on decls for specific types, or on calls for accessible decls).
     325\TODO{} Talk about \CC{}, Cyclone, \etc{}
     326
     327\section{Conclusion}
     328
     329\TODO{}
    368330
    369331\bibliographystyle{ACM-Reference-Format}

  • src/CodeGen/CodeGenerator.cc

    rf20dffa r6013bd7  
    147147
    148148        void CodeGenerator::visit( ObjectDecl * objectDecl ) {
    149                 if (objectDecl->get_name().empty()) {
    150                         static UniqueName name = { "__anonymous_object" };
    151                         objectDecl->set_name( name.newName() );
    152                 }
    153 
    154149                extension( objectDecl );
    155150                genAttributes( objectDecl->get_attributes() );

  • src/libcfa/Makefile.am

    rf20dffa r6013bd7  
    3535         ${AM_V_GEN}@BACKEND_CC@ @CFA_FLAGS@ -D__CFA_DEBUG__ -O0 -c -o $@ $<
    3636
    37 EXTRA_FLAGS = -g -Wall -Werror -Wno-unused-function -I${abs_top_srcdir}/src/libcfa/libhdr -imacros libcfa-prelude.c @CFA_FLAGS@
     37EXTRA_FLAGS = -g -Wall -Wno-unused-function -I${abs_top_srcdir}/src/libcfa/libhdr -imacros libcfa-prelude.c @CFA_FLAGS@
    3838
    3939AM_CCASFLAGS = @CFA_FLAGS@

  • src/libcfa/Makefile.in

    rf20dffa r6013bd7  
    305305AUTOMAKE_OPTIONS = subdir-objects
    306306lib_LIBRARIES = $(am__append_1) $(am__append_2)
    307 EXTRA_FLAGS = -g -Wall -Werror -Wno-unused-function -I${abs_top_srcdir}/src/libcfa/libhdr -imacros libcfa-prelude.c @CFA_FLAGS@
     307EXTRA_FLAGS = -g -Wall -Wno-unused-function -I${abs_top_srcdir}/src/libcfa/libhdr -imacros libcfa-prelude.c @CFA_FLAGS@
    308308AM_CCASFLAGS = @CFA_FLAGS@
    309309headers = limits stdlib math iostream fstream iterator rational assert \

  • src/tests/.expect/32/KRfunctions.txt

    rf20dffa r6013bd7  
    4747    int ___retval_f5__i_1;
    4848}
    49 int (*__f6__FPFi_i__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int __anonymous_object0){
    50     int (*___retval_f6__PFi_i__1)(int __anonymous_object1);
     49int (*__f6__FPFi_i__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int ){
     50    int (*___retval_f6__PFi_i__1)(int );
    5151}
    5252int (*__f7__FPFi_ii__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int __a__i_1, int __b__i_1){
    … …  
    6161int *(*__f10__FPFPi_ii__iPiPid__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1, double __y__d_1))(int __x__i_1, int __y__i_1){
    6262    int *(*___retval_f10__PFPi_ii__1)(int __x__i_1, int __y__i_1);
    63     int *__x__FPi_ii__2(int __anonymous_object2, int __anonymous_object3);
     63    int *__x__FPi_ii__2(int , int );
    6464    ((void)(___retval_f10__PFPi_ii__1=__x__FPi_ii__2) /* ?{} */);
    6565    return ((int *(*)(int __x__i_1, int __y__i_1))___retval_f10__PFPi_ii__1);
    … …  
    7979const int __fred__FCi___1(){
    8080    const int ___retval_fred__Ci_1;
    81     int *(*__x__PFPi_ii__2)(int __anonymous_object4, int __anonymous_object5);
     81    int *(*__x__PFPi_ii__2)(int , int );
    8282    int __a__i_2;
    8383    int __b__i_2;

  • src/tests/.expect/64/KRfunctions.txt

    rf20dffa r6013bd7  
    4747    int ___retval_f5__i_1;
    4848}
    49 int (*__f6__FPFi_i__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int __anonymous_object0){
    50     int (*___retval_f6__PFi_i__1)(int __anonymous_object1);
     49int (*__f6__FPFi_i__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int ){
     50    int (*___retval_f6__PFi_i__1)(int );
    5151}
    5252int (*__f7__FPFi_ii__iPiPi__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1))(int __a__i_1, int __b__i_1){
    … …  
    6161int *(*__f10__FPFPi_ii__iPiPid__1(int __a__i_1, int *__b__Pi_1, int *__c__Pi_1, double __y__d_1))(int __x__i_1, int __y__i_1){
    6262    int *(*___retval_f10__PFPi_ii__1)(int __x__i_1, int __y__i_1);
    63     int *__x__FPi_ii__2(int __anonymous_object2, int __anonymous_object3);
     63    int *__x__FPi_ii__2(int , int );
    6464    ((void)(___retval_f10__PFPi_ii__1=__x__FPi_ii__2) /* ?{} */);
    6565    return ((int *(*)(int __x__i_1, int __y__i_1))___retval_f10__PFPi_ii__1);
    … …  
    7979const int __fred__FCi___1(){
    8080    const int ___retval_fred__Ci_1;
    81     int *(*__x__PFPi_ii__2)(int __anonymous_object4, int __anonymous_object5);
     81    int *(*__x__PFPi_ii__2)(int , int );
    8282    int __a__i_2;
    8383    int __b__i_2;

  • src/tests/.expect/64/attributes.txt

    rf20dffa r6013bd7  
    5858    __attribute__ ((used,unused,unused)) int __f7__i_1;
    5959    __attribute__ ((used,used,unused)) int __f8__i_1;
    60     __attribute__ ((unused)) int __anonymous_object0;
     60    __attribute__ ((unused)) int ;
    6161    __attribute__ ((unused,unused)) int *__f9__Pi_1;
    6262};
    … …  
    226226    int **const ___retval_f2__CPPi_1;
    227227}
    228 __attribute__ ((unused,used,unused)) int (*__f3__FPA0i_i__1(int __anonymous_object1))[];
     228__attribute__ ((unused,used,unused)) int (*__f3__FPA0i_i__1(int ))[];
    229229__attribute__ ((unused,unused)) int (*__f3__FPA0i_i__1(int __p__i_1))[]{
    230230    int (*___retval_f3__PA0i_1)[];
    231231}
    232 __attribute__ ((unused,used,unused)) int (*__f4__FPFi_i____1())(int __anonymous_object2);
    233 __attribute__ ((unused,unused)) int (*__f4__FPFi_i____1())(int __anonymous_object3){
    234     int (*___retval_f4__PFi_i__1)(int __anonymous_object4);
     232__attribute__ ((unused,used,unused)) int (*__f4__FPFi_i____1())(int );
     233__attribute__ ((unused,unused)) int (*__f4__FPFi_i____1())(int ){
     234    int (*___retval_f4__PFi_i__1)(int );
    235235}
    236236__attribute__ ((__nothrow__,__leaf__,__malloc__)) extern void *malloc(long unsigned int __size);
    237237__attribute__ ((__nothrow__,__leaf__)) extern void free(void *__ptr);
    238238__attribute__ ((__nothrow__,__leaf__,__noreturn__)) extern void abort(void);
    239 __attribute__ ((__nothrow__,__leaf__,__nonnull__(1))) extern int atexit0(void (*__func)(void), void *__anonymous_object5, void *__anonymous_object6);
     239__attribute__ ((__nothrow__,__leaf__,__nonnull__(1))) extern int atexit0(void (*__func)(void), void *, void *);
    240240__attribute__ ((__nothrow__,__leaf__,__noreturn__)) extern void exit(int __status);
    241241__attribute__ ((format(printf, 1, 2))) extern int printf(const char *__restrict __format, ...);
    … …  
    268268int __tpr2__Fi_PPi__1(__attribute__ ((unused,unused,unused,unused,unused,unused)) int **__Foo__PPi_1);
    269269int __tpr3__Fi_Pi__1(__attribute__ ((unused,unused,unused)) int *__Foo__Pi_1);
    270 int __tpr4__Fi_PFi_Pi___1(__attribute__ ((unused,unused)) int (*__anonymous_object7)(__attribute__ ((unused,unused)) int __anonymous_object8[((long unsigned int )5)]));
     270int __tpr4__Fi_PFi_Pi___1(__attribute__ ((unused,unused)) int (*)(__attribute__ ((unused,unused)) int [((long unsigned int )5)]));
    271271int __tpr5__Fi_PFi____1(__attribute__ ((unused,unused,unused)) int (*__Foo__PFi___1)());
    272272int __tpr6__Fi_PFi____1(__attribute__ ((unused,unused,unused)) int (*__Foo__PFi___1)());
    273 int __tpr7__Fi_PFi_PFi_i____1(__attribute__ ((unused,unused)) int (*__anonymous_object9)(__attribute__ ((unused)) int (*__anonymous_object10)(__attribute__ ((unused,unused)) int __anonymous_object11)));
     273int __tpr7__Fi_PFi_PFi_i____1(__attribute__ ((unused,unused)) int (*)(__attribute__ ((unused)) int (*)(__attribute__ ((unused,unused)) int )));
    274274int __ad__Fi___1(){
    275275    int ___retval_ad__i_1;
    … …  
    320320    ((void)sizeof(enum __anonymous5 ));
    321321}
    322 int __apd1__Fi_PiPi__1(__attribute__ ((unused,unused,unused)) int *__anonymous_object12, __attribute__ ((unused,unused,unused)) int *__anonymous_object13);
    323 int __apd2__Fi_PPiPPi__1(__attribute__ ((unused,unused,unused,unused)) int **__anonymous_object14, __attribute__ ((unused,unused,unused,unused)) int **__anonymous_object15);
    324 int __apd3__Fi_PiPi__1(__attribute__ ((unused,unused,unused)) int *__anonymous_object16, __attribute__ ((unused,unused,unused)) int *__anonymous_object17);
    325 int __apd4__Fi_PFi__PFi____1(__attribute__ ((unused,unused,unused)) int (*__anonymous_object18)(), __attribute__ ((unused,unused,unused)) int (*__anonymous_object19)());
    326 int __apd5__Fi_PFi_i_PFi_i___1(__attribute__ ((unused,unused,unused)) int (*__anonymous_object20)(__attribute__ ((unused)) int __anonymous_object21), __attribute__ ((unused,unused,unused)) int (*__anonymous_object22)(__attribute__ ((unused)) int __anonymous_object23));
    327 int __apd6__Fi_PFi__PFi____1(__attribute__ ((unused,unused,unused)) int (*__anonymous_object24)(), __attribute__ ((unused,unused,unused)) int (*__anonymous_object25)());
    328 int __apd7__Fi_PFi_i_PFi_i___1(__attribute__ ((unused,unused,unused)) int (*__anonymous_object26)(__attribute__ ((unused)) int __anonymous_object27), __attribute__ ((unused,unused,unused)) int (*__anonymous_object28)(__attribute__ ((unused)) int __anonymous_object29));
     322int __apd1__Fi_PiPi__1(__attribute__ ((unused,unused,unused)) int *, __attribute__ ((unused,unused,unused)) int *);
     323int __apd2__Fi_PPiPPi__1(__attribute__ ((unused,unused,unused,unused)) int **, __attribute__ ((unused,unused,unused,unused)) int **);
     324int __apd3__Fi_PiPi__1(__attribute__ ((unused,unused,unused)) int *, __attribute__ ((unused,unused,unused)) int *);
     325int __apd4__Fi_PFi__PFi____1(__attribute__ ((unused,unused,unused)) int (*)(), __attribute__ ((unused,unused,unused)) int (*)());
     326int __apd5__Fi_PFi_i_PFi_i___1(__attribute__ ((unused,unused,unused)) int (*)(__attribute__ ((unused)) int ), __attribute__ ((unused,unused,unused)) int (*)(__attribute__ ((unused)) int ));
     327int __apd6__Fi_PFi__PFi____1(__attribute__ ((unused,unused,unused)) int (*)(), __attribute__ ((unused,unused,unused)) int (*)());
     328int __apd7__Fi_PFi_i_PFi_i___1(__attribute__ ((unused,unused,unused)) int (*)(__attribute__ ((unused)) int ), __attribute__ ((unused,unused,unused)) int (*)(__attribute__ ((unused)) int ));
    329329struct Vad {
    330     __attribute__ ((unused)) int __anonymous_object30;
    331     __attribute__ ((unused,unused)) int *__anonymous_object31;
    332     __attribute__ ((unused,unused)) int __anonymous_object32[((long unsigned int )10)];
    333     __attribute__ ((unused,unused)) int (*__anonymous_object33)();
     330    __attribute__ ((unused)) int ;
     331    __attribute__ ((unused,unused)) int *;
     332    __attribute__ ((unused,unused)) int [((long unsigned int )10)];
     333    __attribute__ ((unused,unused)) int (*)();
    334334};
    335335static inline void ___constructor__F_P4sVad_autogen___1(struct Vad *___dst__P4sVad_1);

  • src/tests/Makefile.am

    rf20dffa r6013bd7  
    5151        @+python test.py --list --concurrent=${concurrent}
    5252
    53 .dummy : .dummy.c
    54         ${CC} ${CFLAGS} -XCFA -n ${<} -o ${@}
    55 
    5653constant0-1DP : constant0-1.c
    5754        ${CC} ${CFLAGS} -DDUPS ${<} -o ${@}

  • src/tests/Makefile.in

    rf20dffa r6013bd7  
    669669        @+python test.py --list --concurrent=${concurrent}
    670670
    671 .dummy : .dummy.c
    672         ${CC} ${CFLAGS} -XCFA -n ${<} -o ${@}
    673 
    674671constant0-1DP : constant0-1.c
    675672        ${CC} ${CFLAGS} -DDUPS ${<} -o ${@}

  • src/tests/test.py

    rf20dffa r6013bd7  
    2525# parses the Makefile to find the machine type (32-bit / 64-bit)
    2626def getMachineType():
    27         sh('echo "void ?{}(int*a,int b){}int main(){return 0;}" > .dummy.c')
     27        sh('echo "int main() { return 0; }" > .dummy.c')
    2828        sh("make .dummy", print2stdout=False)
    2929        _, out = sh("file .dummy", print2stdout=False)
Note: See TracChangeset for help on using the changeset viewer.