# source:doc/theses/fangren_yu_COOP_S20/Report.tex@a75d464

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-expr
Last change on this file since a75d464 was a75d464, checked in by Peter A. Buhr <pabuhr@…>, 21 months ago

complete latex version of Fangren's co-op report

• Property mode set to 100644
File size: 27.2 KB
Line
1\documentclass[twoside,12pt]{article}
2
3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4
5% Latex packages used in the document.
6\usepackage{fullpage,times,comment}
7\usepackage{epic,eepic}
8\usepackage{upquote}                                                                    % switch curled '" to straight
9\usepackage{calc}
10\usepackage{varioref}                                                                   % extended references
11\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
12\renewcommand{\thesubfigure}{\alph{subfigure})}
13\usepackage{latexsym}                                   % \Box glyph
14\usepackage{mathptmx}                                   % better math font with "times"
15\usepackage[usenames]{color}
16\input{common}                                          % common CFA document macros
18\usepackage{breakurl}
19
20\usepackage[pagewise]{lineno}
21\renewcommand{\linenumberfont}{\scriptsize\sffamily}
22
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
25% AFTER HYPERREF.
26\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
27\newcommand{\NOTE}{\textbf{NOTE}}
28
29\setlength{\topmargin}{-0.45in}                                                 % move running title into header
31
32%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
33
35\lstset{
36language=C++,                                                                                   % make C++ the default language
140\end{cfa}
141Type parameters in \CFA are similar to \CC template type parameters. The \CFA
142declaration
143\begin{cfa}
144forall (dtype T) ...
145\end{cfa}
146behaves similarly as the \CC template declaration
147\begin{C++}
148template <typename T> ...
149\end{C++}
150
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
153parametric function, operations on parameterized types must be declared in assertions.
154
155Consider the following \CC template:
156\begin{C++}
157template <typename T> int foo(T t) {
158        return bar(t) + baz(t);
159}
160\end{C++}
161Unless bar and baz are also parametric functions taking any argument type, they must be
162declared in the assertions, or otherwise the code will not compile:
163\begin{cfa}
164forall (dtype T | { int bar(T); int baz(t); }) int foo (T t) {
165        return bar(t) + baz(t);
166}
167\end{cfa}
168Assertions are written using the usual function declaration syntax. The scope of type
169parameters and assertions is the following declaration.
170
171\subsubsection{Type nodes}
172
173A type node represents the type of an object or expression.
174Named types reference the corresponding type declarations. The type of a function is its
175function pointer type (same as standard C).
176With the addition of type parameters, named types may contain a list of parameter values
177(actual parameter types).
178
179\subsubsection{Statement nodes}
180
181Statement nodes represent the statements in the program, including basic expression
182statements, control flows and blocks.
183Local declarations (within a block statement) are represented as declaration statements.
184
185\subsubsection{Expression nodes}
186
187Some expressions are represented differently in the compiler before and after resolution
188stage:
189\begin{itemize}
190\item
191Name expressions: NameExpr pre-resolution, VariableExpr post-resolution
192\item
193Member expressions: UntypedMemberExpr pre-resolution, MemberExpr post-resolution
194\item
195Function call expressions (including overloadable operators): UntypedExpr pre-resolution, ApplicationExpr post-resolution
196\end{itemize}
197The pre-resolution representations contain only the symbols. Post-resolution results link
198them to the actual variable and function declarations.
199
200
201\subsection{Compilation Passes}
202
203Compilation steps are implemented as passes, which follows a general structural recursion
204pattern on the syntax tree.
205
206The basic work flow of compilation passes follows preorder and postorder traversal on
207tree data structure, implemented with visitor pattern, and can be loosely described with
208the following pseudocode:
209\begin{C++}
210Pass::visit (node_t node) {
211        previsit(node);
212        if (visit_children)
213                for each child of node:
214                        child.accept(this);
215        postvisit(node);
216}
217\end{C++}
218Operations in previsit() happen in preorder (top to bottom) and operations in
219postvisit() happen in postorder (bottom to top). The precise order of recursive
220operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and
221@AST/Pass.impl.hpp@ (new).
222Implementations of compilation passes need to follow certain conventions:
223\begin{itemize}
224\item
225Passes \textbf{should not} directly override the visit method (Non-virtual Interface
226principle); if a pass desires different recursion behavior, it should set
227@visit_children@ to false and perform recursive calls manually within previsit or
228postvisit procedures. To enable this option, inherit from @WithShortCircuiting@ mixin.
229\item
230previsit may mutate the node but \textbf{must not} change the node type or return null.
231\item
232postvisit may mutate the node, reconstruct it to a different node type, or delete it by
233returning null.
234\item
235If the previsit or postvisit method is not defined for a node type, the step is skipped.
236If the return type is declared as void, the original node is returned by default. These
237behaviors are controlled by template specialization rules; see
238@Common/PassVisitor.proto.h@ (old) and @AST/Pass.proto.hpp@ (new) for details.
239\end{itemize}
240Other useful mixin classes for compilation passes include:
241\begin{itemize}
242\item
243WithGuards allows saving values of variables and restore automatically upon exiting
244the current node.
245\item
246WithVisitorRef creates a wrapped entity of current pass (the actual argument
247passed to recursive calls internally) for explicit recursion, usually used together
248with WithShortCircuiting.
249\item
250WithSymbolTable gives a managed symbol table with built-in scoping rule handling
251(\eg on entering and exiting a block statement)
252\end{itemize}
253\NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading
254resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures
255to its own scope, or otherwise they will not be picked up by template resolution:
256\begin{C++}
257class Pass2: public Pass1 {
258        using Pass1::previsit;
259        using Pass1::postvisit;
260        // new procedures
261}
262\end{C++}
263
264
265\subsection{Data Structure Change WIP (new-ast)}
266
267It has been observed that excessive copying of syntax tree structures accounts for a
268majority of computation cost and significantly slows down the compiler. In the previous
269implementation of the syntax tree, every internal node has a unique parent; therefore all
270copies are required to duplicate everything down to the bottom. A new, experimental
271re-implementation of the syntax tree (source under directory AST/ hereby referred to as
272new-ast'') attempts to overcome this issue with a functional approach that allows sharing
273of common sub-structures and only makes copies when necessary.
274
275The core of new-ast is a customized implementation of smart pointers, similar to
276@std::shared_ptr@ and @std::weak_ptr@ in \CC standard library. Reference counting is
277used to detect sharing and allows optimization. For a purely functional (a.k.a. immutable)
278data structure, all mutations are modelled by shallow copies along the path of mutation.
279With reference counting optimization, unique nodes are allowed to be mutated in place.
280This however, may potentially introduce some complications and bugs; a few issues are
281discussed near the end of this section.
282
283\subsubsection{Source: AST/Node.hpp}
284
285class @ast::Node@ is the base class of all new-ast node classes, which implements
286reference counting mechanism. Two different counters are recorded: strong'' reference
287count for number of nodes semantically owning it; weak'' reference count for number of
288nodes holding a mere reference and only need to observe changes.
289class @ast::ptr_base@ is the smart pointer implementation and also takes care of
290resource management.
291
292Direct access through the smart pointer is read-only. A mutable access should be obtained
293by calling shallowCopy or mutate as below.
294
295Currently, the weak pointers are only used to reference declaration nodes from a named
296type, or a variable expression. Since declaration nodes are intended to denote unique
297entities in the program, weak pointers always point to unique (unshared) nodes. This may
298change in the future, and weak references to shared nodes may introduce some problems;
299see mutate function below.
300
301All node classes should always use smart pointers in the structure and should not use raw
302pointers.
303
304\begin{C++}
305void ast::Node::increment(ref_type ref)
306\end{C++}
307Increments this node's strong or weak reference count.
308\begin{C++}
309void ast::Node::decrement(ref_type ref, bool do_delete = true)
310\end{C++}
311Decrements this node's strong or weak reference count. If strong reference count reaches
312zero, the node is deleted by default.
313\NOTE: Setting @do_delete@ to false may result in a detached node. Subsequent code should
314manually delete the node or assign it to a strong pointer to prevent memory leak.
315Reference counting functions are internally called by @ast::ptr_base@.
316\begin{C++}
317template<typename node_t>
318node_t * shallowCopy(const node_t * node)
319\end{C++}
320Returns a mutable, shallow copy of node: all child pointers are pointing to the same child
321nodes.
322\begin{C++}
323template<typename node_t>
324node_t * mutate(const node_t * node)
325\end{C++}
326If node is unique (strong reference count is 1), returns a mutable pointer to the same node.
327Otherwise, returns shallowCopy(node).
328It is an error to mutate a shared node that is weak-referenced. Currently this does not
329happen. The problem may appear once weak pointers to shared nodes (\eg expression
330nodes) are used; special care will be needed.
331
332\NOTE: This naive uniqueness check may not be sufficient in some cases. A discussion of the
333issue is presented at the end of this section.
334\begin{C++}
335template<typename node_t, typename parent_t, typename field_t, typename assn_t>
336const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val)
337\end{C++}
338\begin{C++}
339template<typename node_t, typename parent_t, typename coll_t, typename ind_t,
340                typename field_t>
341const node_t * mutate_field_index(const node_t * node, coll_t parent_t::* field, ind_t i,
342                field_t && val)
343\end{C++}
344Helpers for mutating a field on a node using pointer to member (creates shallow copy
345when necessary).
346
347\subsubsection{Issue: Undetected sharing}
348
349The @mutate@ behavior described above has a problem: deeper shared nodes may be
350mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
351\begin{figure}
352\centering
353\input{DeepNodeSharing}
354\caption{Deep sharing of nodes}
355\label{f:DeepNodeSharing}
356\end{figure}
357Suppose that we are working on the tree rooted at P1, which
358is logically the chain P1-A-B and P2 is irrelevant, and then
359mutate(B) is called. The algorithm considers B as unique since
360it is only directly owned by A. However, the other tree P2-A-B
361indirectly shares the node B and is therefore wrongly mutated.
362
363To partly address this problem, if the mutation is called higher up the tree, a chain
364mutation helper can be used:
365
366\subsubsection{Source: AST/Chain.hpp}
367
368\begin{C++}
369template<typename node_t, Node::ref_type ref_t>
370auto chain_mutate(ptr_base<node_t, ref_t> & base)
371\end{C++}
372This function returns a chain mutator handle which takes pointer-to-member to go down
373the tree while creating shallow copies as necessary; see @struct _chain_mutator@ in the
374source code for details.
375
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:
378\begin{C++}
379chain_mutate(P1.a)(&A.b) = new_value_of_b;
380\end{C++}
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.
392
393
394\vspace*{20pt} % FIX ME, spacing problem with this heading ???
395\section{Compiler Algorithm Documentation}
396
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.
400
401\subsection{Symbol Table}
402
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.
410
411\subsubsection{Source: AST/SymbolTable.hpp}
412
413\subsubsection{Source: SymTab/Indexer.h}
414
415\begin{C++}
417\end{C++}
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{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}, Section 5.1} while
421by type. Naming conflicts are handled by mangled names; lookup by name returns a list of
422declarations with the same literal identifier name.
423
424\begin{C++}
429\end{C++}
430Adds a tag type declaration to the symbol table.
431\begin{C++}
433\end{C++}
434Adds a typedef alias to the symbol table.
435
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:
440\begin{C++}
441struct A {};
442typedef int A;
443// gcc: ok, cfa: Cannot redefine typedef A
444\end{C++}
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:
449\begin{C++}
450typedef int A;
451void A();
452// gcc: A redeclared as different kind of symbol, cfa: ok
453\end{C++}
454
455\subsection{Type Environment and Unification}
456
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
461environments.
462
463The unification algorithm is recursive in nature and runs in two different modes internally:
464\begin{itemize}
465\item
466\textbf{Exact} unification mode requires equivalent parameters to match perfectly;
467\item
468\textbf{Inexact} unification mode allows equivalent parameters to be converted to a
469common type.
470\end{itemize}
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.
473
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.
479
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)@.
485
486The resolver should use the following `@public@'' functions:\footnote{
487Actual code also tracks assertions on type parameters; those extra arguments are omitted here for
488conciseness.}
489
490
491\subsubsection{Source: ResolvExpr/Unify.cc}
492
493\begin{C++}
494bool unify(const Type *type1, const Type *type2, TypeEnvironment &env,
495OpenVarSet &openVars, const SymbolTable &symtab, Type *&commonType)
496\end{C++}
497Attempts to unify @type1@ and @type2@ with current type environment.
498
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.
501
502If operation fails, returns false.
503\begin{C++}
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)
508\end{C++}
509
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.}
513
514The call has no side effect.
515
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.
518
519
520\subsection{Expression Resolution}
521
522The design of the current version of expression resolver is outlined in the Ph.D. Thesis from
523Aaron Moss~\cite{Moss19}.
524
525A summary of the resolver algorithm for each expression type is presented below.
526
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:
530\begin{enumerate}
531\item
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.
535\item
536Valid interpretations with the minimum sum of argument costs are kept.
537\item
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.
540\item
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.
546\end{enumerate}
547Therefore, for each return type, the resolver produces either of:
548\begin{itemize}
549\item
550No alternatives
551\item
552A single valid alternative
553\item
554An ambiguous alternative
555\end{itemize}
556Note that an ambiguous alternative may be discarded at the parent expressions because a
557different return type matches better for the parent expressions.
558
560expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional
561expression (@?:@).
562
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.
568
569For an address-of expression, only lvalue results are kept and the minimum cost is selected.
570
571For logical expressions @&&@ and @||@, arguments are implicitly cast to bool, and follow the rule
572of cast expression as above.
573
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.
578
579TODO: Write a specification for expression costs.
580
581
582\subsection{Assertion Satisfaction}
583
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.
587
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:
592\begin{C++}
593forall (otype T | {void foo(T);})
594void bar (T t) { foo(t); }
595\end{C++}
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.
599
600\textbf{TODO}: Explain how recursive assertion satisfaction and polymorphic recursion work.
601
602
603\section{Tests}
604
605\subsection{Test Suites}
606
607Automatic test suites are located under the @tests/@ directory. A test case consists of an
608input CFA source file (name ending with @.cfa@), 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:
611\begin{C++}
612tests/
613..     tuple/
614......     .expect/
615..........       tupleCast.txt
616......     tupleCast.cfa
617\end{C++}
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 @test.py@ 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.
623
624
625\subsection{Performance Reports}
626
627To turn on performance reports, pass @-S@ flag to the compiler.
628
6293 kinds of performance reports are available:
630\begin{enumerate}
631\item
632Time, reports time spent in each compilation step
633\item
634Heap, reports number of dynamic memory allocations, total bytes allocated, and
635maximum heap memory usage
636\item
637Counters, for certain predefined statistics; counters can be registered anywhere in
638the compiler as a static object, and the interface can be found at
639@Common/Stats/Counter.h@.
640\end{enumerate}
641It is suggested to run performance tests with optimized build (@g++@ flag @-O3@)
642
643
644\bibliographystyle{plain}
645\bibliography{pl}
646
647
648\end{document}
649
650% Local Variables: %
651% tab-width: 4 %
652% fill-column: 100 %
653% compile-command: "make" %
654% End: %
Note: See TracBrowser for help on using the repository browser.