Changes in / [da7454c:0e464f6]
- 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
rda7454c r0e464f6 7 7 void ?{} (MyCoroutine & this) { 8 8 #ifdef EAGER 9 resume(this);9 prime(this); 10 10 #endif 11 11 } -
doc/papers/concurrency/Paper.tex
rda7454c r0e464f6 2705 2705 \label{results} 2706 2706 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. 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} 2710 2742 2711 2743 All benchmarks are run using the following harness. … … 2717 2749 Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark; 2718 2750 the total time is divided by @N@ to obtain the average time for a benchmark. 2719 Each benchmark experiment is run 31 times.2720 2751 All omitted tests for other languages are functionally identical to the \CFA tests and available online~\cite{CforallBenchMarks}. 2721 2752 … … 2748 2779 \begin{tabular}[t]{@{}r*{3}{D{.}{.}{5.2}}@{}} 2749 2780 \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ 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 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 \\ 2789 \end{tabular} 2790 \end{multicols} 2791 2792 2793 \paragraph{Context-Switching} 2794 2795 In procedural programming, the cost of a function call is important as modularization (refactoring) increases. 2796 (In many cases, a compiler inlines function calls to eliminate this cost.) 2797 Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor. 2798 The coroutine test is from resumer to suspender and from suspender to resumer, which is two context switches. 2799 The thread test is using yield to enter and return from the runtime kernel, which is two context switches. 2800 The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling. 2801 Figure~\ref{f:ctx-switch} only shows the \CFA code for coroutines/threads (other systems are similar) with all results in Table~\ref{tab:ctx-switch}. 2802 2803 \begin{multicols}{2} 2804 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2805 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 2806 @coroutine@ C {} c; 2807 void main( C & ) { for ( ;; ) { @suspend;@ } } 2808 int main() { // coroutine test 2809 BENCH( for ( N ) { @resume( c );@ } ) 2810 sout | result`ns; 2811 } 2812 int main() { // task test 2813 BENCH( for ( N ) { @yield();@ } ) 2814 sout | result`ns; 2815 } 2816 \end{cfa} 2817 \captionof{figure}{\CFA context-switch benchmark} 2818 \label{f:ctx-switch} 2819 2820 \columnbreak 2821 2822 \vspace*{-16pt} 2823 \captionof{table}{Context switch comparison (nanoseconds)} 2824 \label{tab:ctx-switch} 2825 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2826 \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 2836 \end{tabular} 2837 \end{multicols} 2838 2839 2840 \paragraph{Mutual-Exclusion} 2841 2842 Uncontented mutual exclusion, which occurs frequently, is measured by entering/leaving a critical section. 2843 For monitors, entering and leaving a monitor function is measured. 2844 To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured. 2845 Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}. 2846 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2847 2848 \begin{multicols}{2} 2849 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2850 \begin{cfa} 2851 @monitor@ M {} m1/*, m2, m3, m4*/; 2852 void __attribute__((noinline)) 2853 do_call( M & @mutex m/*, m2, m3, m4*/@ ) {} 2854 int main() { 2855 BENCH( 2856 for( N ) do_call( m1/*, m2, m3, m4*/ ); 2857 ) 2858 sout | result`ns; 2859 } 2860 \end{cfa} 2861 \captionof{figure}{\CFA acquire/release mutex benchmark} 2862 \label{f:mutex} 2863 2864 \columnbreak 2865 2866 \vspace*{-16pt} 2867 \captionof{table}{Mutex comparison (nanoseconds)} 2868 \label{tab:mutex} 2869 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2870 \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 2759 2878 \end{tabular} 2760 2879 \end{multicols} … … 2804 2923 \begin{tabular}{@{}r*{3}{D{.}{.}{5.2}}@{}} 2805 2924 \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 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 2812 2931 \end{tabular} 2813 2932 \end{multicols} … … 2855 2974 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2856 2975 \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 2861 \end{tabular} 2862 \end{multicols} 2863 2864 2865 \paragraph{Context-Switching} 2866 2867 In procedural programming, the cost of a function call is important as modularization (refactoring) increases. 2868 (In many cases, a compiler inlines function calls to eliminate this cost.) 2869 Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor. 2870 The coroutine test is from resumer to suspender and from suspender to resumer, which is two context switches. 2871 The thread test is using yield to enter and return from the runtime kernel, which is two context switches. 2872 The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling. 2873 Figure~\ref{f:ctx-switch} only shows the \CFA code for coroutines/threads (other systems are similar) with all results in Table~\ref{tab:ctx-switch}. 2874 2875 \begin{multicols}{2} 2876 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2877 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 2878 @coroutine@ C {} c; 2879 void main( C & ) { for ( ;; ) { @suspend;@ } } 2880 int main() { // coroutine test 2881 BENCH( for ( N ) { @resume( c );@ } ) 2882 sout | result`ns; 2883 } 2884 int main() { // task test 2885 BENCH( for ( N ) { @yield();@ } ) 2886 sout | result`ns; 2887 } 2888 \end{cfa} 2889 \captionof{figure}{\CFA context-switch benchmark} 2890 \label{f:ctx-switch} 2891 2892 \columnbreak 2893 2894 \vspace*{-16pt} 2895 \captionof{table}{Context switch comparison (nanoseconds)} 2896 \label{tab:ctx-switch} 2897 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2898 \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ 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 \\ 2909 \end{tabular} 2910 \end{multicols} 2911 2912 2913 \paragraph{Mutual-Exclusion} 2914 2915 Uncontented mutual exclusion, which occurs frequently, is measured by entering/leaving a critical section. 2916 For monitors, entering and leaving a monitor function is measured. 2917 To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured. 2918 Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}. 2919 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2920 2921 \begin{multicols}{2} 2922 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2923 \begin{cfa} 2924 @monitor@ M {} m1/*, m2, m3, m4*/; 2925 void __attribute__((noinline)) 2926 do_call( M & @mutex m/*, m2, m3, m4*/@ ) {} 2927 int main() { 2928 BENCH( 2929 for( N ) do_call( m1/*, m2, m3, m4*/ ); 2930 ) 2931 sout | result`ns; 2932 } 2933 \end{cfa} 2934 \captionof{figure}{\CFA acquire/release mutex benchmark} 2935 \label{f:mutex} 2936 2937 \columnbreak 2938 2939 \vspace*{-16pt} 2940 \captionof{table}{Mutex comparison (nanoseconds)} 2941 \label{tab:mutex} 2942 \begin{tabular}{@{}r*{3}{D{.}{.}{3.2}}@{}} 2943 \multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} &\multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\ 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 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 2951 2980 \end{tabular} 2952 2981 \end{multicols} -
src/AST/Fwd.hpp
rda7454c r0e464f6 10 10 // Created On : Wed May 8 16:05:00 2019 11 11 // Last Modified By : Andrew Beach 12 // Last Modified On : Mon Jun 24 09:48:00 201913 // Update Count : 112 // Last Modified On : Thr May 9 13:09:00 2019 13 // Update Count : 0 14 14 // 15 15 … … 129 129 class Attribute; 130 130 131 class SymbolTable;132 class TypeEnvironment;133 131 class TypeSubstitution; 134 132 -
src/AST/TypeSubstitution.hpp
rda7454c r0e464f6 200 200 } 201 201 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 202 213 } // namespace ast 203 214 -
src/ResolvExpr/ConversionCost.cc
rda7454c r0e464f6 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 07:06:19 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Mon Jun 24 13:33:00201913 // Update Count : 2 611 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon May 6 14:18:22 2019 13 // Update Count : 25 14 14 // 15 15 … … 489 489 } 490 490 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 ) ) { 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); 523 498 return Cost::zero; 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 499 } 790 500 } // namespace ResolvExpr 791 501 -
src/ResolvExpr/ConversionCost.h
rda7454c r0e464f6 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 09:37:28 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Mon Jun 24 10:00:00 201913 // Update Count : 511 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Jul 22 09:38:24 2017 13 // Update Count : 4 14 14 // 15 15 … … 20 20 #include "Cost.h" // for Cost 21 21 22 #include "AST/Fwd.hpp"23 #include "AST/Pass.hpp" // for WithShortCircuiting24 22 #include "Common/PassVisitor.h" 25 23 #include "SynTree/Visitor.h" // for Visitor … … 67 65 typedef std::function<int(Type *, Type *, const SymTab::Indexer &, const TypeEnvironment &)> PtrsFunction; 68 66 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 112 67 } // namespace ResolvExpr 113 68 -
src/ResolvExpr/PtrsAssignable.cc
rda7454c r0e464f6 14 14 // 15 15 16 #include "AST/Fwd.hpp"17 16 #include "Common/PassVisitor.h" 18 17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment … … 108 107 void PtrsAssignable::postvisit( __attribute__((unused)) OneType *oneType ) {} 109 108 110 int ptrsAssignable( const ast::Type * src, const ast::Type * dst,111 const ast::TypeEnvironment & env ) {112 #warning unimplemented113 (void)src;114 (void)dst;115 (void)env;116 assert(0);117 return 0;118 }119 120 109 } // namespace ResolvExpr 121 110 -
src/ResolvExpr/typeops.h
rda7454c r0e464f6 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 );98 96 99 97 // in PtrsCastable.cc -
src/SymTab/Validate.cc
rda7454c r0e464f6 53 53 #include "AST/SymbolTable.hpp" 54 54 #include "AST/Type.hpp" 55 #include "AST/TypeSubstitution.hpp"56 55 #include "CodeGen/CodeGenerator.h" // for genName 57 56 #include "CodeGen/OperatorTable.h" // for isCtorDtor, isCtorDtorAssign … … 1431 1430 }; 1432 1431 1433 /// expand assertions from a trait instance, performing appropriate type variable substitutions1434 void expandAssertions(1435 const ast::TraitInstType * inst, std::vector< ast::ptr< ast::DeclWithType > > & out1436 ) {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 parameters1440 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->base1443 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 1450 1432 /// Associates forward declarations of aggregates with their definitions 1451 1433 class LinkReferenceToTypes_new final … … 1708 1690 const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) { 1709 1691 // 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; 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 ) ); 1741 1701 } 1742 1702 }; … … 1744 1704 /// Replaces array and function types in forall lists by appropriate pointer type and assigns 1745 1705 /// each object and function declaration a unique ID 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 } 1706 struct ForallPointerDecay_new { 1707 #warning incomplete 1830 1708 }; 1831 1709 } // anonymous namespace … … 1835 1713 ast::Pass< EnumAndPointerDecay_new > epc; 1836 1714 ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab }; 1837 ast::Pass< ForallPointerDecay_new > fpd { loc };1715 ast::Pass< ForallPointerDecay_new > fpd; 1838 1716 1839 1717 return type->accept( epc )->accept( lrt )->accept( fpd );
Note:
See TracChangeset
for help on using the changeset viewer.
