Changes in / [0e464f6:da7454c]


Ignore:
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • benchmark/creation/cfa_cor.cfa

    r0e464f6 rda7454c  
    77void ?{} (MyCoroutine & this) {
    88#ifdef EAGER
    9         prime(this);
     9        resume(this);
    1010#endif
    1111}
  • doc/papers/concurrency/Paper.tex

    r0e464f6 rda7454c  
    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}
  • src/AST/Fwd.hpp

    r0e464f6 rda7454c  
    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/TypeSubstitution.hpp

    r0e464f6 rda7454c  
    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/ConversionCost.cc

    r0e464f6 rda7454c  
    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

    r0e464f6 rda7454c  
    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

    r0e464f6 rda7454c  
    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/typeops.h

    r0e464f6 rda7454c  
    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

    r0e464f6 rda7454c  
    5353#include "AST/SymbolTable.hpp"
    5454#include "AST/Type.hpp"
     55#include "AST/TypeSubstitution.hpp"
    5556#include "CodeGen/CodeGenerator.h"     // for genName
    5657#include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
     
    14301431        };
    14311432
     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
    14321450        /// Associates forward declarations of aggregates with their definitions
    14331451        class LinkReferenceToTypes_new final
     
    16901708                const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) {
    16911709                        // set the "sized" status for the special "sized" trait
    1692                         if ( traitDecl->name != "sized" ) return traitDecl;
    1693 
    1694                         assertf( traitDecl->params.size() == 1, "Built-in trait 'sized' has incorrect number "
    1695                                 "of parameters: %zd", traitDecl->params.size() );
    1696 
    1697                         return ast::mutate_field_index(
    1698                                 traitDecl, &ast::TraitDecl::params, 0,
    1699                                 ast::mutate_field(
    1700                                         traitDecl->params.front().get(), &ast::TypeDecl::sized, true ) );
     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;
    17011741                }
    17021742        };
     
    17041744        /// Replaces array and function types in forall lists by appropriate pointer type and assigns
    17051745        /// each object and function declaration a unique ID
    1706         struct ForallPointerDecay_new {
    1707                 #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                }
    17081830        };
    17091831} // anonymous namespace
     
    17131835        ast::Pass< EnumAndPointerDecay_new > epc;
    17141836        ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab };
    1715         ast::Pass< ForallPointerDecay_new > fpd;
     1837        ast::Pass< ForallPointerDecay_new > fpd{ loc };
    17161838
    17171839        return type->accept( epc )->accept( lrt )->accept( fpd );
Note: See TracChangeset for help on using the changeset viewer.