Changeset 67d2b97
- Timestamp:
- Jun 24, 2019, 2:24:57 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:
- 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. - Files:
-
- 17 edited
Legend:
- Unmodified
- Added
- Removed
-
Jenkinsfile
r70a141d4 r67d2b97 130 130 //Run the tests from the tests directory 131 131 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 ' 134 134 } 135 135 else { -
doc/papers/concurrency/Paper.tex
r70a141d4 r67d2b97 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} -
driver/cc1.cc
r70a141d4 r67d2b97 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // cc1.cc -- 7 // cc1.cc -- 8 8 // 9 9 // Author : Peter A. Buhr … … 107 107 if ( tmpfilefd != -1 ) { // RACE, file created ? 108 108 rmtmpfile(); // remove 109 exit( EXIT_FAILURE ); // terminate 109 exit( EXIT_FAILURE ); // terminate 110 110 } // if 111 111 } // sigTermHandler … … 360 360 361 361 #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; 363 363 for ( int i = 0; cargs[i] != NULL; i += 1 ) { 364 364 cerr << cargs[i] << " "; -
src/AST/Convert.cpp
r70a141d4 r67d2b97 1895 1895 }; 1896 1896 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), 1899 1899 }; 1900 1900 -
src/AST/Fwd.hpp
r70a141d4 r67d2b97 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/Node.hpp
r70a141d4 r67d2b97 100 100 101 101 /// 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 ) {102 template<typename node_t, typename parent_t, typename field_t, typename assn_t> 103 const node_t * mutate_field( const node_t * node, field_t parent_t::* field, assn_t && val ) { 104 104 // skip mutate if equivalent 105 105 if ( node->*field == val ) return node; … … 112 112 113 113 /// 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>114 template<typename node_t, typename parent_t, typename coll_t, typename ind_t, typename field_t> 115 115 const node_t * mutate_field_index( 116 const node_t * node, coll_t node_t::* field, ind_t i, field_t && val116 const node_t * node, coll_t parent_t::* field, ind_t i, field_t && val 117 117 ) { 118 118 // skip mutate if equivalent -
src/AST/TypeSubstitution.hpp
r70a141d4 r67d2b97 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/CandidateFinder.cpp
r70a141d4 r67d2b97 1003 1003 assert( toType ); 1004 1004 toType = resolveTypeof( toType, symtab ); 1005 toType = SymTab::validateType( toType, symtab );1005 toType = SymTab::validateType( castExpr->location, toType, symtab ); 1006 1006 toType = adjustExprType( toType, tenv, symtab ); 1007 1007 … … 1410 1410 // calculate target type 1411 1411 const ast::Type * toType = resolveTypeof( initAlt.type, symtab ); 1412 toType = SymTab::validateType( toType, symtab );1412 toType = SymTab::validateType( initExpr->location, toType, symtab ); 1413 1413 toType = adjustExprType( toType, tenv, symtab ); 1414 1414 // The call to find must occur inside this loop, otherwise polymorphic return -
src/ResolvExpr/ConversionCost.cc
r70a141d4 r67d2b97 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
r70a141d4 r67d2b97 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
r70a141d4 r67d2b97 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/Resolver.cc
r70a141d4 r67d2b97 1154 1154 return findKindExpression( untyped, symtab ); 1155 1155 } 1156 1157 /// Resolve `untyped` to the single expression whose candidate is the best match for the 1158 /// given type. 1156 } // anonymous namespace 1157 1159 1158 ast::ptr< ast::Expr > findSingleExpression( 1160 1159 const ast::Expr * untyped, const ast::Type * type, const ast::SymbolTable & symtab … … 1167 1166 } 1168 1167 1168 namespace { 1169 1169 /// Predicate for "Candidate has integral type" 1170 1170 bool hasIntegralType( const Candidate & i ) { -
src/ResolvExpr/Resolver.h
r70a141d4 r67d2b97 35 35 class StmtExpr; 36 36 class SymbolTable; 37 class Type; 37 38 class TypeEnvironment; 38 39 } // namespace ast … … 61 62 ast::ptr< ast::Expr > resolveInVoidContext( 62 63 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 ); 63 68 /// Resolves a constructor init expression 64 69 ast::ptr< ast::Init > resolveCtorInit( -
src/ResolvExpr/typeops.h
r70a141d4 r67d2b97 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
r70a141d4 r67d2b97 44 44 #include <list> // for list 45 45 #include <string> // for string 46 #include <unordered_map> // for unordered_map 46 47 #include <utility> // for pair 47 48 49 #include "AST/Chain.hpp" 48 50 #include "AST/Decl.hpp" 49 51 #include "AST/Node.hpp" … … 51 53 #include "AST/SymbolTable.hpp" 52 54 #include "AST/Type.hpp" 55 #include "AST/TypeSubstitution.hpp" 53 56 #include "CodeGen/CodeGenerator.h" // for genName 54 57 #include "CodeGen/OperatorTable.h" // for isCtorDtor, isCtorDtorAssign 55 58 #include "ControlStruct/Mutate.h" // for ForExprMutator 59 #include "Common/CodeLocation.h" // for CodeLocation 56 60 #include "Common/Stats.h" // for Stats::Heap 57 61 #include "Common/PassVisitor.h" // for PassVisitor, WithDeclsToAdd … … 1427 1431 }; 1428 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 1429 1450 /// Associates forward declarations of aggregates with their definitions 1430 structLinkReferenceToTypes_new final1451 class LinkReferenceToTypes_new final 1431 1452 : public ast::WithSymbolTable, public ast::WithGuards, public 1432 1453 ast::WithVisitorRef<LinkReferenceToTypes_new>, public ast::WithShortCircuiting { 1433 1454 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 } 1439 1742 }; 1440 1743 1441 1744 /// Replaces array and function types in forall lists by appropriate pointer type and assigns 1442 1745 /// 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 } 1445 1830 }; 1446 1831 } // anonymous namespace 1447 1832 1448 const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab ) { 1833 const ast::Type * validateType( 1834 const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab ) { 1449 1835 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 }; 1452 1838 1453 1839 return type->accept( epc )->accept( lrt )->accept( fpd ); -
src/SymTab/Validate.h
r70a141d4 r67d2b97 19 19 #include <list> // for list 20 20 21 class CodeLocation; 21 22 class Declaration; 22 23 class Type; … … 34 35 void validateType( Type *type, const Indexer *indexer ); 35 36 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 ); 37 39 } // namespace SymTab 38 40 -
tests/sum.cfa
r70a141d4 r67d2b97 35 35 36 36 int main( void ) { 37 #if 0 37 38 const int low = 5, High = 15, size = High - low; 38 39 … … 121 122 | sum( size, gs.x ) | ", check" | (int)s; // add field array in generic type 122 123 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 123 212 } // main 124 213
Note: See TracChangeset
for help on using the changeset viewer.