Changeset 27fefeb6


Ignore:
Timestamp:
Aug 10, 2016, 11:31:24 PM (6 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, resolv-new, with_gc
Children:
82da9b8
Parents:
321f55d (diff), 72e2ea0 (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' of plg2:software/cfa/cfa-cc

Files:
4 added
11 edited

Legend:

Unmodified
Added
Removed
  • Jenkins/FullBuild

    r321f55d r27fefeb6  
    9999        //attach the build log to the email
    100100        catch (Exception caughtError) {
     101                echo('error caught')
     102
    101103                //rethrow error later
    102104                err = caughtError
    103105
    104106                //Store the result of the build log
    105                 currentBuild.result = "${status_prefix} FAILURE".trim()
     107                currentBuild.result = 'FAILURE'
    106108
    107109                //Send email to notify the failure
    108                 promote_email(currentBuild.result)
     110                promote_failure_email()
    109111        }
    110112
     
    121123
    122124//Email notification on a full build failure
    123 def promote_email(String status) {
     125def promote_failure_email() {
     126        echo('notifying users')
     127
    124128        //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line
    125129        //Configurations for email format
     
    134138- Status --------------------------------------------------------------
    135139
    136 PROMOTE FAILURE - ${status}
     140PROMOTE FAILURE
    137141"""
    138142
  • doc/aaron_comp_II/comp_II.tex

    r321f55d r27fefeb6  
    3737\setlength{\headsep}{0.25in}
    3838
     39\usepackage{caption}
     40\usepackage{subcaption}
     41
    3942%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    4043
     
    6164
    6265%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     66
     67\newcommand{\bigO}[1]{O\!\left( #1 \right)}
    6368
    6469\begin{document}
     
    116121The ©identity© function above can be applied to any complete object type (or ``©otype©'').
    117122The type variable ©T© is transformed into a set of additional implicit parameters to ©identity© which encode sufficient information about ©T© to create and return a variable of that type.
    118 The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor and destructor.
     123The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor and destructor.
     124Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC virtual function calls.
     125Determining if packaging all polymorphic arguments to a function into a virtual function table would reduce the runtime overhead of polymorphic calls is an open research question.
    119126
    120127Since bare polymorphic types do not provide a great range of available operations, \CFA also provides a \emph{type assertion} mechanism to provide further information about a type:
     
    129136double magic = four_times(10.5); // T is bound to double, uses (1) to satisfy type assertion
    130137\end{lstlisting}
    131 These type assertions may be either variable or function declarations which depend on a polymorphic type variable.
    132 ©four_times© can only be called with an argument for which there exists a function named ©twice© that can take that argument and return another value of the same type; a pointer to the appropriate ©twice© function will be passed as an additional implicit parameter to the call to ©four_times©.
     138These type assertions may be either variable or function declarations that depend on a polymorphic type variable.
     139©four_times© can only be called with an argument for which there exists a function named ©twice© that can take that argument and return another value of the same type; a pointer to the appropriate ©twice© function is passed as an additional implicit parameter to the call to ©four_times©.
    133140
    134141Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
    135 For instance, ©twice© could have been defined as below, using the \CFA syntax for operator overloading:
    136 \begin{lstlisting}
    137 forall(otype S | { S ?+?(S, S); })
     142For instance, ©twice© could have been defined using the \CFA syntax for operator overloading as:
     143\begin{lstlisting}
     144forall(otype S | { ®S ?+?(S, S);® })
    138145S twice(S x) { return x + x; }  // (2)
    139146\end{lstlisting}
    140 This version of ©twice© will work for any type ©S© that has an addition operator defined for it, and it could have been used to satisfy the type assertion on ©four_times©.
     147This version of ©twice© works for any type ©S© that has an addition operator defined for it, and it could have been used to satisfy the type assertion on ©four_times©.
    141148The compiler accomplishes this by creating a wrapper function calling ©twice // (2)© with ©S© bound to ©double©, then providing this wrapper function to ©four_times©\footnote{©twice // (2)© could also have had a type parameter named ©T©; \CFA specifies renaming of the type parameters, which would avoid the name conflict with the type variable ©T© of ©four_times©.}.
    142149
    143150Finding appropriate functions to satisfy type assertions is essentially a recursive case of expression resolution, as it takes a name (that of the type assertion) and attempts to match it to a suitable declaration in the current scope.
    144 If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function will be examined as a candidate for its own type assertion unboundedly repeatedly.
    145 To avoid infinite loops, the current CFA compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \CC compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by CFA.
    146 One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion will not produce a well-typed expression.
     151If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function is examined as a candidate for its own type assertion unboundedly repeatedly.
     152To avoid infinite loops, the current CFA compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \CC compilers for template expansion; this restriction means that there are some semantically well-typed expressions that cannot be resolved by CFA.
     153One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion does not produce a well-typed expression.
    147154
    148155\subsubsection{Traits}
    149156\CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below:
    150157\begin{lstlisting}
    151 trait has_magnitude(otype T) {
     158®trait has_magnitude(otype T)® {
    152159    bool ?<?(T, T);        // comparison operator for T
    153160    T -?(T);               // negation operator for T
     
    168175\end{lstlisting}
    169176
    170 Semantically, a trait is merely a named list of type assertions, but they can be used in many of the same situations where an interface in Java or an abstract base class in \CC would be used.
     177Semantically, traits are simply a named lists of type assertions, but they may be used for many of the same purposes that interfaces in Java or abstract base classes in \CC are used for.
    171178Unlike Java interfaces or \CC base classes, \CFA types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to interface implementation in Go, as opposed to the nominal inheritance model of Java and \CC.
    172 % TODO talk about modelling of nominal inheritance with structural inheritance, possibility of investigating some resolver algorithms that require nominal
     179Nominal inheritance can be simulated with traits using marker variables or functions:
     180\begin{lstlisting}
     181trait nominal(otype T) {
     182    ®T is_nominal;®
     183};
     184
     185int is_nominal;  // int now satisfies the nominal trait
     186{
     187    char is_nominal; // char satisfies the nominal trait
     188}
     189// char no longer satisfies the nominal trait here 
     190\end{lstlisting}
     191
     192Traits, however, are significantly more powerful than nominal-inheritance interfaces; firstly, due to the scoping rules of the declarations which satisfy a trait's type assertions, a type may not satisfy a trait everywhere that the type is declared, as with ©char© and the ©nominal© trait above.
     193Secondly, traits may be used to declare a relationship between multiple types, a property which may be difficult or impossible to represent in nominal-inheritance type systems:
     194\begin{lstlisting}
     195trait pointer_like(®otype Ptr, otype El®) {
     196    lvalue El *?(Ptr); // Ptr can be dereferenced into a modifiable value of type El
     197}
     198
     199struct list {
     200    int value;
     201    list *next;  // may omit "struct" on type names
     202};
     203
     204typedef list* list_iterator;
     205
     206lvalue int *?( list_iterator it ) {
     207    return it->value;
     208}
     209\end{lstlisting}
     210
     211In the example above, ©(list_iterator, int)© satisfies ©pointer_like© by the given function, and ©(list_iterator, list)© also satisfies ©pointer_like© by the built-in pointer dereference operator.
     212While a nominal-inheritance system with associated types could model one of those two relationships by making ©El© an associated type of ©Ptr© in the ©pointer_like© implementation, few such systems could model both relationships simultaneously.
     213
     214The flexibility of \CFA's implicit trait satisfaction mechanism provides user programmers with a great deal of power, but also blocks some optimization approaches for expression resolution.
     215The ability of types to begin to or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters could lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships.
     216On the other hand, the addition of a nominal inheritance mechanism to \CFA's type system or replacement of \CFA's trait satisfaction system with a more object-oriented inheritance model and investigation of possible expression resolution optimizations for such a system may be an interesting avenue of further research.
    173217
    174218\subsection{Name Overloading}
    175 In C, no more than one function or variable in the same scope may share the same name, and function or variable declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration. 
    176 This makes finding the proper declaration to match to a function application or variable expression a simple matter of symbol table lookup, which can be easily and efficiently implemented.
    177 \CFA, on the other hand, allows overloading of variable and function names, so long as the overloaded declarations do not have the same type, avoiding the multiplication of function names for different types common in the C standard library, as in the following example:
    178 \begin{lstlisting}
    179 int three = 3;
    180 double three = 3.0;
    181 
    182 int thrice(int i) { return i * three; } // uses int three
    183 double thrice(double d) { return d * three; } // uses double three
    184 
    185 // thrice(three); // ERROR: ambiguous
    186 int nine = thrice(three);    // uses int thrice and three, based on return type
    187 double nine = thrice(three); // uses double thrice and three, based on return type
    188 \end{lstlisting}
    189 
    190 The presence of name overloading in \CFA means that simple table lookup is not sufficient to match identifiers to declarations, and a type matching algorithm must be part of expression resolution.
     219In C, no more than one variable or function in the same scope may share the same name\footnote{Technically, C has multiple separated namespaces, one holding ©struct©, ©union©, and ©enum© tags, one holding labels, one holding typedef names, variable, function, and enumerator identifiers, and one for each ©struct© or ©union© type holding the field names.}, and variable or function declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration.
     220This makes finding the proper declaration to match to a variable expression or function application a simple matter of symbol table lookup, which can be easily and efficiently implemented.
     221\CFA, on the other hand, allows overloading of variable and function names, so long as the overloaded declarations do not have the same type, avoiding the multiplication of variable and function names for different types common in the C standard library, as in the following example:
     222\begin{lstlisting}
     223#include <limits.h>
     224
     225int max(int a, int b) { return a < b ? b : a; }  // (1)
     226double max(double a, double b) { return a < b ? b : a; }  // (2)
     227
     228int max = INT_MAX;     // (3)
     229double max = DBL_MAX;  // (4)
     230
     231max(7, -max);   // uses (1) and (3), by matching int type of 7
     232max(max, 3.14); // uses (2) and (4), by matching double type of 3.14
     233
     234max(max, -max);  // ERROR: ambiguous
     235int m = max(max, -max); // uses (1) and (3) twice, by return type
     236\end{lstlisting}
     237
     238The presence of name overloading in \CFA means that simple table lookup is insufficient to match identifiers to declarations, and a type matching algorithm must be part of expression resolution.
    191239
    192240\subsection{Implicit Conversions}
     
    194242C does not have a traditionally-defined inheritance hierarchy of types, but the C standard's rules for the ``usual arithmetic conversions'' define which of the built-in types are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type.
    195243\CFA adds to the usual arithmetic conversions rules for determining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, \eg ©int© to ©double©.
     244
    196245The expression resolution problem, then, is to find the unique minimal-cost interpretation of each expression in the program, where all identifiers must be matched to a declaration and implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression.
    197 Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate.
     246Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate.
     247For instance, in the example in the previous subsection, ©max(max, -max)© cannot be unambiguously resolved, but ©int m = max(max, -max);© has a single minimal-cost resolution.
     248©int m = (int)max((double)max, -(double)max)© is also be a valid interpretation, but is not minimal-cost due to the unsafe cast from the ©double© result of ©max© to ©int© (the two ©double© casts function as type ascriptions selecting ©double max© rather than casts from ©int max© to ©double©, and as such are zero-cost).
    198249
    199250\subsubsection{User-generated Implicit Conversions}
     
    201252Such a conversion system should be simple for user programmers to utilize, and fit naturally with the existing design of implicit conversions in C; ideally it would also be sufficiently powerful to encode C's usual arithmetic conversions itself, so that \CFA only has one set of rules for conversions.
    202253
    203 Ditchfield\cite{Ditchfield:conversions} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions.
     254Ditchfield~\cite{Ditchfield:conversions} has laid out a framework for using polymorphic-conversion-constructor functions to create a directed acyclic graph (DAG) of conversions.
    204255A monomorphic variant of these functions can be used to mark a conversion arc in the DAG as only usable as the final step in a conversion.
    205256With these two types of conversion arcs, separate DAGs can be created for the safe and the unsafe conversions, and conversion cost can be represented as path length through the DAG.
    206 Open research questions on this topic include whether a conversion graph can be generated that represents each allowable conversion in C with a unique minimal-length path, such that the path lengths accurately represent the relative costs of the conversions, whether such a graph representation can be usefully augmented to include user-defined types as well as built-in types, and whether the graph can be efficiently represented and included in the expression resolver.
     257\begin{figure}[h]
     258\centering
     259\includegraphics{conversion_dag}
     260\caption{A portion of the implicit conversion DAG for built-in types.}
     261\end{figure}
     262As can be seen in the example DAG above, there are either safe or unsafe paths between each of the arithmetic types listed; the ``final'' arcs are important both to avoid creating cycles in the signed-unsigned conversions, and to disambiguate potential diamond conversions (\eg, if the ©int© to ©unsigned int© conversion was not marked final there would be two length-two paths from ©int© to ©unsigned long©, and it would be impossible to choose which one; however, since the ©unsigned int© to ©unsigned long© arc can not be traversed after the final ©int© to ©unsigned int© arc, there is a single unambiguous conversion path from ©int© to ©unsigned long©).
     263
     264Open research questions on this topic include:
     265\begin{itemize}
     266\item Can a conversion graph be generated that represents each allowable conversion in C with a unique minimal-length path such that the path lengths accurately represent the relative costs of the conversions?
     267\item Can such a graph representation can be usefully augmented to include user-defined types as well as built-in types?
     268\item Can the graph can be efficiently represented and used in the expression resolver?
     269\end{itemize}
    207270
    208271\subsection{Constructors and Destructors}
    209272Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
    210 Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for struct types these functions each call their equivalents on each field of the struct.
     273Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for ©struct© types these functions each call their equivalents on each field of the ©struct©.
    211274This affects expression resolution because an ©otype© type variable ©T© implicitly adds four type assertions, one for each of these four functions, so assertion resolution is pervasive in \CFA polymorphic functions, even those without any explicit type assertions.
     275The following example shows the implicitly-generated code in green:
     276\begin{lstlisting}
     277struct kv {
     278    int key;
     279    char *value;
     280};
     281
     282¢void ?{}(kv *this) {
     283    ?{}(&this->key);
     284    ?{}(&this->value);
     285}
     286void ?{}(kv *this, kv that) {
     287    ?{}(&this->key, that.key);
     288    ?{}(&this->value, that.value);
     289}
     290kv ?=?(kv *this, kv that) {
     291    ?=?(&this->key, that.key);
     292    ?=?(&this->value, that.value);
     293    return *this;
     294}
     295void ^?{}(kv *this) {
     296    ^?{}(&this->key);
     297    ^?{}(&this->value);
     298
     299
     300forall(otype T ¢| { void ?{}(T*); void ?{}(T*, T); T ?=?(T*, T); void ^?{}(T*); }¢)
     301void foo(T);
     302\end{lstlisting}
    212303
    213304\subsection{Generic Types}
    214305I have already added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
    215 A generic type can be declared by placing a ©forall© specifier on a struct or union declaration, and instantiated using a parenthesized list of types after the type name:
     306A generic type can be declared by placing a ©forall© specifier on a ©struct© or ©union© declaration, and instantiated using a parenthesized list of types after the type name:
    216307\begin{lstlisting}
    217308forall(otype R, otype S) struct pair {
     
    229320The default-generated constructors, destructor and assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
    230321
    231 Aside from giving users the ability to create more parameterized types than just the built-in pointer, array and function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where a polymorphic function can match its own assertions much more common, as follows:
     322Aside from giving users the ability to create more parameterized types than just the built-in pointer, array and function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where the resolver may enter an infinite loop much more common, as in the following code example:
     323\begin{lstlisting}
     324forall(otype T) struct box { T x; };
     325
     326void f(void*); // (1)
     327
     328forall(otype S)
     329void f(box(S)* b) { // (2)
     330        f(®(void*)0®);
     331}
     332\end{lstlisting}
     333
     334The loop in the resolver happens as follows:
    232335\begin{itemize}
    233 \item Given an expression in an untyped context, such as a top-level function call with no assignment of return values, apply a polymorphic implicit conversion to the expression that can produce multiple types (the built-in conversion from ©void*© to any other pointer type is one, but not the only).
    234 \item When attempting to use a generic type with ©otype© parameters (such as ©box© above) for the result type of the expression, the resolver will also need to decide what type to use for the ©otype© parameters on the constructors and related functions, and will have no constraints on what they may be.
    235 \item Attempting to match some yet-to-be-determined specialization of the generic type to this ©otype© parameter will create a recursive case of the default constructor, \etc matching their own type assertions, creating an unboundedly deep nesting of the generic type inside itself.
     336\item Since there is an implicit conversion from ©void*© to any pointer type, the highlighted expression can be interpreted as either a ©void*©, matching ©f // (1)©, or a ©box(S)*© for some type ©S©, matching ©f // (2)©.
     337\item To determine the cost of the ©box(S)© interpretation, a type must be found for ©S© which satisfies the ©otype© implicit type assertions (assignment operator, default and copy constructors, and destructor); one option is ©box(S2)© for some type ©S2©.
     338\item The assignment operator, default and copy constructors, and destructor of ©box(T)© are also polymorphic functions, each of which require the type parameter ©T© to have an assignment operator, default and copy constructors, and destructor. When choosing an interpretation for ©S2©, one option is ©box(S3)©, for some type ©S3©.
     339\item The previous step repeats until stopped, with four times as much work performed at each step.
    236340\end{itemize}
    237 As discussed above, any \CFA expression resolver must handle this possible infinite recursion somehow, but the combination of generic types with other language features makes this particular edge case occur somewhat frequently in user code.
     341This problem can occur in any resolution context where a polymorphic function that can satisfy its own type assertions is required for a possible interpretation of an expression with no constraints on its type, and is thus not limited to combinations of generic types with ©void*© conversions, though constructors for generic types often satisfy their own assertions and a polymorphic conversion such as the ©void*© conversion to a polymorphic variable can create an expression with no constraints on its type.
     342As discussed above, the \CFA expression resolver must handle this possible infinite recursion somehow, and it occurs fairly naturally in code like the above that uses generic types.
    238343
    239344\subsection{Tuple Types}
    240 \CFA adds \emph{tuple types} to C, a facility for referring to multiple values with a single identifier.
    241 A variable may name a tuple, and a function may return one.
     345\CFA adds \emph{tuple types} to C, a syntactic facility for referring to lists of values anonymously or with a single identifier.
     346An identifier may name a tuple, and a function may return one.
    242347Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap© below:
    243348\begin{lstlisting}
     
    248353
    249354x = swap( x ); // destructure [char, char] x into two elements of parameter list
    250 // can't use int x for parameter, not enough arguments to swap
     355// cannot use int x for parameter, not enough arguments to swap
    251356\end{lstlisting}
    252357Tuple destructuring means that the mapping from the position of a subexpression in the argument list to the position of a paramter in the function declaration is not straightforward, as some arguments may be expandable to different numbers of parameters, like ©x© above.
     
    256361Given some type ©T©, a ©T&© (``reference to ©T©'') is essentially an automatically dereferenced pointer; with these semantics most of the C standard's discussions of lvalues can be expressed in terms of references instead, with the benefit of being able to express the difference between the reference and non-reference version of a type in user code.
    257362References preserve C's existing qualifier-dropping lvalue-to-rvalue conversion (\eg a ©const volatile int&© can be implicitly converted to a bare ©int©); the reference proposal also adds a rvalue-to-lvalue conversion to \CFA, implemented by storing the value in a new compiler-generated temporary and passing a reference to the temporary.
    258 These two conversions can chain, producing a qualifier-dropping conversion for references, for instance converting a reference to a ©const int© into a reference to a non-©const int© by copying the originally refered to value into a fresh temporary and taking a reference to this temporary.
     363These two conversions can chain, producing a qualifier-dropping conversion for references, for instance converting a reference to a ©const int© into a reference to a non-©const int© by copying the originally refered to value into a fresh temporary and taking a reference to this temporary, as below:
     364\begin{lstlisting}
     365const int magic = 42;
     366
     367void inc_print( int& x ) { printf("%d\n", ++x); }
     368
     369print_inc( magic ); // legal; implicitly generated code in green below:
     370
     371¢int tmp = magic;¢ // copies to safely strip const-qualifier
     372¢print_inc( tmp );¢ // tmp is incremented, magic is unchanged
     373\end{lstlisting}
    259374These reference conversions may also chain with the other implicit type conversions.
    260375The main implication of this for expression resolution is the multiplication of available implicit conversions, though in a restricted context that may be able to be treated efficiently as a special case.
    261376
    262 \subsection{Literal Types}
    263 Another proposal currently under consideration for the \CFA type-system is assigning special types to the literal values ©0© and ©1©.%, say ©zero_t© and ©one_t©.
    264 Implicit conversions from these types would allow ©0© and ©1© to be considered as values of many different types, depending on context, allowing expression desugarings like ©if ( x ) {}© $\Rightarrow$ ©if ( x != 0 ) {}© to be implemented efficiently and precicely.
    265 This is a generalization of C's existing behaviour of treating ©0© as either an integer zero or a null pointer constant, and treating either of those values as boolean false.
    266 The main implication for expression resolution is that the frequently encountered expressions ©0© and ©1© may have a significant number of valid interpretations.
     377\subsection{Special Literal Types}
     378Another proposal currently under consideration for the \CFA type-system is assigning special types to the literal values ©0© and ©1©.
     379Implicit conversions from these types allow ©0© and ©1© to be considered as values of many different types, depending on context, allowing expression desugarings like ©if ( x ) {}© $\Rightarrow$ ©if ( x != 0 ) {}© to be implemented efficiently and precicely.
     380This approach is a generalization of C's existing behaviour of treating ©0© as either an integer zero or a null pointer constant, and treating either of those values as boolean false.
     381The main implication for expression resolution is that the frequently encountered expressions ©0© and ©1© may have a large number of valid interpretations.
    267382
    268383\subsection{Deleted Function Declarations}
     
    271386int somefn(char) = delete;
    272387\end{lstlisting}
     388This feature is typically used in \CCeleven to make a type non-copyable by deleting its copy constructor and assignment operator, or forbidding some interpretations of a polymorphic function by specifically deleting the forbidden overloads.
    273389To add a similar feature to \CFA would involve including the deleted function declarations in expression resolution along with the normal declarations, but producing a compiler error if the deleted function was the best resolution.
    274390How conflicts should be handled between resolution of an expression to both a deleted and a non-deleted function is a small but open research question.
    275391
    276392\section{Expression Resolution}
    277 The expression resolution problem is essentially to determine an optimal matching between some combination of argument interpretations and the parameter list of some overloaded instance of a function; the argument interpretations are produced by recursive invocations of expression resolution, where the base case is zero-argument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions).
    278 Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $O(p^k)$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $O(i)$ valid interpretations for each subexpression, there will be $O(i)$ candidate functions and $O(i^p)$ possible argument combinations for each expression, so a single recursive call to expression resolution will take $O(i^{p+1} \cdot p^k)$ time if it compares all combinations.
    279 Given this bound, resolution of a single top-level expression tree of depth $d$ takes $O(i^{p+1} \cdot p^{k \cdot d})$ time\footnote{The call tree will have leaves at depth $O(d)$, and each internal node will have $O(p)$ fan-out, producing $O(p^d)$ total recursive calls.}.
    280 Expression resolution is somewhat unavoidably exponential in $p$, the number of function parameters, and $d$, the depth of the expression tree, but these values are fixed by the user programmer, and generally bounded by reasonably small constants.
    281 $k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ term is linear in the input size of the source code for the expression, otherwise the resolution algorithm will exibit sub-linear performance scaling on code containing more-deeply nested expressions.
     393The expression resolution problem is determining an optimal match between some combination of argument interpretations and the parameter list of some overloaded instance of a function; the argument interpretations are produced by recursive invocations of expression resolution, where the base case is zero-argument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions).
     394Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $\bigO{p^k}$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $\bigO{i}$ valid interpretations for each subexpression, there will be $\bigO{i}$ candidate functions and $\bigO{i^p}$ possible argument combinations for each expression, so for a single recursive call expression resolution takes $\bigO{i^{p+1} \cdot p^k}$ time if it must compare all combinations, or $\bigO{i(p+1) \cdot p^k}$ time if argument-parameter matches can be chosen independently of each other.
     395Given these bounds, resolution of a single top-level expression tree of depth $d$ takes $\bigO{i^{p+1} \cdot p^{k \cdot d}}$ time under full-combination matching, or $\bigO{i(p+1) \cdot p^{k \cdot d}}$ time for independent-parameter matching\footnote{A call tree has leaves at depth $\bigO{d}$, and each internal node has $\bigO{p}$ fan-out, producing $\bigO{p^d}$ total recursive calls.}.
     396
     397Expression resolution is somewhat unavoidably exponential in $d$, the depth of the expression tree, and if arguments cannot be matched to parameters independently of each other, expression resolution is also exponential in $p$.
     398However, both $d$ and $p$ are fixed by the user programmer, and generally bounded by reasonably small constants.
     399$k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ factor is linear in the input size of the source code for the expression, otherwise the resolution algorithm exibits sub-linear performance scaling on code containing more-deeply nested expressions.
    282400The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type-system completeness.
    283401
    284 The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests two primary areas of investigation to accomplish that end.
    285 The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.
     402The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests three primary areas of investigation to accomplish that end.
     403The first area of investigation is efficient argument-parameter matching; Bilson~\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.
    286404%TODO: look up and lit review
    287 The second, and likely more fruitful, area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; given the large ($p+1$) exponent on number of interpretations considered in the runtime analysis, even small reductions here could have a significant effect on overall resolver runtime.
     405The second area of investigation is minimizing dependencies between argument-parameter matches; the current CFA compiler attempts to match entire argument combinations against functions at once, potentially attempting to match the same argument against the same parameter multiple times.
     406Whether the feature set of \CFA admits an expression resolution algorithm where arguments can be matched to parameters independently of other arguments in the same function application is an area of open research; polymorphic type paramters produce enough of a cross-argument dependency that the problem is not trivial.
     407If cross-argument resolution dependencies cannot be completely eliminated, effective caching strategies to reduce duplicated work between equivalent argument-parameter matches in different combinations may mitigate the asymptotic defecits of the whole-combination matching approach.
     408The final area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; if argument-parameter matches cannot be made independent, even small reductions in $i$ should yield significant reductions in the $i^{p+1}$ resolver runtime factor.
     409
    288410The discussion below presents a number of largely orthagonal axes for expression resolution algorithm design to be investigated, noting prior work where applicable.
     411Though some of the proposed improvements to the expression resolution algorithm are based on heuristics rather than asymptoticly superior algorithms, it should be noted that user programmers often employ idioms and other programming patterns to reduce the mental burden of producing correct code, and if these patterns can be identified and exploited by the compiler then the significant reduction in expression resolution time for common, idiomatic expressions should result in lower total compilation time even for code including difficult-to-resolve expressions that push the expression resolver to its theoretical worst case.
    289412
    290413\subsection{Argument-Parameter Matching}
    291 The first axis we consider is argument-parameter matching --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
    292 
    293 \subsubsection{Argument-directed (``Bottom-up'')}
    294 Baker's algorithm for expression resolution\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up.
     414The first axis for consideration is argument-parameter matching direction --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
     415All expression resolution algorithms form a DAG of interpretations, some explicitly, some implicitly; in this DAG, arcs point from function-call interpretations to argument interpretations, as below:
     416\begin{figure}[h]
     417\centering
     418\begin{subfigure}[h]{2in}
     419\begin{lstlisting}
     420int *p;  // $p_i$
     421char *p; // $p_c$
     422
     423double *f(int*, int*); // $f_d$
     424char *f(char*, char*); // $f_c$
     425
     426f( f( p, p ), p );
     427\end{lstlisting}
     428\end{subfigure}~\begin{subfigure}[h]{2in}
     429\includegraphics{resolution_dag}
     430\end{subfigure}
     431\caption{Resolution DAG for a simple expression. Functions that do not have a valid argument matching are covered with an \textsf{X}.}\label{fig:res_dag}
     432\end{figure}
     433
     434Note that some interpretations may be part of more than one super-interpretation, as with $p_i$ in the bottom row, while some valid subexpression interpretations, like $f_d$ in the middle row, are not used in any interpretation of their containing expression.
     435
     436\subsubsection{Argument-directed (Bottom-up)}
     437Baker's algorithm for expression resolution~\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up.
    295438For each candidate function, Baker attempts to match argument types to parameter types in sequence, failing if any parameter cannot be matched.
    296439
    297 Bilson\cite{Bilson03} similarly pre-computes argument candidates in the original \CFA compiler, but then explicitly enumerates all possible argument combinations for a multi-parameter function; these argument combinations are matched to the parameter types of the candidate function as a unit rather than individual arguments.
    298 This is less efficient than Baker's approach, as the same argument may be compared to the same parameter many times, but allows a more straightforward handling of polymorphic type binding and multiple return types.
    299 It is possible the efficiency losses here relative to Baker could be significantly reduced by application of memoization to the argument-parameter type comparisons.
    300 
    301 \subsubsection{Parameter-directed (``Top-down'')}
    302 Unlike Baker and Bilson, Cormack's algorithm\cite{Cormack81} requests argument candidates which match the type of each parameter of each candidate function, from the top-level expression down; memoization of these requests is presented as an optimization.
     440Bilson~\cite{Bilson03} similarly pre-computes argument candidates in the original \CFA compiler, but then explicitly enumerates all possible argument combinations for a multi-parameter function; these argument combinations are matched to the parameter types of the candidate function as a unit rather than individual arguments.
     441This approach is less efficient than Baker's approach, as the same argument may be compared to the same parameter many times, but allows a more straightforward handling of polymorphic type-binding and multiple return-types.
     442It is possible the efficiency losses here relative to Baker could be significantly reduced by keeping a memoized cache of argument-parameter type comparisons and reading previously-seen argument-parameter matches from this cache rather than recomputing them.
     443
     444\subsubsection{Parameter-directed (Top-down)}
     445Unlike Baker and Bilson, Cormack's algorithm~\cite{Cormack81} requests argument candidates that match the type of each parameter of each candidate function, from the top-level expression down; memoization of these requests is presented as an optimization.
    303446As presented, this algorithm requires the result of the expression to have a known type, though an algorithm based on Cormack's could reasonably request a candidate set of any return type, though such a set may be quite large.
    304447
    305448\subsubsection{Hybrid}
    306449This proposal includes the investigation of hybrid top-down/bottom-up argument-parameter matching.
    307 A reasonable hybrid approach might be to take a top-down approach when the expression to be matched is known to have a fixed type, and a bottom-up approach in untyped contexts.
    308 This may include switches from one type to another at different levels of the expression tree, for instance:
     450A reasonable hybrid approach might take a top-down approach when the expression to be matched has a fixed type, and a bottom-up approach in untyped contexts.
     451This approach may involve switching from one type to another at different levels of the expression tree.
     452For instance:
    309453\begin{lstlisting}
    310454forall(otype T)
     
    315459int x = f( f( '!' ) );
    316460\end{lstlisting}
    317 Here, the outer call to ©f© must have a return type that is (implicitly convertable to) ©int©, so a top-down approach could be used to select \textit{(1)} as the proper interpretation of ©f©. \textit{(1)}'s parameter ©x© here, however, is an unbound type variable, and can thus take a value of any complete type, providing no guidance for the choice of candidate for the inner ©f©. The leaf expression ©'!'©, however, gives us a zero-cost interpretation of the inner ©f© as \textit{(2)}, providing a minimal-cost expression resolution where ©T© is bound to ©void*©.
    318 
    319 Deciding when to switch between bottom-up and top-down resolution in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for it is an open question, one reasonable approach might be to switch from top-down to bottom-up when the number of candidate functions exceeds some threshold.
     461The outer call to ©f© must have a return type that is (implicitly convertable to) ©int©, so a top-down approach is used to select \textit{(1)} as the proper interpretation of ©f©. \textit{(1)}'s parameter ©x©, however, is an unbound type variable, and can thus take a value of any complete type, providing no guidance for the choice of candidate for the inner call to ©f©. The leaf expression ©'!'©, however, determines a zero-cost interpretation of the inner ©f© as \textit{(2)}, providing a minimal-cost expression resolution where ©T© is bound to ©void*©.
     462
     463Deciding when to switch between bottom-up and top-down resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for which subexpressions to swich matching strategies on is an open question, one reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions.
     464
     465\subsubsection{Common Subexpression Caching}
     466With any of these argument-parameter approaches, it may be a useful optimization to cache the resolution results for common subexpressions; in Figure~\ref{fig:res_dag} this optimization would result in the list of interpretations $[p_c, p_i]$ for ©p© only being calculated once, and re-used for each of the three instances of ©p©.
    320467
    321468\subsection{Implicit Conversion Application}
    322 Baker's\cite{Baker82} and Cormack's\cite{Cormack81} algorithms do not account for implicit conversions\footnote{Baker does briefly comment on an approach for handling implicit conversions.}; both assume that there is at most one valid interpretation of a given expression for each distinct type.
     469Baker's and Cormack's algorithms do not account for implicit conversions\footnote{Baker does briefly comment on an approach for handling implicit conversions.}; both assume that there is at most one valid interpretation of a given expression for each distinct type.
    323470Integrating implicit conversion handling into their algorithms provides some choice of implementation approach.
    324471
  • src/GenPoly/Box.cc

    r321f55d r27fefeb6  
    104104                        Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
    105105                        /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
    106                         Expression *addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg );
     106                        Expression *addDynRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg );
    107107                        Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
    108108                        void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
     
    661661                                // process polymorphic return value
    662662                                retval = 0;
    663                                 if ( isPolyRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
     663                                if ( isDynRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
    664664                                        retval = functionDecl->get_functionType()->get_returnVals().front();
    665665
     
    868868                }
    869869
    870                 Expression *Pass1::addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg ) {
     870                Expression *Pass1::addDynRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *dynType, std::list< Expression *>::iterator &arg ) {
    871871                        assert( env );
    872                         Type *concrete = replaceWithConcrete( appExpr, polyType );
     872                        Type *concrete = replaceWithConcrete( appExpr, dynType );
    873873                        // add out-parameter for return value
    874874                        return addRetParam( appExpr, function, concrete, arg );
     
    877877                Expression *Pass1::applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
    878878                        Expression *ret = appExpr;
    879                         if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
     879//                      if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
     880                        if ( isDynRet( function, tyVars ) ) {
    880881                                ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
    881882                        } // if
     
    968969                        // actually make the adapter type
    969970                        FunctionType *adapter = adaptee->clone();
    970                         if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
     971//                      if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
     972                        if ( isDynRet( adapter, tyVars ) ) {
    971973                                makeRetParm( adapter );
    972974                        } // if
     
    10301032                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
    10311033                                bodyStmt = new ExprStmt( noLabels, adapteeApp );
    1032                         } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
     1034//                      } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
     1035                        } else if ( isDynType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
    10331036                                // return type T
    10341037                                if ( (*param)->get_name() == "" ) {
     
    12771280                        TyVarMap exprTyVars( (TypeDecl::Kind)-1 );
    12781281                        makeTyVarMap( function, exprTyVars );
    1279                         ReferenceToType *polyRetType = isPolyRet( function );
    1280 
    1281                         if ( polyRetType ) {
    1282                                 ret = addPolyRetParam( appExpr, function, polyRetType, arg );
     1282                        ReferenceToType *dynRetType = isDynRet( function, exprTyVars );
     1283
     1284                        if ( dynRetType ) {
     1285                                ret = addDynRetParam( appExpr, function, dynRetType, arg );
    12831286                        } else if ( needsAdapter( function, scopeTyVars ) ) {
    12841287                                // std::cerr << "needs adapter: ";
     
    12901293                        arg = appExpr->get_args().begin();
    12911294
    1292                         passTypeVars( appExpr, polyRetType, arg, exprTyVars );
     1295                        passTypeVars( appExpr, dynRetType, arg, exprTyVars );
    12931296                        addInferredParams( appExpr, function, arg, exprTyVars );
    12941297
     
    15771580
    15781581                        // move polymorphic return type to parameter list
    1579                         if ( isPolyRet( funcType ) ) {
     1582                        if ( isDynRet( funcType ) ) {
    15801583                                DeclarationWithType *ret = funcType->get_returnVals().front();
    15811584                                ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
  • src/GenPoly/GenPoly.cc

    r321f55d r27fefeb6  
    2323
    2424namespace GenPoly {
    25         bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars ) {
    26                 if ( ! adaptee->get_returnVals().empty() && isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
    27                         return true;
    28                 } // if
    29                 for ( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); innerArg != adaptee->get_parameters().end(); ++innerArg ) {
    30                         if ( isPolyType( (*innerArg)->get_type(), tyVars ) ) {
    31                                 return true;
    32                         } // if
    33                 } // for
    34                 return false;
    35         }
    36 
    37         ReferenceToType *isPolyRet( FunctionType *function ) {
    38                 if ( ! function->get_returnVals().empty() ) {
    39                         TyVarMap forallTypes( (TypeDecl::Kind)-1 );
    40                         makeTyVarMap( function, forallTypes );
    41                         return (ReferenceToType*)isPolyType( function->get_returnVals().front()->get_type(), forallTypes );
    42                 } // if
    43                 return 0;
    44         }
    45 
    4625        namespace {
    4726                /// Checks a parameter list for polymorphic parameters; will substitute according to env if present
     
    6443                        return false;
    6544                }
     45
     46                /// Checks a parameter list for dynamic-layout parameters from tyVars; will substitute according to env if present
     47                bool hasDynParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
     48                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
     49                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
     50                                assert(paramType && "Aggregate parameters should be type expressions");
     51                                if ( isDynType( paramType->get_type(), tyVars, env ) ) return true;
     52                        }
     53                        return false;
     54                }
    6655        }
    6756
     
    10190                }
    10291                return 0;
     92        }
     93
     94        Type *isDynType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
     95                type = replaceTypeInst( type, env );
     96
     97                if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) {
     98                        auto var = tyVars.find( typeInst->get_name() );
     99                        if ( var != tyVars.end() && var->second == TypeDecl::Any ) {
     100                                return type;
     101                        }
     102                } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
     103                        if ( hasDynParams( structType->get_parameters(), tyVars, env ) ) return type;
     104                } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
     105                        if ( hasDynParams( unionType->get_parameters(), tyVars, env ) ) return type;
     106                }
     107                return 0;
     108        }
     109
     110        ReferenceToType *isDynRet( FunctionType *function, const TyVarMap &forallTypes ) {
     111                if ( function->get_returnVals().empty() ) return 0;
     112               
     113                return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
     114        }
     115
     116        ReferenceToType *isDynRet( FunctionType *function ) {
     117                if ( function->get_returnVals().empty() ) return 0;
     118
     119                TyVarMap forallTypes( (TypeDecl::Kind)-1 );
     120                makeTyVarMap( function, forallTypes );
     121                return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
     122        }
     123
     124        bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars ) {
     125//              if ( ! adaptee->get_returnVals().empty() && isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
     126//                      return true;
     127//              } // if
     128                if ( isDynRet( adaptee, tyVars ) ) return true;
     129               
     130                for ( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); innerArg != adaptee->get_parameters().end(); ++innerArg ) {
     131//                      if ( isPolyType( (*innerArg)->get_type(), tyVars ) ) {
     132                        if ( isDynType( (*innerArg)->get_type(), tyVars ) ) {
     133                                return true;
     134                        } // if
     135                } // for
     136                return false;
    103137        }
    104138
  • src/GenPoly/GenPoly.h

    r321f55d r27fefeb6  
    3131namespace GenPoly {
    3232        typedef ErasableScopedMap< std::string, TypeDecl::Kind > TyVarMap;
    33        
    34         /// A function needs an adapter if it returns a polymorphic value or if any of its
    35         /// parameters have polymorphic type
    36         bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVarr );
    37 
    38         /// true iff function has polymorphic return type
    39         ReferenceToType *isPolyRet( FunctionType *function );
    4033
    4134        /// Replaces a TypeInstType by its referrent in the environment, if applicable
     
    4740        /// returns polymorphic type if is polymorphic type in tyVars, NULL otherwise; will look up substitution in env if provided
    4841        Type *isPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 );
     42
     43        /// returns dynamic-layout type if is dynamic-layout type in tyVars, NULL otherwise; will look up substitution in env if provided
     44        Type *isDynType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 );
     45
     46        /// true iff function has dynamic-layout return type under the given type variable map
     47        ReferenceToType *isDynRet( FunctionType *function, const TyVarMap &tyVars );
     48
     49        /// true iff function has dynamic-layout return type under the type variable map generated from its forall-parameters
     50        ReferenceToType *isDynRet( FunctionType *function );
     51
     52        /// A function needs an adapter if it returns a dynamic-layout value or if any of its parameters have dynamic-layout type
     53        bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVarr );
    4954
    5055        /// returns polymorphic type if is pointer to polymorphic type, NULL otherwise; will look up substitution in env if provided
  • src/GenPoly/InstantiateGeneric.cc

    r321f55d r27fefeb6  
    2424#include "GenPoly.h"
    2525#include "ScopedMap.h"
     26#include "ScopedSet.h"
    2627
    2728#include "ResolvExpr/typeops.h"
     
    122123                }
    123124        };
     125
     126        /// Possible options for a given specialization of a generic type
     127        enum class genericType {
     128                dtypeStatic,  ///< Concrete instantiation based solely on {d,f}type-to-void conversions
     129                concrete,     ///< Concrete instantiation requiring at least one parameter type
     130                dynamic       ///< No concrete instantiation
     131        };
     132
     133        genericType& operator |= ( genericType& gt, const genericType& ht ) {
     134                switch ( gt ) {
     135                case genericType::dtypeStatic:
     136                        gt = ht;
     137                        break;
     138                case genericType::concrete:
     139                        if ( ht == genericType::dynamic ) { gt = genericType::dynamic; }
     140                        break;
     141                case genericType::dynamic:
     142                        // nothing possible
     143                        break;
     144                }
     145                return gt;
     146        }
    124147       
    125148        /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
     
    127150                /// Map of (generic type, parameter list) pairs to concrete type instantiations
    128151                InstantiationMap< AggregateDecl, AggregateDecl > instantiations;
     152                /// Set of types which are dtype-only generic (and therefore have static layout)
     153                ScopedSet< AggregateDecl* > dtypeStatics;
    129154                /// Namer for concrete types
    130155                UniqueName typeNamer;
    131156
    132157        public:
    133                 GenericInstantiator() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
     158                GenericInstantiator() : DeclMutator(), instantiations(), dtypeStatics(), typeNamer("_conc_") {}
    134159
    135160                virtual Type* mutate( StructInstType *inst );
     
    147172                /// Wrap instantiation insertion for unions
    148173                void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); }
     174
     175                /// Strips a dtype-static aggregate decl of its type parameters, marks it as stripped
     176                void stripDtypeParams( AggregateDecl *base, std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs );
    149177        };
    150178
     
    154182        }
    155183
    156         //////////////////////////////////////// GenericInstantiator //////////////////////////////////////////////////
    157 
    158         /// Possible options for a given specialization of a generic type
    159         enum class genericType {
    160                 dtypeStatic,  ///< Concrete instantiation based solely on {d,f}type-to-void conversions
    161                 concrete,     ///< Concrete instantiation requiring at least one parameter type
    162                 dynamic       ///< No concrete instantiation
    163         };
    164 
    165         genericType& operator |= ( genericType& gt, const genericType& ht ) {
    166                 switch ( gt ) {
    167                 case genericType::dtypeStatic:
    168                         gt = ht;
    169                         break;
    170                 case genericType::concrete:
    171                         if ( ht == genericType::dynamic ) { gt = genericType::dynamic; }
    172                         break;
    173                 case genericType::dynamic:
    174                         // nothing possible
    175                         break;
    176                 }
    177                 return gt;
    178         }
    179 
    180         /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
     184        /// Makes substitutions of params into baseParams; returns dtypeStatic if there is a concrete instantiation based only on {d,f}type-to-void conversions,
     185        /// concrete if there is a concrete instantiation requiring at least one parameter type, and dynamic if there is no concrete instantiation
    181186        genericType makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
    182187                genericType gt = genericType::dtypeStatic;
     
    223228        }
    224229
     230        /// Substitutes types of members according to baseParams => typeSubs, working in-place
     231        void substituteMembers( std::list< Declaration* >& members, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs ) {
     232                // substitute types into new members
     233                TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
     234                for ( std::list< Declaration* >::iterator member = members.begin(); member != members.end(); ++member ) {
     235                        subs.apply(*member);
     236                }
     237        }
     238
     239        /// Strips the instances's type parameters
     240        void stripInstParams( ReferenceToType *inst ) {
     241                deleteAll( inst->get_parameters() );
     242                inst->get_parameters().clear();
     243        }
     244       
     245        void GenericInstantiator::stripDtypeParams( AggregateDecl *base, std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs ) {
     246                substituteMembers( base->get_members(), baseParams, typeSubs );
     247
     248                deleteAll( baseParams );
     249                baseParams.clear();
     250               
     251                dtypeStatics.insert( base );
     252        }
     253
    225254        Type* GenericInstantiator::mutate( StructInstType *inst ) {
    226255                // mutate subtypes
     
    231260                // exit early if no need for further mutation
    232261                if ( inst->get_parameters().empty() ) return inst;
     262
     263                // check for an already-instantiatiated dtype-static type
     264                if ( dtypeStatics.find( inst->get_baseStruct() ) != dtypeStatics.end() ) {
     265                        stripInstParams( inst );
     266                        return inst;
     267                }
     268               
     269                // check if type can be concretely instantiated; put substitutions into typeSubs
    233270                assert( inst->get_baseParameters() && "Base struct has parameters" );
    234 
    235                 // check if type can be concretely instantiated; put substitutions into typeSubs
    236271                std::list< TypeExpr* > typeSubs;
    237272                genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs );
    238273                switch ( gt ) {
    239                 case genericType::dtypeStatic: // TODO strip params off original decl and reuse here
    240                 case genericType::concrete:
    241                 {
     274                case genericType::dtypeStatic:
     275                        stripDtypeParams( inst->get_baseStruct(), *inst->get_baseParameters(), typeSubs );
     276                        stripInstParams( inst );
     277                        break;
     278               
     279                case genericType::concrete: {
    242280                        // make concrete instantiation of generic type
    243281                        StructDecl *concDecl = lookup( inst, typeSubs );
     
    274312                // exit early if no need for further mutation
    275313                if ( inst->get_parameters().empty() ) return inst;
     314
     315                // check for an already-instantiatiated dtype-static type
     316                if ( dtypeStatics.find( inst->get_baseUnion() ) != dtypeStatics.end() ) {
     317                        stripInstParams( inst );
     318                        return inst;
     319                }
     320
     321                // check if type can be concretely instantiated; put substitutions into typeSubs
    276322                assert( inst->get_baseParameters() && "Base union has parameters" );
    277 
    278                 // check if type can be concretely instantiated; put substitutions into typeSubs
    279323                std::list< TypeExpr* > typeSubs;
    280324                genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs );
    281325                switch ( gt ) {
    282                 case genericType::dtypeStatic:  // TODO strip params off original decls and reuse here
     326                case genericType::dtypeStatic:
     327                        stripDtypeParams( inst->get_baseUnion(), *inst->get_baseParameters(), typeSubs );
     328                        stripInstParams( inst );
     329                        break;
     330                       
    283331                case genericType::concrete:
    284332                {
     
    311359                DeclMutator::doBeginScope();
    312360                instantiations.beginScope();
     361                dtypeStatics.beginScope();
    313362        }
    314363
     
    316365                DeclMutator::doEndScope();
    317366                instantiations.endScope();
     367                dtypeStatics.endScope();
    318368        }
    319369
  • src/GenPoly/ScrubTyVars.cc

    r321f55d r27fefeb6  
    4545
    4646        Type * ScrubTyVars::mutateAggregateType( Type *ty ) {
    47                 if ( isPolyType( ty, tyVars ) ) {
     47                if ( shouldScrub( ty ) ) {
    4848                        PointerType *ret = new PointerType( Type::Qualifiers(), new VoidType( ty->get_qualifiers() ) );
    4949                        delete ty;
     
    6363        Expression * ScrubTyVars::mutate( SizeofExpr *szeof ) {
    6464                // sizeof( T ) => _sizeof_T parameter, which is the size of T
    65                 if ( Type *polyType = isPolyType( szeof->get_type() ) ) {
    66                         Expression *expr = new NameExpr( sizeofName( mangleType( polyType ) ) );
     65                if ( Type *dynType = shouldScrub( szeof->get_type() ) ) {
     66                        Expression *expr = new NameExpr( sizeofName( mangleType( dynType ) ) );
    6767                        return expr;
    6868                } else {
     
    7373        Expression * ScrubTyVars::mutate( AlignofExpr *algnof ) {
    7474                // alignof( T ) => _alignof_T parameter, which is the alignment of T
    75                 if ( Type *polyType = isPolyType( algnof->get_type() ) ) {
    76                         Expression *expr = new NameExpr( alignofName( mangleType( polyType ) ) );
     75                if ( Type *dynType = shouldScrub( algnof->get_type() ) ) {
     76                        Expression *expr = new NameExpr( alignofName( mangleType( dynType ) ) );
    7777                        return expr;
    7878                } else {
     
    8282
    8383        Type * ScrubTyVars::mutate( PointerType *pointer ) {
    84                 if ( Type *polyType = isPolyType( pointer->get_base(), tyVars ) ) {
    85                         Type *ret = polyType->acceptMutator( *this );
     84//              // special case of shouldScrub that takes all TypeInstType pointer bases, even if they're not dynamic
     85//              Type *base = pointer->get_base();
     86//              Type *dynType = 0;
     87//              if ( dynamicOnly ) {
     88//                      if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( base ) ) {
     89//                              if ( tyVars.find( typeInst->get_name() ) != tyVars.end() ) { dynType = typeInst; }
     90//                      } else {
     91//                              dynType = isDynType( base, tyVars );
     92//                      }
     93//              } else {
     94//                      dynType = isPolyType( base, tyVars );
     95//              }
     96//              if ( dynType ) {
     97                if ( Type *dynType = shouldScrub( pointer->get_base() ) ) {
     98                        Type *ret = dynType->acceptMutator( *this );
    8699                        ret->get_qualifiers() += pointer->get_qualifiers();
    87100                        pointer->set_base( 0 );
  • src/GenPoly/ScrubTyVars.h

    r321f55d r27fefeb6  
    2727        class ScrubTyVars : public Mutator {
    2828          public:
    29                 ScrubTyVars( const TyVarMap &tyVars ): tyVars( tyVars ) {}
     29                ScrubTyVars( const TyVarMap &tyVars, bool dynamicOnly = false ): tyVars( tyVars ), dynamicOnly( dynamicOnly ) {}
    3030
    3131                /// For all polymorphic types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type,
     
    3333                template< typename SynTreeClass >
    3434                static SynTreeClass *scrub( SynTreeClass *target, const TyVarMap &tyVars );
     35
     36                /// For all dynamic-layout types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type,
     37                /// and sizeof/alignof expressions with the proper variable
     38                template< typename SynTreeClass >
     39                static SynTreeClass *scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars );
    3540
    3641                virtual Type* mutate( TypeInstType *typeInst );
     
    4247
    4348          private:
     49                /// Returns the type if it should be scrubbed, NULL otherwise.
     50                Type* shouldScrub( Type *ty ) {
     51                        return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars );
     52//                      if ( ! dynamicOnly ) return isPolyType( ty, tyVars );
     53//
     54//                      if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
     55//                              return tyVars.find( typeInst->get_name() ) != tyVars.end() ? ty : 0;
     56//                      }
     57//
     58//                      return isDynType( ty, tyVars );
     59                }
     60               
    4461                /// Mutates (possibly generic) aggregate types appropriately
    4562                Type* mutateAggregateType( Type *ty );
    4663               
    47                 const TyVarMap &tyVars;
     64                const TyVarMap &tyVars;  ///< Type variables to scrub
     65                bool dynamicOnly;        ///< only scrub the types with dynamic layout? [false]
    4866        };
    4967
    50         /* static class method */
    5168        template< typename SynTreeClass >
    5269        SynTreeClass * ScrubTyVars::scrub( SynTreeClass *target, const TyVarMap &tyVars ) {
    5370                ScrubTyVars scrubber( tyVars );
     71                return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
     72        }
     73
     74        template< typename SynTreeClass >
     75        SynTreeClass * ScrubTyVars::scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ) {
     76                ScrubTyVars scrubber( tyVars, true );
    5477                return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
    5578        }
  • src/SymTab/Autogen.cc

    r321f55d r27fefeb6  
    174174
    175175        void makeStructMemberOp( ObjectDecl * dstParam, Expression * src, DeclarationWithType * field, FunctionDecl * func, TypeSubstitution & genericSubs, bool isDynamicLayout, bool forward = true ) {
    176                 if ( isDynamicLayout && src ) {
    177                         genericSubs.apply( src );
    178                 }
     176//              if ( isDynamicLayout && src ) {
     177//                      genericSubs.apply( src );
     178//              }
    179179
    180180                ObjectDecl * returnVal = NULL;
  • src/examples/gc_no_raii/src/gc.h

    r321f55d r27fefeb6  
    77static inline gcpointer(T) gcmalloc()
    88{
    9     gcpointer(T) ptr;
    10     void* address = gc_allocate(sizeof(T));
    11     (&ptr){ address };
    12     ctor(&ptr, address);
     9    gcpointer(T) ptr = { gc_allocate(sizeof(T)) };
     10    ptr{};
    1311    gc_conditional_collect();
    1412    return ptr;
    1513}
     14
     15forall(otype T)
     16static inline void gcmalloc(gcpointer(T)* ptr)
     17{
     18        ptr{ gc_allocate(sizeof(T)) };
     19      (*ptr){};
     20      gc_conditional_collect();
     21}
  • src/examples/gc_no_raii/test/gctest.c

    r321f55d r27fefeb6  
    88        sout | "Bonjour au monde!\n";
    99
    10         gcpointer(int) anInt = gcmalloc();
     10        for(int i = 0; i < 1000000; i++) {
     11                gcpointer(int) anInt;
     12                gcmalloc(&anInt);
     13        }
    1114}
Note: See TracChangeset for help on using the changeset viewer.