Changeset da7454c
- Timestamp:
- Jun 24, 2019, 2:27:29 PM (5 years ago)
- 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:
- 3623f9d
- Parents:
- 0e464f6 (diff), 67d2b97 (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. - Files:
-
- 9 edited
-
benchmark/creation/cfa_cor.cfa (modified) (1 diff)
-
doc/papers/concurrency/Paper.tex (modified) (5 diffs)
-
src/AST/Fwd.hpp (modified) (2 diffs)
-
src/AST/TypeSubstitution.hpp (modified) (1 diff)
-
src/ResolvExpr/ConversionCost.cc (modified) (2 diffs)
-
src/ResolvExpr/ConversionCost.h (modified) (3 diffs)
-
src/ResolvExpr/PtrsAssignable.cc (modified) (2 diffs)
-
src/ResolvExpr/typeops.h (modified) (1 diff)
-
src/SymTab/Validate.cc (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
benchmark/creation/cfa_cor.cfa
r0e464f6 rda7454c 7 7 void ?{} (MyCoroutine & this) { 8 8 #ifdef EAGER 9 prime(this);9 resume(this); 10 10 #endif 11 11 } -
doc/papers/concurrency/Paper.tex
r0e464f6 rda7454c 2705 2705 \label{results} 2706 2706 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} 2707 To 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. 2708 For 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. 2709 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 \CFA/\uC are compiled with gcc 6.5. 2742 2710 2743 2711 All benchmarks are run using the following harness. … … 2749 2717 Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark; 2750 2718 the total time is divided by @N@ to obtain the average time for a benchmark. 2719 Each benchmark experiment is run 31 times. 2751 2720 All omitted tests for other languages are functionally identical to the \CFA tests and available online~\cite{CforallBenchMarks}. 2752 2721 … … 2779 2748 \begin{tabular}[t]{@{}r*{3}{D{.}{.}{5.2}}@{}} 2780 2749 \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 \\ 2755 Goroutine & 4397.0 & 4362.8 & 390.77 \\ 2756 Java Thread & 107405.0 & 107794.8 & 1601.33 \\ 2757 % Qthreads & 159.9 & 159.6 & 0.73 \\ 2758 Pthreads & 32920.9 & 32882.7 & 213.55 2759 \end{tabular} 2760 \end{multicols} 2761 2762 2763 \paragraph{Internal Scheduling} 2764 2765 Internal scheduling is measured using a cycle of two threads signalling and waiting. 2766 Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}. 2767 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2768 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. 2769 2770 \begin{multicols}{2} 2771 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2772 \begin{cfa} 2773 volatile int go = 0; 2774 @monitor@ M { @condition c;@ } m; 2775 void __attribute__((noinline)) 2776 do_call( M & @mutex@ a1 ) { @signal( c );@ } 2777 thread T {}; 2778 void main( T & this ) { 2779 while ( go == 0 ) { yield(); } 2780 while ( go == 1 ) { do_call( m ); } 2781 } 2782 int __attribute__((noinline)) 2783 do_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 } 2789 int 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 \\ 2810 Java @notify@ & 16520.0 & 20096.7 & 9378.53 \\ 2811 Pthreads Cond. Variable & 4931.3 & 5057.0 & 326.80 2812 \end{tabular} 2813 \end{multicols} 2814 2815 2816 \paragraph{External Scheduling} 2817 2818 External scheduling is measured using a cycle of two threads calling and accepting the call using the @waitfor@ statement. 2819 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}. 2820 Note, 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} 2826 volatile int go = 0; 2827 @monitor@ M {} m; 2828 thread T {}; 2829 void __attribute__((noinline)) 2830 do_call( M & @mutex@ ) {} 2831 void main( T & ) { 2832 while ( go == 0 ) { yield(); } 2833 while ( go == 1 ) { do_call( m ); } 2834 } 2835 int __attribute__((noinline)) 2836 do_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 } 2842 int 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 2789 2861 \end{tabular} 2790 2862 \end{multicols} … … 2825 2897 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2826 2898 \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 2899 C 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 \\ 2905 Goroutine & 140.0 & 139.7 & 2.93 \\ 2906 Java Thread & 374.0 & 375.8 & 10.38 \\ 2907 % Qthreads Thread & 159.5 & 159.3 & 0.71 \\ 2908 Pthreads Thread & 334.4 & 335.0 & 1.95 \\ 2836 2909 \end{tabular} 2837 2910 \end{multicols} … … 2869 2942 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2870 2943 \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 2944 test 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 \\ 2949 Java synchronized method & 27.0 & 27.1 & 0.25 \\ 2950 Pthreads Mutex Lock & 33.6 & 32.7 & 1.12 2980 2951 \end{tabular} 2981 2952 \end{multicols} -
src/AST/Fwd.hpp
r0e464f6 rda7454c 10 10 // Created On : Wed May 8 16:05:00 2019 11 11 // Last Modified By : Andrew Beach 12 // Last Modified On : Thr May 9 13:09:00 201913 // Update Count : 012 // Last Modified On : Mon Jun 24 09:48:00 2019 13 // Update Count : 1 14 14 // 15 15 … … 129 129 class Attribute; 130 130 131 class SymbolTable; 132 class TypeEnvironment; 131 133 class TypeSubstitution; 132 134 -
src/AST/TypeSubstitution.hpp
r0e464f6 rda7454c 200 200 } 201 201 202 /// Instantiate each member of the context given the actual parameters specified, and store the203 /// instantiations for use by the indexer204 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 } // for211 }212 213 202 } // namespace ast 214 203 -
src/ResolvExpr/ConversionCost.cc
r0e464f6 rda7454c 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 07:06:19 2015 11 // Last Modified By : Peter A. Buhr12 // Last Modified On : Mon May 6 14:18:22201913 // Update Count : 2 511 // Last Modified By : Andrew Beach 12 // Last Modified On : Mon Jun 24 13:33:00 2019 13 // Update Count : 26 14 14 // 15 15 … … 489 489 } 490 490 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); 491 static 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. 498 static 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 503 Cost 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 ) ) { 498 523 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 536 Cost 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 600 Cost 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 607 void ConversionCost_new::postvisit( const ast::VoidType * voidType ) { 608 (void)voidType; 609 cost = Cost::infinity; 610 } 611 612 void 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 628 void 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 654 void ConversionCost_new::postvisit( const ast::ArrayType * arrayType ) { 655 (void)arrayType; 656 } 657 658 void 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 671 void ConversionCost_new::postvisit( const ast::FunctionType * functionType ) { 672 (void)functionType; 673 } 674 675 void 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 684 void 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 693 void 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 702 void ConversionCost_new::postvisit( const ast::TraitInstType * traitInstType ) { 703 (void)traitInstType; 704 } 705 706 void 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 723 void 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 745 void 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 752 void 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 769 void 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 500 790 } // namespace ResolvExpr 501 791 -
src/ResolvExpr/ConversionCost.h
r0e464f6 rda7454c 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 09:37:28 2015 11 // Last Modified By : Peter A. Buhr12 // Last Modified On : Sat Jul 22 09:38:24 201713 // Update Count : 411 // Last Modified By : Andrew Beach 12 // Last Modified On : Mon Jun 24 10:00:00 2019 13 // Update Count : 5 14 14 // 15 15 … … 20 20 #include "Cost.h" // for Cost 21 21 22 #include "AST/Fwd.hpp" 23 #include "AST/Pass.hpp" // for WithShortCircuiting 22 24 #include "Common/PassVisitor.h" 23 25 #include "SynTree/Visitor.h" // for Visitor … … 65 67 typedef std::function<int(Type *, Type *, const SymTab::Indexer &, const TypeEnvironment &)> PtrsFunction; 66 68 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. 71 using CostCalculation = std::function<Cost(const ast::Type *, const ast::Type *, 72 const ast::SymbolTable &, const ast::TypeEnvironment &)>; 73 using 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. 77 class ConversionCost_new : public ast::WithShortCircuiting { 78 const ast::Type * dst; 79 const ast::SymbolTable & symtab; 80 const ast::TypeEnvironment & env; 81 CostCalculation costCalc; 82 public: 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 109 Cost convertToReferenceCost( const ast::Type * src, const ast::ReferenceType * dest, 110 const ast::SymbolTable & indexer, const ast::TypeEnvironment & env, NumCostCalculation func ); 111 67 112 } // namespace ResolvExpr 68 113 -
src/ResolvExpr/PtrsAssignable.cc
r0e464f6 rda7454c 14 14 // 15 15 16 #include "AST/Fwd.hpp" 16 17 #include "Common/PassVisitor.h" 17 18 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment … … 107 108 void PtrsAssignable::postvisit( __attribute__((unused)) OneType *oneType ) {} 108 109 110 int 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 109 120 } // namespace ResolvExpr 110 121 -
src/ResolvExpr/typeops.h
r0e464f6 rda7454c 94 94 // in PtrsAssignable.cc 95 95 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 ); 96 98 97 99 // in PtrsCastable.cc -
src/SymTab/Validate.cc
r0e464f6 rda7454c 53 53 #include "AST/SymbolTable.hpp" 54 54 #include "AST/Type.hpp" 55 #include "AST/TypeSubstitution.hpp" 55 56 #include "CodeGen/CodeGenerator.h" // for genName 56 57 #include "CodeGen/OperatorTable.h" // for isCtorDtor, isCtorDtorAssign … … 1430 1431 }; 1431 1432 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 1432 1450 /// Associates forward declarations of aggregates with their definitions 1433 1451 class LinkReferenceToTypes_new final … … 1690 1708 const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) { 1691 1709 // 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; 1701 1741 } 1702 1742 }; … … 1704 1744 /// Replaces array and function types in forall lists by appropriate pointer type and assigns 1705 1745 /// 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 } 1708 1830 }; 1709 1831 } // anonymous namespace … … 1713 1835 ast::Pass< EnumAndPointerDecay_new > epc; 1714 1836 ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab }; 1715 ast::Pass< ForallPointerDecay_new > fpd ;1837 ast::Pass< ForallPointerDecay_new > fpd{ loc }; 1716 1838 1717 1839 return type->accept( epc )->accept( lrt )->accept( fpd );
Note: See TracChangeset
for help on using the changeset viewer.
