Changeset a75d464 for doc

Sep 14, 2020, 9:02:19 AM (12 months ago)
Peter A. Buhr <pabuhr@…>
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Peter A. Buhr <pabuhr@…> (09/14/20 08:55:23)
Peter A. Buhr <pabuhr@…> (09/14/20 09:02:19)

complete latex version of Fangren's co-op report

1 edited


  • doc/theses/fangren_yu_COOP_S20/Report.tex

    rd1864da ra75d464  
    1616\input{common}                                          % common CFA document macros
     23% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     24% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
     29\setlength{\topmargin}{-0.45in}                                                 % move running title into header
     36language=C++,                                                                                   % make C++ the default language
    1837escapechar=\$,                                                                                  % LaTeX escape in CFA code
    2039}% lstset
    22 \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    23 \usepackage{breakurl}
    25 \usepackage[pagewise]{lineno}
    26 \renewcommand{\linenumberfont}{\scriptsize\sffamily}
    28 % Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
    29 % removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
    31 \renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    33 \setlength{\topmargin}{-0.45in}                                                 % move running title into header
    34 \setlength{\headsep}{0.25in}
    36 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    38 \CFAStyle                                                                                               % use default CFA format-style
    3941\lstnewenvironment{C++}[1][]                            % use C++ style
    84 cfa-cc is the reference compiler for the Cforall programming language, which is a non-
     86cfa-cc is the reference compiler for the \CFA programming language, which is a non-
    8587object-oriented extension to C.
    86 Cforall attempts to introduce productive modern programming language features to C
     88\CFA attempts to introduce productive modern programming language features to C
    8789while maintaining as much backward-compatibility as possible, so that most existing C
    88 programs can seamlessly work with Cforall.
    90 Since the Cforall project was dated back to the early 2000s, and only restarted in the past
     90programs can seamlessly work with \CFA.
     92Since the \CFA project was dated back to the early 2000s, and only restarted in the past
    9193few years, there is a significant amount of legacy code in the current compiler codebase,
    9294with little proper documentation available. This becomes a difficulty while developing new
    96 Currently, the Cforall team is also facing another problem: bad compiler performance. For
     98Currently, the \CFA team is also facing another problem: bad compiler performance. For
    9799the development of a new programming language, writing a standard library is an
    98100important part. The incompetence of the compiler causes building the library files to take
    106108performance bottleneck, namely the resolution algorithm. It is aimed to provide new
    107109developers to the project enough guidance and clarify the purposes and behavior of certain
    108 functions which are not mentioned in the previous Cforall research papers.
     110functions which are not mentioned in the previous \CFA research papers.
    132134Declarations are introduced by standard C declarations, with the usual scoping rules.
    133135In addition, declarations can also be introduced by the forall clause (which is the origin
    134 of Cforall's name):
     136of \CFA's name):
    136138forall (<$\emph{TypeParameterList}$> | <$\emph{AssertionList}$>)
    137139        $\emph{declaration}$
    139 Type parameters in Cforall are similar to \CC template type parameters. The Cforall
     141Type parameters in \CFA are similar to \CC template type parameters. The \CFA
    149 Assertions are a distinctive feature of Cforall: contrary to the \CC template where
    150 arbitrary functions and operators can be used in a template definition, in a Cforall
     151Assertions are a distinctive feature of \CFA: contrary to the \CC template where
     152arbitrary functions and operators can be used in a template definition, in a \CFA
    151153parametric function, operations on parameterized types must be declared in assertions.
    205207tree data structure, implemented with visitor pattern, and can be loosely described with
    206208the following pseudocode:
    207 \begin{cfa}
    208210Pass::visit (node_t node) {
    209211        previsit(node);
    213215        postvisit(node);
    215 \end{cfa}
    216218Operations in previsit() happen in preorder (top to bottom) and operations in
    217219postvisit() happen in postorder (bottom to top). The precise order of recursive
    248250WithSymbolTable gives a managed symbol table with built-in scoping rule handling
    249 (e.g. on entering and exiting a block statement)
     251(\eg on entering and exiting a block statement)
    251 \textbf{NOTE}: If a pass extends the functionality of another existing pass, due to \CC overloading
     253\NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading
    252254resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures
    253255to its own scope, or otherwise they will not be picked up by template resolution:
    254 \begin{cfa}
    255257class Pass2: public Pass1 {
    256258        using Pass1::previsit;
    258260        // new procedures
    260 \end{cfa}
    273275The core of new-ast is a customized implementation of smart pointers, similar to
    274 @std::shared_ptr@ and @std::weak_ptr@ in C++ standard library. Reference counting is
     276@std::shared_ptr@ and @std::weak_ptr@ in \CC standard library. Reference counting is
    275277used to detect sharing and allows optimization. For a purely functional (a.k.a. immutable)
    276278data structure, all mutations are modelled by shallow copies along the path of mutation.
    309311Decrements this node's strong or weak reference count. If strong reference count reaches
    310312zero, the node is deleted by default.
    311 \textbf{NOTE}: Setting @do_delete@ to false may result in a detached node. Subsequent code should
     313\NOTE: Setting @do_delete@ to false may result in a detached node. Subsequent code should
    312314manually delete the node or assign it to a strong pointer to prevent memory leak.
    313315Reference counting functions are internally called by @ast::ptr_base@.
    325327Otherwise, returns shallowCopy(node).
    326328It is an error to mutate a shared node that is weak-referenced. Currently this does not
    327 happen. The problem may appear once weak pointers to shared nodes (e.g. expression
     329happen. The problem may appear once weak pointers to shared nodes (\eg expression
    328330nodes) are used; special care will be needed.
    330 \textbf{NOTE}: This naive uniqueness check may not be sufficient in some cases. A discussion of the
     332\NOTE: This naive uniqueness check may not be sufficient in some cases. A discussion of the
    331333issue is presented at the end of this section.
    372374source code for details.
     376For example, in the above diagram, if mutation of B is wanted while at P1, the call using
     377@chain_mutate@ looks like the following:
     379chain_mutate(P1.a)(&A.b) = new_value_of_b;
     381Note that if some node in chain mutate is shared (therefore shallow copied), it implies that
     382every node further down will also be copied, thus correctly executing the functional
     383mutation algorithm. This example code creates copies of both A and B and performs
     384mutation on the new nodes, so that the other tree P2-A-B is untouched.
     385However, if a pass traverses down to node B and performs mutation, for example, in
     386@postvisit(B)@, information on sharing higher up is lost. Since the new-ast structure is only in
     387experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up,
     388this issue does not actually happen. It should be addressed in the future when other
     389compilation passes are migrated to new-ast and many of them contain procedural
     390mutations, where it might cause accidental mutations to other logically independent trees
     391(\eg common sub-expression) and become a bug.
     394\vspace*{20pt} % FIX ME, spacing problem with this heading ???
     395\section{Compiler Algorithm Documentation}
     397This documentation currently covers most of the resolver, data structures used in variable
     398and expression resolution, and a few directly related passes. Later passes involving code
     399generation is not included yet; documentation for those will be done afterwards.
     401\subsection{Symbol Table}
     403\NOTE: For historical reasons, the symbol table data structure was called ``indexer'' in the
     404old implementation. Hereby we will be using the name SymbolTable everywhere.
     405The symbol table stores a mapping from names to declarations and implements a similar
     406name space separation rule, and the same scoping rules in standard C.\footnote{ISO/IEC 9899:1999, Sections 6.2.1 and 6.2.3} The difference in
     407name space rule is that typedef aliases are no longer considered ordinary identifiers.
     408In addition to C tag types (struct, union, enum), \CFA introduces another tag type, trait,
     409which is a named collection of assertions.
     411\subsubsection{Source: AST/SymbolTable.hpp}
     413\subsubsection{Source: SymTab/Indexer.h}
     416SymbolTable::addId(const DeclWithType * decl)
     418Since \CFA allows overloading of variables and functions, ordinary identifier names need
     419to be mangled. The mangling scheme is closely based on the Itanium \CC ABI,\footnote{\url{}, Section 5.1} while
     420making adaptations to \CFA specific features, mainly assertions and overloaded variables
     421by type. Naming conflicts are handled by mangled names; lookup by name returns a list of
     422declarations with the same literal identifier name.
     425SymbolTable::addStruct(const StructDecl * decl)
     426SymbolTable::addUnion(const UnionDecl * decl)
     427SymbolTable::addEnum(const EnumDecl * decl)
     428SymbolTable::addTrait(const TraitDecl * decl)
     430Adds a tag type declaration to the symbol table.
     432SymbolTable::addType(const NamedTypeDecl * decl)
     434Adds a typedef alias to the symbol table.
     436\textbf{C Incompatibility Note}: Since Cforall allows using struct, union and enum type names
     437without the keywords, typedef names and tag type names cannot be disambiguated by
     438syntax rules. Currently the compiler puts them together and disallows collision. The
     439following program is valid C but not valid Cforall:
     441struct A {};
     442typedef int A;
     443// gcc: ok, cfa: Cannot redefine typedef A
     445In actual practices however, such usage is extremely rare, and typedef struct A A; is
     446not considered an error, but silently discarded. Therefore, we expect this change to have
     447minimal impact on existing C programs.
     448Meanwhile, the following program is allowed in Cforall:
     450typedef int A;
     451void A();
     452// gcc: A redeclared as different kind of symbol, cfa: ok
     455\subsection{Type Environment and Unification}
     457The core of parametric type resolution algorithm.
     458Type Environment organizes type parameters in \textbf{equivalent classes} and maps them to
     459actual types. Unification is the algorithm that takes two (possibly parametric) types and
     460parameter mappings and attempts to produce a common type by matching the type
     463The unification algorithm is recursive in nature and runs in two different modes internally:
     466\textbf{Exact} unification mode requires equivalent parameters to match perfectly;
     468\textbf{Inexact} unification mode allows equivalent parameters to be converted to a
     469common type.
     471For a pair of matching parameters (actually, their equivalent classes), if either side is open
     472(not bound to a concrete type yet), they are simply combined.
     474Within inexact mode, types are allowed to differ on their cv-qualifiers; additionally, if a
     475type never appear either in parameter list or as the base type of a pointer, it may also be
     476widened (i.e. safely converted). As Cforall currently does not implement subclassing similar
     477to object-oriented languages, widening conversions are on primitive types only, for
     478example the conversion from int to long.
     480The need for two unification modes come from the fact that parametric types are
     481considered compatible only if all parameters are exactly the same (not just compatible).
     482Pointer types also behaves similarly; in fact, they may be viewed as a primitive kind of
     483parametric types. @int*@ and @long*@ are different types, just like @vector(int)@ and
     484@vector(long)@ are, for the parametric type @vector(T)@.
     486The resolver should use the following ``@public@'' functions:\footnote{
     487Actual code also tracks assertions on type parameters; those extra arguments are omitted here for
     491\subsubsection{Source: ResolvExpr/}
     494bool unify(const Type *type1, const Type *type2, TypeEnvironment &env,
     495OpenVarSet &openVars, const SymbolTable &symtab, Type *&commonType)
     497Attempts to unify @type1@ and @type2@ with current type environment.
     499If operation succeeds, @env@ is modified by combining the equivalence classes of matching
     500parameters in @type1@ and @type2@, and their common type is written to commonType.
     502If operation fails, returns false.
     504bool typesCompatible(const Type * type1, const Type * type2, const
     505SymbolTable &symtab, const TypeEnvironment &env)
     506bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type *
     507type2, const SymbolTable &symtab, const TypeEnvironment &env)
     510Determines if type1 and type2 can possibly be the same type. The second version ignores
     511the outermost cv-qualifiers if present.\footnote{
     512In const \lstinline@int * const@, only the second \lstinline@const@ is ignored.}
     514The call has no side effect.
     516\NOTE: No attempts are made to widen the types (exact unification is used), although the
     517function names may suggest otherwise. E.g. @typesCompatible(int, long)@ returns false.
     520\subsection{Expression Resolution}
     522The design of the current version of expression resolver is outlined in the Ph.D. Thesis from
     523Aaron Moss~\cite{Moss19}.
     525A summary of the resolver algorithm for each expression type is presented below.
     527All overloadable operators are modelled as function calls. For a function call,
     528interpretations of the function and arguments are found recursively. Then the following
     529steps produce a filtered list of valid interpretations:
     532From all possible combinations of interpretations of the function and arguments,
     533those where argument types may be converted to function parameter types are
     534considered valid.
     536Valid interpretations with the minimum sum of argument costs are kept.
     538Argument costs are then discarded; the actual cost for the function call expression is
     539the sum of conversion costs from the argument types to parameter types.
     541For each return type, the interpretations with satisfiable assertions are then sorted
     542by actual cost computed in step 3. If for a given type, the minimum cost
     543interpretations are not unique, it is said that for that return type the interpretation
     544is ambiguous. If the minimum cost interpretation is unique but contains an
     545ambiguous argument, it is also considered ambiguous.
     547Therefore, for each return type, the resolver produces either of:
     550No alternatives
     552A single valid alternative
     554An ambiguous alternative
     556Note that an ambiguous alternative may be discarded at the parent expressions because a
     557different return type matches better for the parent expressions.
     559The non-overloadable expressions in Cforall are: cast expressions, address-of (unary @&@)
     560expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional
     561expression (@?:@).
     563For a cast expression, the convertible argument types are kept. Then the result is selected
     564by lowest argument cost, and further by lowest conversion cost to target type. If the lowest
     565cost is still not unique, or an ambiguous argument interpretation is selected, the cast
     566expression is ambiguous. In an expression statement, the top level expression is implicitly
     567cast to void.
     569For an address-of expression, only lvalue results are kept and the minimum cost is selected.
     571For logical expressions @&&@ and @||@, arguments are implicitly cast to bool, and follow the rule
     572of cast expression as above.
     574For the ternary conditional expression, the condition is implicitly cast to bool, and the
     575branch expressions must have compatible types. Each pair of compatible branch
     576expression types produce a possible interpretation, and the cost is defined as the sum of
     577expression costs plus the sum of conversion costs to the common type.
     579TODO: Write a specification for expression costs.
     582\subsection{Assertion Satisfaction}
     584The resolver tries to satisfy assertions on expressions only when it is needed: either while
     585selecting from multiple alternatives of a same result type for a function call (step 4 of
     586resolving function calls), or upon reaching the top level of an expression statement.
     588Unsatisfiable alternatives are discarded. Satisfiable alternatives receive \textbf{implicit
     589parameters}: in Cforall, parametric functions are designed such that they can be compiled
     590separately, as opposed to \CC templates which are only compiled at instantiation. Given a
     591parametric function definition:
     593forall (otype T | {void foo(T);})
     594void bar (T t) { foo(t); }
     596The function bar does not know which @foo@ to call when compiled without knowing the call
     597site, so it requests a function pointer to be passed as an extra argument. At the call site,
     598implicit parameters are automatically inserted by the compiler.
     600\textbf{TODO}: Explain how recursive assertion satisfaction and polymorphic recursion work.
     605\subsection{Test Suites}
     607Automatic test suites are located under the @tests/@ directory. A test case consists of an
     608input CFA source file (name ending with, and an expected output file located
     609in @.expect/@ directory relative to the source file, with the same file name ending with @.txt@.
     610So a test named @tuple/tupleCast@ has the following files, for example:
     613..     tuple/
     614......     .expect/
     615..........       tupleCast.txt
     618If compilation fails, the error output is compared to the expect file. If compilation succeeds,
     619the built program is run and its output compared to the expect file.
     620To run the tests, execute the test script under the @tests/@ directory, with a list of
     621test names to be run, or @--all@ to run all tests. The test script reports test cases
     622fail/success, compilation time and program run time.
     625\subsection{Performance Reports}
     627To turn on performance reports, pass @-S@ flag to the compiler.
     6293 kinds of performance reports are available:
     632Time, reports time spent in each compilation step
     634Heap, reports number of dynamic memory allocations, total bytes allocated, and
     635maximum heap memory usage
     637Counters, for certain predefined statistics; counters can be registered anywhere in
     638the compiler as a static object, and the interface can be found at
     641It is suggested to run performance tests with optimized build (@g++@ flag @-O3@)
Note: See TracChangeset for help on using the changeset viewer.