Changeset 67d2b97


Ignore:
Timestamp:
Jun 24, 2019, 2:24:57 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
093a5d7, da7454c
Parents:
70a141d4 (diff), 08c0780 (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:
17 edited

Legend:

Unmodified
Added
Removed
  • Jenkinsfile

    r70a141d4 r67d2b97  
    130130                        //Run the tests from the tests directory
    131131                        if ( Settings.RunAllTests ) {
    132                                 sh 'make --no-print-directory -C tests timeouts="--timeout=600" all-tests debug=yes'
    133                                 sh 'make --no-print-directory -C tests timeouts="--timeout=600" all-tests debug=no '
     132                                sh 'make --no-print-directory -C tests timeouts="--timeout=1200" all-tests debug=yes'
     133                                sh 'make --no-print-directory -C tests timeouts="--timeout=1200" all-tests debug=no '
    134134                        }
    135135                        else {
  • doc/papers/concurrency/Paper.tex

    r70a141d4 r67d2b97  
    27052705\label{results}
    27062706
    2707 To verify the implementation of the \CFA runtime, a series of microbenchmarks are performed comparing \CFA with Java OpenJDK-9, Go 1.9.2 and \uC 7.0.0.
    2708 The benchmark computer is an AMD Opteron\texttrademark\ 6380 NUMA 64-core, 8 socket, 2.5 GHz processor, running Ubuntu 16.04.6 LTS, and \uC/\CFA are compiled with gcc 6.5.
    2709 
    2710 \begin{comment}
    2711 \begin{table}
    2712 \centering
    2713 \caption{Experiment environment}
    2714 \label{t:machine}
    2715 
    2716 \begin{tabular}{|l|r||l|r|}
    2717 \hline
    2718 Architecture            & x86\_64                               & NUMA node(s)  & 8 \\
    2719 \hline
    2720 CPU op-mode(s)          & 32-bit, 64-bit                & Model name    & AMD Opteron\texttrademark\ Processor 6380 \\
    2721 \hline
    2722 Byte Order                      & Little Endian                 & CPU Freq              & 2.5 GHz \\
    2723 \hline
    2724 CPU(s)                          & 64                                    & L1d cache     & 16 KiB \\
    2725 \hline
    2726 Thread(s) per core      & 2                                     & L1i cache     & 64 KiB \\
    2727 \hline
    2728 Core(s) per socket      & 8                                     & L2 cache              & 2048 KiB \\
    2729 \hline
    2730 Socket(s)                       & 4                                     & L3 cache              & 6144 KiB \\
    2731 \hline
    2732 \hline
    2733 Operating system        & Ubuntu 16.04.3 LTS    & Kernel                & Linux 4.4-97-generic \\
    2734 \hline
    2735 gcc                                     & 6.3                                   & \CFA                  & 1.0.0 \\
    2736 \hline
    2737 Java                            & OpenJDK-9                     & Go                    & 1.9.2 \\
    2738 \hline
    2739 \end{tabular}
    2740 \end{table}
    2741 \end{comment}
     2707To verify the implementation of the \CFA runtime, a series of microbenchmarks are performed comparing \CFA with pthreads, Java OpenJDK-9, Go 1.12.6 and \uC 7.0.0.
     2708For comparison, the package must be multi-processor (M:N), which excludes libdill/libmil~\cite{libdill} (M:1)), and use a shared-memory programming model, \eg not message passing.
     2709The benchmark computer is an AMD Opteron\texttrademark\ 6380 NUMA 64-core, 8 socket, 2.5 GHz processor, running Ubuntu 16.04.6 LTS, and \CFA/\uC are compiled with gcc 6.5.
    27422710
    27432711All benchmarks are run using the following harness.
     
    27492717Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark;
    27502718the total time is divided by @N@ to obtain the average time for a benchmark.
     2719Each benchmark experiment is run 31 times.
    27512720All omitted tests for other languages are functionally identical to the \CFA tests and available online~\cite{CforallBenchMarks}.
    27522721
     
    27792748\begin{tabular}[t]{@{}r*{3}{D{.}{.}{5.2}}@{}}
    27802749\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    2781 Pthreads                                & 28091         & 28073.39      & 163.1         \\
    2782 \CFA Coroutine Lazy             & 6                     & 6.07          & 0.26          \\
    2783 \CFA Coroutine Eager    & 520           & 520.61        & 2.04          \\
    2784 \CFA Thread                             & 2032          & 2016.29       & 112.07        \\
    2785 \uC Coroutine                   & 106           & 107.36        & 1.47          \\
    2786 \uC Thread                              & 536.5         & 537.07        & 4.64          \\
    2787 Goroutine                               & 3103          & 3086.29       & 90.25         \\
    2788 Java Thread                             & 103416.5      & 103732.29     & 1137          \\
     2750\CFA Coroutine Lazy             & 14.3          & 14.3          & 0.32          \\
     2751\CFA Coroutine Eager    & 2203.7        & 2205.6        & 26.03         \\
     2752\CFA Thread                             & 1257.8        & 1291.2        & 86.19         \\
     2753\uC Coroutine                   & 92.2          & 91.4          & 1.58          \\
     2754\uC Thread                              & 499.5         & 500.1         & 5.67          \\
     2755Goroutine                               & 4397.0        & 4362.8        & 390.77        \\
     2756Java Thread                             & 107405.0      & 107794.8      & 1601.33       \\
     2757% Qthreads                              & 159.9         & 159.6         & 0.73          \\
     2758Pthreads                                & 32920.9       & 32882.7       & 213.55
     2759\end{tabular}
     2760\end{multicols}
     2761
     2762
     2763\paragraph{Internal Scheduling}
     2764
     2765Internal scheduling is measured using a cycle of two threads signalling and waiting.
     2766Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}.
     2767Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
     2768Java scheduling is significantly greater because the benchmark explicitly creates multiple thread in order to prevent the JIT from making the program sequential, \ie removing all locking.
     2769
     2770\begin{multicols}{2}
     2771\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2772\begin{cfa}
     2773volatile int go = 0;
     2774@monitor@ M { @condition c;@ } m;
     2775void __attribute__((noinline))
     2776do_call( M & @mutex@ a1 ) { @signal( c );@ }
     2777thread T {};
     2778void main( T & this ) {
     2779        while ( go == 0 ) { yield(); }
     2780        while ( go == 1 ) { do_call( m ); }
     2781}
     2782int  __attribute__((noinline))
     2783do_wait( M & mutex m ) with(m) {
     2784        go = 1; // continue other thread
     2785        BENCH( for ( N ) { @wait( c );@ } );
     2786        go = 0; // stop other thread
     2787        sout | result`ns;
     2788}
     2789int main() {
     2790        T t;
     2791        do_wait( m );
     2792}
     2793\end{cfa}
     2794\captionof{figure}{\CFA Internal-scheduling benchmark}
     2795\label{f:int-sched}
     2796
     2797\columnbreak
     2798
     2799\vspace*{-16pt}
     2800\captionof{table}{Internal-scheduling comparison (nanoseconds)}
     2801\label{tab:int-sched}
     2802\bigskip
     2803
     2804\begin{tabular}{@{}r*{3}{D{.}{.}{5.2}}@{}}
     2805\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
     2806\CFA @signal@, 1 @monitor@      & 367.0         & 371.5         & 17.34         \\
     2807\CFA @signal@, 2 @monitor@      & 477.2         & 478.6         & 8.31          \\
     2808\CFA @signal@, 4 @monitor@      & 725.8         & 734.0         & 17.98         \\
     2809\uC @signal@                            & 322.8         & 323.0         & 3.64          \\
     2810Java @notify@                           & 16520.0       & 20096.7       & 9378.53       \\
     2811Pthreads Cond. Variable         & 4931.3        & 5057.0        & 326.80
     2812\end{tabular}
     2813\end{multicols}
     2814
     2815
     2816\paragraph{External Scheduling}
     2817
     2818External scheduling is measured using a cycle of two threads calling and accepting the call using the @waitfor@ statement.
     2819Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}.
     2820Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
     2821
     2822\begin{multicols}{2}
     2823\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2824\vspace*{-16pt}
     2825\begin{cfa}
     2826volatile int go = 0;
     2827@monitor@ M {} m;
     2828thread T {};
     2829void __attribute__((noinline))
     2830do_call( M & @mutex@ ) {}
     2831void main( T & ) {
     2832        while ( go == 0 ) { yield(); }
     2833        while ( go == 1 ) { do_call( m ); }
     2834}
     2835int __attribute__((noinline))
     2836do_wait( M & @mutex@ m ) {
     2837        go = 1; // continue other thread
     2838        BENCH( for ( N ) { @waitfor( do_call, m );@ } )
     2839        go = 0; // stop other thread
     2840        sout | result`ns;
     2841}
     2842int main() {
     2843        T t;
     2844        do_wait( m );
     2845}
     2846\end{cfa}
     2847\captionof{figure}{\CFA external-scheduling benchmark}
     2848\label{f:ext-sched}
     2849
     2850\columnbreak
     2851
     2852\vspace*{-16pt}
     2853\captionof{table}{External-scheduling comparison (nanoseconds)}
     2854\label{tab:ext-sched}
     2855\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}}
     2856\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
     2857\CFA @waitfor@, 1 @monitor@     & 366.7         & 369.5 & 7.52  \\
     2858\CFA @waitfor@, 2 @monitor@     & 453.6         & 455.8 & 12.38 \\
     2859\CFA @waitfor@, 4 @monitor@     & 671.6         & 672.4 & 14.16 \\
     2860\uC @_Accept@                           & 336.0         & 335.8         & 3.22
    27892861\end{tabular}
    27902862\end{multicols}
     
    28252897\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}}
    28262898\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    2827 C function              & 2                     & 2             & 0             \\
    2828 \CFA generator  & 2                     & 2             & 0             \\
    2829 \CFA Coroutine  & 49    & 48.68         & 0.47  \\
    2830 \CFA Thread             & 105   & 105.57        & 1.37  \\
    2831 \uC Coroutine   & 44    & 44            & 0             \\
    2832 \uC Thread              & 100   & 99.29         & 0.96  \\
    2833 Goroutine               & 145   & 147.25        & 4.15  \\
    2834 Java Thread             & 373.5 & 375.14        & 8.72  \\
    2835 Pthreads Thread & 333.5 & 332.96        & 4.1
     2899C function              & 1.8           & 1.8   & 0             \\
     2900\CFA generator  & 2.7           & 2.4   & 0.27  \\
     2901\CFA Coroutine  & 37.8          & 37.7  & 0.22  \\
     2902\CFA Thread             & 93.6          & 93.8  & 1.46  \\
     2903\uC Coroutine   & 52.7          & 52.8  & 0.28  \\
     2904\uC Thread              & 93.4          & 93.7  & 1.04  \\
     2905Goroutine               & 140.0         & 139.7 & 2.93  \\
     2906Java Thread             & 374.0         & 375.8 & 10.38 \\
     2907% Qthreads Thread       & 159.5         & 159.3 & 0.71  \\
     2908Pthreads Thread & 334.4         & 335.0 & 1.95  \\
    28362909\end{tabular}
    28372910\end{multicols}
     
    28692942\begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}}
    28702943\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    2871 test and test-and-test lock             & 26            & 26    & 0             \\
    2872 Pthreads Mutex Lock                             & 31            & 31.71 & 0.97  \\
    2873 \uC @monitor@ member rtn.               & 31            & 31    & 0             \\
    2874 \CFA @mutex@ function, 1 arg.   & 46            & 46.68 & 0.93  \\
    2875 \CFA @mutex@ function, 2 arg.   & 84            & 85.36 & 1.99  \\
    2876 \CFA @mutex@ function, 4 arg.   & 158           & 161   & 4.22  \\
    2877 Java synchronized method                & 27.5          & 29.79 & 2.93
    2878 \end{tabular}
    2879 \end{multicols}
    2880 
    2881 
    2882 \paragraph{Internal Scheduling}
    2883 
    2884 Internal scheduling is measured using a cycle of two threads signalling and waiting.
    2885 Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}.
    2886 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
    2887 Java scheduling is significantly greater because the benchmark explicitly creates multiple thread in order to prevent the JIT from making the program sequential, \ie removing all locking.
    2888 
    2889 \begin{multicols}{2}
    2890 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
    2891 \begin{cfa}
    2892 volatile int go = 0;
    2893 @monitor@ M { @condition c;@ } m;
    2894 void __attribute__((noinline))
    2895 do_call( M & @mutex@ a1 ) { @signal( c );@ }
    2896 thread T {};
    2897 void main( T & this ) {
    2898         while ( go == 0 ) { yield(); }
    2899         while ( go == 1 ) { do_call( m ); }
    2900 }
    2901 int  __attribute__((noinline))
    2902 do_wait( M & mutex m ) with(m) {
    2903         go = 1; // continue other thread
    2904         BENCH( for ( N ) { @wait( c );@ } );
    2905         go = 0; // stop other thread
    2906         sout | result`ns;
    2907 }
    2908 int main() {
    2909         T t;
    2910         do_wait( m );
    2911 }
    2912 \end{cfa}
    2913 \captionof{figure}{\CFA Internal-scheduling benchmark}
    2914 \label{f:int-sched}
    2915 
    2916 \columnbreak
    2917 
    2918 \vspace*{-16pt}
    2919 \captionof{table}{Internal-scheduling comparison (nanoseconds)}
    2920 \label{tab:int-sched}
    2921 \bigskip
    2922 
    2923 \begin{tabular}{@{}r*{3}{D{.}{.}{5.2}}@{}}
    2924 \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    2925 Pthreads Cond. Variable         & 6005          & 5681.43       & 835.45        \\
    2926 \uC @signal@                            & 324           & 325.54        & 3.02          \\
    2927 \CFA @signal@, 1 @monitor@      & 368.5         & 370.61        & 4.77          \\
    2928 \CFA @signal@, 2 @monitor@      & 467           & 470.5         & 6.79          \\
    2929 \CFA @signal@, 4 @monitor@      & 700.5         & 702.46        & 7.23          \\
    2930 Java @notify@                           & 15471         & 172511        & 5689
    2931 \end{tabular}
    2932 \end{multicols}
    2933 
    2934 
    2935 \paragraph{External Scheduling}
    2936 
    2937 External scheduling is measured using a cycle of two threads calling and accepting the call using the @waitfor@ statement.
    2938 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}.
    2939 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
    2940 
    2941 \begin{multicols}{2}
    2942 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
    2943 \vspace*{-16pt}
    2944 \begin{cfa}
    2945 volatile int go = 0;
    2946 @monitor@ M {} m;
    2947 thread T {};
    2948 void __attribute__((noinline))
    2949 do_call( M & @mutex@ ) {}
    2950 void main( T & ) {
    2951         while ( go == 0 ) { yield(); }
    2952         while ( go == 1 ) { do_call( m ); }
    2953 }
    2954 int __attribute__((noinline))
    2955 do_wait( M & @mutex@ m ) {
    2956         go = 1; // continue other thread
    2957         BENCH( for ( N ) { @waitfor( do_call, m );@ } )
    2958         go = 0; // stop other thread
    2959         sout | result`ns;
    2960 }
    2961 int main() {
    2962         T t;
    2963         do_wait( m );
    2964 }
    2965 \end{cfa}
    2966 \captionof{figure}{\CFA external-scheduling benchmark}
    2967 \label{f:ext-sched}
    2968 
    2969 \columnbreak
    2970 
    2971 \vspace*{-16pt}
    2972 \captionof{table}{External-scheduling comparison (nanoseconds)}
    2973 \label{tab:ext-sched}
    2974 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}}
    2975 \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    2976 \uC @_Accept@                           & 358           & 359.11        & 2.53          \\
    2977 \CFA @waitfor@, 1 @monitor@     & 359           & 360.93        & 4.07          \\
    2978 \CFA @waitfor@, 2 @monitor@     & 450           & 449.39        & 6.62          \\
    2979 \CFA @waitfor@, 4 @monitor@     & 652           & 655.64        & 7.73
     2944test and test-and-test lock             & 19.1  & 19.0  & 0.36  \\
     2945\CFA @mutex@ function, 1 arg.   & 46.6  & 46.8  & 0.86  \\
     2946\CFA @mutex@ function, 2 arg.   & 84.1  & 85.3  & 1.86  \\
     2947\CFA @mutex@ function, 4 arg.   & 158.6 & 160.7 & 3.07  \\
     2948\uC @monitor@ member rtn.               & 54.0  & 53.7  & 0.83  \\
     2949Java synchronized method                & 27.0  & 27.1  & 0.25  \\
     2950Pthreads Mutex Lock                             & 33.6  & 32.7  & 1.12
    29802951\end{tabular}
    29812952\end{multicols}
  • driver/cc1.cc

    r70a141d4 r67d2b97  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // cc1.cc -- 
     7// cc1.cc --
    88//
    99// Author           : Peter A. Buhr
     
    107107        if ( tmpfilefd != -1 ) {                                                        // RACE, file created ?
    108108                rmtmpfile();                                                                    // remove
    109                 exit( EXIT_FAILURE );                                                   // terminate 
     109                exit( EXIT_FAILURE );                                                   // terminate
    110110        } // if
    111111} // sigTermHandler
     
    360360
    361361                #ifdef __DEBUG_H__
    362                 cerr << "cfa-cpp ncargs: " << o_name << " " << CFA_flag << " " << ncargs << endl;
     362                cerr << "cfa-cpp ncargs: " << (o_name ? o_name : "No -o") << " " << CFA_flag << " " << ncargs << endl;
    363363                for ( int i = 0; cargs[i] != NULL; i += 1 ) {
    364364                        cerr << cargs[i] << " ";
  • src/AST/Convert.cpp

    r70a141d4 r67d2b97  
    18951895                };
    18961896                stmt->orElse = {
    1897                         GET_ACCEPT_1(timeout.statement, Stmt),
    1898                         GET_ACCEPT_1(timeout.condition, Expr),
     1897                        GET_ACCEPT_1(orelse.statement, Stmt),
     1898                        GET_ACCEPT_1(orelse.condition, Expr),
    18991899                };
    19001900
  • src/AST/Fwd.hpp

    r70a141d4 r67d2b97  
    1010// Created On       : Wed May  8 16:05:00 2019
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Thr May  9 13:09:00 2019
    13 // Update Count     : 0
     12// Last Modified On : Mon Jun 24 09:48:00 2019
     13// Update Count     : 1
    1414//
    1515
     
    129129class Attribute;
    130130
     131class SymbolTable;
     132class TypeEnvironment;
    131133class TypeSubstitution;
    132134
  • src/AST/Node.hpp

    r70a141d4 r67d2b97  
    100100
    101101/// Mutate a node field (only clones if not equal to existing value)
    102 template<typename node_t, typename field_t, typename assn_t>
    103 const node_t * mutate_field( const node_t * node, field_t node_t::* field, assn_t && val ) {
     102template<typename node_t, typename parent_t, typename field_t, typename assn_t>
     103const node_t * mutate_field( const node_t * node, field_t parent_t::* field, assn_t && val ) {
    104104        // skip mutate if equivalent
    105105        if ( node->*field == val ) return node;
     
    112112
    113113/// Mutate a single index of a node field (only clones if not equal to existing value)
    114 template<typename node_t, typename coll_t, typename ind_t, typename field_t>
     114template<typename node_t, typename parent_t, typename coll_t, typename ind_t, typename field_t>
    115115const node_t * mutate_field_index(
    116         const node_t * node, coll_t node_t::* field, ind_t i, field_t && val
     116        const node_t * node, coll_t parent_t::* field, ind_t i, field_t && val
    117117) {
    118118        // skip mutate if equivalent
  • src/AST/TypeSubstitution.hpp

    r70a141d4 r67d2b97  
    200200}
    201201
    202 /// Instantiate each member of the context given the actual parameters specified, and store the
    203 /// instantiations for use by the indexer
    204 template< typename FormalIterator, typename ActualIterator, typename MemberIterator, typename OutputIterator >
    205 void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) {
    206         TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual );
    207         for ( auto i = memberBegin; i != memberEnd; ++i ) {
    208                 sub.apply( *i );
    209                 *out++ = *i;
    210         } // for
    211 }
    212 
    213202} // namespace ast
    214203
  • src/ResolvExpr/CandidateFinder.cpp

    r70a141d4 r67d2b97  
    10031003                        assert( toType );
    10041004                        toType = resolveTypeof( toType, symtab );
    1005                         toType = SymTab::validateType( toType, symtab );
     1005                        toType = SymTab::validateType( castExpr->location, toType, symtab );
    10061006                        toType = adjustExprType( toType, tenv, symtab );
    10071007
     
    14101410                                // calculate target type
    14111411                                const ast::Type * toType = resolveTypeof( initAlt.type, symtab );
    1412                                 toType = SymTab::validateType( toType, symtab );
     1412                                toType = SymTab::validateType( initExpr->location, toType, symtab );
    14131413                                toType = adjustExprType( toType, tenv, symtab );
    14141414                                // The call to find must occur inside this loop, otherwise polymorphic return
  • src/ResolvExpr/ConversionCost.cc

    r70a141d4 r67d2b97  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 07:06:19 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon May  6 14:18:22 2019
    13 // Update Count     : 25
     11// Last Modified By : Andrew Beach
     12// Last Modified On : Mon Jun 24 13:33:00 2019
     13// Update Count     : 26
    1414//
    1515
     
    489489        }
    490490
    491         Cost conversionCost(
    492                 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
    493                 const ast::TypeEnvironment & env
    494         ) {
    495                 #warning unimplemented
    496                 (void)src; (void)dst; (void)symtab; (void)env;
    497                 assert(false);
     491static int localPtrsAssignable(const ast::Type * t1, const ast::Type * t2,
     492                const ast::SymbolTable &, const ast::TypeEnvironment & env ) {
     493        return ptrsAssignable( t1, t2, env );
     494}
     495
     496// TODO: This is used for overload resolution. It might be able to be dropped once the old system
     497// is removed.
     498static Cost localConversionCost(
     499        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     500        const ast::TypeEnvironment & env
     501) { return conversionCost( src, dst, symtab, env ); }
     502
     503Cost conversionCost(
     504        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     505        const ast::TypeEnvironment & env
     506) {
     507        if ( const ast::TypeInstType * inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
     508                if ( const ast::EqvClass * eqv = env.lookup( inst->name ) ) {
     509                        if ( eqv->bound ) {
     510                                return conversionCost(src, eqv->bound, symtab, env );
     511                        } else {
     512                                return Cost::infinity;
     513                        }
     514                } else if ( const ast::NamedTypeDecl * named = symtab.lookupType( inst->name ) ) {
     515                        const ast::TypeDecl * type = dynamic_cast< const ast::TypeDecl * >( named );
     516                        assertf( type, "Unexpected typedef." );
     517                        if ( type->base ) {
     518                                return conversionCost( src, type->base, symtab, env ) + Cost::safe;
     519                        }
     520                }
     521        }
     522        if ( typesCompatibleIgnoreQualifiers( src, dst, symtab, env ) ) {
    498523                return Cost::zero;
    499         }
     524        } else if ( dynamic_cast< const ast::VoidType * >( dst ) ) {
     525                return Cost::safe;
     526        } else if ( const ast::ReferenceType * refType =
     527                         dynamic_cast< const ast::ReferenceType * >( dst ) ) {
     528                return convertToReferenceCost( src, refType, symtab, env, localPtrsAssignable );
     529        } else {
     530                ast::Pass<ConversionCost_new> converter( dst, symtab, env, localConversionCost );
     531                src->accept( converter );
     532                return converter.pass.cost;
     533        }
     534}
     535
     536Cost convertToReferenceCost( const ast::Type * src, const ast::Type * dst, int diff,
     537                const ast::SymbolTable & symtab, const ast::TypeEnvironment & env,
     538                NumCostCalculation func ) {
     539        if ( 0 < diff ) {
     540                Cost cost = convertToReferenceCost(
     541                        strict_dynamic_cast< const ast::ReferenceType * >( src )->base,
     542                        dst, (diff - 1), symtab, env, func );
     543                cost.incReference();
     544                return cost;
     545        } else if ( diff < -1 ) {
     546                Cost cost = convertToReferenceCost(
     547                        src, strict_dynamic_cast< const ast::ReferenceType * >( dst )->base,
     548                        (diff + 1), symtab, env, func );
     549                cost.incReference();
     550                return cost;
     551        } else if ( 0 == diff ) {
     552                const ast::ReferenceType * srcAsRef = dynamic_cast< const ast::ReferenceType * >( src );
     553                const ast::ReferenceType * dstAsRef = dynamic_cast< const ast::ReferenceType * >( dst );
     554                if ( srcAsRef && dstAsRef ) {
     555                        ast::CV::Qualifiers tq1 = srcAsRef->base->qualifiers;
     556                        ast::CV::Qualifiers tq2 = dstAsRef->base->qualifiers;
     557                        if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers(
     558                                        srcAsRef->base, dstAsRef->base, symtab, env ) ) {
     559                                if ( tq1 == tq2 ) {
     560                                        return Cost::zero;
     561                                } else {
     562                                        return Cost::safe;
     563                                }
     564                        } else {
     565                                int assignResult = func( srcAsRef->base, dstAsRef->base, symtab, env );
     566                                if ( 0 < assignResult ) {
     567                                        return Cost::safe;
     568                                } else if ( assignResult < 0 ) {
     569                                        return Cost::unsafe;
     570                                }
     571                        }
     572                } else {
     573                        ast::Pass<ConversionCost_new> converter( dst, symtab, env, localConversionCost );
     574                        src->accept( converter );
     575                        return converter.pass.cost;
     576                }
     577        } else {
     578                assert( -1 == diff );
     579                const ast::ReferenceType * dstAsRef = dynamic_cast< const ast::ReferenceType * >( dst );
     580                assert( dstAsRef );
     581                if ( typesCompatibleIgnoreQualifiers( src, dstAsRef->base, symtab, env ) ) {
     582                        if ( src->is_lvalue() ) {
     583                                if ( src->qualifiers == dstAsRef->base->qualifiers ) {
     584                                        return Cost::reference;
     585                                } else if ( src->qualifiers < dstAsRef->base->qualifiers ) {
     586                                        return Cost::safe;
     587                                } else {
     588                                        return Cost::unsafe;
     589                                }
     590                        } else if ( dstAsRef->base->is_const() ) {
     591                                return Cost::safe;
     592                        } else {
     593                                return Cost::unsafe;
     594                        }
     595                }
     596        }
     597        return Cost::infinity;
     598}
     599
     600Cost convertToReferenceCost( const ast::Type * src, const ast::ReferenceType * dst,
     601            const ast::SymbolTable & symtab, const ast::TypeEnvironment & env,
     602                NumCostCalculation func ) {
     603        int sdepth = src->referenceDepth(), ddepth = dst->referenceDepth();
     604        return convertToReferenceCost( src, dst, sdepth - ddepth, symtab, env, func );
     605}
     606
     607void ConversionCost_new::postvisit( const ast::VoidType * voidType ) {
     608        (void)voidType;
     609        cost = Cost::infinity;
     610}
     611
     612void ConversionCost_new::postvisit( const ast::BasicType * basicType ) {
     613        if ( const ast::BasicType * dstAsBasic = dynamic_cast< const ast::BasicType * >( dst ) ) {
     614                int tableResult = costMatrix[ basicType->kind ][ dstAsBasic->kind ];
     615                if ( tableResult == -1 ) {
     616                        cost = Cost::unsafe;
     617                } else {
     618                        cost = Cost::zero;
     619                        cost.incSafe( tableResult );
     620                        cost.incSign( signMatrix[ basicType->kind ][ dstAsBasic->kind ] );
     621                }
     622        } else if ( dynamic_cast< const ast::EnumInstType * >( dst ) ) {
     623                // xxx - not positive this is correct, but appears to allow casting int => enum
     624                cost = Cost::unsafe;
     625        }
     626}
     627
     628void ConversionCost_new::postvisit( const ast::PointerType * pointerType ) {
     629        if ( const ast::PointerType * dstAsPtr = dynamic_cast< const ast::PointerType * >( dst ) ) {
     630                ast::CV::Qualifiers tq1 = pointerType->base->qualifiers;
     631                ast::CV::Qualifiers tq2 = dstAsPtr->base->qualifiers;
     632                if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers(
     633                                pointerType->base, dstAsPtr->base, symtab, env ) ) {
     634                        if ( tq1 == tq2 ) {
     635                                cost = Cost::zero;
     636                        } else {
     637                                cost = Cost::safe;
     638                        }
     639                } else {
     640                        int assignResult = ptrsAssignable( pointerType->base, dstAsPtr->base, env );
     641                        if ( 0 < assignResult && tq1 <= tq2 ) {
     642                                if ( tq1 == tq2 ) {
     643                                        cost = Cost::safe;
     644                                } else {
     645                                        cost = Cost::safe + Cost::safe;
     646                                }
     647                        } else if ( assignResult < 0 ) {
     648                                cost = Cost::unsafe;
     649                        } // else Cost::infinity
     650                }
     651        }
     652}
     653
     654void ConversionCost_new::postvisit( const ast::ArrayType * arrayType ) {
     655        (void)arrayType;
     656}
     657
     658void ConversionCost_new::postvisit( const ast::ReferenceType * refType ) {
     659        assert( nullptr == dynamic_cast< const ast::ReferenceType * >( dst ) );
     660
     661        cost = costCalc( refType->base, dst, symtab, env );
     662        if ( refType->base->qualifiers == dst->qualifiers ) {
     663                cost.incReference();
     664        } else if ( refType->base->qualifiers < dst->qualifiers ) {
     665                cost.incSafe();
     666        } else {
     667                cost.incUnsafe();
     668        }
     669}
     670
     671void ConversionCost_new::postvisit( const ast::FunctionType * functionType ) {
     672        (void)functionType;
     673}
     674
     675void ConversionCost_new::postvisit( const ast::StructInstType * structInstType ) {
     676        if ( const ast::StructInstType * dstAsInst =
     677                        dynamic_cast< const ast::StructInstType * >( dst ) ) {
     678                if ( structInstType->name == dstAsInst->name ) {
     679                        cost = Cost::zero;
     680                }
     681        }
     682}
     683
     684void ConversionCost_new::postvisit( const ast::UnionInstType * unionInstType ) {
     685        if ( const ast::UnionInstType * dstAsInst =
     686                        dynamic_cast< const ast::UnionInstType * >( dst ) ) {
     687                if ( unionInstType->name == dstAsInst->name ) {
     688                        cost = Cost::zero;
     689                }
     690        }
     691}
     692
     693void ConversionCost_new::postvisit( const ast::EnumInstType * enumInstType ) {
     694        (void)enumInstType;
     695        static const ast::BasicType integer( ast::BasicType::SignedInt );
     696        cost = costCalc( &integer, dst, symtab, env );
     697        if ( cost < Cost::unsafe ) {
     698                cost.incSafe();
     699        }
     700}
     701
     702void ConversionCost_new::postvisit( const ast::TraitInstType * traitInstType ) {
     703        (void)traitInstType;
     704}
     705
     706void ConversionCost_new::postvisit( const ast::TypeInstType * typeInstType ) {
     707        if ( const ast::EqvClass * eqv = env.lookup( typeInstType->name ) ) {
     708                cost = costCalc( eqv->bound, dst, symtab, env );
     709        } else if ( const ast::TypeInstType * dstAsInst =
     710                        dynamic_cast< const ast::TypeInstType * >( dst ) ) {
     711                if ( typeInstType->name == dstAsInst->name ) {
     712                        cost = Cost::zero;
     713                }
     714        } else if ( const ast::NamedTypeDecl * namedType = symtab.lookupType( typeInstType->name ) ) {
     715                const ast::TypeDecl * type = dynamic_cast< const ast::TypeDecl * >( namedType );
     716                assertf( type, "Unexpected typedef.");
     717                if ( type->base ) {
     718                        cost = costCalc( type->base, dst, symtab, env ) + Cost::safe;
     719                }
     720        }
     721}
     722
     723void ConversionCost_new::postvisit( const ast::TupleType * tupleType ) {
     724        Cost c = Cost::zero;
     725        if ( const ast::TupleType * dstAsTuple = dynamic_cast< const ast::TupleType * >( dst ) ) {
     726                auto srcIt = tupleType->types.begin();
     727                auto dstIt = dstAsTuple->types.begin();
     728                auto srcEnd = tupleType->types.end();
     729                auto dstEnd = dstAsTuple->types.end();
     730                while ( srcIt != srcEnd && dstIt != dstEnd ) {
     731                        Cost newCost = costCalc( *srcIt++, *dstIt++, symtab, env );
     732                        if ( newCost == Cost::infinity ) {
     733                                return;
     734                        }
     735                        c += newCost;
     736                }
     737                if ( dstIt != dstEnd ) {
     738                        cost = Cost::infinity;
     739                } else {
     740                        cost = c;
     741                }
     742        }
     743}
     744
     745void ConversionCost_new::postvisit( const ast::VarArgsType * varArgsType ) {
     746        (void)varArgsType;
     747        if ( dynamic_cast< const ast::VarArgsType * >( dst ) ) {
     748                cost = Cost::zero;
     749        }
     750}
     751
     752void ConversionCost_new::postvisit( const ast::ZeroType * zeroType ) {
     753        (void)zeroType;
     754        if ( dynamic_cast< const ast::ZeroType * >( dst ) ) {
     755                cost = Cost::zero;
     756        } else if ( const ast::BasicType * dstAsBasic =
     757                        dynamic_cast< const ast::BasicType * >( dst ) ) {
     758                int tableResult = costMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ];
     759                if ( -1 == tableResult ) {
     760                        cost = Cost::unsafe;
     761                } else {
     762                        cost = Cost::zero;
     763                        cost.incSafe( tableResult + 1 );
     764                        cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] );
     765                }
     766        }
     767}
     768
     769void ConversionCost_new::postvisit( const ast::OneType * oneType ) {
     770        (void)oneType;
     771        if ( dynamic_cast< const ast::OneType * >( dst ) ) {
     772                cost = Cost::zero;
     773        } else if ( const ast::BasicType * dstAsBasic =
     774                        dynamic_cast< const ast::BasicType * >( dst ) ) {
     775                int tableResult = costMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ];
     776                if ( -1 == tableResult ) {
     777                        cost = Cost::unsafe;
     778                } else {
     779                        cost = Cost::zero;
     780                        cost.incSafe( tableResult + 1 );
     781                        cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] );
     782                }
     783        } else if ( dynamic_cast< const ast::PointerType * >( dst ) ) {
     784                cost = Cost::zero;
     785                cost.incSafe( maxIntCost + 2 );
     786        }
     787}
     788
     789
    500790} // namespace ResolvExpr
    501791
  • src/ResolvExpr/ConversionCost.h

    r70a141d4 r67d2b97  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 09:37:28 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Jul 22 09:38:24 2017
    13 // Update Count     : 4
     11// Last Modified By : Andrew Beach
     12// Last Modified On : Mon Jun 24 10:00:00 2019
     13// Update Count     : 5
    1414//
    1515
     
    2020#include "Cost.h"             // for Cost
    2121
     22#include "AST/Fwd.hpp"
     23#include "AST/Pass.hpp"       // for WithShortCircuiting
    2224#include "Common/PassVisitor.h"
    2325#include "SynTree/Visitor.h"  // for Visitor
     
    6567        typedef std::function<int(Type *, Type *, const SymTab::Indexer &, const TypeEnvironment &)> PtrsFunction;
    6668        Cost convertToReferenceCost( Type * src, ReferenceType * dest, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func );
     69
     70// Some function pointer types, differ in return type.
     71using CostCalculation = std::function<Cost(const ast::Type *, const ast::Type *,
     72        const ast::SymbolTable &, const ast::TypeEnvironment &)>;
     73using NumCostCalculation = std::function<int(const ast::Type *, const ast::Type *,
     74        const ast::SymbolTable &, const ast::TypeEnvironment &)>;
     75
     76// TODO: When the old ConversionCost is removed, get ride of the _new suffix.
     77class ConversionCost_new : public ast::WithShortCircuiting {
     78        const ast::Type * dst;
     79        const ast::SymbolTable & symtab;
     80        const ast::TypeEnvironment & env;
     81        CostCalculation costCalc;
     82public:
     83        Cost cost;
     84
     85        ConversionCost_new( const ast::Type * dst, const ast::SymbolTable & symtab,
     86                        const ast::TypeEnvironment & env, CostCalculation costCalc ) :
     87                dst( dst ), symtab( symtab ), env( env ), costCalc( costCalc ), cost( Cost::infinity )
     88        {}
     89
     90        void previsit( const ast::Node * ) { visit_children = false; }
     91
     92        void postvisit( const ast::VoidType * voidType );
     93        void postvisit( const ast::BasicType * basicType );
     94        void postvisit( const ast::PointerType * pointerType );
     95        void postvisit( const ast::ArrayType * arrayType );
     96        void postvisit( const ast::ReferenceType * refType );
     97        void postvisit( const ast::FunctionType * functionType );
     98        void postvisit( const ast::StructInstType * structInstType );
     99        void postvisit( const ast::UnionInstType * unionInstType );
     100        void postvisit( const ast::EnumInstType * enumInstType );
     101        void postvisit( const ast::TraitInstType * traitInstType );
     102        void postvisit( const ast::TypeInstType * typeInstType );
     103        void postvisit( const ast::TupleType * tupleType );
     104        void postvisit( const ast::VarArgsType * varArgsType );
     105        void postvisit( const ast::ZeroType * zeroType );
     106        void postvisit( const ast::OneType * oneType );
     107};
     108
     109Cost convertToReferenceCost( const ast::Type * src, const ast::ReferenceType * dest,
     110        const ast::SymbolTable & indexer, const ast::TypeEnvironment & env, NumCostCalculation func );
     111
    67112} // namespace ResolvExpr
    68113
  • src/ResolvExpr/PtrsAssignable.cc

    r70a141d4 r67d2b97  
    1414//
    1515
     16#include "AST/Fwd.hpp"
    1617#include "Common/PassVisitor.h"
    1718#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     
    107108        void PtrsAssignable::postvisit(  __attribute__((unused)) OneType *oneType ) {}
    108109
     110int ptrsAssignable( const ast::Type * src, const ast::Type * dst,
     111                const ast::TypeEnvironment & env ) {
     112        #warning unimplemented
     113        (void)src;
     114        (void)dst;
     115        (void)env;
     116        assert(0);
     117        return 0;
     118}
     119
    109120} // namespace ResolvExpr
    110121
  • src/ResolvExpr/Resolver.cc

    r70a141d4 r67d2b97  
    11541154                        return findKindExpression( untyped, symtab );
    11551155                }
    1156 
    1157                 /// Resolve `untyped` to the single expression whose candidate is the best match for the
    1158                 /// given type.
     1156        } // anonymous namespace
     1157
    11591158                ast::ptr< ast::Expr > findSingleExpression(
    11601159                        const ast::Expr * untyped, const ast::Type * type, const ast::SymbolTable & symtab
     
    11671166                }
    11681167
     1168        namespace {
    11691169                /// Predicate for "Candidate has integral type"
    11701170                bool hasIntegralType( const Candidate & i ) {
  • src/ResolvExpr/Resolver.h

    r70a141d4 r67d2b97  
    3535        class StmtExpr;
    3636        class SymbolTable;
     37        class Type;
    3738        class TypeEnvironment;
    3839} // namespace ast
     
    6162        ast::ptr< ast::Expr > resolveInVoidContext(
    6263                const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env );
     64        /// Resolve `untyped` to the single expression whose candidate is the best match for the
     65        /// given type.
     66        ast::ptr< ast::Expr > findSingleExpression(
     67                const ast::Expr * untyped, const ast::Type * type, const ast::SymbolTable & symtab );
    6368        /// Resolves a constructor init expression
    6469        ast::ptr< ast::Init > resolveCtorInit(
  • src/ResolvExpr/typeops.h

    r70a141d4 r67d2b97  
    9494        // in PtrsAssignable.cc
    9595        int ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env );
     96        int ptrsAssignable( const ast::Type * src, const ast::Type * dst,
     97                const ast::TypeEnvironment & env );
    9698
    9799        // in PtrsCastable.cc
  • src/SymTab/Validate.cc

    r70a141d4 r67d2b97  
    4444#include <list>                        // for list
    4545#include <string>                      // for string
     46#include <unordered_map>               // for unordered_map
    4647#include <utility>                     // for pair
    4748
     49#include "AST/Chain.hpp"
    4850#include "AST/Decl.hpp"
    4951#include "AST/Node.hpp"
     
    5153#include "AST/SymbolTable.hpp"
    5254#include "AST/Type.hpp"
     55#include "AST/TypeSubstitution.hpp"
    5356#include "CodeGen/CodeGenerator.h"     // for genName
    5457#include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
    5558#include "ControlStruct/Mutate.h"      // for ForExprMutator
     59#include "Common/CodeLocation.h"       // for CodeLocation
    5660#include "Common/Stats.h"              // for Stats::Heap
    5761#include "Common/PassVisitor.h"        // for PassVisitor, WithDeclsToAdd
     
    14271431        };
    14281432
     1433        /// expand assertions from a trait instance, performing appropriate type variable substitutions
     1434        void expandAssertions(
     1435                const ast::TraitInstType * inst, std::vector< ast::ptr< ast::DeclWithType > > & out
     1436        ) {
     1437                assertf( inst->base, "Trait instance not linked to base trait: %s", toCString( inst ) );
     1438
     1439                // build list of trait members, substituting trait decl parameters for instance parameters
     1440                ast::TypeSubstitution sub{
     1441                        inst->base->params.begin(), inst->base->params.end(), inst->params.begin() };
     1442                // deliberately take ast::ptr by-value to ensure this does not mutate inst->base
     1443                for ( ast::ptr< ast::Decl > decl : inst->base->members ) {
     1444                        auto member = decl.strict_as< ast::DeclWithType >();
     1445                        sub.apply( member );
     1446                        out.emplace_back( member );
     1447                }
     1448        }
     1449
    14291450        /// Associates forward declarations of aggregates with their definitions
    1430         struct LinkReferenceToTypes_new final
     1451        class LinkReferenceToTypes_new final
    14311452        : public ast::WithSymbolTable, public ast::WithGuards, public
    14321453          ast::WithVisitorRef<LinkReferenceToTypes_new>, public ast::WithShortCircuiting {
    14331454               
    1434                 const ast::SymbolTable * localSyms;
    1435 
    1436                 LinkReferenceToTypes_new( const ast::SymbolTable & syms ) : localSyms( &syms ) {}
    1437 
    1438                 #warning incomplete
     1455                // these maps of uses of forward declarations of types need to have the actual type
     1456                // declaration switched in *after* they have been traversed. To enable this in the
     1457                // ast::Pass framework, any node that needs to be so mutated has mutate() called on it
     1458                // before it is placed in the map, properly updating its parents in the usual traversal,
     1459                // then can have the actual mutation applied later
     1460                using ForwardEnumsType = std::unordered_multimap< std::string, ast::EnumInstType * >;
     1461                using ForwardStructsType = std::unordered_multimap< std::string, ast::StructInstType * >;
     1462                using ForwardUnionsType = std::unordered_multimap< std::string, ast::UnionInstType * >;
     1463               
     1464                const CodeLocation & location;
     1465                const ast::SymbolTable * localSymtab;
     1466               
     1467                ForwardEnumsType forwardEnums;
     1468                ForwardStructsType forwardStructs;
     1469                ForwardUnionsType forwardUnions;
     1470
     1471                /// true if currently in a generic type body, so that type parameter instances can be
     1472                /// renamed appropriately
     1473                bool inGeneric = false;
     1474
     1475        public:
     1476                /// contstruct using running symbol table
     1477                LinkReferenceToTypes_new( const CodeLocation & loc )
     1478                : location( loc ), localSymtab( &symtab ) {}
     1479               
     1480                /// construct using provided symbol table
     1481                LinkReferenceToTypes_new( const CodeLocation & loc, const ast::SymbolTable & syms )
     1482                : location( loc ), localSymtab( &syms ) {}
     1483
     1484                const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
     1485                        // ensure generic parameter instances are renamed like the base type
     1486                        if ( inGeneric && typeInst->base ) {
     1487                                typeInst = ast::mutate_field(
     1488                                        typeInst, &ast::TypeInstType::name, typeInst->base->name );
     1489                        }
     1490
     1491                        if (
     1492                                auto typeDecl = dynamic_cast< const ast::TypeDecl * >(
     1493                                        localSymtab->lookupType( typeInst->name ) )
     1494                        ) {
     1495                                typeInst = ast::mutate_field( typeInst, &ast::TypeInstType::kind, typeDecl->kind );
     1496                        }
     1497
     1498                        return typeInst;
     1499                }
     1500
     1501                const ast::Type * postvisit( const ast::EnumInstType * inst ) {
     1502                        const ast::EnumDecl * decl = localSymtab->lookupEnum( inst->name );
     1503                        // not a semantic error if the enum is not found, just an implicit forward declaration
     1504                        if ( decl ) {
     1505                                inst = ast::mutate_field( inst, &ast::EnumInstType::base, decl );
     1506                        }
     1507                        if ( ! decl || ! decl->body ) {
     1508                                // forward declaration
     1509                                auto mut = mutate( inst );
     1510                                forwardEnums.emplace( inst->name, mut );
     1511                                inst = mut;
     1512                        }
     1513                        return inst;
     1514                }
     1515
     1516                void checkGenericParameters( const ast::ReferenceToType * inst ) {
     1517                        for ( const ast::Expr * param : inst->params ) {
     1518                                if ( ! dynamic_cast< const ast::TypeExpr * >( param ) ) {
     1519                                        SemanticError(
     1520                                                location, inst, "Expression parameters for generic types are currently "
     1521                                                "unsupported: " );
     1522                                }
     1523                        }
     1524                }
     1525
     1526                const ast::StructInstType * postvisit( const ast::StructInstType * inst ) {
     1527                        const ast::StructDecl * decl = localSymtab->lookupStruct( inst->name );
     1528                        // not a semantic error if the struct is not found, just an implicit forward declaration
     1529                        if ( decl ) {
     1530                                inst = ast::mutate_field( inst, &ast::StructInstType::base, decl );
     1531                        }
     1532                        if ( ! decl || ! decl->body ) {
     1533                                // forward declaration
     1534                                auto mut = mutate( inst );
     1535                                forwardStructs.emplace( inst->name, mut );
     1536                                inst = mut;
     1537                        }
     1538                        checkGenericParameters( inst );
     1539                        return inst;
     1540                }
     1541
     1542                const ast::UnionInstType * postvisit( const ast::UnionInstType * inst ) {
     1543                        const ast::UnionDecl * decl = localSymtab->lookupUnion( inst->name );
     1544                        // not a semantic error if the struct is not found, just an implicit forward declaration
     1545                        if ( decl ) {
     1546                                inst = ast::mutate_field( inst, &ast::UnionInstType::base, decl );
     1547                        }
     1548                        if ( ! decl || ! decl->body ) {
     1549                                // forward declaration
     1550                                auto mut = mutate( inst );
     1551                                forwardUnions.emplace( inst->name, mut );
     1552                                inst = mut;
     1553                        }
     1554                        checkGenericParameters( inst );
     1555                        return inst;
     1556                }
     1557
     1558                const ast::Type * postvisit( const ast::TraitInstType * traitInst ) {
     1559                        // handle other traits
     1560                        const ast::TraitDecl * traitDecl = localSymtab->lookupTrait( traitInst->name );
     1561                        if ( ! traitDecl )       {
     1562                                SemanticError( location, "use of undeclared trait " + traitInst->name );
     1563                        }
     1564                        if ( traitDecl->params.size() != traitInst->params.size() ) {
     1565                                SemanticError( location, traitInst, "incorrect number of trait parameters: " );
     1566                        }
     1567                        traitInst = ast::mutate_field( traitInst, &ast::TraitInstType::base, traitDecl );
     1568
     1569                        // need to carry over the "sized" status of each decl in the instance
     1570                        for ( unsigned i = 0; i < traitDecl->params.size(); ++i ) {
     1571                                auto expr = traitInst->params[i].as< ast::TypeExpr >();
     1572                                if ( ! expr ) {
     1573                                        SemanticError(
     1574                                                traitInst->params[i].get(), "Expression parameters for trait instances "
     1575                                                "are currently unsupported: " );
     1576                                }
     1577
     1578                                if ( auto inst = expr->type.as< ast::TypeInstType >() ) {
     1579                                        if ( traitDecl->params[i]->sized && ! inst->base->sized ) {
     1580                                                // traitInst = ast::mutate_field_index(
     1581                                                //      traitInst, &ast::TraitInstType::params, i,
     1582                                                //      ...
     1583                                                // );
     1584                                                ast::TraitInstType * mut = ast::mutate( traitInst );
     1585                                                ast::chain_mutate( mut->params[i] )
     1586                                                        ( &ast::TypeExpr::type )
     1587                                                                ( &ast::TypeInstType::base )->sized = true;
     1588                                                traitInst = mut;
     1589                                        }
     1590                                }
     1591                        }
     1592
     1593                        return traitInst;
     1594                }
     1595               
     1596                void previsit( const ast::QualifiedType * ) { visit_children = false; }
     1597               
     1598                const ast::Type * postvisit( const ast::QualifiedType * qualType ) {
     1599                        // linking only makes sense for the "oldest ancestor" of the qualified type
     1600                        return ast::mutate_field(
     1601                                qualType, &ast::QualifiedType::parent, qualType->parent->accept( *visitor ) );
     1602                }
     1603
     1604                const ast::Decl * postvisit( const ast::EnumDecl * enumDecl ) {
     1605                        // visit enum members first so that the types of self-referencing members are updated
     1606                        // properly
     1607                        if ( ! enumDecl->body ) return enumDecl;
     1608
     1609                        // update forward declarations to point here
     1610                        auto fwds = forwardEnums.equal_range( enumDecl->name );
     1611                        if ( fwds.first != fwds.second ) {
     1612                                auto inst = fwds.first;
     1613                                do {
     1614                                        // forward decl is stored *mutably* in map, can thus be updated
     1615                                        inst->second->base = enumDecl;
     1616                                } while ( ++inst != fwds.second );
     1617                                forwardEnums.erase( fwds.first, fwds.second );
     1618                        }
     1619                       
     1620                        // ensure that enumerator initializers are properly set
     1621                        for ( unsigned i = 0; i < enumDecl->members.size(); ++i ) {
     1622                                auto field = enumDecl->members[i].strict_as< ast::ObjectDecl >();
     1623                                if ( field->init ) {
     1624                                        // need to resolve enumerator initializers early so that other passes that
     1625                                        // determine if an expression is constexpr have appropriate information
     1626                                        auto init = field->init.strict_as< ast::SingleInit >();
     1627                                       
     1628                                        enumDecl = ast::mutate_field_index(
     1629                                                enumDecl, &ast::EnumDecl::members, i,
     1630                                                ast::mutate_field( field, &ast::ObjectDecl::init,
     1631                                                        ast::mutate_field( init, &ast::SingleInit::value,
     1632                                                                ResolvExpr::findSingleExpression(
     1633                                                                        init->value, new ast::BasicType{ ast::BasicType::SignedInt },
     1634                                                                        symtab ) ) ) );
     1635                                }
     1636                        }
     1637
     1638                        return enumDecl;
     1639                }
     1640
     1641                /// rename generic type parameters uniquely so that they do not conflict with user defined
     1642                /// function forall parameters, e.g. the T in Box and the T in f, below
     1643                ///   forall(otype T)
     1644                ///   struct Box {
     1645                ///     T x;
     1646                ///   };
     1647                ///   forall(otype T)
     1648                ///   void f(Box(T) b) {
     1649                ///     ...
     1650                ///   }
     1651                template< typename AggrDecl >
     1652                const AggrDecl * renameGenericParams( const AggrDecl * aggr ) {
     1653                        GuardValue( inGeneric );
     1654                        inGeneric = ! aggr->params.empty();
     1655
     1656                        for ( unsigned i = 0; i < aggr->params.size(); ++i ) {
     1657                                const ast::TypeDecl * td = aggr->params[i];
     1658
     1659                                aggr = ast::mutate_field_index(
     1660                                        aggr, &AggrDecl::params, i,
     1661                                        ast::mutate_field( td, &ast::TypeDecl::name, "__" + td->name + "_generic_" ) );
     1662                        }
     1663                        return aggr;
     1664                }
     1665
     1666                const ast::StructDecl * previsit( const ast::StructDecl * structDecl ) {
     1667                        return renameGenericParams( structDecl );
     1668                }
     1669
     1670                void postvisit( const ast::StructDecl * structDecl ) {
     1671                        // visit struct members first so that the types of self-referencing members are
     1672                        // updated properly
     1673                        if ( ! structDecl->body ) return;
     1674
     1675                        // update forward declarations to point here
     1676                        auto fwds = forwardStructs.equal_range( structDecl->name );
     1677                        if ( fwds.first != fwds.second ) {
     1678                                auto inst = fwds.first;
     1679                                do {
     1680                                        // forward decl is stored *mutably* in map, can thus be updated
     1681                                        inst->second->base = structDecl;
     1682                                } while ( ++inst != fwds.second );
     1683                                forwardStructs.erase( fwds.first, fwds.second );
     1684                        }
     1685                }
     1686
     1687                const ast::UnionDecl * previsit( const ast::UnionDecl * unionDecl ) {
     1688                        return renameGenericParams( unionDecl );
     1689                }
     1690
     1691                void postvisit( const ast::UnionDecl * unionDecl ) {
     1692                        // visit union members first so that the types of self-referencing members are updated
     1693                        // properly
     1694                        if ( ! unionDecl->body ) return;
     1695
     1696                        // update forward declarations to point here
     1697                        auto fwds = forwardUnions.equal_range( unionDecl->name );
     1698                        if ( fwds.first != fwds.second ) {
     1699                                auto inst = fwds.first;
     1700                                do {
     1701                                        // forward decl is stored *mutably* in map, can thus be updated
     1702                                        inst->second->base = unionDecl;
     1703                                } while ( ++inst != fwds.second );
     1704                                forwardUnions.erase( fwds.first, fwds.second );
     1705                        }
     1706                }
     1707
     1708                const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) {
     1709                        // set the "sized" status for the special "sized" trait
     1710                        if ( traitDecl->name == "sized" ) {
     1711                                assertf( traitDecl->params.size() == 1, "Built-in trait 'sized' has incorrect "
     1712                                        "number of parameters: %zd", traitDecl->params.size() );
     1713
     1714                                traitDecl = ast::mutate_field_index(
     1715                                        traitDecl, &ast::TraitDecl::params, 0,
     1716                                        ast::mutate_field(
     1717                                                traitDecl->params.front().get(), &ast::TypeDecl::sized, true ) );
     1718                        }
     1719
     1720                        // move assertions from type parameters into the body of the trait
     1721                        std::vector< ast::ptr< ast::DeclWithType > > added;
     1722                        for ( const ast::TypeDecl * td : traitDecl->params ) {
     1723                                for ( const ast::DeclWithType * assn : td->assertions ) {
     1724                                        auto inst = dynamic_cast< const ast::TraitInstType * >( assn->get_type() );
     1725                                        if ( inst ) {
     1726                                                expandAssertions( inst, added );
     1727                                        } else {
     1728                                                added.emplace_back( assn );
     1729                                        }
     1730                                }
     1731                        }
     1732                        if ( ! added.empty() ) {
     1733                                auto mut = mutate( traitDecl );
     1734                                for ( const ast::DeclWithType * decl : added ) {
     1735                                        mut->members.emplace_back( decl );
     1736                                }
     1737                                traitDecl = mut;
     1738                        }
     1739                       
     1740                        return traitDecl;
     1741                }
    14391742        };
    14401743
    14411744        /// Replaces array and function types in forall lists by appropriate pointer type and assigns
    14421745        /// each object and function declaration a unique ID
    1443         struct ForallPointerDecay_new {
    1444                 #warning incomplete
     1746        class ForallPointerDecay_new {
     1747                const CodeLocation & location;
     1748        public:
     1749                ForallPointerDecay_new( const CodeLocation & loc ) : location( loc ) {}
     1750
     1751                const ast::ObjectDecl * previsit( const ast::ObjectDecl * obj ) {
     1752                        // ensure that operator names only apply to functions or function pointers
     1753                        if (
     1754                                CodeGen::isOperator( obj->name )
     1755                                && ! dynamic_cast< const ast::FunctionType * >( obj->type->stripDeclarator() )
     1756                        ) {
     1757                                SemanticError( obj->location, toCString( "operator ", obj->name.c_str(), " is not "
     1758                                        "a function or function pointer." )  );
     1759                        }
     1760
     1761                        // ensure object has unique ID
     1762                        if ( obj->uniqueId ) return obj;
     1763                        auto mut = mutate( obj );
     1764                        mut->fixUniqueId();
     1765                        return mut;
     1766                }
     1767
     1768                const ast::FunctionDecl * previsit( const ast::FunctionDecl * func ) {
     1769                        // ensure function has unique ID
     1770                        if ( func->uniqueId ) return func;
     1771                        auto mut = mutate( func );
     1772                        mut->fixUniqueId();
     1773                        return mut;
     1774                }
     1775
     1776                /// Fix up assertions -- flattens assertion lists, removing all trait instances
     1777                template< typename node_t, typename parent_t >
     1778                static const node_t * forallFixer(
     1779                        const CodeLocation & loc, const node_t * node,
     1780                        ast::ParameterizedType::ForallList parent_t::* forallField
     1781                ) {
     1782                        for ( unsigned i = 0; i < (node->*forallField).size(); ++i ) {
     1783                                const ast::TypeDecl * type = (node->*forallField)[i];
     1784                                if ( type->assertions.empty() ) continue;
     1785
     1786                                std::vector< ast::ptr< ast::DeclWithType > > asserts;
     1787                                asserts.reserve( type->assertions.size() );
     1788
     1789                                // expand trait instances into their members
     1790                                for ( const ast::DeclWithType * assn : type->assertions ) {
     1791                                        auto traitInst =
     1792                                                dynamic_cast< const ast::TraitInstType * >( assn->get_type() );
     1793                                        if ( traitInst ) {
     1794                                                // expand trait instance to all its members
     1795                                                expandAssertions( traitInst, asserts );
     1796                                        } else {
     1797                                                // pass other assertions through
     1798                                                asserts.emplace_back( assn );
     1799                                        }
     1800                                }
     1801
     1802                                // apply FixFunction to every assertion to check for invalid void type
     1803                                for ( ast::ptr< ast::DeclWithType > & assn : asserts ) {
     1804                                        bool isVoid = false;
     1805                                        assn = fixFunction( assn, isVoid );
     1806                                        if ( isVoid ) {
     1807                                                SemanticError( loc, node, "invalid type void in assertion of function " );
     1808                                        }
     1809                                }
     1810
     1811                                // place mutated assertion list in node
     1812                                auto mut = mutate( type );
     1813                                mut->assertions = move( asserts );
     1814                                node = ast::mutate_field_index( node, forallField, i, mut );
     1815                        }
     1816                        return node;
     1817                }
     1818
     1819                const ast::FunctionType * previsit( const ast::FunctionType * ftype ) {
     1820                        return forallFixer( location, ftype, &ast::FunctionType::forall );
     1821                }
     1822
     1823                const ast::StructDecl * previsit( const ast::StructDecl * aggrDecl ) {
     1824                        return forallFixer( aggrDecl->location, aggrDecl, &ast::StructDecl::params );
     1825                }
     1826
     1827                const ast::UnionDecl * previsit( const ast::UnionDecl * aggrDecl ) {
     1828                        return forallFixer( aggrDecl->location, aggrDecl, &ast::UnionDecl::params );
     1829                }
    14451830        };
    14461831} // anonymous namespace
    14471832
    1448 const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab ) {
     1833const ast::Type * validateType(
     1834                const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab ) {
    14491835        ast::Pass< EnumAndPointerDecay_new > epc;
    1450         ast::Pass< LinkReferenceToTypes_new > lrt{ symtab };
    1451         ast::Pass< ForallPointerDecay_new > fpd;
     1836        ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab };
     1837        ast::Pass< ForallPointerDecay_new > fpd{ loc };
    14521838
    14531839        return type->accept( epc )->accept( lrt )->accept( fpd );
  • src/SymTab/Validate.h

    r70a141d4 r67d2b97  
    1919#include <list>  // for list
    2020
     21class CodeLocation;
    2122class Declaration;
    2223class Type;
     
    3435        void validateType( Type *type, const Indexer *indexer );
    3536
    36         const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab );
     37        const ast::Type * validateType(
     38                const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab );
    3739} // namespace SymTab
    3840
  • tests/sum.cfa

    r70a141d4 r67d2b97  
    3535
    3636int main( void ) {
     37#if 0
    3738        const int low = 5, High = 15, size = High - low;
    3839
     
    121122                 | sum( size, gs.x ) | ", check" | (int)s;              // add field array in generic type
    122123        delete( gs.x );
     124#else
     125        const int low = 5, High = 15, size = High - low;
     126
     127        signed char s = 0, a[size], v = (char)low;
     128        for ( int i = 0; i < size; i += 1, v += 1hh ) {
     129                s += v;
     130                a[i] = v;
     131        } // for
     132        printf( "sum from %d to %d is %hhd, check %hhd\n", low, High,
     133                 sum( size, (signed char *)a ), (signed char)s );
     134
     135        unsigned char s = 0, a[size], v = low;
     136        for ( int i = 0; i < size; i += 1, v += 1hhu ) {
     137                s += (unsigned char)v;
     138                a[i] = (unsigned char)v;
     139        } // for
     140        printf( "sum from %d to %d is %hhu, check %hhu\n", low, High,
     141                 sum( size, (unsigned char *)a ), (unsigned char)s );
     142
     143        short int s = 0, a[size], v = low;
     144        for ( int i = 0; i < size; i += 1, v += 1h ) {
     145                s += (short int)v;
     146                a[i] = (short int)v;
     147        } // for
     148        printf( "sum from %d to %d is %hd, check %hd\n", low, High,
     149                 sum( size, (short int *)a ), (short int)s );
     150
     151        int s = 0, a[size], v = low;
     152        for ( int i = 0; i < size; i += 1, v += 1 ) {
     153                s += (int)v;
     154                a[i] = (int)v;
     155        } // for
     156        printf( "sum from %d to %d is %d, check %d\n", low, High,
     157                 sum( size, (int *)a ), (int)s );
     158
     159        float s = 0.0f, a[size], v = low / 10.0f;
     160        for ( int i = 0; i < size; i += 1, v += 0.1f ) {
     161                s += (float)v;
     162                a[i] = (float)v;
     163        } // for
     164        printf( "sum from %g to %g is %g, check %g\n", low / 10.0f, High / 10.0f,
     165                 sum( size, (float *)a ), (float)s );
     166
     167        double s = 0.0, a[size], v = low / 10.0;
     168        for ( int i = 0; i < size; i += 1, v += 0.1 ) {
     169                s += (double)v;
     170                a[i] = (double)v;
     171        } // for
     172        printf( "sum from %g to %g is %g, check %g\n", low / 10.0f, High / 10.0f,
     173                 sum( size, (double *)a ), (double)s );
     174
     175        struct S { int i, j; };
     176        void ?{}( S & s ) { s.[i, j] = 0; }
     177        void ?{}( S & s, int i ) { s.[i, j] = [i, 0]; }
     178        void ?{}( S & s, int i, int j ) { s.[i, j] = [i, j]; }
     179        void ?{}( S & s, zero_t ) { s.[i, j] = 0; }
     180        void ?{}( S & s, one_t ) { s.[i, j] = 1; }
     181        S ?+?( S t1, S t2 ) { return (S){ t1.i + t2.i, t1.j + t2.j }; }
     182        S ?+=?( S & t1, S t2 ) { t1 = t1 + t2; return t1; }
     183        S ++?( S & t ) { t += (S){1}; return t; }
     184        S ?++( S & t ) { S temp = t; t += (S){1}; return temp; }
     185        ofstream & ?|?( ofstream & os, S v ) { return os | v.i | v.j; }
     186        void ?|?( ofstream & os, S v ) { (ofstream &)(os | v); nl( os ); }
     187
     188        S s = (S){0}, a[size], v = { low, low };
     189        for ( int i = 0; i < size; i += 1, v += (S){1} ) {
     190                s += (S)v;
     191                a[i] = (S)v;
     192        } // for
     193        printf( "sum from %d to %d is %d %d, check %d %d\n", low, High,
     194                 sum( size, (S *)a ).[i, j], s.[i, j] );
     195
     196        forall( otype Impl | sumable( Impl ) )
     197        struct GS {
     198                Impl * x, * y;
     199        };
     200        GS(int) gs;
     201        // FIX ME, resolution problem with anew not picking up the LH type
     202        gs.x = (typeof(gs.x))anew( size );                                      // create array storage for field
     203        s = 0; v = low;
     204        for ( int i = 0; i < size; i += 1, v += 1 ) {
     205                s += (int)v;
     206                gs.x[i] = (int)v;                                                               // set field array in generic type
     207        } // for
     208        printf( "sum from %d to %d is %d, check %d\n", low, High,
     209                 sum( size, gs.x ), (int)s );           // add field array in generic type
     210        delete( gs.x );
     211#endif
    123212} // main
    124213
Note: See TracChangeset for help on using the changeset viewer.