Changeset c0d00b6


Ignore:
Timestamp:
Nov 25, 2017, 3:22:18 PM (5 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
arm-eh, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
c6e2c18
Parents:
9d06142 (diff), 3de176d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' into cleanup-dtors

Files:
9 added
2 deleted
84 edited

Legend:

Unmodified
Added
Removed
  • Jenkinsfile

    r9d06142 rc0d00b6  
    1515        arch_name               = ''
    1616        architecture    = ''
    17        
     17
    1818        do_alltests             = false
    1919        do_benchmark    = false
     
    183183                sh 'make clean > /dev/null'
    184184                sh 'make > /dev/null 2>&1'
    185         } 
     185        }
    186186        catch (Exception caughtError) {
    187187                err = caughtError //rethrow error later
     
    257257def build() {
    258258        build_stage('Build') {
    259        
     259
    260260                def install_dir = pwd tmp: true
    261                
     261
    262262                //Configure the conpilation (Output is not relevant)
    263263                //Use the current directory as the installation target so nothing
     
    290290                if( !do_benchmark ) return
    291291
    292                 //Write the commit id to Benchmark
    293                 writeFile  file: 'bench.csv', text:'data=' + gitRefNewValue + ',' + arch_name + ','
    294  
    295292                //Append bench results
    296                 sh 'make -C src/benchmark --no-print-directory csv-data >> bench.csv'
     293                sh 'make -C src/benchmark --no-print-directory jenkins githash=' + gitRefNewValue + ' arch=' + arch_name + ' | tee bench.json'
    297294        }
    298295}
     
    327324
    328325                //Then publish the results
    329                 sh 'curl --silent --data @bench.csv http://plg2:8082/jenkins/publish > /dev/null || true'
     326                sh 'curl -H "Content-Type: application/json" --silent --data @bench.json http://plg2:8082/jenkins/publish > /dev/null || true'
    330327        }
    331328}
  • doc/proposals/concurrency/Makefile

    r9d06142 rc0d00b6  
    3232PICTURES = ${addprefix build/, ${addsuffix .pstex, \
    3333        system \
     34        monitor_structs \
    3435}}
    3536
     
    8384        dvips $< -o $@
    8485
    85 build/${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../../LaTeXmacros/common.tex ../../LaTeXmacros/indexstyle
     86build/${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../../LaTeXmacros/common.tex ../../LaTeXmacros/indexstyle annex/local.bib
    8687
    8788        @ if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi                           # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
     
    9495        @ -${BibTeX} ${basename $@}
    9596        @ echo "Glossary"
    96         makeglossaries -q -s ${basename $@}.ist ${basename $@}                                          # Make index from *.aux entries and input index at end of document
     97        @ makeglossaries -q -s ${basename $@}.ist ${basename $@}                                                # Make index from *.aux entries and input index at end of document
    9798        @ echo ".dvi generation"
    9899        @ -build/bump_ver.sh
  • doc/proposals/concurrency/annex/local.bib

    r9d06142 rc0d00b6  
    5252        year            = 2017
    5353}
     54
     55@manual{Cpp-Transactions,
     56        keywords        = {C++, Transactional Memory},
     57        title           = {Technical Specification for C++ Extensions for Transactional Memory},
     58        organization= {International Standard ISO/IEC TS 19841:2015 },
     59        publisher   = {American National Standards Institute},
     60        address = {http://www.iso.org},
     61        year            = 2015,
     62}
     63
     64@article{BankTransfer,
     65        keywords        = {Bank Transfer},
     66        title   = {Bank Account Transfer Problem},
     67        publisher       = {Wiki Wiki Web},
     68        address = {http://wiki.c2.com},
     69        year            = 2010
     70}
     71
     72@misc{2FTwoHardThings,
     73        keywords        = {Hard Problem},
     74        title   = {TwoHardThings},
     75        author  = {Martin Fowler},
     76        address = {https://martinfowler.com/bliki/TwoHardThings.html},
     77        year            = 2009
     78}
     79
     80@article{IntrusiveData,
     81        title           = {Intrusive Data Structures},
     82        author  = {Jiri Soukup},
     83        journal = {CppReport},
     84        year            = 1998,
     85        month           = May,
     86        volume  = {10/No5.},
     87        page            = 22
     88}
     89
     90@misc{affinityLinux,
     91        title           = "{Linux man page - sched\_setaffinity(2)}"
     92}
     93
     94@misc{affinityWindows,
     95        title           = "{Windows (vs.85) - SetThreadAffinityMask function}"
     96}
     97
     98@misc{affinityFreebsd,
     99        title           = "{FreeBSD General Commands Manual - CPUSET(1)}"
     100}
     101
     102@misc{affinityNetbsd,
     103        title           = "{NetBSD Library Functions Manual - AFFINITY(3)}"
     104}
     105
     106@misc{affinityMacosx,
     107        title           = "{Affinity API Release Notes for OS X v10.5}"
     108}
  • doc/proposals/concurrency/figures/int_monitor.fig

    r9d06142 rc0d00b6  
    88-2
    991200 2
    10 5 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 600.000 2625.000 600 2325 300 2625 600 2925
    11 6 3225 4500 7425 4800
    12 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3375 4650 80 80 3375 4650 3455 4730
    13 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4725 4650 105 105 4725 4650 4830 4755
    14 1 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 6225 4650 105 105 6225 4650 6330 4755
    15 4 0 -1 0 0 0 12 0.0000 2 135 1035 4950 4725 blocked task\001
    16 4 0 -1 0 0 0 12 0.0000 2 135 870 3525 4725 active task\001
    17 4 0 -1 0 0 0 12 0.0000 2 180 930 6450 4725 routine ptrs\001
     105 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 675.000 2700.000 675 2400 375 2700 675 3000
     116 4533 2866 4655 3129
     125 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 4657.017 2997.000 4655 2873 4533 2997 4655 3121
     132 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     14         4655 2866 4655 3129
    1815-6
    19 6 8445 1695 8655 1905
    20 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 8550 1800 105 105 8550 1800 8655 1905
    21 4 1 -1 0 0 0 10 0.0000 2 75 75 8550 1860 a\001
     166 4725 2866 4847 3129
     175 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 4849.017 2997.000 4847 2873 4725 2997 4847 3121
     182 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     19         4847 2866 4847 3129
    2220-6
    23 6 8445 1395 8655 1605
    24 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 8550 1500 105 105 8550 1500 8655 1605
    25 4 1 -1 0 0 0 10 0.0000 2 105 90 8550 1560 b\001
     216 4911 2866 5033 3129
     225 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 5035.017 2997.000 5033 2873 4911 2997 5033 3121
     232 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     24         5033 2866 5033 3129
    2625-6
    27 6 3945 1695 4155 1905
    28 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 1800 105 105 4050 1800 4155 1905
    29 4 1 -1 0 0 0 10 0.0000 2 75 75 4050 1860 a\001
     266 9027 2866 9149 3129
     275 1 0 1 0 7 50 -1 -1 0.000 0 0 0 0 9024.983 2997.000 9027 2873 9149 2997 9027 3121
     282 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     29         9027 2866 9027 3129
    3030-6
    31 6 3945 1395 4155 1605
    32 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 1500 105 105 4050 1500 4155 1605
    33 4 1 -1 0 0 0 10 0.0000 2 105 90 4050 1560 b\001
     316 9253 2866 9375 3129
     325 1 0 1 0 7 50 -1 -1 0.000 0 0 0 0 9250.983 2997.000 9253 2873 9375 2997 9253 3121
     332 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     34         9253 2866 9253 3129
     35-6
     366 9478 2866 9600 3129
     375 1 0 1 0 7 50 -1 -1 0.000 0 0 0 0 9475.983 2997.000 9478 2873 9600 2997 9478 3121
     382 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     39         9478 2866 9478 3129
    3440-6
    35411 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7650 3675 80 80 7650 3675 7730 3755
    36421 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3150 3675 80 80 3150 3675 3230 3755
     431 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4047 1793 125 125 4047 1793 3929 1752
     441 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1500 125 125 4050 1500 3932 1459
     451 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 8550 1500 125 125 8550 1500 8432 1459
     461 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 8550 1800 125 125 8550 1800 8432 1759
     471 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1200 2850 125 125 1200 2850 1082 2809
     481 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 900 2850 125 125 900 2850 782 2809
     491 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 6225 4650 105 105 6225 4650 6330 4755
     501 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3150 4650 80 80 3150 4650 3230 4730
     511 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4575 4650 105 105 4575 4650 4680 4755
    37522 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    3853         3900 1950 4200 2100
     
    6277         3000 4050 3300 4200
    63782 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    64          600 2925 1350 2925
     79         675 3000 1425 3000
    65802 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    66          600 2325 1350 2325
     81         675 2400 1425 2400
    67822 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    68          1350 2625 1425 2850
     83         1425 2700 1500 2925
    69842 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    70          1350 2325 1275 2550
     85         1425 2400 1350 2625
    71862 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    72          600 2625 1350 2625
    73 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    74          1350 2775 1275 2645 1125 2645 1050 2775 1125 2905 1275 2905
    75          1350 2775
    76 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    77          975 2775 900 2645 750 2645 675 2775 750 2905 900 2905
    78          975 2775
    79 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    80          4800 3000 4725 2870 4575 2870 4500 3000 4575 3130 4725 3130
    81          4800 3000
    82 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    83          5100 3000 5025 2870 4875 2870 4800 3000 4875 3130 5025 3130
    84          5100 3000
    85 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    86          9300 3000 9225 2870 9075 2870 9000 3000 9075 3130 9225 3130
    87          9300 3000
    88 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    89          9600 3000 9525 2870 9375 2870 9300 3000 9375 3130 9525 3130
    90          9600 3000
    91 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    92          675 2775 975 2775
    93 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    94          1050 2775 1350 2775
    95 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    96          4875 4950 4800 4820 4650 4820 4575 4950 4650 5080 4800 5080
    97          4875 4950
    98 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    99          4575 4950 4875 4950
    100 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    101          3525 4970 3450 4840 3300 4840 3225 4970 3300 5100 3450 5100
    102          3525 4970
     87         675 2700 1425 2700
    103884 1 -1 0 0 0 12 0.0000 2 135 315 2850 4275 exit\001
    104894 1 -1 0 0 0 12 0.0000 2 135 315 7350 4275 exit\001
     
    1211064 1 -1 0 0 0 12 0.0000 2 135 495 4050 1275 queue\001
    1221074 1 -1 0 0 0 12 0.0000 2 165 420 4050 1050 entry\001
    123 4 0 0 50 -1 0 11 0.0000 2 120 705 450 2250 Condition\001
    124 4 0 0 50 -1 0 11 0.0000 2 165 630 3600 5025 signalled\001
    125 4 0 0 50 -1 0 11 0.0000 2 165 525 4950 5025 waiting\001
     1084 0 0 50 -1 0 11 0.0000 2 120 705 600 2325 Condition\001
     1094 0 -1 0 0 0 12 0.0000 2 180 930 6450 4725 routine ptrs\001
     1104 0 -1 0 0 0 12 0.0000 2 135 1050 3300 4725 active thread\001
     1114 0 -1 0 0 0 12 0.0000 2 135 1215 4725 4725 blocked thread\001
  • doc/proposals/concurrency/text/basics.tex

    r9d06142 rc0d00b6  
    1111Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining. Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread perspective) across the stacks is called concurrency.
    1212
    13 Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stackfull coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption.
    14 
    15 A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchronisation are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desireable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows\cit.
     13Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stackfull coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a non-preemptive scheduling). The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption.
     14
     15A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchronisation are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desireable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows.
    1616
    1717\section{\protect\CFA 's Thread Building Blocks}
     
    307307\subsection{Alternative: Lamda Objects}
    308308
    309 For coroutines as for threads, many implementations are based on routine pointers or function objects\cit. For example, Boost implements coroutines in terms of four functor object types:
     309For coroutines as for threads, many implementations are based on routine pointers or function objects\cite{Butenhof97, ANSI14:C++, MS:VisualC++, BoostCoroutines15}. For example, Boost implements coroutines in terms of four functor object types:
    310310\begin{cfacode}
    311311asymmetric_coroutine<>::pull_type
  • doc/proposals/concurrency/text/concurrency.tex

    r9d06142 rc0d00b6  
    88Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}.
    99
    10 An approach that is worth mentioning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for systems language, which is why it was rejected as the core paradigm for concurrency in \CFA.
     10An approach that is worth mentioning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cite{Cpp-Transactions}, the performance and feature set is currently too restrictive to be the main concurrency paradigm for systems language, which is why it was rejected as the core paradigm for concurrency in \CFA.
    1111
    1212One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared-memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct.
     
    139139The \gls{multi-acq} monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order.
    140140
    141 However, such use leads to the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown\cit, solving this problem requires:
     141However, such use leads to the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown\cite{Lister77}, solving this problem requires:
    142142\begin{enumerate}
    143143        \item Dynamically tracking of the monitor-call order.
    144144        \item Implement rollback semantics.
    145145\end{enumerate}
    146 While the first requirement is already a significant constraint on the system, implementing a general rollback semantics in a C-like language is prohibitively complex \cit. In \CFA, users simply need to be carefull when acquiring multiple monitors at the same time or only use \gls{bulk-acq} of all the monitors. While \CFA provides only a partial solution, many system provide no solution and the \CFA partial solution handles many useful cases.
     146While the first requirement is already a significant constraint on the system, implementing a general rollback semantics in a C-like language is still prohibitively complex \cite{Dice10}. In \CFA, users simply need to be carefull when acquiring multiple monitors at the same time or only use \gls{bulk-acq} of all the monitors. While \CFA provides only a partial solution, many system provide no solution and the \CFA partial solution handles many useful cases.
    147147
    148148For example, \gls{multi-acq} and \gls{bulk-acq} can be used together in interesting ways:
     
    157157}
    158158\end{cfacode}
    159 This example shows a trivial solution to the bank-account transfer-problem\cit. Without \gls{multi-acq} and \gls{bulk-acq}, the solution to this problem is much more involved and requires carefull engineering.
     159This example shows a trivial solution to the bank-account transfer-problem\cite{BankTransfer}. Without \gls{multi-acq} and \gls{bulk-acq}, the solution to this problem is much more involved and requires carefull engineering.
    160160
    161161\subsection{\code{mutex} statement} \label{mutex-stmt}
    162162
    163 The call semantics discussed aboved have one software engineering issue, only a named routine can acquire the mutual-exclusion of a set of monitor. \CFA offers the \code{mutex} statement to workaround the need for unnecessary names, avoiding a major software engineering problem\cit. Listing \ref{lst:mutex-stmt} shows an example of the \code{mutex} statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired. Beyond naming, the \code{mutex} statement has no semantic difference from a routine call with \code{mutex} parameters.
     163The call semantics discussed aboved have one software engineering issue, only a named routine can acquire the mutual-exclusion of a set of monitor. \CFA offers the \code{mutex} statement to workaround the need for unnecessary names, avoiding a major software engineering problem\cite{2FTwoHardThings}. Listing \ref{lst:mutex-stmt} shows an example of the \code{mutex} statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired. Beyond naming, the \code{mutex} statement has no semantic difference from a routine call with \code{mutex} parameters.
    164164
    165165\begin{figure}
     
    232232% ======================================================================
    233233% ======================================================================
    234 In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this capability is generally achieved with internal or external scheduling as in\cit. Since internal scheduling within a single monitor is mostly a solved problem, this thesis concentrates on extending internal scheduling to multiple monitors. Indeed, like the \gls{bulk-acq} semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
     234In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this capability is generally achieved with internal or external scheduling as in \cite{Hoare74}. Since internal scheduling within a single monitor is mostly a solved problem, this thesis concentrates on extending internal scheduling to multiple monitors. Indeed, like the \gls{bulk-acq} semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
    235235
    236236First, here is a simple example of such a technique:
     
    305305This version uses \gls{bulk-acq} (denoted using the {\sf\&} symbol), but the presence of multiple monitors does not add a particularly new meaning. Synchronization happens between the two threads in exactly the same way and order. The only difference is that mutual exclusion covers more monitors. On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
    306306
    307 While deadlock issues can occur when nesting monitors, these issues are only a symptom of the fact that locks, and by extension monitors, are not perfectly composable. For monitors, a well known deadlock problem is the Nested Monitor Problem\cit, which occurs when a \code{wait} is made by a thread that holds more than one monitor. For example, the following pseudo-code runs into the nested-monitor problem :
     307While deadlock issues can occur when nesting monitors, these issues are only a symptom of the fact that locks, and by extension monitors, are not perfectly composable. For monitors, a well known deadlock problem is the Nested Monitor Problem \cite{Lister77}, which occurs when a \code{wait} is made by a thread that holds more than one monitor. For example, the following pseudo-code runs into the nested-monitor problem :
    308308\begin{multicols}{2}
    309309\begin{pseudo}
     
    771771For the first two conditions, it is easy to implement a check that can evaluate the condition in a few instruction. However, a fast check for \pscode{monitor accepts me} is much harder to implement depending on the constraints put on the monitors. Indeed, monitors are often expressed as an entry queue and some acceptor queue as in the following figure:
    772772
     773\begin{figure}[H]
    773774\begin{center}
    774775{\resizebox{0.4\textwidth}{!}{\input{monitor}}}
    775776\end{center}
     777\label{fig:monitor}
     778\end{figure}
    776779
    777780There are other alternatives to these pictures, but in the case of this picture, implementing a fast accept check is relatively easy. Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (e.g., 128) of mutex members. This technique cannot be used in \CFA because it relies on the fact that the monitor type enumerates (declares) all the acceptable routines. For OO languages this does not compromise much since monitors already have an exhaustive list of member routines. However, for \CFA this is not the case; routines can be added to a type anywhere after its declaration. It is important to note that the bitmask approach does not actually require an exhaustive list of routines, but it requires a dense unique ordering of routines with an upper-bound and that ordering must be consistent across translation units.
  • doc/proposals/concurrency/text/future.tex

    r9d06142 rc0d00b6  
    66
    77\section{Flexible Scheduling} \label{futur:sched}
    8 
     8An important part of concurrency is scheduling. Different scheduling algorithm can affact peformance (both in terms of average and variation). However, no single scheduler is optimal for all workloads and therefore there is value in being able to change the scheduler for given programs. One solution is to offer various tweaking options to users, allowing the scheduler to be adjusted the to requirements of the workload. However, in order to be truly flexible, it would be interesting to allow users to add arbitrary data and arbirary scheduling algorithms to the scheduler. For example, a web server could attach Type-of-Service information to threads and have a ``ToS aware'' scheduling algorithm tailored to this specific web server. This path of flexible schedulers will be explored for \CFA.
    99
    1010\section{Non-Blocking IO} \label{futur:nbio}
    1111While most of the parallelism tools
    12 However, many modern workloads are not bound on computation but on IO operations, an common case being webservers and XaaS (anything as a service). These type of workloads often require significant engineering around amortising costs of blocking IO operations. While improving throughtput of these operations is outside what \CFA can do as a language, it can help users to make better use of the CPU time otherwise spent waiting on IO operations. The current trend is to use asynchronous programming using tools like callbacks and/or futurs and promises\cit. However, while these are valid solutions, they lead to code that is harder to read and maintain because it is much less linear
    13 
    14 
     12However, many modern workloads are not bound on computation but on IO operations, an common case being webservers and XaaS (anything as a service). These type of workloads often require significant engineering around amortising costs of blocking IO operations. While improving throughtput of these operations is outside what \CFA can do as a language, it can help users to make better use of the CPU time otherwise spent waiting on IO operations. The current trend is to use asynchronous programming using tools like callbacks and/or futurs and promises\cite. However, while these are valid solutions, they lead to code that is harder to read and maintain because it is much less linear
    1513
    1614\section{Other concurrency tools} \label{futur:tools}
    17 
     15While monitors offer a flexible and powerful concurent core for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package. Example of such tools can include simple locks and condition variables, futures and promises\cite{promises}, and executors. These additional features are useful when monitors offer a level of abstraction which is indaquate for certain tasks.
    1816
    1917\section{Implicit threading} \label{futur:implcit}
    20 Simpler applications can benefit greatly from having implicit parallelism. That is, parallelism that does not rely on the user to write concurrency. This type of parallelism can be achieved both at the language level and at the library level. The cannonical example of implcit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithm\cit. Listing \ref{lst:parfor} shows three different code examples that accomplish pointwise sums of large arrays. Note that none of these example explicitly declare any concurrency or parallelism objects.
     18Simpler applications can benefit greatly from having implicit parallelism. That is, parallelism that does not rely on the user to write concurrency. This type of parallelism can be achieved both at the language level and at the library level. The cannonical example of implcit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithm\cite{uC++book}. Listing \ref{lst:parfor} shows three different code examples that accomplish pointwise sums of large arrays. Note that none of these example explicitly declare any concurrency or parallelism objects.
    2119
    2220\begin{figure}
     
    103101\end{figure}
    104102
    105 Implicit parallelism is a general solution and therefore is
    106 
    107 \section{Multiple Paradigms} \label{futur:paradigms}
     103Implicit parallelism is a general solution and therefore has its limitations. However, it is a quick and simple approach to parallelism which may very well be sufficient for smaller applications and reduces the amount of boiler-plate that is needed to start benefiting from parallelism in modern CPUs.
    108104
    109105
    110 \section{Transactions} \label{futur:transaction}
    111 Concurrency and parallelism is still a very active field that strongly benefits from hardware advances. As such certain features that aren't necessarily mature enough in their current state could become relevant in the lifetime of \CFA.
  • doc/proposals/concurrency/text/internals.tex

    r9d06142 rc0d00b6  
    11
    22\chapter{Behind the scene}
    3 There are several challenges specific to \CFA when implementing concurrency. These challenges are direct results of \gls{bulk-acq} and loose object definitions. These two constraints are to root cause of most design decisions in the implementation. Furthermore, to avoid the head-aches of dynamically allocating memory in a concurrent environment, the internal-scheduling design is (almost) entirely free of mallocs and other dynamic memory allocation scheme. This is to avoid the chicken and egg problem \cite{Chicken} of having a memory allocator that relies on the threading system and a threading system that relies on the runtime. This extra goal, means that memory management is a constant concern in the design of the system.
    4 
    5 The main memory concern for concurrency is queues. All blocking operations are made by parking threads onto queues. These queues need to be intrinsic\cit to avoid the need memory allocation. This entails that all the fields needed to keep track of all needed information. Since many conconcurrency operations can use an unbound amount of memory (depending on \gls{bulk-acq}) statically defining information in the intrusive fields of threads is insufficient. The only variable sized container that does not require memory allocation is the callstack, which is heavily used in the implementation of internal scheduling. Particularly the GCC extension variable length arrays which is used extensively.
     3There are several challenges specific to \CFA when implementing concurrency. These challenges are a direct result of \gls{bulk-acq} and loose object-definitions. These two constraints are the root cause of most design decisions in the implementation. Furthermore, to avoid contention from dynamically allocating memory in a concurrent environment, the internal-scheduling design is (almost) entirely free of mallocs. This is to avoid the chicken and egg problem \cite{Chicken} of having a memory allocator that relies on the threading system and a threading system that relies on the runtime. This extra goal, means that memory management is a constant concern in the design of the system.
     4
     5The main memory concern for concurrency is queues. All blocking operations are made by parking threads onto queues. The queue design needs to be intrusive\cite{IntrusiveData} to avoid the need for memory allocation, which entails that all the nodes need specific fields to keep track of all needed information. Since many concurrency operations can use an unbound amount of memory (depending on \gls{bulk-acq}), statically defining information in the intrusive fields of threads is insufficient. The only variable sized container that does not require memory allocation is the callstack, which is heavily used in the implementation of internal scheduling. Particularly variable length arrays, which are used extensively.
    66
    77Since stack allocation is based around scope, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable length. The threads and the condition both allow a fixed amount of memory to be stored, while mutex-routines and the actual blocking call allow for an unbound amount (though the later is preferable in terms of performance).
    88
    9 Note that since the major contributions of this thesis are extending monitor semantics to \gls{bulk-acq} and loose object definitions, any challenges that are not resulting of these characteristiques of \CFA are consired as problems which have already been solved and therefore will not be discussed further.
     9Note that since the major contributions of this thesis are extending monitor semantics to \gls{bulk-acq} and loose object definitions, any challenges that are not resulting of these characteristiques of \CFA are considered as solved problems and therefore not discussed further.
    1010
    1111% ======================================================================
     
    1515% ======================================================================
    1616
    17 The first step towards the monitor implementation is simple mutex-routines using monitors. In the single monitor case, this is done using the entry/exit procedure highlighted in listing \ref{lst:entry1}. This entry/exit procedure doesn't actually have to be extended to support multiple monitors, indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlocks\cit. In \CFA, ordering of monitor relies on memory ordering, this is sufficient because all objects are guaranteed to have distinct non-overlaping memory layouts and mutual-exclusion for a monitor is only defined for its lifetime, meaning that destroying a monitor while it is acquired is undefined behavior. When a mutex call is made, the concerned monitors are agregated into an variable-length pointer array and sorted based on pointer values. This array is concerved during the entire duration of the mutual-exclusion and it's ordering reused extensively.
     17The first step towards the monitor implementation is simple mutex-routines using monitors. In the single monitor case, this is done using the entry/exit procedure highlighted in listing \ref{lst:entry1}. This entry/exit procedure does not actually have to be extended to support multiple monitors, indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlocks\cite{Havender68}. In \CFA, ordering of monitor relies on memory ordering, this is sufficient because all objects are guaranteed to have distinct non-overlaping memory layouts and mutual-exclusion for a monitor is only defined for its lifetime, meaning that destroying a monitor while it is acquired is undefined behavior. When a mutex call is made, the concerned monitors are agregated into a variable-length pointer array and sorted based on pointer values. This array presists for the entire duration of the mutual-exclusion and its ordering reused extensively.
    1818\begin{figure}
    1919\begin{multicols}{2}
     
    9696\end{tabular}
    9797\end{center}
    98 \caption{Callsite vs entry-point locking for mutex calls}
     98\caption{Call-site vs entry-point locking for mutex calls}
    9999\label{fig:locking-site}
    100100\end{figure}
    101101
    102 Note the \code{mutex} keyword relies on the type system, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait, for example:
     102Note the \code{mutex} keyword relies on the type system, which means that in cases where a generic monitor routine is desired, writing the mutex routine is possible with the proper trait, for example:
    103103\begin{cfacode}
    104 //Incorrect: T is not a monitor
     104//Incorrect: T may not be monitor
    105105forall(dtype T)
    106106void foo(T * mutex t);
     
    111111\end{cfacode}
    112112
    113 Both entry-point and callsite locking are valid implementations. The current \CFA implementations uses entry-point locking because it seems to require less work if done using \gls{raii}, effectively transferring the burden of implementation to object construction/destruction. The same could be said of callsite locking, the difference being that the later does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, i.e.: the function body.
     113Both entry-point and callsite locking are feasible implementations. The current \CFA implementations uses entry-point locking because it requires less work when using \gls{raii}, effectively transferring the burden of implementation to object construction/destruction. The same could be said of callsite locking, the difference being that the later does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, i.e.: the function body. Furthermore, entry-point locking requires less code generation since any useful routine is called at least as often as it is define, there can be only one entry-point but many callsites.
    114114
    115115% ======================================================================
     
    119119% ======================================================================
    120120
    121 Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency.
     121Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency. Each component of the picture is explained in details in the fllowing sections.
    122122
    123123\begin{figure}
     
    130130
    131131\subsection{Context Switching}
    132 As mentionned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading. This is because they share the same mechanism for context-switching between different stacks. To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific function call. This assumptions means that the basic recipe for context-switch is only to copy all callee-saved registers unto the stack and then switch the stack registers with the ones of the target coroutine/thread. Note that instruction pointer can be left untouched since the context-switch always inside the same function. In the case of coroutines, that is the entire story. Threads however do not simply context-switch between each other directly. The context-switch to processors which is where the scheduling happens. This method is called a 2-step context-switch and has the advantage of having a clear distinction between user code and the "kernel" where scheduling and other system operation happen. Obiously, this has the cost of doubling the context-switch cost from because threads must context-switch to an intermediate stack. However, the performance of the 2-step context-switch is still superior to a \code{pthread_yield}(see section \ref{results}). additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch to use manually (or as part of monitors). This option is not currently present in \CFA but the changes required to add it are strictly additive.
     132As mentionned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading. This is because they share the same mechanism for context-switching between different stacks. To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific function call. This assumption means that the context-switch only has to copy the callee-saved registers onto the stack and then switch the stack registers with the ones of the target coroutine/thread. Note that the instruction pointer can be left untouched since the context-switch is always inside the same function. Threads however do not context-switch between each other directly. They context-switch to the scheduler. This method is called a 2-step context-switch and has the advantage of having a clear distinction between user code and the kernel where scheduling and other system operation happen. Obiously, this has the cost of doubling the context-switch cost because threads must context-switch to an intermediate stack. However, the performance of the 2-step context-switch is still superior to a \code{pthread_yield}(see section \ref{results}). additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch to use manually (or as part of monitors). This option is not currently present in \CFA but the changes required to add it are strictly additive.
    133133
    134134\subsection{Processors}
    135 Parallelism in \CFA are built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically pthreads in the current implementation of \CFA. Indeed, any parallelism must go through operatiing system librairies. However, \gls{cfathread} are still the main source of concurrency, processors are simply the underlying source of parallelism. Indeed, processor kernel threads simply fetch a user-level thread from the scheduler and run, they are effectively executers for user-threads. The main benefit of this approach is that it offers a well defined boundary between kernel code and user-code, for example kernel thread quiescing, scheduling and interrupt handling. Processors internally use coroutines to take advantage of the existing context-switching semantics.
     135Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically pthreads in the current implementation of \CFA. Indeed, any parallelism must go through operating-system librairies. However, \glspl{uthread} are still the main source of concurrency, processors are simply the underlying source of parallelism. Indeed, processor \glspl{kthread} simply fetch a \glspl{uthread} from the scheduler and run, they are effectively executers for user-threads. The main benefit of this approach is that it offers a well defined boundary between kernel code and user code, for example, kernel thread quiescing, scheduling and interrupt handling. Processors internally use coroutines to take advantage of the existing context-switching semantics.
    136136
    137137\subsection{Stack management}
    138138One of the challenges of this system is to reduce the footprint as much as possible. Specifically, all pthreads created also have a stack created with them, which should be used as much as possible. Normally, coroutines also create there own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the kernel thread stack, effectively stealing the processor stack. The exception to this rule is the Main Processor, i.e. the initial kernel thread that is given to any program. In order to respect user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor.
    139139
    140 \subsection{Preemption}
    141 Finally, an important aspect for any complete threading system is preemption. As mentionned in chapter \ref{basics}, preemption introduces an extra degree of unceretainty, which enables users to have multiple threads interleave transparrently between eachother, rather than having to cooperate between thread for proper scheduling and CPU distribution. Indeed, preemption is desireable because it adds a degree of isolation between tasks. In a fully cooperative system, any thread that runs into a long loop can starve other threads, while in a preemptive system starvation can still occur but it does not rely on every thread having to yield or block on a regular basis, which reduces significantly programmer burden. Obviously, preemption is not optimal for every workload, however any preemptive system can become a cooperative system by making the time-slices extremely large. Which is why \CFA uses a preemptive threading system.
    142 
    143 Preemption in \CFA is based on kernel timers which are used to run a discreet event simulation. Every processor keeps track of the current time and registers an expiration time with the preemption system. When the preemption system receives a change in preemption it sorts these expiration times in a list and sets a kernel timer for the closest one, effectiveling stepping between preemption events on each signals sent by the timer. These timers use the linux signal {\tt SIGALRM}, which is delivered to the process. This is important because when delivering signals to a process, the kernel documentation states that the signal can be delivered to any kernel thread for which the signal isn't block i.e. :
     140\subsection{Preemption} \label{preemption}
     141Finally, an important aspect for any complete threading system is preemption. As mentionned in chapter \ref{basics}, preemption introduces an extra degree of uncertainty, which enables users to have multiple threads interleave transparently, rather than having to cooperate among threads for proper scheduling and CPU distribution. Indeed, preemption is desireable because it adds a degree of isolation among threads. In a fully cooperative system, any thread that runs into a long loop can starve other threads, while in a preemptive system starvation can still occur but it does not rely on every thread having to yield or block on a regular basis, which reduces significantly a programmer burden. Obviously, preemption is not optimal for every workload, however any preemptive system can become a cooperative system by making the time-slices extremely large. Which is why \CFA uses a preemptive threading system.
     142
     143Preemption in \CFA is based on kernel timers, which are used to run a discrete-event simulation. Every processor keeps track of the current time and registers an expiration time with the preemption system. When the preemption system receives a change in preemption, it sorts these expiration times in a list and sets a kernel timer for the closest one, effectively stepping between preemption events on each signals sent by the timer. These timers use the linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread. This results in an implementation problem,because when delivering signals to a process, the kernel documentation states that the signal can be delivered to any kernel thread for which the signal is not blocked i.e. :
    144144\begin{quote}
    145145A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked. If more than one of the threads has the signal unblocked, then the kernel chooses an arbitrary thread to which to deliver the signal.
     
    148148For the sake of simplicity and in order to prevent the case of having two threads receiving alarms simultaneously, \CFA programs block the {\tt SIGALRM} signal on every thread except one. Now because of how involontary context-switches are handled, the kernel thread handling {\tt SIGALRM} cannot also be a processor thread.
    149149
    150 Involontary context-switching is done by sending {\tt SIGUSER1} to the corresponding processor and having the thread yield from inside the signal handler. Effectively context-switch away from the signal-handler back to the kernel and the signal-handler frame will be unwound when the thread is scheduled again. This means that a signal-handler can start on one kernel thread and terminate on a second kernel thread (but the same user thread). It is important to note that signal-handlers save and restore signal masks because user-thread migration can cause signal mask to migrate from one kernel thread to another. This is only a problem if all kernel threads among which a user thread can migrate differ in terms of signal masks. However, since the kernel thread hanlding preemption requires a different signal mask, executing user threads on the kernel alarm thread can cause deadlocks. For this reason, the alarm thread is on a tight loop around a system call to \code{sigwait} or more specifically \code{sigwaitinfo}, requiring very little CPU time for preemption. One final detail about the alarm thread is how to wake it when additional communication is required (e.g. on thread termination). This is also done using {\tt SIGALRM}, but sent throught the \code{pthread_sigqueue}. Indeed, \code{sigwait} can differentiate signals sent from \code{pthread_sigqueue} from signals sent from alarms or the kernel.
    151 
    152 \subsection{Scheduler} \footnote{ I'm not sure what to write here, is this section even needed. }
    153 Finally, an aspect that was not mentionned yet is the scheduling algorithm. Currently, the \CFA scheduler uses a single ready queue for all processors. Will this is not the highest performance algorithm, it has the significant advantage of being robust to heterogenous workloads. This is a very simple scheduling approach but is sufficient to for the context of this thesis.
    154 
    155 What to do here?
    156 
    157 However, when
    158 As will be mentionned \ref{futur:sched} it needs to be updated when clusters will be
    159 
    160 clusters
    161 
    162 
    163 
    164 Among the most pressing updates to the \CFA
    165 uses single queue
    166 in future should move to multiple queues with workstealing
    167 general purpouse means robust > fast
    168 worksharing can higher standard deviation in performance
    169 
     150Involuntary context-switching is done by sending signal {\tt SIGUSER1} to the corresponding processor and having the thread yield from inside the signal handler. Effectively context-switching away from the signal-handler back to the kernel and the signal-handler frame is eventually unwound when the thread is scheduled again. This approach means that a signal-handler can start on one kernel thread and terminate on a second kernel thread (but the same user thread). It is important to note that signal-handlers save and restore signal masks because user-thread migration can cause signal mask to migrate from one kernel thread to another. This behaviour is only a problem if all kernel threads among which a user thread can migrate differ in terms of signal masks\footnote{Sadly, official POSIX documentation is silent on what distiguishes ``async-signal-safe'' functions from other functions}. However, since the kernel thread hanlding preemption requires a different signal mask, executing user threads on the kernel alarm thread can cause deadlocks. For this reason, the alarm thread is on a tight loop around a system call to \code{sigwaitinfo}, requiring very little CPU time for preemption. One final detail about the alarm thread is how to wake it when additional communication is required (e.g., on thread termination). This unblocking is also done using {\tt SIGALRM}, but sent throught the \code{pthread_sigqueue}. Indeed, \code{sigwait} can differentiate signals sent from \code{pthread_sigqueue} from signals sent from alarms or the kernel.
     151
     152\subsection{Scheduler}
     153Finally, an aspect that was not mentionned yet is the scheduling algorithm. Currently, the \CFA scheduler uses a single ready queue for all processors, which is the simplest approach to scheduling. Further discussion on scheduling is present in section \label{futur:sched}.
    170154
    171155% ======================================================================
     
    174158% ======================================================================
    175159% ======================================================================
    176 To ease the understanding of monitors, like many other concepts, they are generelly represented graphically. While non-scheduled monitors are simple enough for a graphical representation to be useful, internal scheduling is complex enough to justify a visual representation. The following figure is the traditionnal illustration of a monitor :
    177 
     160The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:monitor} for convenience) :
     161
     162\begin{figure}[H]
    178163\begin{center}
    179164{\resizebox{0.4\textwidth}{!}{\input{monitor}}}
    180165\end{center}
    181 
    182 This picture has several components, the two most important being the entry-queue and the AS-stack. The entry-queue is a (almost) FIFO list where threads waiting to enter are parked, while the AS-stack is a FILO list used for threads that have been signaled or otherwise marked as running next. For \CFA, the previous picture does not have support for blocking multiple monitors on a single condition. To support \gls{bulk-acq} two changes to this picture are required. First, it doesn't make sense to tie the condition to a single monitor since blocking two monitors as one would require arbitrarily picking a monitor to hold the condition. Secondly, the object waiting on the conditions and AS-stack cannot simply contain the waiting thread since a single thread can potentially wait on multiple monitors. As mentionned in section \ref{intsched}, the handling in multiple monitors is done by partially passing, which entails that each concerned monitor needs to have a node object. However, for waiting on the condition, since all threads need to wait together, a single object needs to be queued in the condition. Moving out the condition and updating the node types yields :
    183 
     166\caption{Traditional illustration of a monitor}
     167\label{fig:monitor}
     168\end{figure}
     169
     170This picture has several components, the two most important being the entry-queue and the AS-stack. The entry-queue is an (almost) FIFO list where threads waiting to enter are parked, while the acceptor-signalor (AS) stack is a FILO list used for threads that have been signalled or otherwise marked as running next.
     171
     172For \CFA, this picture does not have support for blocking multiple monitors on a single condition. To support \gls{bulk-acq} two changes to this picture are required. First, it is non longer helpful to attach the condition to a single monitor. Secondly, the thread waiting on the conditions has to be seperated multiple monitors, which yields :
     173
     174\begin{figure}[H]
    184175\begin{center}
    185176{\resizebox{0.8\textwidth}{!}{\input{int_monitor}}}
    186177\end{center}
    187 
    188 This picture and the proper entry and leave algorithms is the fundamental implementation of internal scheduling (see listing \ref{lst:entry2}).
     178\caption{Illustration of \CFA monitor}
     179\label{fig:monitor_cfa}
     180\end{figure}
     181
     182This picture and the proper entry and leave algorithms is the fundamental implementation of internal scheduling (see listing \ref{lst:entry2}). Note that when threads are moved from the condition to the AS-stack, it splits the thread into to pieces. The thread is woken up when all the pieces have moved from the AS-stacks to the active thread seat. In this picture, the threads are split into halves but this is only because there are two monitors in this picture. For a specific signaling operation every monitor needs a piece of thread on its AS-stack.
    189183
    190184\begin{figure}[b]
     
    219213\end{figure}
    220214
    221 Some important things to notice about the exit routine. The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{lst:entry2}. Basically, the solution boils down to having a seperate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership. This solution is deadlock safe as well as preventing any potential barging.
    222 
    223 The data structure used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the callstack of the \code{wait} and \code{signal_block} routines.
     215Some important things to notice about the exit routine. The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{lst:entry2}. Basically, the solution boils down to having a seperate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership. This solution is deadlock safe as well as preventing any potential barging. The data structure used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the callstack of the \code{wait} and \code{signal_block} routines.
     216
     217\begin{figure}[H]
     218\begin{center}
     219{\resizebox{0.8\textwidth}{!}{\input{monitor_structs.pstex_t}}}
     220\end{center}
     221\caption{Data structures involved in internal/external scheduling}
     222\label{fig:structs}
     223\end{figure}
     224
     225Figure \ref{fig:structs} shows a high level representation of these data-structures. The main idea behind them is that, while figure \ref{fig:monitor_cfa} is a nice illustration in theory, in practice breaking a threads into multiple pieces to put unto intrusive stacks does not make sense. The \code{condition node} is the data structure that is queued into a condition variable and, when signaled, the condition queue is popped and each \code{condition criterion} are moved to the AS-stack. Once all the criterion have be popped from their respective AS-stacks, the thread is woken-up, which is what is shown in listing \ref{lst:entry2}.
    224226
    225227% ======================================================================
     
    228230% ======================================================================
    229231% ======================================================================
    230 Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that entry-queues are no longer specific to a single monitor, as mentionned in section \ref{extsched}. This means that some kind of entry-queues must be used that is aware of both monitors and which holds threads that are currently waiting to enter the critical section. This challenge is solved for internal scheduling by having the entry-queues in conditions no longer be tied to a monitor, effectively allowing conditions to be moved outside of monitors. However, in the case of external scheduling, acceptable routines must be aware of the entry queues, which means they must be stored inside at least one of the monitors that will be acquired. This in turn adds the requirement that a systematic algorithm of disambiguating which monitor holds the relevant queue regardless of user ordering. The proposed algorithm is to fall back on monitor lock ordering and specify that the monitor that is acquired first is the one with the relevant entry queue. This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonable constraint.
    231 
    232 This algorithm choice has two consequences, the entry queue of the highest priority monitor is no longer a true FIFO queue and the queue of the lowest priority monitor is both required and probably unused. The queue can no longer be a FIFO queue because instead of simply containing the waiting threads in order of arrival, they also contain a set of monitors. Therefore, another thread whos set contains the same highest priority monitor but different lower priority monitors may arrive first but enter the critical section after a thread with the correct pairing. Secondly, since it is not known at compile time which monitor will be the lowest priority monitor, every monitor needs to have the correct queues even though it is probable that some queues will go unused for the entire duration of the program, for example if a monitor is only used in a pair.
     232Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentionned in section \ref{extsched}. For internal scheduling, these queues are part of condition variables which are still unique for a given scheduling operation (e.g., no single statment uses multiple conditions). However, in the case of external scheduling, there is no equivalent object which is associated with \code{waitfor} statements. This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired. The monitors being the only objects that have sufficient lifetime and are available on both sides of the \code{waitfor} statment. This requires an algorithm to choose which monitor holds the relevant queue. It is also important that said algorithm be independent of the order in which users list parameters. The proposed algorithm is to fall back on monitor lock ordering and specify that the monitor that is acquired first is the one with the relevant wainting queue. This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonable constraint.
     233
     234This algorithm choice has two consequences :
     235\begin{itemize}
     236        \item The queue of the highest priority monitor is no longer a true FIFO queue because threads can be moved to the front of the queue. These queues need to contain a set of monitors for each of the waiting threads. Therefore, another thread whose set contains the same highest priority monitor but different lower priority monitors may arrive first but enter the critical section after a thread with the correct pairing.
     237        \item The queue of the lowest priority monitor is both required and potentially unused. Indeed, since it is not known at compile time which monitor will be the lowest priority monitor, every monitor needs to have the correct queues even though it is possible that some queues will go unused for the entire duration of the program, for example if a monitor is only used in a specific pair.
     238\end{itemize}
    233239
    234240Therefore, the following modifications need to be made to support external scheduling :
    235241\begin{itemize}
    236         \item The threads waiting on the entry-queue need to keep track of which routine is trying to enter, and using which set of monitors. The \code{mutex} routine already has all the required information on it's stack so the thread only needs to keep a pointer to that information.
     242        \item The threads waiting on the entry-queue need to keep track of which routine is trying to enter, and using which set of monitors. The \code{mutex} routine already has all the required information on its stack so the thread only needs to keep a pointer to that information.
    237243        \item The monitors need to keep a mask of acceptable routines. This mask contains for each acceptable routine, a routine pointer and an array of monitors to go with it. It also needs storage to keep track of which routine was accepted. Since this information is not specific to any monitor, the monitors actually contain a pointer to an integer on the stack of the waiting thread. Note that the complete mask can be pushed to any owned monitors, regardless of \code{when} statements, the \code{waitfor} statement is used in a context where the thread already has full ownership of (at least) every concerned monitor and therefore monitors will refuse all calls no matter what.
    238244        \item The entry/exit routine need to be updated as shown in listing \ref{lst:entry3}.
    239245\end{itemize}
    240246
     247\subsection{External scheduling - destructors}
    241248Finally, to support the ordering inversion of destructors, the code generation needs to be modified to use a special entry routine. This routine is needed because of the storage requirements of the call order inversion. Indeed, when waiting for the destructors, storage is need for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for. For regular \code{waitfor} statements, the callstack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later. The waitfor semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
    242249
     
    250257        continue
    251258elif matches waitfor mask
    252         push waiter to AS-stack
     259        push criterions to AS-stack
    253260        continue
    254261else
     
    265272                if all monitors ready
    266273                        wake-up thread
     274                endif
     275        endif
    267276
    268277        if entry queue not empty
    269278                wake-up thread
     279        endif
    270280\end{pseudo}
    271281\end{multicols}
     
    295305Waitfor
    296306\begin{pseudo}
    297 lock all monitors
    298307if matching thread is already there
    299308        if found destructor
     
    303312                push self to AS-stack
    304313                baton pass
     314        endif
    305315        return
    306 
     316endif
    307317if non-blocking
    308318        Unlock all monitors
    309319        Return
     320endif
    310321
    311322push self to AS-stack
  • doc/proposals/concurrency/text/parallelism.tex

    r9d06142 rc0d00b6  
    1515Examples of languages that support \glspl{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
    1616
    17 \subsection{Fibers : user-level threads without preemption}
     17\subsection{Fibers : user-level threads without preemption} \label{fibers}
    1818A popular varient of \glspl{uthread} is what is often refered to as \glspl{fiber}. However, \glspl{fiber} do not present meaningful semantical differences with \glspl{uthread}. The significant difference between \glspl{uthread} and \glspl{fiber} is the lack of \gls{preemption} in the later one. Advocates of \glspl{fiber} list their high performance and ease of implementation as majors strenghts of \glspl{fiber} but the performance difference between \glspl{uthread} and \glspl{fiber} is controversial, and the ease of implementation, while true, is a weak argument in the context of language design. Therefore this proposal largely ignores fibers.
    1919
     
    3333
    3434\subsection{Future Work: Machine setup}\label{machine}
    35 While this was not done in the context of this thesis, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heteregenous setups. For example, system using \acrshort{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certains CPU cores. OS support for CPU affinity is now common \cit, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
     35While this was not done in the context of this thesis, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heteregenous setups. For example, system using \acrshort{numa} configurations may benefit from users being able to tie clusters and\/or kernel threads to certains CPU cores. OS support for CPU affinity is now common \cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx} which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
    3636
    37 \subsection{Paradigms}\label{cfaparadigms}
    38 Given these building blocks, it is possible to reproduce all three of the popular paradigms. Indeed, \glspl{uthread} is the default paradigm in \CFA. However, disabling \gls{preemption} on the \gls{cfacluster} means \glspl{cfathread} effectively become \glspl{fiber}. Since several \glspl{cfacluster} with different scheduling policy can coexist in the same application, this allows \glspl{fiber} and \glspl{uthread} to coexist in the runtime of an application. Finally, it is possible to build executors for thread pools from \glspl{uthread} or \glspl{fiber}.
     37% \subsection{Paradigms}\label{cfaparadigms}
     38% Given these building blocks, it is possible to reproduce all three of the popular paradigms. Indeed, \glspl{uthread} is the default paradigm in \CFA. However, disabling \gls{preemption} on the \gls{cfacluster} means \glspl{cfathread} effectively become \glspl{fiber}. Since several \glspl{cfacluster} with different scheduling policy can coexist in the same application, this allows \glspl{fiber} and \glspl{uthread} to coexist in the runtime of an application. Finally, it is possible to build executors for thread pools from \glspl{uthread} or \glspl{fiber}.
  • doc/proposals/concurrency/text/results.tex

    r9d06142 rc0d00b6  
    11% ======================================================================
    22% ======================================================================
    3 \chapter{Performance results}
     3\chapter{Performance results} \label{results}
    44% ======================================================================
    55% ======================================================================
    6 
    76\section{Machine setup}
    8 
    9 \begin{figure}
     7Table \ref{tab:machine} shows the characteristiques of the machine used to run the benchmarks. All tests where made on this machine.
     8\begin{figure}[H]
    109\begin{center}
    1110\begin{tabular}{| l | r | l | r |}
     
    3736
    3837\section{Micro benchmarks}
     38All benchmarks are run using the same harness to produce the results, seen as the \code{BENCH()} macro in the following examples. This macro uses the following logic to benchmark the code :
     39\begin{pseudo}
     40#define BENCH(run, result)
     41        gettime();
     42        run;
     43        gettime();
     44        result = (after - before) / N;
     45\end{pseudo}
     46The method used to get time is \code{clock_gettime(CLOCK_THREAD_CPUTIME_ID);}. Each benchmark is using many interations of a simple call to measure the cost of the call. The specific number of interation dependes on the specific benchmark.
     47
     48\subsection{Context-switching}
     49The first interesting benchmark is to measure how long context-switches take. The simplest approach to do this is to yield on a thread, which executes a 2-step context switch. In order to make the comparison fair, coroutines also execute a 2-step context-switch, which is a resume/suspend cycle instead of a yield. Listing \ref{lst:ctx-switch} shows the code for coroutines and threads. All omitted tests are functionally identical to one of these tests. The results can be shown in table \ref{tab:ctx-switch}.
     50\begin{figure}
     51\begin{multicols}{2}
     52\CFA Coroutines
     53\begin{cfacode}
     54coroutine GreatSuspender {};
     55void main(GreatSuspender& this) {
     56        while(true) { suspend(); }
     57}
     58int main() {
     59        GreatSuspender s;
     60        resume(s);
     61        BENCH(
     62                for(size_t i=0; i<n; i++) {
     63                        resume(s);
     64                },
     65                result
     66        )
     67        printf("%llu\n", result);
     68}
     69\end{cfacode}
     70\columnbreak
     71\CFA Threads
     72\begin{cfacode}
     73
     74
     75
     76
     77int main() {
     78
     79
     80        BENCH(
     81                for(size_t i=0; i<n; i++) {
     82                        yield();
     83                },
     84                result
     85        )
     86        printf("%llu\n", result);
     87}
     88\end{cfacode}
     89\end{multicols}
     90\caption{\CFA benchmark code used to measure context-switches for coroutines and threads.}
     91\label{lst:ctx-switch}
     92\end{figure}
    3993
    4094\begin{figure}
     
    54108\caption{Context Switch comparaison. All numbers are in nanoseconds(\si{\nano\second})}
    55109\label{tab:ctx-switch}
     110\end{figure}
     111
     112\subsection{Mutual-exclusion}
     113The next interesting benchmark is to measure the overhead to enter/leave a critical-section. For monitors, the simplest appraoch is to measure how long it takes enter and leave a monitor routine. Listing \ref{lst:mutex} shows the code for \CFA. 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 are also mesured. The results can be shown in table \ref{tab:mutex}.
     114
     115\begin{figure}
     116\begin{cfacode}
     117monitor M {};
     118void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
     119
     120int main() {
     121        M m/*, m2, m3, m4*/;
     122        BENCH(
     123                for(size_t i=0; i<n; i++) {
     124                        call(m/*, m2, m3, m4*/);
     125                },
     126                result
     127        )
     128        printf("%llu\n", result);
     129}
     130\end{cfacode}
     131\caption{\CFA benchmark code used to measure mutex routines.}
     132\label{lst:mutex}
    56133\end{figure}
    57134
     
    75152\end{figure}
    76153
     154\subsection{Internal scheduling}
     155The Internal scheduling benchmark measures the cost of waiting on and signaling a condition variable. Listing \ref{lst:int-sched} shows the code for \CFA. The results can be shown in table \ref{tab:int-sched}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
     156
     157\begin{figure}
     158\begin{cfacode}
     159volatile int go = 0;
     160condition c;
     161monitor M {};
     162M m1;
     163
     164void __attribute__((noinline)) do_call( M & mutex a1 ) { signal(c); }
     165
     166thread T {};
     167void ^?{}( T & mutex this ) {}
     168void main( T & this ) {
     169        while(go == 0) { yield(); }
     170        while(go == 1) { do_call(m1); }
     171}
     172int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
     173        go = 1;
     174        BENCH(
     175                for(size_t i=0; i<n; i++) {
     176                        wait(c);
     177                },
     178                result
     179        )
     180        printf("%llu\n", result);
     181        go = 0;
     182        return 0;
     183}
     184int main() {
     185        T t;
     186        return do_wait(m1);
     187}
     188\end{cfacode}
     189\caption{Benchmark code for internal scheduling}
     190\label{lst:int-sched}
     191\end{figure}
     192
    77193\begin{figure}
    78194\begin{center}
     
    92208\end{figure}
    93209
     210\subsection{External scheduling}
     211The Internal scheduling benchmark measures the cost of the \code{waitfor} statement (\code{_Accept} in \uC). Listing \ref{lst:ext-sched} shows the code for \CFA. The results can be shown in table \ref{tab:ext-sched}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
     212
     213\begin{figure}
     214\begin{cfacode}
     215volatile int go = 0;
     216monitor M {};
     217M m1;
     218thread T {};
     219
     220void __attribute__((noinline)) do_call( M & mutex a1 ) {}
     221
     222void ^?{}( T & mutex this ) {}
     223void main( T & this ) {
     224        while(go == 0) { yield(); }
     225        while(go == 1) { do_call(m1); }
     226}
     227int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
     228        go = 1;
     229        BENCH(
     230                for(size_t i=0; i<n; i++) {
     231                        waitfor(call, a1);
     232                },
     233                result
     234        )
     235        printf("%llu\n", result);
     236        go = 0;
     237        return 0;
     238}
     239int main() {
     240        T t;
     241        return do_wait(m1);
     242}
     243\end{cfacode}
     244\caption{Benchmark code for external scheduling}
     245\label{lst:ext-sched}
     246\end{figure}
     247
    94248\begin{figure}
    95249\begin{center}
     
    109263\end{figure}
    110264
    111 \begin{figure}
    112 \begin{center}
    113 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
    114 \cline{2-4}
    115 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
    116 \hline
    117 Pthreads                & 26974.5       & 26977 & 124.12 \\
    118 \CFA Coroutines & 5             & 5             & 0      \\
    119 \CFA Threads    & 1122.5        & 1109.86       & 36.54  \\
    120 \uC Coroutines  & 106           & 107.04        & 1.61   \\
    121 \uC Threads             & 525.5 & 533.04        & 11.14  \\
     265\subsection{Object creation}
     266Finaly, the last benchmark measured is the cost of creation for concurrent objects. Listing \ref{lst:creation} shows the code for pthreads and \CFA threads. The results can be shown in table \ref{tab:creation}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests. The only note here is that the callstacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
     267
     268\begin{figure}
     269\begin{multicols}{2}
     270pthread
     271\begin{cfacode}
     272int main() {
     273        BENCH(
     274                for(size_t i=0; i<n; i++) {
     275                        pthread_t thread;
     276                        if(pthread_create(
     277                                &thread,
     278                                NULL,
     279                                foo,
     280                                NULL
     281                        ) < 0) {
     282                                perror( "failure" );
     283                                return 1;
     284                        }
     285
     286                        if(pthread_join(
     287                                thread,
     288                                NULL
     289                        ) < 0) {
     290                                perror( "failure" );
     291                                return 1;
     292                        }
     293                },
     294                result
     295        )
     296        printf("%llu\n", result);
     297}
     298\end{cfacode}
     299\columnbreak
     300\CFA Threads
     301\begin{cfacode}
     302int main() {
     303        BENCH(
     304                for(size_t i=0; i<n; i++) {
     305                        MyThread m;
     306                },
     307                result
     308        )
     309
     310        printf("%llu\n", result);
     311}
     312\end{cfacode}
     313\end{multicols}
     314\caption{Bechmark code for pthreads and \CFA to measure object creation}
     315\label{lst:creation}
     316\end{figure}
     317
     318\begin{figure}
     319\begin{center}
     320\begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     321\cline{2-4}
     322\multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     323\hline
     324Pthreads                        & 26974.5       & 26977 & 124.12 \\
     325\CFA Coroutines Lazy    & 5             & 5             & 0      \\
     326\CFA Coroutines Eager   & 335.0 & 357.67        & 34.2   \\
     327\CFA Threads            & 1122.5        & 1109.86       & 36.54  \\
     328\uC Coroutines          & 106           & 107.04        & 1.61   \\
     329\uC Threads                     & 525.5 & 533.04        & 11.14  \\
    122330\hline
    123331\end{tabular}
  • doc/proposals/concurrency/text/together.tex

    r9d06142 rc0d00b6  
    77
    88\section{Threads as monitors}
    9 As it was subtely alluded in section \ref{threads}, \code{threads} in \CFA are in fact monitors. This means that all the monitors features are available when using threads. For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine :
     9As it was subtely alluded in section \ref{threads}, \code{threads} in \CFA are in fact monitors, which means that all monitor features are available when using threads. For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine :
    1010\begin{cfacode}
    1111// Visualization declaration
     
    7272        }
    7373}
     74
     75// Call destructor for simulator once simulator finishes
     76// Call destructor for renderer to signify shutdown
    7477\end{cfacode}
    7578
    7679\section{Fibers \& Threads}
     80As mentionned in section \ref{preemption}, \CFA uses preemptive threads by default but can use fibers on demand. Currently, using fibers is done by adding the following line of code to the program~:
     81\begin{cfacode}
     82unsigned int default_preemption() {
     83        return 0;
     84}
     85\end{cfacode}
     86This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice i.e. no preemption. However, once clusters are fully implemented, it will be possible to create fibers and uthreads in on the same system :
     87\begin{figure}
     88\begin{cfacode}
     89//Cluster forward declaration
     90struct cluster;
     91
     92//Processor forward declaration
     93struct processor;
     94
     95//Construct clusters with a preemption rate
     96void ?{}(cluster& this, unsigned int rate);
     97//Construct processor and add it to cluster
     98void ?{}(processor& this, cluster& cluster);
     99//Construct thread and schedule it on cluster
     100void ?{}(thread& this, cluster& cluster);
     101
     102//Declare two clusters
     103cluster thread_cluster = { 10`ms };                     //Preempt every 10 ms
     104cluster fibers_cluster = { 0 };                         //Never preempt
     105
     106//Construct 4 processors
     107processor processors[4] = {
     108        //2 for the thread cluster
     109        thread_cluster;
     110        thread_cluster;
     111        //2 for the fibers cluster
     112        fibers_cluster;
     113        fibers_cluster;
     114};
     115
     116//Declares thread
     117thread UThread {};
     118void ?{}(UThread& this) {
     119        //Construct underlying thread to automatically
     120        //be scheduled on the thread cluster
     121        (this){ thread_cluster }
     122}
     123
     124void main(UThread & this);
     125
     126//Declares fibers
     127thread Fiber {};
     128void ?{}(Fiber& this) {
     129        //Construct underlying thread to automatically
     130        //be scheduled on the fiber cluster
     131        (this.__thread){ fibers_cluster }
     132}
     133
     134void main(Fiber & this);
     135\end{cfacode}
     136\end{figure}
  • doc/proposals/concurrency/version

    r9d06142 rc0d00b6  
    1 0.11.47
     10.11.129
  • src/Common/Debug.h

    r9d06142 rc0d00b6  
    2424#include "SynTree/Declaration.h"
    2525
    26 /// debug codegen a translation unit
    27 static inline void debugCodeGen( const std::list< Declaration * > & translationUnit, const std::string & label ) {
    28         std::list< Declaration * > decls;
     26#define DEBUG
    2927
    30         filter( translationUnit.begin(), translationUnit.end(), back_inserter( decls ), []( Declaration * decl ) {
    31                 return ! LinkageSpec::isBuiltin( decl->get_linkage() );
    32         });
     28namespace Debug {
     29        /// debug codegen a translation unit
     30        static inline void codeGen( __attribute__((unused)) const std::list< Declaration * > & translationUnit, __attribute__((unused)) const std::string & label ) {
     31        #ifdef DEBUG
     32                std::list< Declaration * > decls;
    3333
    34         std::cerr << "======" << label << "======" << std::endl;
    35         CodeGen::generate( decls, std::cerr, false, true );
    36 } // dump
     34                filter( translationUnit.begin(), translationUnit.end(), back_inserter( decls ), []( Declaration * decl ) {
     35                        return ! LinkageSpec::isBuiltin( decl->get_linkage() );
     36                });
     37
     38                std::cerr << "======" << label << "======" << std::endl;
     39                CodeGen::generate( decls, std::cerr, false, true );
     40        #endif
     41        } // dump
     42
     43        static inline void treeDump( __attribute__((unused)) const std::list< Declaration * > & translationUnit, __attribute__((unused)) const std::string & label ) {
     44        #ifdef DEBUG
     45                std::list< Declaration * > decls;
     46
     47                filter( translationUnit.begin(), translationUnit.end(), back_inserter( decls ), []( Declaration * decl ) {
     48                        return ! LinkageSpec::isBuiltin( decl->get_linkage() );
     49                });
     50
     51                std::cerr << "======" << label << "======" << std::endl;
     52                printAll( decls, std::cerr );
     53        #endif
     54        } // dump
     55}
    3756
    3857// Local Variables: //
  • src/Concurrency/Keywords.cc

    r9d06142 rc0d00b6  
    553553                        ),
    554554                        new ListInit(
    555                                 map_range < std::list<Initializer*> > ( args, [this](DeclarationWithType * var ){
     555                                map_range < std::list<Initializer*> > ( args, [](DeclarationWithType * var ){
    556556                                        Type * type = var->get_type()->clone();
    557557                                        type->set_mutex( false );
  • src/GenPoly/Box.cc

    r9d06142 rc0d00b6  
    167167                        Expression *postmutate( OffsetofExpr *offsetofExpr );
    168168                        Expression *postmutate( OffsetPackExpr *offsetPackExpr );
     169                        void premutate( StructDecl * );
     170                        void premutate( UnionDecl * );
    169171
    170172                        void beginScope();
     
    178180                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
    179181                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
     182                        /// change the type of generic aggregate members to char[]
     183                        void mutateMembers( AggregateDecl * aggrDecl );
    180184
    181185                        /// Enters a new scope for type-variables, adding the type variables from ty
     
    14141418
    14151419                void PolyGenericCalculator::premutate( TypedefDecl *typedefDecl ) {
     1420                        assert(false);
    14161421                        beginTypeScope( typedefDecl->get_base() );
    14171422                }
     
    14601465                }
    14611466
     1467                /// converts polymorphic type T into a suitable monomorphic representation, currently: __attribute__((aligned(8)) char[size_T]
     1468                Type * polyToMonoType( Type * declType ) {
     1469                        Type * charType = new BasicType( Type::Qualifiers(), BasicType::Kind::Char);
     1470                        Expression * size = new NameExpr( sizeofName( mangleType(declType) ) );
     1471                        Attribute * aligned = new Attribute( "aligned", std::list<Expression*>{ new ConstantExpr( Constant::from_int(8) ) } );
     1472                        return new ArrayType( Type::Qualifiers(), charType, size,
     1473                                true, false, std::list<Attribute *>{ aligned } );
     1474                }
     1475
     1476                void PolyGenericCalculator::mutateMembers( AggregateDecl * aggrDecl ) {
     1477                        std::set< std::string > genericParams;
     1478                        for ( TypeDecl * td : aggrDecl->parameters ) {
     1479                                genericParams.insert( td->name );
     1480                        }
     1481                        for ( Declaration * decl : aggrDecl->members ) {
     1482                                if ( ObjectDecl * field = dynamic_cast< ObjectDecl * >( decl ) ) {
     1483                                        Type * ty = replaceTypeInst( field->type, env );
     1484                                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
     1485                                                // do not try to monomorphize generic parameters
     1486                                                if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() && ! genericParams.count( typeInst->name ) ) {
     1487                                                        // polymorphic aggregate members should be converted into monomorphic members.
     1488                                                        // Using char[size_T] here respects the expected sizing rules of an aggregate type.
     1489                                                        Type * newType = polyToMonoType( field->type );
     1490                                                        delete field->type;
     1491                                                        field->type = newType;
     1492                                                }
     1493                                        }
     1494                                }
     1495                        }
     1496                }
     1497
     1498                void PolyGenericCalculator::premutate( StructDecl * structDecl ) {
     1499                        mutateMembers( structDecl );
     1500                }
     1501
     1502                void PolyGenericCalculator::premutate( UnionDecl * unionDecl ) {
     1503                        mutateMembers( unionDecl );
     1504                }
     1505
    14621506                void PolyGenericCalculator::premutate( DeclStmt *declStmt ) {
    14631507                        if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
     
    14651509                                        // change initialization of a polymorphic value object to allocate via a VLA
    14661510                                        // (alloca was previously used, but can't be safely used in loops)
    1467                                         Type *declType = objectDecl->get_type();
    1468                                         ObjectDecl *newBuf = new ObjectDecl( bufNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0,
    1469                                                 new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::Kind::Char), new NameExpr( sizeofName( mangleType(declType) ) ),
    1470                                                 true, false, std::list<Attribute*>{ new Attribute( "aligned", std::list<Expression*>{ new ConstantExpr( Constant::from_int(8) ) } ) } ), 0 );
     1511                                        ObjectDecl *newBuf = ObjectDecl::newObject( bufNamer.newName(), polyToMonoType( objectDecl->type ), nullptr );
    14711512                                        stmtsToAddBefore.push_back( new DeclStmt( noLabels, newBuf ) );
    14721513
  • src/GenPoly/InstantiateGeneric.cc

    r9d06142 rc0d00b6  
    2727#include "Common/utility.h"            // for deleteAll, cloneAll
    2828#include "GenPoly.h"                   // for isPolyType, typesPolyCompatible
     29#include "ResolvExpr/typeops.h"
    2930#include "ScopedSet.h"                 // for ScopedSet, ScopedSet<>::iterator
    3031#include "ScrubTyVars.h"               // for ScrubTyVars
     
    151152                return gt;
    152153        }
     154
     155        /// Add cast to dtype-static member expressions so that type information is not lost in GenericInstantiator
     156        struct FixDtypeStatic final {
     157                Expression * postmutate( MemberExpr * memberExpr );
     158
     159                template<typename AggrInst>
     160                Expression * fixMemberExpr( AggrInst * inst, MemberExpr * memberExpr );
     161        };
    153162
    154163        /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
     
    198207
    199208        void instantiateGeneric( std::list< Declaration* > &translationUnit ) {
     209                PassVisitor<FixDtypeStatic> fixer;
    200210                PassVisitor<GenericInstantiator> instantiator;
     211
     212                mutateAll( translationUnit, fixer );
    201213                mutateAll( translationUnit, instantiator );
     214        }
     215
     216        bool isDtypeStatic( const std::list< TypeDecl* >& baseParams ) {
     217                return std::all_of( baseParams.begin(), baseParams.end(), []( TypeDecl * td ) { return ! td->isComplete(); } );
    202218        }
    203219
     
    479495        }
    480496
     497        template< typename AggrInst >
     498        Expression * FixDtypeStatic::fixMemberExpr( AggrInst * inst, MemberExpr * memberExpr ) {
     499                // need to cast dtype-static member expressions to their actual type before that type is erased.
     500                auto & baseParams = *inst->get_baseParameters();
     501                if ( isDtypeStatic( baseParams ) ) {
     502                        if ( ! ResolvExpr::typesCompatible( memberExpr->result, memberExpr->member->get_type(), SymTab::Indexer() ) ) {
     503                                // type of member and type of expression differ, so add cast to actual type
     504                                return new CastExpr( memberExpr, memberExpr->result->clone() );
     505                        }
     506                }
     507                return memberExpr;
     508        }
     509
     510        Expression * FixDtypeStatic::postmutate( MemberExpr * memberExpr ) {
     511                Type * aggrType = memberExpr->aggregate->result;
     512                if ( isGenericType( aggrType ) ) {
     513                        if ( StructInstType * inst = dynamic_cast< StructInstType * >( aggrType ) ) {
     514                                return fixMemberExpr( inst, memberExpr );
     515                        } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( aggrType ) ) {
     516                                return fixMemberExpr( inst, memberExpr );
     517                        }
     518                }
     519                return memberExpr;
     520        }
     521
    481522} // namespace GenPoly
    482523
  • src/InitTweak/FixInit.cc

    r9d06142 rc0d00b6  
    396396                        if ( skipCopyConstruct( result ) ) return; // skip certain non-copyable types
    397397
    398                         // type may involve type variables, so apply type substitution to get temporary variable's actual type.
     398                        // type may involve type variables, so apply type substitution to get temporary variable's actual type,
     399                        // since result type may not be substituted (e.g., if the type does not appear in the parameter list)
    399400                        // Use applyFree so that types bound in function pointers are not substituted, e.g. in forall(dtype T) void (*)(T).
    400                         result = result->clone();
    401401                        env->applyFree( result );
    402402                        ObjectDecl * tmp = ObjectDecl::newObject( "__tmp", result, nullptr );
     
    573573
    574574                        if ( returnDecl ) {
    575                                 UntypedExpr * assign = new UntypedExpr( new NameExpr( "?=?" ) );
    576                                 assign->get_args().push_back( new VariableExpr( returnDecl ) );
    577                                 assign->get_args().push_back( callExpr );
    578                                 // know the result type of the assignment is the type of the LHS (minus the pointer), so
    579                                 // add that onto the assignment expression so that later steps have the necessary information
    580                                 assign->set_result( returnDecl->get_type()->clone() );
    581 
     575                                ApplicationExpr * assign = createBitwiseAssignment( new VariableExpr( returnDecl ), callExpr );
    582576                                Expression * retExpr = new CommaExpr( assign, new VariableExpr( returnDecl ) );
    583577                                // move env from callExpr to retExpr
     
    937931                }
    938932
    939                 void addIds( SymTab::Indexer & indexer, const std::list< DeclarationWithType * > & decls ) {
    940                         for ( auto d : decls ) {
    941                                 indexer.addId( d );
    942                         }
    943                 }
    944 
    945                 void addTypes( SymTab::Indexer & indexer, const std::list< TypeDecl * > & tds ) {
    946                         for ( auto td : tds ) {
    947                                 indexer.addType( td );
    948                                 addIds( indexer, td->assertions );
    949                         }
    950                 }
    951 
    952933                void GenStructMemberCalls::previsit( StructDecl * structDecl ) {
    953934                        if ( ! dtorStruct && structDecl->name == "__Destructor" ) {
     
    1018999                                // need to explicitly re-add function parameters to the indexer in order to resolve copy constructors
    10191000                                auto guard = makeFuncGuard( [this]() { indexer.enterScope(); }, [this]() { indexer.leaveScope(); } );
    1020                                 addTypes( indexer, function->type->forall );
    1021                                 addIds( indexer, function->type->returnVals );
    1022                                 addIds( indexer, function->type->parameters );
     1001                                indexer.addFunctionType( function->type );
    10231002
    10241003                                // need to iterate through members in reverse in order for
     
    10351014                                        // insert and resolve default/copy constructor call for each field that's unhandled
    10361015                                        std::list< Statement * > stmt;
    1037                                         Expression * arg2 = 0;
     1016                                        Expression * arg2 = nullptr;
    10381017                                        if ( isCopyConstructor( function ) ) {
    10391018                                                // if copy ctor, need to pass second-param-of-this-function.field
     
    11881167                        assert( ctorExpr->result && ctorExpr->get_result()->size() == 1 );
    11891168
    1190                         // xxx - ideally we would reuse the temporary generated from the copy constructor passes from within firstArg if it exists and not generate a temporary if it's unnecessary.
    1191                         ObjectDecl * tmp = ObjectDecl::newObject( tempNamer.newName(), ctorExpr->get_result()->clone(), nullptr );
    1192                         declsToAddBefore.push_back( tmp );
    1193 
    11941169                        // xxx - this can be TupleAssignExpr now. Need to properly handle this case.
    11951170                        ApplicationExpr * callExpr = strict_dynamic_cast< ApplicationExpr * > ( ctorExpr->get_callExpr() );
     
    11971172                        ctorExpr->set_callExpr( nullptr );
    11981173                        ctorExpr->set_env( nullptr );
     1174
     1175                        // xxx - ideally we would reuse the temporary generated from the copy constructor passes from within firstArg if it exists and not generate a temporary if it's unnecessary.
     1176                        ObjectDecl * tmp = ObjectDecl::newObject( tempNamer.newName(), callExpr->args.front()->result->clone(), nullptr );
     1177                        declsToAddBefore.push_back( tmp );
    11991178                        delete ctorExpr;
    12001179
  • src/InitTweak/InitTweak.cc

    r9d06142 rc0d00b6  
    1212#include "Parser/LinkageSpec.h"    // for Spec, isBuiltin, Intrinsic
    1313#include "ResolvExpr/typeops.h"    // for typesCompatibleIgnoreQualifiers
     14#include "SymTab/Autogen.h"
    1415#include "SymTab/Indexer.h"        // for Indexer
    1516#include "SynTree/Attribute.h"     // for Attribute
     
    9899        class InitExpander::ExpanderImpl {
    99100        public:
     101                virtual ~ExpanderImpl() = default;
    100102                virtual std::list< Expression * > next( std::list< Expression * > & indices ) = 0;
    101103                virtual Statement * buildListInit( UntypedExpr * callExpr, std::list< Expression * > & indices ) = 0;
     
    105107        public:
    106108                InitImpl( Initializer * init ) : init( init ) {}
     109                virtual ~InitImpl() = default;
    107110
    108111                virtual std::list< Expression * > next( __attribute((unused)) std::list< Expression * > & indices ) {
     
    121124        public:
    122125                ExprImpl( Expression * expr ) : arg( expr ) {}
    123 
    124                 ~ExprImpl() { delete arg; }
     126                virtual ~ExprImpl() { delete arg; }
    125127
    126128                virtual std::list< Expression * > next( std::list< Expression * > & indices ) {
     
    523525        }
    524526
     527        ApplicationExpr * createBitwiseAssignment( Expression * dst, Expression * src ) {
     528                static FunctionDecl * assign = nullptr;
     529                if ( ! assign ) {
     530                        // temporary? Generate a fake assignment operator to represent bitwise assignments.
     531                        // This operator could easily exist as a real function, but it's tricky because nothing should resolve to this function.
     532                        TypeDecl * td = new TypeDecl( "T", noStorageClasses, nullptr, TypeDecl::Dtype, true );
     533                        assign = new FunctionDecl( "?=?", noStorageClasses, LinkageSpec::Intrinsic, SymTab::genAssignType( new TypeInstType( noQualifiers, td->name, td ) ), nullptr );
     534                }
     535                if ( dynamic_cast< ReferenceType * >( dst->result ) ) {
     536                        dst = new AddressExpr( dst );
     537                } else {
     538                        dst = new CastExpr( dst, new ReferenceType( noQualifiers, dst->result->clone() ) );
     539                }
     540                if ( dynamic_cast< ReferenceType * >( src->result ) ) {
     541                        src = new CastExpr( src, new ReferenceType( noQualifiers, src->result->stripReferences()->clone() ) );
     542                }
     543                return new ApplicationExpr( VariableExpr::functionPointer( assign ), { dst, src } );
     544        }
     545
    525546        class ConstExprChecker : public Visitor {
    526547        public:
  • src/InitTweak/InitTweak.h

    r9d06142 rc0d00b6  
    3535        /// returns the first parameter of a constructor/destructor/assignment function
    3636        ObjectDecl * getParamThis( FunctionType * ftype );
     37
     38        /// generate a bitwise assignment operation.
     39        ApplicationExpr * createBitwiseAssignment( Expression * dst, Expression * src );
    3740
    3841        /// transform Initializer into an argument list that can be passed to a call expression
  • src/Makefile.in

    r9d06142 rc0d00b6  
    210210        ResolvExpr/driver_cfa_cpp-TypeEnvironment.$(OBJEXT) \
    211211        ResolvExpr/driver_cfa_cpp-CurrentObject.$(OBJEXT) \
     212        ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT) \
    212213        SymTab/driver_cfa_cpp-Indexer.$(OBJEXT) \
    213214        SymTab/driver_cfa_cpp-Mangler.$(OBJEXT) \
     
    511512        ResolvExpr/FindOpenVars.cc ResolvExpr/PolyCost.cc \
    512513        ResolvExpr/Occurs.cc ResolvExpr/TypeEnvironment.cc \
    513         ResolvExpr/CurrentObject.cc SymTab/Indexer.cc \
    514         SymTab/Mangler.cc SymTab/Validate.cc SymTab/FixFunction.cc \
    515         SymTab/ImplementationType.cc SymTab/TypeEquality.cc \
    516         SymTab/Autogen.cc SynTree/Type.cc SynTree/VoidType.cc \
    517         SynTree/BasicType.cc SynTree/PointerType.cc \
    518         SynTree/ArrayType.cc SynTree/ReferenceType.cc \
    519         SynTree/FunctionType.cc SynTree/ReferenceToType.cc \
    520         SynTree/TupleType.cc SynTree/TypeofType.cc SynTree/AttrType.cc \
     514        ResolvExpr/CurrentObject.cc ResolvExpr/ExplodedActual.cc \
     515        SymTab/Indexer.cc SymTab/Mangler.cc SymTab/Validate.cc \
     516        SymTab/FixFunction.cc SymTab/ImplementationType.cc \
     517        SymTab/TypeEquality.cc SymTab/Autogen.cc SynTree/Type.cc \
     518        SynTree/VoidType.cc SynTree/BasicType.cc \
     519        SynTree/PointerType.cc SynTree/ArrayType.cc \
     520        SynTree/ReferenceType.cc SynTree/FunctionType.cc \
     521        SynTree/ReferenceToType.cc SynTree/TupleType.cc \
     522        SynTree/TypeofType.cc SynTree/AttrType.cc \
    521523        SynTree/VarArgsType.cc SynTree/ZeroOneType.cc \
    522524        SynTree/Constant.cc SynTree/Expression.cc SynTree/TupleExpr.cc \
     
    825827        ResolvExpr/$(am__dirstamp) \
    826828        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
     829ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT):  \
     830        ResolvExpr/$(am__dirstamp) \
     831        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
    827832SymTab/$(am__dirstamp):
    828833        @$(MKDIR_P) SymTab
     
    10221027@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ConversionCost.Po@am__quote@
    10231028@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-CurrentObject.Po@am__quote@
     1029@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po@am__quote@
    10241030@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-FindOpenVars.Po@am__quote@
    10251031@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-Occurs.Po@am__quote@
     
    19641970@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-CurrentObject.obj `if test -f 'ResolvExpr/CurrentObject.cc'; then $(CYGPATH_W) 'ResolvExpr/CurrentObject.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/CurrentObject.cc'; fi`
    19651971
     1972ResolvExpr/driver_cfa_cpp-ExplodedActual.o: ResolvExpr/ExplodedActual.cc
     1973@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.o -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc
     1974@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po
     1975@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.o' libtool=no @AMDEPBACKSLASH@
     1976@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1977@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc
     1978
     1979ResolvExpr/driver_cfa_cpp-ExplodedActual.obj: ResolvExpr/ExplodedActual.cc
     1980@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.obj -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi`
     1981@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po
     1982@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.obj' libtool=no @AMDEPBACKSLASH@
     1983@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1984@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi`
     1985
    19661986SymTab/driver_cfa_cpp-Indexer.o: SymTab/Indexer.cc
    19671987@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT SymTab/driver_cfa_cpp-Indexer.o -MD -MP -MF SymTab/$(DEPDIR)/driver_cfa_cpp-Indexer.Tpo -c -o SymTab/driver_cfa_cpp-Indexer.o `test -f 'SymTab/Indexer.cc' || echo '$(srcdir)/'`SymTab/Indexer.cc
  • src/Parser/DeclarationNode.cc

    r9d06142 rc0d00b6  
    1010// Created On       : Sat May 16 12:34:05 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Sep 23 18:16:48 2017
    13 // Update Count     : 1024
     12// Last Modified On : Mon Nov 20 09:21:52 2017
     13// Update Count     : 1031
    1414//
    1515
     
    509509
    510510DeclarationNode * DeclarationNode::addQualifiers( DeclarationNode * q ) {
    511         if ( ! q ) { delete q; return this; }
     511        if ( ! q ) { delete q; return this; }                           // empty qualifier
    512512
    513513        checkSpecifiers( q );
    514514        copySpecifiers( q );
    515515
    516         if ( ! q->type ) {
    517                 delete q;
    518                 return this;
    519         } // if
     516        if ( ! q->type ) { delete q; return this; }
    520517
    521518        if ( ! type ) {
    522                 type = q->type;                                                                 // reuse this structure
     519                type = q->type;                                                                 // reuse structure
    523520                q->type = nullptr;
    524521                delete q;
     
    526523        } // if
    527524
    528         if ( q->type->forall ) {
    529                 if ( type->forall ) {
    530                         type->forall->appendList( q->type->forall );
     525        if ( q->type->forall ) {                                                        // forall qualifier ?
     526                if ( type->forall ) {                                                   // polymorphic routine ?
     527                        type->forall->appendList( q->type->forall ); // augment forall qualifier
    531528                } else {
    532                         if ( type->kind == TypeData::Aggregate ) {
    533                                 type->aggregate.params = q->type->forall;
    534                                 // change implicit typedef from TYPEDEFname to TYPEGENname
    535                                 typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG );
    536                         } else {
    537                                 type->forall = q->type->forall;
     529                        if ( type->kind == TypeData::Aggregate ) {      // struct/union ?
     530                                if ( type->aggregate.params ) {                 // polymorphic ?
     531                                        type->aggregate.params->appendList( q->type->forall ); // augment forall qualifier
     532                                } else {                                                                // not polymorphic
     533                                        type->aggregate.params = q->type->forall; // make polymorphic type
     534                                        // change implicit typedef from TYPEDEFname to TYPEGENname
     535                                        typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG );
     536                                } // if
     537                        } else {                                                                        // not polymorphic
     538                                type->forall = q->type->forall;                 // make polymorphic routine
    538539                        } // if
    539540                } // if
    540                 q->type->forall = nullptr;
     541                q->type->forall = nullptr;                                              // forall qualifier moved
    541542        } // if
    542543
  • src/Parser/parser.yy

    r9d06142 rc0d00b6  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Oct 25 12:28:54 2017
    13 // Update Count     : 2893
     12// Last Modified On : Mon Nov 20 09:45:36 2017
     13// Update Count     : 2945
    1414//
    1515
     
    114114        } // for
    115115} // distExt
     116
     117// There is an ambiguity for inline generic-routine return-types and generic routines.
     118//   forall( otype T ) struct S { int i; } bar( T ) {}
     119// Does the forall bind to the struct or the routine, and how would it be possible to explicitly specify the binding.
     120//   forall( otype T ) struct S { int T; } forall( otype W ) bar( W ) {}
     121
     122void rebindForall( DeclarationNode * declSpec, DeclarationNode * funcDecl ) {
     123        if ( declSpec->type->kind == TypeData::Aggregate ) { // return is aggregate definition
     124                funcDecl->type->forall = declSpec->type->aggregate.params; // move forall from aggregate to function type
     125                declSpec->type->aggregate.params = nullptr;
     126        } // if
     127} // rebindForall
    116128
    117129bool forall = false;                                                                    // aggregate have one or more forall qualifiers ?
     
    348360
    349361
    350 // Handle single shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string
    351 // is ambiguous:
    352 // .---------.                          matches IF '(' comma_expression ')' statement . (reduce)
    353 // if ( C ) S1 else S2
    354 // `-----------------'          matches IF '(' comma_expression ')' statement . (shift) ELSE statement */
     362// Handle shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string is ambiguous:
     363//   .---------.                                matches IF '(' comma_expression ')' statement . (reduce)
     364//   if ( C ) S1 else S2
     365//   `-----------------'                matches IF '(' comma_expression ')' statement . (shift) ELSE statement */
    355366// Similar issues exit with the waitfor statement.
    356367
     
    361372%precedence TIMEOUT     // token precedence for start of TIMEOUT in WAITFOR statement
    362373%precedence ELSE        // token precedence for start of else clause in IF/WAITFOR statement
     374
     375// Handle shift/reduce conflict for generic type by shifting the '(' token. For example, this string is ambiguous:
     376//   forall( otype T ) struct Foo { T v; };
     377//       .-----.                                matches pointer to function returning a generic (which is impossible without a type)
     378//   Foo ( *fp )( int );
     379//   `---'                                              matches start of TYPEGENname '('
     380// Must be:
     381// Foo( int ) ( *fp )( int );
     382
     383// Order of these lines matters (low-to-high precedence).
     384%precedence TYPEGENname
     385%precedence '('
    363386
    364387%locations                      // support location tracking for error messages
     
    17651788
    17661789typegen_name:                                                                                   // CFA
    1767         TYPEGENname '(' ')'
     1790        TYPEGENname
     1791                { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); }
     1792        | TYPEGENname '(' ')'
    17681793                { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); }
    17691794        | TYPEGENname '(' type_list ')'
     
    18091834                }
    18101835        | aggregate_key attribute_list_opt typegen_name         // CFA
    1811                 { $$ = $3->addQualifiers( $2 ); }
     1836                {
     1837                        // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is
     1838                        // switched to a TYPEGENname. Link any generic arguments from typegen_name to new generic declaration and
     1839                        // delete newFromTypeGen.
     1840                        $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $3->type->symbolic.actuals, nullptr, false )->addQualifiers( $2 );
     1841                        $3->type->symbolic.name = nullptr;
     1842                        $3->type->symbolic.actuals = nullptr;
     1843                        delete $3;
     1844                }
    18121845        ;
    18131846
     
    23802413        | declaration_specifier function_declarator with_clause_opt compound_statement
    23812414                {
     2415                        rebindForall( $1, $2 );
    23822416                        typedefTable.addToEnclosingScope( TypedefTable::ID );
    23832417                        typedefTable.leaveScope();
     
    24062440        | declaration_specifier KR_function_declarator KR_declaration_list_opt with_clause_opt compound_statement
    24072441                {
     2442                        rebindForall( $1, $2 );
    24082443                        typedefTable.addToEnclosingScope( TypedefTable::ID );
    24092444                        typedefTable.leaveScope();
  • src/ResolvExpr/Alternative.cc

    r9d06142 rc0d00b6  
    1818#include <ostream>                       // for operator<<, ostream, basic_o...
    1919#include <string>                        // for operator<<, char_traits, string
     20#include <utility>                       // for move
    2021
    2122#include "Common/utility.h"              // for maybeClone
     
    8182                os << std::endl;
    8283        }
     84
     85        void splice( AltList& dst, AltList& src ) {
     86                dst.reserve( dst.size() + src.size() );
     87                for ( Alternative& alt : src ) {
     88                        dst.push_back( std::move(alt) );
     89                }
     90                src.clear();
     91        }
     92
     93        void spliceBegin( AltList& dst, AltList& src ) {
     94                splice( src, dst );
     95                dst.swap( src );
     96        }
     97
    8398} // namespace ResolvExpr
    8499
  • src/ResolvExpr/Alternative.h

    r9d06142 rc0d00b6  
    1717
    1818#include <iosfwd>             // for ostream
    19 #include <list>               // for list
     19#include <vector>             // for vector
    2020
    2121#include "Cost.h"             // for Cost
     
    2525
    2626namespace ResolvExpr {
    27         struct Alternative;
    28 
    29         typedef std::list< Alternative > AltList;
    30 
    3127        struct Alternative {
    3228                Alternative();
     
    4137                void print( std::ostream &os, Indenter indent = {} ) const;
    4238
     39                /// Returns the stored expression, but released from management of this Alternative
     40                Expression* release_expr() {
     41                        Expression* tmp = expr;
     42                        expr = nullptr;
     43                        return tmp;
     44                }
     45
    4346                Cost cost;
    4447                Cost cvtCost;
     
    4649                TypeEnvironment env;
    4750        };
     51
     52        typedef std::vector< Alternative > AltList;
     53
     54        /// Moves all elements from src to the end of dst
     55        void splice( AltList& dst, AltList& src );
     56
     57        /// Moves all elements from src to the beginning of dst
     58        void spliceBegin( AltList& dst, AltList& src );
    4859} // namespace ResolvExpr
    4960
  • src/ResolvExpr/AlternativeFinder.cc

    r9d06142 rc0d00b6  
    1616#include <algorithm>               // for copy
    1717#include <cassert>                 // for strict_dynamic_cast, assert, assertf
     18#include <cstddef>                 // for size_t
    1819#include <iostream>                // for operator<<, cerr, ostream, endl
    1920#include <iterator>                // for back_insert_iterator, back_inserter
    2021#include <list>                    // for _List_iterator, list, _List_const_...
    2122#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
    22 #include <memory>                  // for allocator_traits<>::value_type
     23#include <memory>                  // for allocator_traits<>::value_type, unique_ptr
    2324#include <utility>                 // for pair
     25#include <vector>                  // for vector
    2426
    2527#include "Alternative.h"           // for AltList, Alternative
     
    2830#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
    2931#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
     32#include "ExplodedActual.h"        // for ExplodedActual
    3033#include "InitTweak/InitTweak.h"   // for getFunctionName
    3134#include "RenameVars.h"            // for RenameVars, global_renamer
     
    4952#define PRINT( text ) if ( resolvep ) { text }
    5053//#define DEBUG_COST
     54
     55using std::move;
     56
     57/// copies any copyable type
     58template<typename T>
     59T copy(const T& x) { return x; }
    5160
    5261namespace ResolvExpr {
     
    178187                expr->accept( *this );
    179188                if ( failFast && alternatives.empty() ) {
     189                        PRINT(
     190                                std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
     191                        )
    180192                        throw SemanticError( "No reasonable alternatives for expression ", expr );
    181193                }
     
    186198                                printAlts( alternatives, std::cerr );
    187199                        )
    188                         AltList::iterator oldBegin = alternatives.begin();
    189                         pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
    190                         if ( failFast && alternatives.begin() == oldBegin ) {
     200                        AltList pruned;
     201                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
     202                        if ( failFast && pruned.empty() ) {
    191203                                std::ostringstream stream;
    192204                                AltList winners;
     
    198210                                throw SemanticError( stream.str() );
    199211                        }
    200                         alternatives.erase( oldBegin, alternatives.end() );
     212                        alternatives = move(pruned);
    201213                        PRINT(
    202214                                std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
     
    333345                tmpCost.incPoly( -tmpCost.get_polyCost() );
    334346                if ( tmpCost != Cost::zero ) {
    335                 // if ( convCost != Cost::zero ) {
    336347                        Type *newType = formalType->clone();
    337348                        env.apply( newType );
     
    405416///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
    406417                }
    407         }
    408 
    409         /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
    410         /// producing expression(s) in out and their total cost in cost.
    411         template< typename AltIterator, typename OutputIterator >
    412         bool instantiateArgument( Type * formalType, Initializer * defaultValue, AltIterator & actualIt, AltIterator actualEnd, OpenVarSet & openVars, TypeEnvironment & resultEnv, AssertionSet & resultNeed, AssertionSet & resultHave, const SymTab::Indexer & indexer, Cost & cost, OutputIterator out ) {
    413                 if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
    414                         // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
    415                         std::list< Expression * > exprs;
    416                         for ( Type * type : *tupleType ) {
    417                                 if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) {
    418                                         deleteAll( exprs );
    419                                         return false;
    420                                 }
    421                         }
    422                         *out++ = new TupleExpr( exprs );
    423                 } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
    424                         // xxx - mixing default arguments with variadic??
    425                         std::list< Expression * > exprs;
    426                         for ( ; actualIt != actualEnd; ++actualIt ) {
    427                                 exprs.push_back( actualIt->expr->clone() );
    428                                 cost += actualIt->cost;
    429                         }
    430                         Expression * arg = nullptr;
    431                         if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) {
    432                                 // the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes
    433                                 // xxx - what if passing multiple arguments, last of which is ttype?
    434                                 // xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below.
    435                                 arg = exprs.front();
    436                         } else {
    437                                 arg = new TupleExpr( exprs );
    438                         }
    439                         assert( arg && arg->get_result() );
    440                         if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
    441                                 return false;
    442                         }
    443                         *out++ = arg;
    444                 } else if ( actualIt != actualEnd ) {
    445                         // both actualType and formalType are atomic (non-tuple) types - if they unify
    446                         // then accept actual as an argument, otherwise return false (fail to instantiate argument)
    447                         Expression * actual = actualIt->expr;
    448                         Type * actualType = actual->get_result();
    449 
    450                         PRINT(
    451                                 std::cerr << "formal type is ";
    452                                 formalType->print( std::cerr );
    453                                 std::cerr << std::endl << "actual type is ";
    454                                 actualType->print( std::cerr );
    455                                 std::cerr << std::endl;
    456                         )
    457                         if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
    458                                 // std::cerr << "unify failed" << std::endl;
    459                                 return false;
    460                         }
    461                         // move the expression from the alternative to the output iterator
    462                         *out++ = actual;
    463                         actualIt->expr = nullptr;
    464                         cost += actualIt->cost;
    465                         ++actualIt;
    466                 } else {
    467                         // End of actuals - Handle default values
    468                         if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
    469                                 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) {
    470                                         // so far, only constant expressions are accepted as default values
    471                                         if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( castExpr->get_arg() ) ) {
    472                                                 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
    473                                                         if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
    474                                                                 *out++ = cnstexpr->clone();
    475                                                                 return true;
    476                                                         } // if
    477                                                 } // if
    478                                         } // if
    479                                 }
    480                         } // if
    481                         return false;
    482                 } // if
    483                 return true;
    484         }
    485 
    486         bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
    487                 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
    488                 // make sure we don't widen any existing bindings
    489                 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
    490                         i->allowWidening = false;
    491                 }
    492                 resultEnv.extractOpenVars( openVars );
    493 
    494                 // flatten actuals so that each actual has an atomic (non-tuple) type
    495                 AltList exploded;
    496                 Tuples::explode( actuals, indexer, back_inserter( exploded ) );
    497 
    498                 AltList::iterator actualExpr = exploded.begin();
    499                 AltList::iterator actualEnd = exploded.end();
    500                 for ( DeclarationWithType * formal : formals ) {
    501                         // match flattened actuals with formal parameters - actuals will be grouped to match
    502                         // with formals as appropriate
    503                         Cost cost = Cost::zero;
    504                         std::list< Expression * > newExprs;
    505                         ObjectDecl * obj = strict_dynamic_cast< ObjectDecl * >( formal );
    506                         if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
    507                                 deleteAll( newExprs );
    508                                 return false;
    509                         }
    510                         // success - produce argument as a new alternative
    511                         assert( newExprs.size() == 1 );
    512                         out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
    513                 }
    514                 if ( actualExpr != actualEnd ) {
    515                         // there are still actuals remaining, but we've run out of formal parameters to match against
    516                         // this is okay only if the function is variadic
    517                         if ( ! isVarArgs ) {
    518                                 return false;
    519                         }
    520                         out.splice( out.end(), exploded, actualExpr, actualEnd );
    521                 }
    522                 return true;
    523418        }
    524419
     
    675570        }
    676571
    677         template< typename OutputIterator >
    678         void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
    679                 OpenVarSet openVars;
    680                 AssertionSet resultNeed, resultHave;
    681                 TypeEnvironment resultEnv( func.env );
    682                 makeUnifiableVars( funcType, openVars, resultNeed );
    683                 resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open
    684                 AltList instantiatedActuals; // filled by instantiate function
     572        /// Gets a default value from an initializer, nullptr if not present
     573        ConstantExpr* getDefaultValue( Initializer* init ) {
     574                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
     575                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) {
     576                                return dynamic_cast<ConstantExpr*>( ce->get_arg() );
     577                        }
     578                }
     579                return nullptr;
     580        }
     581
     582        /// State to iteratively build a match of parameter expressions to arguments
     583        struct ArgPack {
     584                std::size_t parent;                ///< Index of parent pack
     585                std::unique_ptr<Expression> expr;  ///< The argument stored here
     586                Cost cost;                         ///< The cost of this argument
     587                TypeEnvironment env;               ///< Environment for this pack
     588                AssertionSet need;                 ///< Assertions outstanding for this pack
     589                AssertionSet have;                 ///< Assertions found for this pack
     590                OpenVarSet openVars;               ///< Open variables for this pack
     591                unsigned nextArg;                  ///< Index of next argument in arguments list
     592                unsigned tupleStart;               ///< Number of tuples that start at this index
     593                unsigned nextExpl;                 ///< Index of next exploded element
     594                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
     595
     596                ArgPack()
     597                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
     598
     599                          tupleStart(0), nextExpl(0), explAlt(0) {}
     600
     601                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
     602                                const OpenVarSet& openVars)
     603                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
     604                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
     605
     606                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
     607                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
     608                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
     609                                unsigned explAlt = 0 )
     610                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
     611                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
     612                          nextExpl(nextExpl), explAlt(explAlt) {}
     613
     614                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
     615                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
     616                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
     617                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
     618                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
     619
     620                /// true iff this pack is in the middle of an exploded argument
     621                bool hasExpl() const { return nextExpl > 0; }
     622
     623                /// Gets the list of exploded alternatives for this pack
     624                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
     625                        return args[nextArg-1][explAlt];
     626                }
     627
     628                /// Ends a tuple expression, consolidating the appropriate actuals
     629                void endTuple( const std::vector<ArgPack>& packs ) {
     630                        // add all expressions in tuple to list, summing cost
     631                        std::list<Expression*> exprs;
     632                        const ArgPack* pack = this;
     633                        if ( expr ) { exprs.push_front( expr.release() ); }
     634                        while ( pack->tupleStart == 0 ) {
     635                                pack = &packs[pack->parent];
     636                                exprs.push_front( pack->expr->clone() );
     637                                cost += pack->cost;
     638                        }
     639                        // reset pack to appropriate tuple
     640                        expr.reset( new TupleExpr( exprs ) );
     641                        tupleStart = pack->tupleStart - 1;
     642                        parent = pack->parent;
     643                }
     644        };
     645
     646        /// Instantiates an argument to match a formal, returns false if no results left
     647        bool instantiateArgument( Type* formalType, Initializer* initializer,
     648                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
     649                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
     650                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
     651                        // formalType is a TupleType - group actuals into a TupleExpr
     652                        ++nTuples;
     653                        for ( Type* type : *tupleType ) {
     654                                // xxx - dropping initializer changes behaviour from previous, but seems correct
     655                                if ( ! instantiateArgument(
     656                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
     657                                        return false;
     658                                nTuples = 0;
     659                        }
     660                        // re-consititute tuples for final generation
     661                        for ( auto i = genStart; i < results.size(); ++i ) {
     662                                results[i].endTuple( results );
     663                        }
     664                        return true;
     665                } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
     666                        // formalType is a ttype, consumes all remaining arguments
     667                        // xxx - mixing default arguments with variadic??
     668
     669                        // completed tuples; will be spliced to end of results to finish
     670                        std::vector<ArgPack> finalResults{};
     671
     672                        // iterate until all results completed
     673                        std::size_t genEnd;
     674                        ++nTuples;
     675                        do {
     676                                genEnd = results.size();
     677
     678                                // add another argument to results
     679                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     680                                        auto nextArg = results[i].nextArg;
     681
     682                                        // use next element of exploded tuple if present
     683                                        if ( results[i].hasExpl() ) {
     684                                                const ExplodedActual& expl = results[i].getExpl( args );
     685
     686                                                unsigned nextExpl = results[i].nextExpl + 1;
     687                                                if ( nextExpl == expl.exprs.size() ) {
     688                                                        nextExpl = 0;
     689                                                }
     690
     691                                                results.emplace_back(
     692                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
     693                                                        copy(results[i].need), copy(results[i].have),
     694                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
     695                                                        results[i].explAlt );
     696
     697                                                continue;
     698                                        }
     699
     700                                        // finish result when out of arguments
     701                                        if ( nextArg >= args.size() ) {
     702                                                ArgPack newResult{
     703                                                        results[i].env, results[i].need, results[i].have,
     704                                                        results[i].openVars };
     705                                                newResult.nextArg = nextArg;
     706                                                Type* argType;
     707
     708                                                if ( nTuples > 0 ) {
     709                                                        // first iteration, push empty tuple expression
     710                                                        newResult.parent = i;
     711                                                        std::list<Expression*> emptyList;
     712                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
     713                                                        argType = newResult.expr->get_result();
     714                                                } else {
     715                                                        // clone result to collect tuple
     716                                                        newResult.parent = results[i].parent;
     717                                                        newResult.cost = results[i].cost;
     718                                                        newResult.tupleStart = results[i].tupleStart;
     719                                                        newResult.expr.reset( results[i].expr->clone() );
     720                                                        argType = newResult.expr->get_result();
     721
     722                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
     723                                                                // the case where a ttype value is passed directly is special,
     724                                                                // e.g. for argument forwarding purposes
     725                                                                // xxx - what if passing multiple arguments, last of which is
     726                                                                //       ttype?
     727                                                                // xxx - what would happen if unify was changed so that unifying
     728                                                                //       tuple
     729                                                                // types flattened both before unifying lists? then pass in
     730                                                                // TupleType (ttype) below.
     731                                                                --newResult.tupleStart;
     732                                                        } else {
     733                                                                // collapse leftover arguments into tuple
     734                                                                newResult.endTuple( results );
     735                                                                argType = newResult.expr->get_result();
     736                                                        }
     737                                                }
     738
     739                                                // check unification for ttype before adding to final
     740                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
     741                                                                newResult.openVars, indexer ) ) {
     742                                                        finalResults.push_back( move(newResult) );
     743                                                }
     744
     745                                                continue;
     746                                        }
     747
     748                                        // add each possible next argument
     749                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     750                                                const ExplodedActual& expl = args[nextArg][j];
     751
     752                                                // fresh copies of parent parameters for this iteration
     753                                                TypeEnvironment env = results[i].env;
     754                                                OpenVarSet openVars = results[i].openVars;
     755
     756                                                env.addActual( expl.env, openVars );
     757
     758                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     759                                                if ( expl.exprs.empty() ) {
     760                                                        results.emplace_back(
     761                                                                results[i], move(env), copy(results[i].need),
     762                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
     763
     764                                                        continue;
     765                                                }
     766
     767                                                // add new result
     768                                                results.emplace_back(
     769                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
     770                                                        copy(results[i].have), move(openVars), nextArg + 1,
     771                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
     772                                        }
     773                                }
     774
     775                                // reset for next round
     776                                genStart = genEnd;
     777                                nTuples = 0;
     778                        } while ( genEnd != results.size() );
     779
     780                        // splice final results onto results
     781                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
     782                                results.push_back( move(finalResults[i]) );
     783                        }
     784                        return ! finalResults.empty();
     785                }
     786
     787                // iterate each current subresult
     788                std::size_t genEnd = results.size();
     789                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     790                        auto nextArg = results[i].nextArg;
     791
     792                        // use remainder of exploded tuple if present
     793                        if ( results[i].hasExpl() ) {
     794                                const ExplodedActual& expl = results[i].getExpl( args );
     795                                Expression* expr = expl.exprs[results[i].nextExpl].get();
     796
     797                                TypeEnvironment env = results[i].env;
     798                                AssertionSet need = results[i].need, have = results[i].have;
     799                                OpenVarSet openVars = results[i].openVars;
     800
     801                                Type* actualType = expr->get_result();
     802
     803                                PRINT(
     804                                        std::cerr << "formal type is ";
     805                                        formalType->print( std::cerr );
     806                                        std::cerr << std::endl << "actual type is ";
     807                                        actualType->print( std::cerr );
     808                                        std::cerr << std::endl;
     809                                )
     810
     811                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     812                                        unsigned nextExpl = results[i].nextExpl + 1;
     813                                        if ( nextExpl == expl.exprs.size() ) {
     814                                                nextExpl = 0;
     815                                        }
     816
     817                                        results.emplace_back(
     818                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
     819                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
     820                                }
     821
     822                                continue;
     823                        }
     824
     825                        // use default initializers if out of arguments
     826                        if ( nextArg >= args.size() ) {
     827                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
     828                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
     829                                                TypeEnvironment env = results[i].env;
     830                                                AssertionSet need = results[i].need, have = results[i].have;
     831                                                OpenVarSet openVars = results[i].openVars;
     832
     833                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
     834                                                                indexer ) ) {
     835                                                        results.emplace_back(
     836                                                                i, cnstExpr, move(env), move(need), move(have),
     837                                                                move(openVars), nextArg, nTuples );
     838                                                }
     839                                        }
     840                                }
     841
     842                                continue;
     843                        }
     844
     845                        // Check each possible next argument
     846                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     847                                const ExplodedActual& expl = args[nextArg][j];
     848
     849                                // fresh copies of parent parameters for this iteration
     850                                TypeEnvironment env = results[i].env;
     851                                AssertionSet need = results[i].need, have = results[i].have;
     852                                OpenVarSet openVars = results[i].openVars;
     853
     854                                env.addActual( expl.env, openVars );
     855
     856                                // skip empty tuple arguments by (near-)cloning parent into next gen
     857                                if ( expl.exprs.empty() ) {
     858                                        results.emplace_back(
     859                                                results[i], move(env), move(need), move(have), move(openVars),
     860                                                nextArg + 1, expl.cost );
     861
     862                                        continue;
     863                                }
     864
     865                                // consider only first exploded actual
     866                                Expression* expr = expl.exprs.front().get();
     867                                Type* actualType = expr->get_result()->clone();
     868
     869                                PRINT(
     870                                        std::cerr << "formal type is ";
     871                                        formalType->print( std::cerr );
     872                                        std::cerr << std::endl << "actual type is ";
     873                                        actualType->print( std::cerr );
     874                                        std::cerr << std::endl;
     875                                )
     876
     877                                // attempt to unify types
     878                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     879                                        // add new result
     880                                        results.emplace_back(
     881                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
     882                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
     883                                }
     884                        }
     885                }
     886
     887                // reset for next parameter
     888                genStart = genEnd;
     889
     890                return genEnd != results.size();
     891        }
     892
     893        template<typename OutputIterator>
     894        void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
     895                        const std::vector<ArgPack>& results, OutputIterator out ) {
     896                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
     897                // sum cost and accumulate actuals
     898                std::list<Expression*>& args = appExpr->get_args();
     899                Cost cost = Cost::zero;
     900                const ArgPack* pack = &result;
     901                while ( pack->expr ) {
     902                        args.push_front( pack->expr->clone() );
     903                        cost += pack->cost;
     904                        pack = &results[pack->parent];
     905                }
     906                // build and validate new alternative
     907                Alternative newAlt( appExpr, result.env, cost );
     908                PRINT(
     909                        std::cerr << "instantiate function success: " << appExpr << std::endl;
     910                        std::cerr << "need assertions:" << std::endl;
     911                        printAssertionSet( result.need, std::cerr, 8 );
     912                )
     913                inferParameters( result.need, result.have, newAlt, result.openVars, out );
     914        }
     915
     916        template<typename OutputIterator>
     917        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
     918                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
     919                OpenVarSet funcOpenVars;
     920                AssertionSet funcNeed, funcHave;
     921                TypeEnvironment funcEnv( func.env );
     922                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
     923                // add all type variables as open variables now so that those not used in the parameter
     924                // list are still considered open.
     925                funcEnv.add( funcType->get_forall() );
     926
    685927                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
    686928                        // attempt to narrow based on expected target type
    687929                        Type * returnType = funcType->get_returnVals().front()->get_type();
    688                         if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
    689                                 // unification failed, don't pursue this alternative
     930                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
     931                                        indexer ) ) {
     932                                // unification failed, don't pursue this function alternative
    690933                                return;
    691934                        }
    692935                }
    693936
    694                 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
    695                         ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
    696                         Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
    697                         makeExprList( instantiatedActuals, appExpr->get_args() );
    698                         PRINT(
    699                                 std::cerr << "instantiate function success: " << appExpr << std::endl;
    700                                 std::cerr << "need assertions:" << std::endl;
    701                                 printAssertionSet( resultNeed, std::cerr, 8 );
    702                         )
    703                         inferParameters( resultNeed, resultHave, newAlt, openVars, out );
     937                // iteratively build matches, one parameter at a time
     938                std::vector<ArgPack> results;
     939                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
     940                std::size_t genStart = 0;
     941
     942                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
     943                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
     944                        if ( ! instantiateArgument(
     945                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
     946                                return;
     947                }
     948
     949                if ( funcType->get_isVarArgs() ) {
     950                        // append any unused arguments to vararg pack
     951                        std::size_t genEnd;
     952                        do {
     953                                genEnd = results.size();
     954
     955                                // iterate results
     956                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     957                                        auto nextArg = results[i].nextArg;
     958
     959                                        // use remainder of exploded tuple if present
     960                                        if ( results[i].hasExpl() ) {
     961                                                const ExplodedActual& expl = results[i].getExpl( args );
     962
     963                                                unsigned nextExpl = results[i].nextExpl + 1;
     964                                                if ( nextExpl == expl.exprs.size() ) {
     965                                                        nextExpl = 0;
     966                                                }
     967
     968                                                results.emplace_back(
     969                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
     970                                                        copy(results[i].need), copy(results[i].have),
     971                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
     972                                                        results[i].explAlt );
     973
     974                                                continue;
     975                                        }
     976
     977                                        // finish result when out of arguments
     978                                        if ( nextArg >= args.size() ) {
     979                                                validateFunctionAlternative( func, results[i], results, out );
     980
     981                                                continue;
     982                                        }
     983
     984                                        // add each possible next argument
     985                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     986                                                const ExplodedActual& expl = args[nextArg][j];
     987
     988                                                // fresh copies of parent parameters for this iteration
     989                                                TypeEnvironment env = results[i].env;
     990                                                OpenVarSet openVars = results[i].openVars;
     991
     992                                                env.addActual( expl.env, openVars );
     993
     994                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     995                                                if ( expl.exprs.empty() ) {
     996                                                        results.emplace_back(
     997                                                                results[i], move(env), copy(results[i].need),
     998                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
     999
     1000                                                        continue;
     1001                                                }
     1002
     1003                                                // add new result
     1004                                                results.emplace_back(
     1005                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
     1006                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
     1007                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
     1008                                        }
     1009                                }
     1010
     1011                                genStart = genEnd;
     1012                        } while ( genEnd != results.size() );
     1013                } else {
     1014                        // filter out results that don't use all the arguments
     1015                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
     1016                                ArgPack& result = results[i];
     1017                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
     1018                                        validateFunctionAlternative( func, result, results, out );
     1019                                }
     1020                        }
    7041021                }
    7051022        }
     
    7111028                if ( funcFinder.alternatives.empty() ) return;
    7121029
    713                 std::list< AlternativeFinder > argAlternatives;
    714                 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
    715 
    716                 std::list< AltList > possibilities;
    717                 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
     1030                std::vector< AlternativeFinder > argAlternatives;
     1031                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
     1032                        back_inserter( argAlternatives ) );
    7181033
    7191034                // take care of possible tuple assignments
    7201035                // if not tuple assignment, assignment is taken care of as a normal function call
    721                 Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
     1036                Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
    7221037
    7231038                // find function operators
     
    7301045                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
    7311046                )
     1047
     1048                // pre-explode arguments
     1049                ExplodedArgs argExpansions;
     1050                argExpansions.reserve( argAlternatives.size() );
     1051
     1052                for ( const AlternativeFinder& arg : argAlternatives ) {
     1053                        argExpansions.emplace_back();
     1054                        auto& argE = argExpansions.back();
     1055                        argE.reserve( arg.alternatives.size() );
     1056
     1057                        for ( const Alternative& actual : arg ) {
     1058                                argE.emplace_back( actual, indexer );
     1059                        }
     1060                }
    7321061
    7331062                AltList candidates;
     
    7441073                                                Alternative newFunc( *func );
    7451074                                                referenceToRvalueConversion( newFunc.expr );
    746                                                 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
    747                                                         // XXX
    748                                                         //Designators::check_alternative( function, *actualAlt );
    749                                                         makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
    750                                                 }
     1075                                                makeFunctionAlternatives( newFunc, function, argExpansions,
     1076                                                        std::back_inserter( candidates ) );
    7511077                                        }
    7521078                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
     
    7561082                                                        Alternative newFunc( *func );
    7571083                                                        referenceToRvalueConversion( newFunc.expr );
    758                                                         for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
    759                                                                 makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
    760                                                         } // for
     1084                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
     1085                                                                std::back_inserter( candidates ) );
    7611086                                                } // if
    7621087                                        } // if
    7631088                                }
    764 
    765                                 // try each function operator ?() with the current function alternative and each of the argument combinations
    766                                 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
    767                                         // check if the type is pointer to function
    768                                         if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) {
    769                                                 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
     1089                        } catch ( SemanticError &e ) {
     1090                                errors.append( e );
     1091                        }
     1092                } // for
     1093
     1094                // try each function operator ?() with each function alternative
     1095                if ( ! funcOpFinder.alternatives.empty() ) {
     1096                        // add exploded function alternatives to front of argument list
     1097                        std::vector<ExplodedActual> funcE;
     1098                        funcE.reserve( funcFinder.alternatives.size() );
     1099                        for ( const Alternative& actual : funcFinder ) {
     1100                                funcE.emplace_back( actual, indexer );
     1101                        }
     1102                        argExpansions.insert( argExpansions.begin(), move(funcE) );
     1103
     1104                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
     1105                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
     1106                                try {
     1107                                        // check if type is a pointer to function
     1108                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
     1109                                                        funcOp->expr->get_result()->stripReferences() ) ) {
     1110                                                if ( FunctionType* function =
     1111                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
    7701112                                                        Alternative newFunc( *funcOp );
    7711113                                                        referenceToRvalueConversion( newFunc.expr );
    772                                                         for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
    773                                                                 AltList currentAlt;
    774                                                                 currentAlt.push_back( *func );
    775                                                                 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
    776                                                                 makeFunctionAlternatives( newFunc, function, currentAlt, std::back_inserter( candidates ) );
    777                                                         } // for
    778                                                 } // if
    779                                         } // if
    780                                 } // for
    781                         } catch ( SemanticError &e ) {
    782                                 errors.append( e );
    783                         }
    784                 } // for
     1114                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
     1115                                                                std::back_inserter( candidates ) );
     1116                                                }
     1117                                        }
     1118                                } catch ( SemanticError &e ) {
     1119                                        errors.append( e );
     1120                                }
     1121                        }
     1122                }
    7851123
    7861124                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
     
    7881126
    7891127                // compute conversionsion costs
    790                 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
    791                         Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
     1128                for ( Alternative& withFunc : candidates ) {
     1129                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
    7921130
    7931131                        PRINT(
    794                                 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
     1132                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
    7951133                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
    7961134                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
     
    8011139                                printAll( appExpr->get_args(), std::cerr, 8 );
    8021140                                std::cerr << "bindings are:" << std::endl;
    803                                 withFunc->env.print( std::cerr, 8 );
     1141                                withFunc.env.print( std::cerr, 8 );
    8041142                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
    8051143                        )
    8061144                        if ( cvtCost != Cost::infinity ) {
    807                                 withFunc->cvtCost = cvtCost;
    808                                 alternatives.push_back( *withFunc );
     1145                                withFunc.cvtCost = cvtCost;
     1146                                alternatives.push_back( withFunc );
    8091147                        } // if
    8101148                } // for
    8111149
    812                 candidates.clear();
    813                 candidates.splice( candidates.end(), alternatives );
    814 
    815                 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
    816 
    817                 // function may return struct or union value, in which case we need to add alternatives for implicit
    818                 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
    819                 // are never the cheapest expression
    820                 for ( const Alternative & alt : alternatives ) {
     1150                candidates = move(alternatives);
     1151
     1152                // use a new list so that alternatives are not examined by addAnonConversions twice.
     1153                AltList winners;
     1154                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
     1155
     1156                // function may return struct or union value, in which case we need to add alternatives
     1157                // for implicitconversions to each of the anonymous members, must happen after findMinCost
     1158                // since anon conversions are never the cheapest expression
     1159                for ( const Alternative & alt : winners ) {
    8211160                        addAnonConversions( alt );
    8221161                }
     1162                spliceBegin( alternatives, winners );
    8231163
    8241164                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
     
    8441184                AlternativeFinder finder( indexer, env );
    8451185                finder.find( addressExpr->get_arg() );
    846                 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
    847                         if ( isLvalue( i->expr ) ) {
    848                                 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
     1186                for ( Alternative& alt : finder.alternatives ) {
     1187                        if ( isLvalue( alt.expr ) ) {
     1188                                alternatives.push_back(
     1189                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
    8491190                        } // if
    8501191                } // for
     
    8521193
    8531194        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
    854                 alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
     1195                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
    8551196        }
    8561197
     
    8941235
    8951236                AltList candidates;
    896                 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
     1237                for ( Alternative & alt : finder.alternatives ) {
    8971238                        AssertionSet needAssertions, haveAssertions;
    8981239                        OpenVarSet openVars;
     
    9021243                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
    9031244                        // to.
    904                         int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
     1245                        int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
    9051246                        if ( discardedValues < 0 ) continue;
    9061247                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
    9071248                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
    9081249                        // unification run for side-effects
    909                         unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
    910                         Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
     1250                        unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
     1251                                haveAssertions, openVars, indexer );
     1252                        Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
     1253                                alt.env );
     1254                        PRINT(
     1255                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
     1256                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
     1257                                std::cerr << "env: " << alt.env << std::endl;
     1258                        )
    9111259                        if ( thisCost != Cost::infinity ) {
     1260                                PRINT(
     1261                                        std::cerr << "has finite cost." << std::endl;
     1262                                )
    9121263                                // count one safe conversion for each value that is thrown away
    9131264                                thisCost.incSafe( discardedValues );
    914                                 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
    915                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
     1265                                Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
     1266                                        alt.cost, thisCost );
     1267                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
     1268                                        back_inserter( candidates ) );
    9161269                        } // if
    9171270                } // for
     
    12001553
    12011554        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
    1202                 std::list< AlternativeFinder > subExprAlternatives;
    1203                 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
    1204                 std::list< AltList > possibilities;
    1205                 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
    1206                 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
     1555                std::vector< AlternativeFinder > subExprAlternatives;
     1556                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
     1557                        back_inserter( subExprAlternatives ) );
     1558                std::vector< AltList > possibilities;
     1559                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
     1560                        back_inserter( possibilities ) );
     1561                for ( const AltList& alts : possibilities ) {
    12071562                        std::list< Expression * > exprs;
    1208                         makeExprList( *i, exprs );
     1563                        makeExprList( alts, exprs );
    12091564
    12101565                        TypeEnvironment compositeEnv;
    1211                         simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
    1212                         alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
     1566                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
     1567                        alternatives.push_back(
     1568                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
    12131569                } // for
    12141570        }
  • src/ResolvExpr/AlternativeFinder.h

    r9d06142 rc0d00b6  
    2121
    2222#include "Alternative.h"                 // for AltList, Alternative
     23#include "ExplodedActual.h"              // for ExplodedActual
    2324#include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
    2425#include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
     
    3132
    3233namespace ResolvExpr {
     34        struct ArgPack;
     35
     36        /// First index is which argument, second index is which alternative for that argument,
     37        /// third index is which exploded element of that alternative
     38        using ExplodedArgs = std::vector< std::vector< ExplodedActual > >;
     39
    3340        class AlternativeFinder : public Visitor {
    3441          public:
    3542                AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env );
     43
     44                AlternativeFinder( const AlternativeFinder& o )
     45                        : indexer(o.indexer), alternatives(o.alternatives), env(o.env),
     46                          targetType(o.targetType) {}
     47
     48                AlternativeFinder( AlternativeFinder&& o )
     49                        : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env),
     50                          targetType(o.targetType) {}
     51
     52                AlternativeFinder& operator= ( const AlternativeFinder& o ) {
     53                        if (&o == this) return *this;
     54
     55                        // horrific nasty hack to rebind references...
     56                        alternatives.~AltList();
     57                        new(this) AlternativeFinder(o);
     58                        return *this;
     59                }
     60
     61                AlternativeFinder& operator= ( AlternativeFinder&& o ) {
     62                        if (&o == this) return *this;
     63
     64                        // horrific nasty hack to rebind references...
     65                        alternatives.~AltList();
     66                        new(this) AlternativeFinder(std::move(o));
     67                        return *this;
     68                }
     69
    3670                void find( Expression *expr, bool adjust = false, bool prune = true, bool failFast = true );
    3771                /// Calls find with the adjust flag set; adjustment turns array and function types into equivalent pointer types
     
    99133                /// Adds alternatives for offsetof expressions, given the base type and name of the member
    100134                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
    101                 bool instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out );
    102                 template< typename OutputIterator >
    103                 void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out );
     135                /// Takes a final result and checks if its assertions can be satisfied
     136                template<typename OutputIterator>
     137                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
     138                /// Finds matching alternatives for a function, given a set of arguments
     139                template<typename OutputIterator>
     140                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
     141                /// Checks if assertion parameters match for a new alternative
    104142                template< typename OutputIterator >
    105143                void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
  • src/ResolvExpr/PtrsAssignable.cc

    r9d06142 rc0d00b6  
    6868
    6969        void PtrsAssignable::visit( __attribute((unused)) VoidType *voidType ) {
    70                 if ( ! dynamic_cast< FunctionType* >( dest ) ) {
    71                         // T * = void * is safe for any T that is not a function type.
    72                         // xxx - this should be unsafe...
    73                         result = 1;
    74                 } // if
     70                // T * = void * is disallowed - this is a change from C, where any
     71                // void * can be assigned or passed to a non-void pointer without a cast.
    7572        }
    7673
  • src/ResolvExpr/RenameVars.cc

    r9d06142 rc0d00b6  
    2929        RenameVars global_renamer;
    3030
    31         RenameVars::RenameVars() : level( 0 ) {
     31        RenameVars::RenameVars() : level( 0 ), resetCount( 0 ) {
    3232                mapStack.push_front( std::map< std::string, std::string >() );
    3333        }
     
    3535        void RenameVars::reset() {
    3636                level = 0;
     37                resetCount++;
    3738        }
    3839
     
    130131                        for ( Type::ForallList::iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) {
    131132                                std::ostringstream output;
    132                                 output << "_" << level << "_" << (*i)->get_name();
     133                                output << "_" << resetCount << "_" << level << "_" << (*i)->get_name();
    133134                                std::string newname( output.str() );
    134135                                mapStack.front()[ (*i)->get_name() ] = newname;
  • src/ResolvExpr/RenameVars.h

    r9d06142 rc0d00b6  
    4848                void typeBefore( Type *type );
    4949                void typeAfter( Type *type );
    50                 int level;
     50                int level, resetCount;
    5151                std::list< std::map< std::string, std::string > > mapStack;
    5252        };
  • src/ResolvExpr/Resolver.cc

    r9d06142 rc0d00b6  
    1818#include <memory>                        // for allocator, allocator_traits<...
    1919#include <tuple>                         // for get
     20#include <vector>
    2021
    2122#include "Alternative.h"                 // for Alternative, AltList
     
    411412
    412413                        // Find all alternatives for all arguments in canonical form
    413                         std::list< AlternativeFinder > argAlternatives;
     414                        std::vector< AlternativeFinder > argAlternatives;
    414415                        funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) );
    415416
    416417                        // List all combinations of arguments
    417                         std::list< AltList > possibilities;
     418                        std::vector< AltList > possibilities;
    418419                        combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
    419420
  • src/ResolvExpr/TypeEnvironment.cc

    r9d06142 rc0d00b6  
    201201        }
    202202
     203        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
     204                for ( const EqvClass& c : actualEnv ) {
     205                        EqvClass c2 = c;
     206                        c2.allowWidening = false;
     207                        for ( const std::string& var : c2.vars ) {
     208                                openVars[ var ] = c2.data;
     209                        }
     210                        env.push_back( std::move(c2) );
     211                }
     212        }
     213
     214        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
     215                env.print( out );
     216                return out;
     217        }
    203218} // namespace ResolvExpr
    204219
  • src/ResolvExpr/TypeEnvironment.h

    r9d06142 rc0d00b6  
    8686                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
    8787
     88                /// Iteratively adds the environment of a new actual (with allowWidening = false),
     89                /// and extracts open variables.
     90                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
     91
    8892                typedef std::list< EqvClass >::iterator iterator;
    8993                iterator begin() { return env.begin(); }
     
    110114                return sub.applyFree( type );
    111115        }
     116
     117        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
    112118} // namespace ResolvExpr
    113119
  • src/ResolvExpr/module.mk

    r9d06142 rc0d00b6  
    3232       ResolvExpr/Occurs.cc \
    3333       ResolvExpr/TypeEnvironment.cc \
    34        ResolvExpr/CurrentObject.cc
     34       ResolvExpr/CurrentObject.cc \
     35       ResolvExpr/ExplodedActual.cc
  • src/ResolvExpr/typeops.h

    r9d06142 rc0d00b6  
    1616#pragma once
    1717
     18#include <vector>
     19
    1820#include "SynTree/SynTree.h"
    1921#include "SynTree/Type.h"
     
    2830        void combos( InputIterator begin, InputIterator end, OutputIterator out ) {
    2931                typedef typename InputIterator::value_type SetType;
    30                 typedef typename std::list< typename SetType::value_type > ListType;
     32                typedef typename std::vector< typename SetType::value_type > ListType;
    3133
    3234                if ( begin == end )     {
     
    3840                begin++;
    3941
    40                 std::list< ListType > recursiveResult;
     42                std::vector< ListType > recursiveResult;
    4143                combos( begin, end, back_inserter( recursiveResult ) );
    4244
    43                 for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) {
    44                         for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) {
    45                                 ListType result;
    46                                 std::back_insert_iterator< ListType > inserter = back_inserter( result );
    47                                 *inserter++ = *j;
    48                                 std::copy( i->begin(), i->end(), inserter );
    49                                 *out++ = result;
    50                         } // for
    51                 } // for
     45                for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) {
     46                        ListType result;
     47                        std::back_insert_iterator< ListType > inserter = back_inserter( result );
     48                        *inserter++ = j;
     49                        std::copy( i.begin(), i.end(), inserter );
     50                        *out++ = result;
     51                }
    5252        }
    5353
  • src/SymTab/Autogen.cc

    r9d06142 rc0d00b6  
    6262                void previsit( FunctionDecl * functionDecl );
    6363
    64                 void previsit( FunctionType * ftype );
    65                 void previsit( PointerType * ptype );
    66 
    6764                void previsit( CompoundStmt * compoundStmt );
    6865
     
    7269                unsigned int functionNesting = 0;     // current level of nested functions
    7370
    74                 InitTweak::ManagedTypes managedTypes;
    7571                std::vector< FuncData > data;
    7672        };
     
    625621        // generate ctor/dtors/assign for typedecls, e.g., otype T = int *;
    626622        void AutogenerateRoutines::previsit( TypeDecl * typeDecl ) {
    627                 visit_children = false;
    628623                if ( ! typeDecl->base ) return;
    629624
     
    631626                TypeFuncGenerator gen( typeDecl, &refType, data, functionNesting, indexer );
    632627                generateFunctions( gen, declsToAddAfter );
    633         }
    634 
    635         void AutogenerateRoutines::previsit( FunctionType *) {
    636                 // ensure that we don't add assignment ops for types defined as part of the function
    637                 visit_children = false;
    638         }
    639 
    640         void AutogenerateRoutines::previsit( PointerType *) {
    641                 // ensure that we don't add assignment ops for types defined as part of the pointer
    642                 visit_children = false;
     628
    643629        }
    644630
     
    648634        }
    649635
    650         void AutogenerateRoutines::previsit( FunctionDecl * functionDecl ) {
    651                 visit_children = false;
    652                 // record the existence of this function as appropriate
    653                 managedTypes.handleDWT( functionDecl );
    654 
    655                 maybeAccept( functionDecl->type, *visitor );
     636        void AutogenerateRoutines::previsit( FunctionDecl * ) {
     637                // Track whether we're currently in a function.
     638                // Can ignore function type idiosyncrasies, because function type can never
     639                // declare a new type.
    656640                functionNesting += 1;
    657                 maybeAccept( functionDecl->statements, *visitor );
    658                 functionNesting -= 1;
     641                GuardAction( [this]()  { functionNesting -= 1; } );
    659642        }
    660643
    661644        void AutogenerateRoutines::previsit( CompoundStmt * ) {
    662                 GuardScope( managedTypes );
    663645                GuardScope( structsDone );
    664646        }
  • src/SymTab/Autogen.h

    r9d06142 rc0d00b6  
    5959        /// inserts into out a generated call expression to function fname with arguments dstParam and srcParam. Intended to be used with generated ?=?, ?{}, and ^?{} calls.
    6060        template< typename OutputIterator >
    61         Statement * genCall( InitTweak::InitExpander & srcParam, Expression * dstParam, const std::string & fname, OutputIterator out, Type * type, bool addCast = false, bool forward = true );
     61        Statement * genCall( InitTweak::InitExpander & srcParam, Expression * dstParam, const std::string & fname, OutputIterator out, Type * type, Type * addCast = nullptr, bool forward = true );
    6262
    6363        /// inserts into out a generated call expression to function fname with arguments dstParam and srcParam. Should only be called with non-array types.
    6464        /// optionally returns a statement which must be inserted prior to the containing loop, if there is one
    6565        template< typename OutputIterator >
    66         Statement * genScalarCall( InitTweak::InitExpander & srcParam, Expression * dstParam, std::string fname, OutputIterator out, Type * type, bool addCast = false ) {
     66        Statement * genScalarCall( InitTweak::InitExpander & srcParam, Expression * dstParam, std::string fname, OutputIterator out, Type * type, Type * addCast = nullptr ) {
    6767                bool isReferenceCtorDtor = false;
    6868                if ( dynamic_cast< ReferenceType * >( type ) && CodeGen::isCtorDtor( fname ) ) {
     
    7171                        fname = "?=?";
    7272                        dstParam = new AddressExpr( dstParam );
    73                         addCast = false;
     73                        addCast = nullptr;
    7474                        isReferenceCtorDtor = true;
    7575                }
     
    8686                        // remove lvalue as a qualifier, this can change to
    8787                        //   type->get_qualifiers() = Type::Qualifiers();
    88                         assert( type );
    89                         Type * castType = type->clone();
     88                        Type * castType = addCast->clone();
    9089                        castType->get_qualifiers() -= Type::Qualifiers( Type::Lvalue | Type::Const | Type::Volatile | Type::Restrict | Type::Atomic );
    9190                        // castType->set_lvalue( true ); // xxx - might not need this
     
    118117        /// If forward is true, loop goes from 0 to N-1, else N-1 to 0
    119118        template< typename OutputIterator >
    120         void genArrayCall( InitTweak::InitExpander & srcParam, Expression *dstParam, const std::string & fname, OutputIterator out, ArrayType *array, bool addCast = false, bool forward = true ) {
     119        void genArrayCall( InitTweak::InitExpander & srcParam, Expression *dstParam, const std::string & fname, OutputIterator out, ArrayType *array, Type * addCast = nullptr, bool forward = true ) {
    121120                static UniqueName indexName( "_index" );
    122121
    123122                // for a flexible array member nothing is done -- user must define own assignment
    124                 if ( ! array->get_dimension() ) return ;
     123                if ( ! array->get_dimension() ) return;
     124
     125                if ( addCast ) {
     126                        // peel off array layer from cast
     127                        ArrayType * at = strict_dynamic_cast< ArrayType * >( addCast );
     128                        addCast = at->base;
     129                }
    125130
    126131                Expression * begin, * end, * update, * cmp;
     
    174179
    175180        template< typename OutputIterator >
    176         Statement * genCall( InitTweak::InitExpander & srcParam, Expression * dstParam, const std::string & fname, OutputIterator out, Type * type, bool addCast, bool forward ) {
     181        Statement * genCall( InitTweak::InitExpander & srcParam, Expression * dstParam, const std::string & fname, OutputIterator out, Type * type, Type * addCast, bool forward ) {
    177182                if ( ArrayType * at = dynamic_cast< ArrayType * >( type ) ) {
    178183                        genArrayCall( srcParam, dstParam, fname, out, at, addCast, forward );
     
    194199                if ( isUnnamedBitfield( obj ) ) return;
    195200
    196                 bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && ! obj->get_bitfieldWidth() ) );
     201                Type * addCast = nullptr;
     202                if ( (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && ! obj->get_bitfieldWidth() ) ) ) {
     203                        assert( dstParam->result );
     204                        addCast = dstParam->result;
     205                }
    197206                std::list< Statement * > stmts;
    198207                genCall( srcParam, dstParam, fname, back_inserter( stmts ), obj->type, addCast, forward );
  • src/SymTab/Indexer.cc

    r9d06142 rc0d00b6  
    567567        }
    568568
     569        void Indexer::addIds( const std::list< DeclarationWithType * > & decls ) {
     570                for ( auto d : decls ) {
     571                        addId( d );
     572                }
     573        }
     574
     575        void Indexer::addTypes( const std::list< TypeDecl * > & tds ) {
     576                for ( auto td : tds ) {
     577                        addType( td );
     578                        addIds( td->assertions );
     579                }
     580        }
     581
     582        void Indexer::addFunctionType( FunctionType * ftype ) {
     583                addTypes( ftype->forall );
     584                addIds( ftype->returnVals );
     585                addIds( ftype->parameters );
     586        }
     587
    569588        void Indexer::enterScope() {
    570589                ++scope;
  • src/SymTab/Indexer.h

    r9d06142 rc0d00b6  
    7676                void addTrait( TraitDecl *decl );
    7777
     78                /// convenience function for adding a list of Ids to the indexer
     79                void addIds( const std::list< DeclarationWithType * > & decls );
     80
     81                /// convenience function for adding a list of forall parameters to the indexer
     82                void addTypes( const std::list< TypeDecl * > & tds );
     83
     84                /// convenience function for adding all of the declarations in a function type to the indexer
     85                void addFunctionType( FunctionType * ftype );
     86
    7887                bool doDebug = false; ///< Display debugging trace?
    7988          private:
  • src/SymTab/Validate.cc

    r9d06142 rc0d00b6  
    124124
    125125        /// Associates forward declarations of aggregates with their definitions
    126         struct LinkReferenceToTypes final : public WithIndexer {
     126        struct LinkReferenceToTypes final : public WithIndexer, public WithGuards {
    127127                LinkReferenceToTypes( const Indexer *indexer );
    128128                void postvisit( TypeInstType *typeInst );
     
    137137                void postvisit( UnionDecl *unionDecl );
    138138                void postvisit( TraitDecl * traitDecl );
     139
     140                void previsit( StructDecl *structDecl );
     141                void previsit( UnionDecl *unionDecl );
     142
     143                void renameGenericParams( std::list< TypeDecl * > & params );
    139144
    140145          private:
     
    147152                ForwardStructsType forwardStructs;
    148153                ForwardUnionsType forwardUnions;
     154                /// true if currently in a generic type body, so that type parameter instances can be renamed appropriately
     155                bool inGeneric = false;
    149156        };
    150157
     
    423430        }
    424431
     432        void checkGenericParameters( ReferenceToType * inst ) {
     433                for ( Expression * param : inst->parameters ) {
     434                        if ( ! dynamic_cast< TypeExpr * >( param ) ) {
     435                                throw SemanticError( "Expression parameters for generic types are currently unsupported: ", inst );
     436                        }
     437                }
     438        }
     439
    425440        void LinkReferenceToTypes::postvisit( StructInstType *structInst ) {
    426441                StructDecl *st = local_indexer->lookupStruct( structInst->get_name() );
     
    434449                        forwardStructs[ structInst->get_name() ].push_back( structInst );
    435450                } // if
     451                checkGenericParameters( structInst );
    436452        }
    437453
     
    446462                        forwardUnions[ unionInst->get_name() ].push_back( unionInst );
    447463                } // if
     464                checkGenericParameters( unionInst );
    448465        }
    449466
     
    525542                // need to carry over the 'sized' status of each decl in the instance
    526543                for ( auto p : group_iterate( traitDecl->get_parameters(), traitInst->get_parameters() ) ) {
    527                         TypeExpr * expr = strict_dynamic_cast< TypeExpr * >( std::get<1>(p) );
     544                        TypeExpr * expr = dynamic_cast< TypeExpr * >( std::get<1>(p) );
     545                        if ( ! expr ) {
     546                                throw SemanticError( "Expression parameters for trait instances are currently unsupported: ", std::get<1>(p) );
     547                        }
    528548                        if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( expr->get_type() ) ) {
    529549                                TypeDecl * formalDecl = std::get<0>(p);
     
    546566                        } // if
    547567                } // if
     568        }
     569
     570        void LinkReferenceToTypes::renameGenericParams( std::list< TypeDecl * > & params ) {
     571                // rename generic type parameters uniquely so that they do not conflict with user-defined function forall parameters, e.g.
     572                //   forall(otype T)
     573                //   struct Box {
     574                //     T x;
     575                //   };
     576                //   forall(otype T)
     577                //   void f(Box(T) b) {
     578                //     ...
     579                //   }
     580                // The T in Box and the T in f are different, so internally the naming must reflect that.
     581                GuardValue( inGeneric );
     582                inGeneric = ! params.empty();
     583                for ( TypeDecl * td : params ) {
     584                        td->name = "__" + td->name + "_generic_";
     585                }
     586        }
     587
     588        void LinkReferenceToTypes::previsit( StructDecl * structDecl ) {
     589                renameGenericParams( structDecl->parameters );
     590        }
     591
     592        void LinkReferenceToTypes::previsit( UnionDecl * unionDecl ) {
     593                renameGenericParams( unionDecl->parameters );
    548594        }
    549595
     
    575621
    576622        void LinkReferenceToTypes::postvisit( TypeInstType *typeInst ) {
     623                // ensure generic parameter instances are renamed like the base type
     624                if ( inGeneric && typeInst->baseType ) typeInst->name = typeInst->baseType->name;
    577625                if ( NamedTypeDecl *namedTypeDecl = local_indexer->lookupType( typeInst->get_name() ) ) {
    578626                        if ( TypeDecl *typeDecl = dynamic_cast< TypeDecl * >( namedTypeDecl ) ) {
  • src/SynTree/Expression.cc

    r9d06142 rc0d00b6  
    8888        Type * type = var->get_type()->clone();
    8989        type->set_lvalue( true );
     90
     91        // xxx - doesn't quite work yet - get different alternatives with the same cost
     92
     93        // // enumerators are not lvalues
     94        // if ( EnumInstType * inst = dynamic_cast< EnumInstType * >( var->get_type() ) ) {
     95        //      assert( inst->baseEnum );
     96        //      EnumDecl * decl = inst->baseEnum;
     97        //      for ( Declaration * member : decl->members ) {
     98        //              if ( member == _var ) {
     99        //                      type->set_lvalue( false );
     100        //              }
     101        //      }
     102        // }
     103
    90104        set_result( type );
    91105}
     
    324338                        return makeSub( refType->get_base() );
    325339                } else if ( StructInstType * aggInst = dynamic_cast< StructInstType * >( t ) ) {
    326                         return TypeSubstitution( aggInst->get_baseParameters()->begin(), aggInst->get_baseParameters()->end(), aggInst->get_parameters().begin() );
     340                        return TypeSubstitution( aggInst->get_baseParameters()->begin(), aggInst->get_baseParameters()->end(), aggInst->parameters.begin() );
    327341                } else if ( UnionInstType * aggInst = dynamic_cast< UnionInstType * >( t ) ) {
    328                         return TypeSubstitution( aggInst->get_baseParameters()->begin(), aggInst->get_baseParameters()->end(), aggInst->get_parameters().begin() );
     342                        return TypeSubstitution( aggInst->get_baseParameters()->begin(), aggInst->get_baseParameters()->end(), aggInst->parameters.begin() );
    329343                } else {
    330344                        assertf( false, "makeSub expects struct or union type for aggregate, but got: %s", toString( t ).c_str() );
  • src/Tuples/Explode.h

    r9d06142 rc0d00b6  
    1616#pragma once
    1717
    18 #include <iterator>                  // for back_inserter, back_insert_iterator
     18#include <iterator>                     // for back_inserter, back_insert_iterator
     19#include <utility>                      // for forward
    1920
    20 #include "ResolvExpr/Alternative.h"  // for Alternative, AltList
    21 #include "SynTree/Expression.h"      // for Expression, UniqueExpr, AddressExpr
    22 #include "SynTree/Type.h"            // for TupleType, Type
    23 #include "Tuples.h"                  // for maybeImpure
     21#include "ResolvExpr/Alternative.h"     // for Alternative, AltList
     22#include "ResolvExpr/ExplodedActual.h"  // for ExplodedActual
     23#include "SynTree/Expression.h"         // for Expression, UniqueExpr, AddressExpr
     24#include "SynTree/Type.h"               // for TupleType, Type
     25#include "Tuples.h"                     // for maybeImpure
    2426
    2527namespace SymTab {
     
    3941        }
    4042
     43        /// Append alternative to an OutputIterator of Alternatives
     44        template<typename OutputIterator>
     45        void append( OutputIterator out, Expression* expr, const ResolvExpr::TypeEnvironment& env,
     46                        const ResolvExpr::Cost& cost, const ResolvExpr::Cost& cvtCost ) {
     47                *out++ = ResolvExpr::Alternative{ expr, env, cost, cvtCost };
     48        }
     49
     50        /// Append alternative to an ExplodedActual
     51        static inline void append( ResolvExpr::ExplodedActual& ea, Expression* expr,
     52                        const ResolvExpr::TypeEnvironment&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
     53                ea.exprs.emplace_back( expr );
     54                /// xxx -- merge environment, cost?
     55        }
     56
    4157        /// helper function used by explode
    42         template< typename OutputIterator >
    43         void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign ) {
     58        template< typename Output >
     59        void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt,
     60                        const SymTab::Indexer & indexer, Output&& out, bool isTupleAssign ) {
    4461                if ( isTupleAssign ) {
    4562                        // tuple assignment needs CastExprs to be recursively exploded to easily get at all of the components
    4663                        if ( CastExpr * castExpr = isReferenceCast( expr ) ) {
    4764                                ResolvExpr::AltList alts;
    48                                 explodeUnique( castExpr->get_arg(), alt, indexer, back_inserter( alts ), isTupleAssign );
     65                                explodeUnique(
     66                                        castExpr->get_arg(), alt, indexer, back_inserter( alts ), isTupleAssign );
    4967                                for ( ResolvExpr::Alternative & alt : alts ) {
    5068                                        // distribute reference cast over all components
    51                                         alt.expr = distributeReference( alt.expr );
    52                                         *out++ = alt;
     69                                        append( std::forward<Output>(out), distributeReference( alt.release_expr() ),
     70                                                alt.env, alt.cost, alt.cvtCost );
    5371                                }
    5472                                // in tuple assignment, still need to handle the other cases, but only if not already handled here (don't want to output too many alternatives)
     
    6179                                // can open tuple expr and dump its exploded components
    6280                                for ( Expression * expr : tupleExpr->get_exprs() ) {
    63                                         explodeUnique( expr, alt, indexer, out, isTupleAssign );
     81                                        explodeUnique( expr, alt, indexer, std::forward<Output>(out), isTupleAssign );
    6482                                }
    6583                        } else {
     
    7795                                for ( unsigned int i = 0; i < tupleType->size(); i++ ) {
    7896                                        TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i );
    79                                         explodeUnique( idx, alt, indexer, out, isTupleAssign );
     97                                        explodeUnique( idx, alt, indexer, std::forward<Output>(out), isTupleAssign );
    8098                                        delete idx;
    8199                                }
     
    84102                } else {
    85103                        // atomic (non-tuple) type - output a clone of the expression in a new alternative
    86                         *out++ = ResolvExpr::Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost );
     104                        append( std::forward<Output>(out), expr->clone(), alt.env, alt.cost, alt.cvtCost );
    87105                }
    88106        }
    89107
    90108        /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type
    91         template< typename OutputIterator >
    92         void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) {
    93                 explodeUnique( alt.expr, alt, indexer, out, isTupleAssign );
     109        template< typename Output >
     110        void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer,
     111                        Output&& out, bool isTupleAssign = false ) {
     112                explodeUnique( alt.expr, alt, indexer, std::forward<Output>(out), isTupleAssign );
    94113        }
    95114
    96115        // explode list of alternatives
    97         template< typename AltIterator, typename OutputIterator >
    98         void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) {
     116        template< typename AltIterator, typename Output >
     117        void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer,
     118                        Output&& out, bool isTupleAssign = false ) {
    99119                for ( ; altBegin != altEnd; ++altBegin ) {
    100                         explode( *altBegin, indexer, out, isTupleAssign );
     120                        explode( *altBegin, indexer, std::forward<Output>(out), isTupleAssign );
    101121                }
    102122        }
    103123
    104         template< typename OutputIterator >
    105         void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) {
    106                 explode( alts.begin(), alts.end(), indexer, out, isTupleAssign );
     124        template< typename Output >
     125        void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, Output&& out,
     126                        bool isTupleAssign = false ) {
     127                explode( alts.begin(), alts.end(), indexer, std::forward<Output>(out), isTupleAssign );
    107128        }
    108129} // namespace Tuples
  • src/Tuples/TupleAssignment.cc

    r9d06142 rc0d00b6  
    2020#include <memory>                          // for unique_ptr, allocator_trai...
    2121#include <string>                          // for string
     22#include <vector>
    2223
    2324#include "CodeGen/OperatorTable.h"
     
    3334#include "ResolvExpr/Resolver.h"           // for resolveCtorInit
    3435#include "ResolvExpr/TypeEnvironment.h"    // for TypeEnvironment
     36#include "ResolvExpr/typeops.h"            // for combos
    3537#include "SynTree/Declaration.h"           // for ObjectDecl
    3638#include "SynTree/Expression.h"            // for Expression, CastExpr, Name...
     
    5254                // dispatcher for Tuple (multiple and mass) assignment operations
    5355                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
    54                 void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
     56                void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
    5557
    5658          private:
     
    5961                struct Matcher {
    6062                  public:
    61                         Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
     63                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
     64                                ResolvExpr::AltList& rhs );
    6265                        virtual ~Matcher() {}
    6366                        virtual void match( std::list< Expression * > &out ) = 0;
     
    7275                struct MassAssignMatcher : public Matcher {
    7376                  public:
    74                         MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
     77                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
     78                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
    7579                        virtual void match( std::list< Expression * > &out );
    7680                };
     
    7882                struct MultipleAssignMatcher : public Matcher {
    7983                  public:
    80                         MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
     84                        MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
     85                                const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
    8186                        virtual void match( std::list< Expression * > &out );
    8287                };
     
    114119        }
    115120
    116         void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
     121        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
     122                                std::vector<ResolvExpr::AlternativeFinder> &args ) {
    117123                TupleAssignSpotter spotter( currentFinder );
    118                 spotter.spot( expr, possibilities );
     124                spotter.spot( expr, args );
    119125        }
    120126
     
    122128                : currentFinder(f) {}
    123129
    124         void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
     130        void TupleAssignSpotter::spot( UntypedExpr * expr,
     131                        std::vector<ResolvExpr::AlternativeFinder> &args ) {
    125132                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
    126133                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
    127                                fname = op->get_name();
    128                                 PRINT( std::cerr << "TupleAssignment: " << fname << std::endl; )
    129                                 for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
    130                                         if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
    131                                         if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) {
    132                                                 // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
    133                                                 continue;
     134                                fname = op->get_name();
     135
     136                                // AlternativeFinder will naturally handle this case case, if it's legal
     137                                if ( args.size() == 0 ) return;
     138
     139                                // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
     140                                // the function, in which case AlternativeFinder will handle it normally
     141                                if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;
     142
     143                                // look over all possible left-hand-sides
     144                                for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
     145                                        // skip non-tuple LHS
     146                                        if ( ! refToTuple(lhsAlt.expr) ) continue;
     147
     148                                        // explode is aware of casts - ensure every LHS expression is sent into explode
     149                                        // with a reference cast
     150                                        // xxx - this seems to change the alternatives before the normal
     151                                        //  AlternativeFinder flow; maybe this is desired?
     152                                        if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
     153                                                lhsAlt.expr = new CastExpr( lhsAlt.expr,
     154                                                                new ReferenceType( Type::Qualifiers(),
     155                                                                        lhsAlt.expr->get_result()->clone() ) );
    134156                                        }
    135157
    136                                         assert( ! ali->empty() );
    137                                         // grab args 2-N and group into a TupleExpr
    138                                         const ResolvExpr::Alternative & alt1 = ali->front();
    139                                         auto begin = std::next(ali->begin(), 1), end = ali->end();
    140                                         PRINT( std::cerr << "alt1 is " << alt1.expr << std::endl; )
    141                                         if ( refToTuple(alt1.expr) ) {
    142                                                 PRINT( std::cerr << "and is reference to tuple" << std::endl; )
    143                                                 if ( isMultAssign( begin, end ) ) {
    144                                                         PRINT( std::cerr << "possible multiple assignment" << std::endl; )
    145                                                         matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
    146                                                 } else {
    147                                                         // mass assignment
    148                                                         PRINT( std::cerr << "possible mass assignment" << std::endl; )
    149                                                         matcher.reset( new MassAssignMatcher( *this,  *ali ) );
     158                                        // explode the LHS so that each field of a tuple-valued-expr is assigned
     159                                        ResolvExpr::AltList lhs;
     160                                        explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
     161                                        for ( ResolvExpr::Alternative& alt : lhs ) {
     162                                                // each LHS value must be a reference - some come in with a cast expression,
     163                                                // if not just cast to reference here
     164                                                if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
     165                                                        alt.expr = new CastExpr( alt.expr,
     166                                                                new ReferenceType( Type::Qualifiers(),
     167                                                                        alt.expr->get_result()->clone() ) );
    150168                                                }
     169                                        }
     170
     171                                        if ( args.size() == 1 ) {
     172                                                // mass default-initialization/destruction
     173                                                ResolvExpr::AltList rhs{};
     174                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
    151175                                                match();
     176                                        } else if ( args.size() > 2 ) {
     177                                                // expand all possible RHS possibilities
     178                                                // TODO build iterative version of this instead of using combos
     179                                                std::vector< ResolvExpr::AltList > rhsAlts;
     180                                                combos( std::next(args.begin(), 1), args.end(),
     181                                                        std::back_inserter( rhsAlts ) );
     182                                                for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
     183                                                        // multiple assignment
     184                                                        ResolvExpr::AltList rhs;
     185                                                        explode( rhsAlt, currentFinder.get_indexer(),
     186                                                                std::back_inserter(rhs), true );
     187                                                        matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
     188                                                        match();
     189                                                }
     190                                        } else {
     191                                                for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
     192                                                        ResolvExpr::AltList rhs;
     193                                                        if ( isTuple(rhsAlt.expr) ) {
     194                                                                // multiple assignment
     195                                                                explode( rhsAlt, currentFinder.get_indexer(), 
     196                                                                        std::back_inserter(rhs), true );
     197                                                                matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
     198                                                        } else {
     199                                                                // mass assignment
     200                                                                rhs.push_back( rhsAlt );
     201                                                                matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
     202                                                        }
     203                                                        match();
     204                                                }
    152205                                        }
    153206                                }
     
    169222                ResolvExpr::AltList current;
    170223                // now resolve new assignments
    171                 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
     224                for ( std::list< Expression * >::iterator i = new_assigns.begin();
     225                                i != new_assigns.end(); ++i ) {
    172226                        PRINT(
    173227                                std::cerr << "== resolving tuple assign ==" << std::endl;
     
    175229                        )
    176230
    177                         ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
     231                        ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
     232                                currentFinder.get_environ() };
    178233                        try {
    179234                                finder.findWithAdjustment(*i);
     
    196251                // combine assignment environments into combined expression environment
    197252                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
    198                 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
    199         }
    200 
    201         TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
    202                 assert( ! alts.empty() );
    203                 // combine argument environments into combined expression environment
    204                 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
    205 
    206                 ResolvExpr::Alternative lhsAlt = alts.front();
    207                 // explode is aware of casts - ensure every LHS expression is sent into explode with a reference cast
    208                 if ( ! dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
    209                         lhsAlt.expr = new CastExpr( lhsAlt.expr, new ReferenceType( Type::Qualifiers(), lhsAlt.expr->get_result()->clone() ) );
    210                 }
    211 
    212                 // explode the lhs so that each field of the tuple-valued-expr is assigned.
    213                 explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
    214 
    215                 for ( ResolvExpr::Alternative & alt : lhs ) {
    216                         // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here.
    217                         if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) {
    218                                 alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) );
    219                         }
    220                 }
    221         }
    222 
    223         TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
    224                 assert( alts.size() == 1 || alts.size() == 2 );
    225                 if ( alts.size() == 2 ) {
    226                         rhs.push_back( alts.back() );
    227                 }
    228         }
    229 
    230         TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
    231                 // explode the rhs so that each field of the tuple-valued-expr is assigned.
    232                 explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
     253                // xxx -- was push_front
     254                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
     255                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
     256                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
     257        }
     258
     259        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
     260                const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
     261        : lhs(lhs), rhs(rhs), spotter(spotter),
     262          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
     263                simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
     264                simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
    233265        }
    234266
  • src/Tuples/Tuples.h

    r9d06142 rc0d00b6  
    1717
    1818#include <string>
     19#include <vector>
    1920
    2021#include "SynTree/Expression.h"
     
    2627namespace Tuples {
    2728        // TupleAssignment.cc
    28         void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, const std::list<ResolvExpr::AltList> & possibilities );
    29 
     29        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign,
     30                std::vector< ResolvExpr::AlternativeFinder >& args );
     31       
    3032        // TupleExpansion.cc
    3133        /// expands z.[a, b.[x, y], c] into [z.a, z.b.x, z.b.y, z.c], inserting UniqueExprs as appropriate
  • src/benchmark/Makefile.am

    r9d06142 rc0d00b6  
    2323STATS    = ${TOOLSDIR}stat.py
    2424repeats  = 30
     25TIME_FORMAT = "%E"
     26PRINT_FORMAT = %20s: #Comments needed for spacing
    2527
    2628.NOTPARALLEL:
     
    2931
    3032all : ctxswitch$(EXEEXT) mutex$(EXEEXT) signal$(EXEEXT) waitfor$(EXEEXT) creation$(EXEEXT)
    31 
    32 bench$(EXEEXT) :
    33         @for ccflags in "-debug" "-nodebug"; do \
    34                 echo ${CC} ${AM_CFLAGS} ${CFLAGS} ${ccflags} @CFA_FLAGS@ -lrt bench.c;\
    35                 ${CC} ${AM_CFLAGS} ${CFLAGS} $${ccflags} -lrt bench.c;\
    36                 ./a.out ; \
    37         done ; \
    38         rm -f ./a.out ;
    39 
    40 csv-data$(EXEEXT):
    41         @${CC} ${AM_CFLAGS} ${CFLAGS} ${ccflags} @CFA_FLAGS@ -nodebug -lrt -quiet -DN=50000000 csv-data.c
    42         @./a.out
    43         @rm -f ./a.out
    44 
    45 ## =========================================================================================================
    46 ctxswitch$(EXEEXT): \
    47         ctxswitch-pthread.run           \
    48         ctxswitch-cfa_coroutine.run     \
    49         ctxswitch-cfa_thread.run        \
    50         ctxswitch-upp_coroutine.run     \
    51         ctxswitch-upp_thread.run
    52 
    53 ctxswitch-cfa_coroutine$(EXEEXT):
    54         ${CC}        ctxswitch/cfa_cor.c   -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    55 
    56 ctxswitch-cfa_thread$(EXEEXT):
    57         ${CC}        ctxswitch/cfa_thrd.c  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    58 
    59 ctxswitch-upp_coroutine$(EXEEXT):
    60         u++          ctxswitch/upp_cor.cc  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    61 
    62 ctxswitch-upp_thread$(EXEEXT):
    63         u++          ctxswitch/upp_thrd.cc -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    64 
    65 ctxswitch-pthread$(EXEEXT):
    66         @BACKEND_CC@ ctxswitch/pthreads.c  -DBENCH_N=50000000  -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    67 
    68 ## =========================================================================================================
    69 mutex$(EXEEXT) :\
    70         mutex-function.run      \
    71         mutex-pthread_lock.run  \
    72         mutex-upp.run           \
    73         mutex-cfa1.run          \
    74         mutex-cfa2.run          \
    75         mutex-cfa4.run
    76 
    77 mutex-function$(EXEEXT):
    78         @BACKEND_CC@ mutex/function.c    -DBENCH_N=500000000   -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    79 
    80 mutex-pthread_lock$(EXEEXT):
    81         @BACKEND_CC@ mutex/pthreads.c    -DBENCH_N=50000000    -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    82 
    83 mutex-upp$(EXEEXT):
    84         u++          mutex/upp.cc        -DBENCH_N=50000000    -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    85 
    86 mutex-cfa1$(EXEEXT):
    87         ${CC}        mutex/cfa1.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    88 
    89 mutex-cfa2$(EXEEXT):
    90         ${CC}        mutex/cfa2.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    91 
    92 mutex-cfa4$(EXEEXT):
    93         ${CC}        mutex/cfa4.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    94 
    95 ## =========================================================================================================
    96 signal$(EXEEXT) :\
    97         signal-upp.run          \
    98         signal-cfa1.run         \
    99         signal-cfa2.run         \
    100         signal-cfa4.run
    101 
    102 signal-upp$(EXEEXT):
    103         u++          schedint/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    104 
    105 signal-cfa1$(EXEEXT):
    106         ${CC}        schedint/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    107 
    108 signal-cfa2$(EXEEXT):
    109         ${CC}        schedint/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    110 
    111 signal-cfa4$(EXEEXT):
    112         ${CC}        schedint/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    113 
    114 ## =========================================================================================================
    115 waitfor$(EXEEXT) :\
    116         waitfor-upp.run         \
    117         waitfor-cfa1.run                \
    118         waitfor-cfa2.run                \
    119         waitfor-cfa4.run
    120 
    121 waitfor-upp$(EXEEXT):
    122         u++          schedext/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    123 
    124 waitfor-cfa1$(EXEEXT):
    125         ${CC}        schedext/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    126 
    127 waitfor-cfa2$(EXEEXT):
    128         ${CC}        schedext/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    129 
    130 waitfor-cfa4$(EXEEXT):
    131         ${CC}        schedext/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    132 
    133 ## =========================================================================================================
    134 creation$(EXEEXT) :\
    135         creation-pthread.run            \
    136         creation-cfa_coroutine.run      \
    137         creation-cfa_thread.run         \
    138         creation-upp_coroutine.run      \
    139         creation-upp_thread.run
    140 
    141 creation-cfa_coroutine$(EXEEXT):
    142         ${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    143 
    144 creation-cfa_thread$(EXEEXT):
    145         ${CC}        creation/cfa_thrd.c  -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    146 
    147 creation-upp_coroutine$(EXEEXT):
    148         u++          creation/upp_cor.cc  -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    149 
    150 creation-upp_thread$(EXEEXT):
    151         u++          creation/upp_thrd.cc -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    152 
    153 creation-pthread$(EXEEXT):
    154         @BACKEND_CC@ creation/pthreads.c  -DBENCH_N=250000     -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    155 
    156 ## =========================================================================================================
    15733
    15834%.run : %$(EXEEXT) ${REPEAT}
     
    16541        @rm -f a.out .result.log
    16642
     43%.runquiet :
     44        @+make $(basename $@)
     45        @./a.out
     46        @rm -f a.out
     47
     48%.make :
     49        @printf "${PRINT_FORMAT}" $(basename $(subst compile-,,$@))
     50        @+/usr/bin/time -f ${TIME_FORMAT} make $(basename $@) 2>&1
     51
    16752${REPEAT} :
    16853        @+make -C ${TOOLSDIR} repeat
     54
     55## =========================================================================================================
     56
     57jenkins$(EXEEXT):
     58        @echo "{"
     59        @echo -e '\t"githash": "'${githash}'",'
     60        @echo -e '\t"arch": "'   ${arch}   '",'
     61        @echo -e '\t"compile": {'
     62        @+make compile TIME_FORMAT='%e,' PRINT_FORMAT='\t\t\"%s\" :'
     63        @echo -e '\t\t"dummy" : {}'
     64        @echo -e '\t},'
     65        @echo -e '\t"ctxswitch": {'
     66        @echo -en '\t\t"coroutine":'
     67        @+make ctxswitch-cfa_coroutine.runquiet
     68        @echo -en '\t\t,"thread":'
     69        @+make ctxswitch-cfa_thread.runquiet
     70        @echo -e '\t},'
     71        @echo -e '\t"mutex": ['
     72        @echo -en '\t\t'
     73        @+make mutex-cfa1.runquiet
     74        @echo -en '\t\t,'
     75        @+make mutex-cfa2.runquiet
     76        @echo -e '\t],'
     77        @echo -e '\t"scheduling": ['
     78        @echo -en '\t\t'
     79        @+make signal-cfa1.runquiet
     80        @echo -en '\t\t,'
     81        @+make signal-cfa2.runquiet
     82        @echo -en '\t\t,'
     83        @+make waitfor-cfa1.runquiet
     84        @echo -en '\t\t,'
     85        @+make waitfor-cfa2.runquiet
     86        @echo -e '\n\t],'
     87        @echo -e '\t"epoch": ' $(shell date +%s)
     88        @echo "}"
     89
     90## =========================================================================================================
     91ctxswitch$(EXEEXT): \
     92        ctxswitch-pthread.run           \
     93        ctxswitch-cfa_coroutine.run     \
     94        ctxswitch-cfa_thread.run        \
     95        ctxswitch-upp_coroutine.run     \
     96        ctxswitch-upp_thread.run
     97
     98ctxswitch-cfa_coroutine$(EXEEXT):
     99        @${CC}        ctxswitch/cfa_cor.c   -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     100
     101ctxswitch-cfa_thread$(EXEEXT):
     102        @${CC}        ctxswitch/cfa_thrd.c  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     103
     104ctxswitch-upp_coroutine$(EXEEXT):
     105        @u++          ctxswitch/upp_cor.cc  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     106
     107ctxswitch-upp_thread$(EXEEXT):
     108        @u++          ctxswitch/upp_thrd.cc -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     109
     110ctxswitch-pthread$(EXEEXT):
     111        @@BACKEND_CC@ ctxswitch/pthreads.c  -DBENCH_N=50000000  -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     112
     113## =========================================================================================================
     114mutex$(EXEEXT) :\
     115        mutex-function.run      \
     116        mutex-pthread_lock.run  \
     117        mutex-upp.run           \
     118        mutex-cfa1.run          \
     119        mutex-cfa2.run          \
     120        mutex-cfa4.run
     121
     122mutex-function$(EXEEXT):
     123        @@BACKEND_CC@ mutex/function.c    -DBENCH_N=500000000   -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     124
     125mutex-pthread_lock$(EXEEXT):
     126        @@BACKEND_CC@ mutex/pthreads.c    -DBENCH_N=50000000    -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     127
     128mutex-upp$(EXEEXT):
     129        @u++          mutex/upp.cc        -DBENCH_N=50000000    -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     130
     131mutex-cfa1$(EXEEXT):
     132        @${CC}        mutex/cfa1.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     133
     134mutex-cfa2$(EXEEXT):
     135        @${CC}        mutex/cfa2.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     136
     137mutex-cfa4$(EXEEXT):
     138        @${CC}        mutex/cfa4.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     139
     140## =========================================================================================================
     141signal$(EXEEXT) :\
     142        signal-upp.run          \
     143        signal-cfa1.run         \
     144        signal-cfa2.run         \
     145        signal-cfa4.run
     146
     147signal-upp$(EXEEXT):
     148        @u++          schedint/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     149
     150signal-cfa1$(EXEEXT):
     151        @${CC}        schedint/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     152
     153signal-cfa2$(EXEEXT):
     154        @${CC}        schedint/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     155
     156signal-cfa4$(EXEEXT):
     157        @${CC}        schedint/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     158
     159## =========================================================================================================
     160waitfor$(EXEEXT) :\
     161        waitfor-upp.run         \
     162        waitfor-cfa1.run                \
     163        waitfor-cfa2.run                \
     164        waitfor-cfa4.run
     165
     166waitfor-upp$(EXEEXT):
     167        @u++          schedext/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     168
     169waitfor-cfa1$(EXEEXT):
     170        @${CC}        schedext/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     171
     172waitfor-cfa2$(EXEEXT):
     173        @${CC}        schedext/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     174
     175waitfor-cfa4$(EXEEXT):
     176        @${CC}        schedext/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     177
     178## =========================================================================================================
     179creation$(EXEEXT) :\
     180        creation-pthread.run                    \
     181        creation-cfa_coroutine.run              \
     182        creation-cfa_coroutine_eager.run        \
     183        creation-cfa_thread.run                 \
     184        creation-upp_coroutine.run              \
     185        creation-upp_thread.run
     186
     187creation-cfa_coroutine$(EXEEXT):
     188        @${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     189
     190creation-cfa_coroutine_eager$(EXEEXT):
     191        @${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags} -DEAGER
     192
     193creation-cfa_thread$(EXEEXT):
     194        @${CC}        creation/cfa_thrd.c  -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     195
     196creation-upp_coroutine$(EXEEXT):
     197        @u++          creation/upp_cor.cc  -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     198
     199creation-upp_thread$(EXEEXT):
     200        @u++          creation/upp_thrd.cc -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     201
     202creation-pthread$(EXEEXT):
     203        @@BACKEND_CC@ creation/pthreads.c  -DBENCH_N=250000     -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     204
     205## =========================================================================================================
     206
     207compile$(EXEEXT) :\
     208        compile-array.make      \
     209        compile-attributes.make \
     210        compile-empty.make      \
     211        compile-expression.make \
     212        compile-io.make         \
     213        compile-monitor.make    \
     214        compile-operators.make  \
     215        compile-typeof.make
     216
     217
     218compile-array$(EXEEXT):
     219        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/array.c                @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     220
     221compile-attributes$(EXEEXT):
     222        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/attributes.c   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     223
     224compile-empty$(EXEEXT):
     225        @${CC} -nodebug -quiet -fsyntax-only -w compile/empty.c         @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     226
     227compile-expression$(EXEEXT):
     228        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/expression.c   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     229
     230compile-io$(EXEEXT):
     231        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/io.c                   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     232
     233compile-monitor$(EXEEXT):
     234        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/monitor.c              @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     235
     236compile-operators$(EXEEXT):
     237        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/operators.c    @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     238
     239compile-thread$(EXEEXT):
     240        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/thread.c               @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     241
     242compile-typeof$(EXEEXT):
     243        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/typeof.c               @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     244
  • src/benchmark/Makefile.in

    r9d06142 rc0d00b6  
    124124  esac
    125125am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP)
    126 am__DIST_COMMON = $(srcdir)/Makefile.in
     126am__DIST_COMMON = $(srcdir)/Makefile.in compile
    127127DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
    128128ACLOCAL = @ACLOCAL@
     
    253253STATS = ${TOOLSDIR}stat.py
    254254repeats = 30
     255TIME_FORMAT = "%E"
     256PRINT_FORMAT = %20s: #Comments needed for spacing
    255257all: all-am
    256258
     
    446448all : ctxswitch$(EXEEXT) mutex$(EXEEXT) signal$(EXEEXT) waitfor$(EXEEXT) creation$(EXEEXT)
    447449
    448 bench$(EXEEXT) :
    449         @for ccflags in "-debug" "-nodebug"; do \
    450                 echo ${CC} ${AM_CFLAGS} ${CFLAGS} ${ccflags} @CFA_FLAGS@ -lrt bench.c;\
    451                 ${CC} ${AM_CFLAGS} ${CFLAGS} $${ccflags} -lrt bench.c;\
    452                 ./a.out ; \
    453         done ; \
    454         rm -f ./a.out ;
    455 
    456 csv-data$(EXEEXT):
    457         @${CC} ${AM_CFLAGS} ${CFLAGS} ${ccflags} @CFA_FLAGS@ -nodebug -lrt -quiet -DN=50000000 csv-data.c
    458         @./a.out
    459         @rm -f ./a.out
    460 
    461 ctxswitch$(EXEEXT): \
    462         ctxswitch-pthread.run           \
    463         ctxswitch-cfa_coroutine.run     \
    464         ctxswitch-cfa_thread.run        \
    465         ctxswitch-upp_coroutine.run     \
    466         ctxswitch-upp_thread.run
    467 
    468 ctxswitch-cfa_coroutine$(EXEEXT):
    469         ${CC}        ctxswitch/cfa_cor.c   -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    470 
    471 ctxswitch-cfa_thread$(EXEEXT):
    472         ${CC}        ctxswitch/cfa_thrd.c  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    473 
    474 ctxswitch-upp_coroutine$(EXEEXT):
    475         u++          ctxswitch/upp_cor.cc  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    476 
    477 ctxswitch-upp_thread$(EXEEXT):
    478         u++          ctxswitch/upp_thrd.cc -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    479 
    480 ctxswitch-pthread$(EXEEXT):
    481         @BACKEND_CC@ ctxswitch/pthreads.c  -DBENCH_N=50000000  -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    482 
    483 mutex$(EXEEXT) :\
    484         mutex-function.run      \
    485         mutex-pthread_lock.run  \
    486         mutex-upp.run           \
    487         mutex-cfa1.run          \
    488         mutex-cfa2.run          \
    489         mutex-cfa4.run
    490 
    491 mutex-function$(EXEEXT):
    492         @BACKEND_CC@ mutex/function.c    -DBENCH_N=500000000   -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    493 
    494 mutex-pthread_lock$(EXEEXT):
    495         @BACKEND_CC@ mutex/pthreads.c    -DBENCH_N=50000000    -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    496 
    497 mutex-upp$(EXEEXT):
    498         u++          mutex/upp.cc        -DBENCH_N=50000000    -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    499 
    500 mutex-cfa1$(EXEEXT):
    501         ${CC}        mutex/cfa1.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    502 
    503 mutex-cfa2$(EXEEXT):
    504         ${CC}        mutex/cfa2.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    505 
    506 mutex-cfa4$(EXEEXT):
    507         ${CC}        mutex/cfa4.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    508 
    509 signal$(EXEEXT) :\
    510         signal-upp.run          \
    511         signal-cfa1.run         \
    512         signal-cfa2.run         \
    513         signal-cfa4.run
    514 
    515 signal-upp$(EXEEXT):
    516         u++          schedint/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    517 
    518 signal-cfa1$(EXEEXT):
    519         ${CC}        schedint/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    520 
    521 signal-cfa2$(EXEEXT):
    522         ${CC}        schedint/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    523 
    524 signal-cfa4$(EXEEXT):
    525         ${CC}        schedint/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    526 
    527 waitfor$(EXEEXT) :\
    528         waitfor-upp.run         \
    529         waitfor-cfa1.run                \
    530         waitfor-cfa2.run                \
    531         waitfor-cfa4.run
    532 
    533 waitfor-upp$(EXEEXT):
    534         u++          schedext/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    535 
    536 waitfor-cfa1$(EXEEXT):
    537         ${CC}        schedext/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    538 
    539 waitfor-cfa2$(EXEEXT):
    540         ${CC}        schedext/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    541 
    542 waitfor-cfa4$(EXEEXT):
    543         ${CC}        schedext/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    544 
    545 creation$(EXEEXT) :\
    546         creation-pthread.run            \
    547         creation-cfa_coroutine.run      \
    548         creation-cfa_thread.run         \
    549         creation-upp_coroutine.run      \
    550         creation-upp_thread.run
    551 
    552 creation-cfa_coroutine$(EXEEXT):
    553         ${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    554 
    555 creation-cfa_thread$(EXEEXT):
    556         ${CC}        creation/cfa_thrd.c  -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    557 
    558 creation-upp_coroutine$(EXEEXT):
    559         u++          creation/upp_cor.cc  -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    560 
    561 creation-upp_thread$(EXEEXT):
    562         u++          creation/upp_thrd.cc -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    563 
    564 creation-pthread$(EXEEXT):
    565         @BACKEND_CC@ creation/pthreads.c  -DBENCH_N=250000     -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    566 
    567450%.run : %$(EXEEXT) ${REPEAT}
    568451        @rm -f .result.log
     
    574457        @rm -f a.out .result.log
    575458
     459%.runquiet :
     460        @+make $(basename $@)
     461        @./a.out
     462        @rm -f a.out
     463
     464%.make :
     465        @printf "${PRINT_FORMAT}" $(basename $(subst compile-,,$@))
     466        @+/usr/bin/time -f ${TIME_FORMAT} make $(basename $@) 2>&1
     467
    576468${REPEAT} :
    577469        @+make -C ${TOOLSDIR} repeat
     470
     471jenkins$(EXEEXT):
     472        @echo "{"
     473        @echo -e '\t"githash": "'${githash}'",'
     474        @echo -e '\t"arch": "'   ${arch}   '",'
     475        @echo -e '\t"compile": {'
     476        @+make compile TIME_FORMAT='%e,' PRINT_FORMAT='\t\t\"%s\" :'
     477        @echo -e '\t\t"dummy" : {}'
     478        @echo -e '\t},'
     479        @echo -e '\t"ctxswitch": {'
     480        @echo -en '\t\t"coroutine":'
     481        @+make ctxswitch-cfa_coroutine.runquiet
     482        @echo -en '\t\t,"thread":'
     483        @+make ctxswitch-cfa_thread.runquiet
     484        @echo -e '\t},'
     485        @echo -e '\t"mutex": ['
     486        @echo -en '\t\t'
     487        @+make mutex-cfa1.runquiet
     488        @echo -en '\t\t,'
     489        @+make mutex-cfa2.runquiet
     490        @echo -e '\t],'
     491        @echo -e '\t"scheduling": ['
     492        @echo -en '\t\t'
     493        @+make signal-cfa1.runquiet
     494        @echo -en '\t\t,'
     495        @+make signal-cfa2.runquiet
     496        @echo -en '\t\t,'
     497        @+make waitfor-cfa1.runquiet
     498        @echo -en '\t\t,'
     499        @+make waitfor-cfa2.runquiet
     500        @echo -e '\n\t],'
     501        @echo -e '\t"epoch": ' $(shell date +%s)
     502        @echo "}"
     503
     504ctxswitch$(EXEEXT): \
     505        ctxswitch-pthread.run           \
     506        ctxswitch-cfa_coroutine.run     \
     507        ctxswitch-cfa_thread.run        \
     508        ctxswitch-upp_coroutine.run     \
     509        ctxswitch-upp_thread.run
     510
     511ctxswitch-cfa_coroutine$(EXEEXT):
     512        @${CC}        ctxswitch/cfa_cor.c   -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     513
     514ctxswitch-cfa_thread$(EXEEXT):
     515        @${CC}        ctxswitch/cfa_thrd.c  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     516
     517ctxswitch-upp_coroutine$(EXEEXT):
     518        @u++          ctxswitch/upp_cor.cc  -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     519
     520ctxswitch-upp_thread$(EXEEXT):
     521        @u++          ctxswitch/upp_thrd.cc -DBENCH_N=50000000  -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     522
     523ctxswitch-pthread$(EXEEXT):
     524        @@BACKEND_CC@ ctxswitch/pthreads.c  -DBENCH_N=50000000  -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     525
     526mutex$(EXEEXT) :\
     527        mutex-function.run      \
     528        mutex-pthread_lock.run  \
     529        mutex-upp.run           \
     530        mutex-cfa1.run          \
     531        mutex-cfa2.run          \
     532        mutex-cfa4.run
     533
     534mutex-function$(EXEEXT):
     535        @@BACKEND_CC@ mutex/function.c    -DBENCH_N=500000000   -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     536
     537mutex-pthread_lock$(EXEEXT):
     538        @@BACKEND_CC@ mutex/pthreads.c    -DBENCH_N=50000000    -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     539
     540mutex-upp$(EXEEXT):
     541        @u++          mutex/upp.cc        -DBENCH_N=50000000    -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     542
     543mutex-cfa1$(EXEEXT):
     544        @${CC}        mutex/cfa1.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     545
     546mutex-cfa2$(EXEEXT):
     547        @${CC}        mutex/cfa2.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     548
     549mutex-cfa4$(EXEEXT):
     550        @${CC}        mutex/cfa4.c        -DBENCH_N=5000000     -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     551
     552signal$(EXEEXT) :\
     553        signal-upp.run          \
     554        signal-cfa1.run         \
     555        signal-cfa2.run         \
     556        signal-cfa4.run
     557
     558signal-upp$(EXEEXT):
     559        @u++          schedint/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     560
     561signal-cfa1$(EXEEXT):
     562        @${CC}        schedint/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     563
     564signal-cfa2$(EXEEXT):
     565        @${CC}        schedint/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     566
     567signal-cfa4$(EXEEXT):
     568        @${CC}        schedint/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     569
     570waitfor$(EXEEXT) :\
     571        waitfor-upp.run         \
     572        waitfor-cfa1.run                \
     573        waitfor-cfa2.run                \
     574        waitfor-cfa4.run
     575
     576waitfor-upp$(EXEEXT):
     577        @u++          schedext/upp.cc     -DBENCH_N=5000000     -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     578
     579waitfor-cfa1$(EXEEXT):
     580        @${CC}        schedext/cfa1.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     581
     582waitfor-cfa2$(EXEEXT):
     583        @${CC}        schedext/cfa2.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     584
     585waitfor-cfa4$(EXEEXT):
     586        @${CC}        schedext/cfa4.c     -DBENCH_N=500000      -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     587
     588creation$(EXEEXT) :\
     589        creation-pthread.run                    \
     590        creation-cfa_coroutine.run              \
     591        creation-cfa_coroutine_eager.run        \
     592        creation-cfa_thread.run                 \
     593        creation-upp_coroutine.run              \
     594        creation-upp_thread.run
     595
     596creation-cfa_coroutine$(EXEEXT):
     597        @${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     598
     599creation-cfa_coroutine_eager$(EXEEXT):
     600        @${CC}        creation/cfa_cor.c   -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags} -DEAGER
     601
     602creation-cfa_thread$(EXEEXT):
     603        @${CC}        creation/cfa_thrd.c  -DBENCH_N=10000000   -I. -nodebug -lrt -quiet @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     604
     605creation-upp_coroutine$(EXEEXT):
     606        @u++          creation/upp_cor.cc  -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     607
     608creation-upp_thread$(EXEEXT):
     609        @u++          creation/upp_thrd.cc -DBENCH_N=50000000   -I. -nodebug -lrt -quiet             ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     610
     611creation-pthread$(EXEEXT):
     612        @@BACKEND_CC@ creation/pthreads.c  -DBENCH_N=250000     -I. -lrt -pthread                    ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     613
     614compile$(EXEEXT) :\
     615        compile-array.make      \
     616        compile-attributes.make \
     617        compile-empty.make      \
     618        compile-expression.make \
     619        compile-io.make         \
     620        compile-monitor.make    \
     621        compile-operators.make  \
     622        compile-typeof.make
     623
     624compile-array$(EXEEXT):
     625        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/array.c                @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     626
     627compile-attributes$(EXEEXT):
     628        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/attributes.c   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     629
     630compile-empty$(EXEEXT):
     631        @${CC} -nodebug -quiet -fsyntax-only -w compile/empty.c         @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     632
     633compile-expression$(EXEEXT):
     634        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/expression.c   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     635
     636compile-io$(EXEEXT):
     637        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/io.c                   @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     638
     639compile-monitor$(EXEEXT):
     640        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/monitor.c              @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     641
     642compile-operators$(EXEEXT):
     643        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/operators.c    @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     644
     645compile-thread$(EXEEXT):
     646        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/thread.c               @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
     647
     648compile-typeof$(EXEEXT):
     649        @${CC} -nodebug -quiet -fsyntax-only -w ../tests/typeof.c               @CFA_FLAGS@ ${AM_CFLAGS} ${CFLAGS} ${ccflags}
    578650
    579651# Tell versions [3.59,3.63) of GNU make to not export all variables.
  • src/benchmark/creation/cfa_cor.c

    r9d06142 rc0d00b6  
    55
    66coroutine MyCoroutine {};
    7 void ?{} (MyCoroutine & this) { prime(this); }
     7void ?{} (MyCoroutine & this) {
     8#ifdef EAGER
     9        prime(this);
     10#endif
     11}
    812void main(MyCoroutine & this) {}
    913
  • src/libcfa/Makefile.am

    r9d06142 rc0d00b6  
    9595
    9696cfa_includedir = $(CFA_INCDIR)
    97 nobase_cfa_include_HEADERS = ${headers} ${stdhdr} math gmp concurrency/invoke.h
     97nobase_cfa_include_HEADERS =    \
     98        ${headers}                      \
     99        ${stdhdr}                       \
     100        math                            \
     101        gmp                             \
     102        bits/defs.h             \
     103        bits/locks.h            \
     104        concurrency/invoke.h    \
     105        libhdr.h                        \
     106        libhdr/libalign.h       \
     107        libhdr/libdebug.h       \
     108        libhdr/libtools.h
    98109
    99110CLEANFILES = libcfa-prelude.c
  • src/libcfa/Makefile.in

    r9d06142 rc0d00b6  
    264264        containers/result containers/vector concurrency/coroutine \
    265265        concurrency/thread concurrency/kernel concurrency/monitor \
    266         ${shell echo stdhdr/*} math gmp concurrency/invoke.h
     266        ${shell echo stdhdr/*} math gmp bits/defs.h bits/locks.h \
     267        concurrency/invoke.h libhdr.h libhdr/libalign.h \
     268        libhdr/libdebug.h libhdr/libtools.h
    267269HEADERS = $(nobase_cfa_include_HEADERS)
    268270am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP)
     
    430432stdhdr = ${shell echo stdhdr/*}
    431433cfa_includedir = $(CFA_INCDIR)
    432 nobase_cfa_include_HEADERS = ${headers} ${stdhdr} math gmp concurrency/invoke.h
     434nobase_cfa_include_HEADERS = \
     435        ${headers}                      \
     436        ${stdhdr}                       \
     437        math                            \
     438        gmp                             \
     439        bits/defs.h             \
     440        bits/locks.h            \
     441        concurrency/invoke.h    \
     442        libhdr.h                        \
     443        libhdr/libalign.h       \
     444        libhdr/libdebug.h       \
     445        libhdr/libtools.h
     446
    433447CLEANFILES = libcfa-prelude.c
    434448all: all-am
  • src/libcfa/concurrency/alarm.c

    r9d06142 rc0d00b6  
    186186
    187187        disable_interrupts();
    188         lock( &event_kernel->lock DEBUG_CTX2 );
     188        lock( event_kernel->lock DEBUG_CTX2 );
    189189        {
    190190                verify( validate( alarms ) );
     
    196196                }
    197197        }
    198         unlock( &event_kernel->lock );
     198        unlock( event_kernel->lock );
    199199        this->set = true;
    200200        enable_interrupts( DEBUG_CTX );
     
    203203void unregister_self( alarm_node_t * this ) {
    204204        disable_interrupts();
    205         lock( &event_kernel->lock DEBUG_CTX2 );
     205        lock( event_kernel->lock DEBUG_CTX2 );
    206206        {
    207207                verify( validate( &event_kernel->alarms ) );
    208208                remove( &event_kernel->alarms, this );
    209209        }
    210         unlock( &event_kernel->lock );
     210        unlock( event_kernel->lock );
    211211        enable_interrupts( DEBUG_CTX );
    212212        this->set = false;
  • src/libcfa/concurrency/invoke.h

    r9d06142 rc0d00b6  
    1414//
    1515
    16 #include <stdbool.h>
    17 #include <stdint.h>
     16#include "bits/defs.h"
     17#include "bits/locks.h"
    1818
    1919#ifdef __CFORALL__
     
    2525#define _INVOKE_H_
    2626
    27         #define unlikely(x)    __builtin_expect(!!(x), 0)
    28         #define thread_local _Thread_local
    29 
    3027        typedef void (*fptr_t)();
    3128        typedef int_fast16_t __lock_size_t;
    32 
    33         struct spinlock {
    34                 volatile int lock;
    35                 #ifdef __CFA_DEBUG__
    36                         const char * prev_name;
    37                         void* prev_thrd;
    38                 #endif
    39         };
    4029
    4130        struct __thread_queue_t {
     
    5847                void push( struct __condition_stack_t &, struct __condition_criterion_t * );
    5948                struct __condition_criterion_t * pop( struct __condition_stack_t & );
    60 
    61                 void  ?{}(spinlock & this);
    62                 void ^?{}(spinlock & this);
    6349        }
    6450        #endif
     
    122108        struct monitor_desc {
    123109                // spinlock to protect internal data
    124                 struct spinlock lock;
     110                struct __spinlock_t lock;
    125111
    126112                // current owner of the monitor
  • src/libcfa/concurrency/kernel

    r9d06142 rc0d00b6  
    2626//-----------------------------------------------------------------------------
    2727// Locks
    28 // Lock the spinlock, spin if already acquired