[ae45007] | 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 |
---|
| 17 | \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref} |
---|
| 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}}} |
---|
[a75d464] | 27 | \newcommand{\NOTE}{\textbf{NOTE}} |
---|
[ae45007] | 28 | |
---|
| 29 | \setlength{\topmargin}{-0.45in} % move running title into header |
---|
| 30 | \setlength{\headsep}{0.25in} |
---|
| 31 | |
---|
| 32 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 33 | |
---|
[a75d464] | 34 | \CFADefaults |
---|
| 35 | \lstset{ |
---|
| 36 | language=C++, % make C++ the default language |
---|
| 37 | escapechar=\$, % LaTeX escape in CFA code |
---|
| 38 | moredelim=**[is][\color{red}]{`}{`}, |
---|
| 39 | }% lstset |
---|
| 40 | \lstMakeShortInline@% |
---|
[ae45007] | 41 | \lstnewenvironment{C++}[1][] % use C++ style |
---|
| 42 | {\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}} |
---|
| 43 | {} |
---|
| 44 | |
---|
| 45 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 46 | |
---|
| 47 | \setcounter{secnumdepth}{3} % number subsubsections |
---|
| 48 | \setcounter{tocdepth}{3} % subsubsections in table of contents |
---|
| 49 | \makeindex |
---|
| 50 | |
---|
| 51 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 52 | |
---|
| 53 | \title{\Huge |
---|
| 54 | cfa-cc Developer's Reference |
---|
| 55 | }% title |
---|
| 56 | |
---|
| 57 | \author{\LARGE |
---|
| 58 | Fangren Yu |
---|
| 59 | }% author |
---|
| 60 | |
---|
| 61 | \date{ |
---|
| 62 | \today |
---|
| 63 | }% date |
---|
| 64 | |
---|
| 65 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 66 | |
---|
| 67 | \begin{document} |
---|
| 68 | \pagestyle{headings} |
---|
| 69 | % changed after setting pagestyle |
---|
| 70 | \renewcommand{\sectionmark}[1]{\markboth{\thesection\quad #1}{\thesection\quad #1}} |
---|
| 71 | \renewcommand{\subsectionmark}[1]{\markboth{\thesubsection\quad #1}{\thesubsection\quad #1}} |
---|
| 72 | \pagenumbering{roman} |
---|
| 73 | \linenumbers % comment out to turn off line numbering |
---|
| 74 | |
---|
| 75 | \maketitle |
---|
| 76 | \pdfbookmark[1]{Contents}{section} |
---|
| 77 | \tableofcontents |
---|
| 78 | |
---|
| 79 | \clearpage |
---|
| 80 | \thispagestyle{plain} |
---|
| 81 | \pagenumbering{arabic} |
---|
| 82 | |
---|
| 83 | |
---|
| 84 | \section{Overview} |
---|
| 85 | |
---|
[a75d464] | 86 | cfa-cc is the reference compiler for the \CFA programming language, which is a non- |
---|
[ae45007] | 87 | object-oriented extension to C. |
---|
[a75d464] | 88 | \CFA attempts to introduce productive modern programming language features to C |
---|
[ae45007] | 89 | while maintaining as much backward-compatibility as possible, so that most existing C |
---|
[a75d464] | 90 | programs can seamlessly work with \CFA. |
---|
[ae45007] | 91 | |
---|
[a75d464] | 92 | Since the \CFA project was dated back to the early 2000s, and only restarted in the past |
---|
[ae45007] | 93 | few years, there is a significant amount of legacy code in the current compiler codebase, |
---|
| 94 | with little proper documentation available. This becomes a difficulty while developing new |
---|
| 95 | features based on the previous implementations, and especially while diagnosing |
---|
| 96 | problems. |
---|
| 97 | |
---|
[a75d464] | 98 | Currently, the \CFA team is also facing another problem: bad compiler performance. For |
---|
[ae45007] | 99 | the development of a new programming language, writing a standard library is an |
---|
| 100 | important part. The incompetence of the compiler causes building the library files to take |
---|
| 101 | tens of minutes, making iterative development and testing almost impossible. There is |
---|
| 102 | ongoing effort to rewrite the core data structure of the compiler to overcome the |
---|
| 103 | performance issue, but many bugs may appear during the work, and lack of documentation |
---|
| 104 | makes debugging extremely difficult. |
---|
| 105 | |
---|
| 106 | This developer's reference will be continuously improved and eventually cover the |
---|
| 107 | compiler codebase. For now, the focus is mainly on the parts being rewritten, and also the |
---|
| 108 | performance bottleneck, namely the resolution algorithm. It is aimed to provide new |
---|
| 109 | developers to the project enough guidance and clarify the purposes and behavior of certain |
---|
[a75d464] | 110 | functions which are not mentioned in the previous \CFA research papers. |
---|
[ae45007] | 111 | |
---|
| 112 | |
---|
| 113 | \section{Compiler Framework} |
---|
| 114 | |
---|
| 115 | \subsection{AST Representation} |
---|
| 116 | |
---|
| 117 | Source code input is first transformed into abstract syntax tree (AST) representation by the |
---|
| 118 | parser before analyzed by the compiler. |
---|
| 119 | |
---|
| 120 | There are 4 major categories of AST nodes used by the compiler, along with some derived |
---|
| 121 | structures. |
---|
| 122 | |
---|
[d1864da] | 123 | \subsubsection{Declaration nodes} |
---|
[ae45007] | 124 | |
---|
| 125 | A declaration node represents either of: |
---|
| 126 | \begin{itemize} |
---|
| 127 | \item |
---|
| 128 | Type declaration: struct, union, typedef or type parameter (see Appendix A.3) |
---|
| 129 | \item |
---|
| 130 | Variable declaration |
---|
| 131 | \item |
---|
| 132 | Function declaration |
---|
| 133 | \end{itemize} |
---|
| 134 | Declarations are introduced by standard C declarations, with the usual scoping rules. |
---|
| 135 | In addition, declarations can also be introduced by the forall clause (which is the origin |
---|
[a75d464] | 136 | of \CFA's name): |
---|
[ae45007] | 137 | \begin{cfa} |
---|
| 138 | forall (<$\emph{TypeParameterList}$> | <$\emph{AssertionList}$>) |
---|
| 139 | $\emph{declaration}$ |
---|
| 140 | \end{cfa} |
---|
[a75d464] | 141 | Type parameters in \CFA are similar to \CC template type parameters. The \CFA |
---|
[ae45007] | 142 | declaration |
---|
| 143 | \begin{cfa} |
---|
| 144 | forall (dtype T) ... |
---|
| 145 | \end{cfa} |
---|
| 146 | behaves similarly as the \CC template declaration |
---|
| 147 | \begin{C++} |
---|
| 148 | template <typename T> ... |
---|
| 149 | \end{C++} |
---|
| 150 | |
---|
[a75d464] | 151 | Assertions are a distinctive feature of \CFA: contrary to the \CC template where |
---|
| 152 | arbitrary functions and operators can be used in a template definition, in a \CFA |
---|
[ae45007] | 153 | parametric function, operations on parameterized types must be declared in assertions. |
---|
| 154 | |
---|
| 155 | Consider the following \CC template: |
---|
| 156 | \begin{C++} |
---|
| 157 | template <typename T> int foo(T t) { |
---|
| 158 | return bar(t) + baz(t); |
---|
| 159 | } |
---|
| 160 | \end{C++} |
---|
| 161 | Unless bar and baz are also parametric functions taking any argument type, they must be |
---|
| 162 | declared in the assertions, or otherwise the code will not compile: |
---|
| 163 | \begin{cfa} |
---|
| 164 | forall (dtype T | { int bar(T); int baz(t); }) int foo (T t) { |
---|
| 165 | return bar(t) + baz(t); |
---|
| 166 | } |
---|
| 167 | \end{cfa} |
---|
| 168 | Assertions are written using the usual function declaration syntax. The scope of type |
---|
| 169 | parameters and assertions is the following declaration. |
---|
| 170 | |
---|
[d1864da] | 171 | \subsubsection{Type nodes} |
---|
[ae45007] | 172 | |
---|
| 173 | A type node represents the type of an object or expression. |
---|
| 174 | Named types reference the corresponding type declarations. The type of a function is its |
---|
| 175 | function pointer type (same as standard C). |
---|
| 176 | With the addition of type parameters, named types may contain a list of parameter values |
---|
| 177 | (actual parameter types). |
---|
| 178 | |
---|
[d1864da] | 179 | \subsubsection{Statement nodes} |
---|
[ae45007] | 180 | |
---|
| 181 | Statement nodes represent the statements in the program, including basic expression |
---|
| 182 | statements, control flows and blocks. |
---|
| 183 | Local declarations (within a block statement) are represented as declaration statements. |
---|
| 184 | |
---|
[d1864da] | 185 | \subsubsection{Expression nodes} |
---|
[ae45007] | 186 | |
---|
| 187 | Some expressions are represented differently in the compiler before and after resolution |
---|
| 188 | stage: |
---|
| 189 | \begin{itemize} |
---|
| 190 | \item |
---|
| 191 | Name expressions: NameExpr pre-resolution, VariableExpr post-resolution |
---|
| 192 | \item |
---|
| 193 | Member expressions: UntypedMemberExpr pre-resolution, MemberExpr post-resolution |
---|
| 194 | \item |
---|
| 195 | Function call expressions (including overloadable operators): UntypedExpr pre-resolution, ApplicationExpr post-resolution |
---|
| 196 | \end{itemize} |
---|
| 197 | The pre-resolution representations contain only the symbols. Post-resolution results link |
---|
| 198 | them to the actual variable and function declarations. |
---|
| 199 | |
---|
| 200 | |
---|
| 201 | \subsection{Compilation Passes} |
---|
| 202 | |
---|
| 203 | Compilation steps are implemented as passes, which follows a general structural recursion |
---|
| 204 | pattern on the syntax tree. |
---|
| 205 | |
---|
| 206 | The basic work flow of compilation passes follows preorder and postorder traversal on |
---|
| 207 | tree data structure, implemented with visitor pattern, and can be loosely described with |
---|
| 208 | the following pseudocode: |
---|
[a75d464] | 209 | \begin{C++} |
---|
[ae45007] | 210 | Pass::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 | } |
---|
[a75d464] | 217 | \end{C++} |
---|
[ae45007] | 218 | Operations in previsit() happen in preorder (top to bottom) and operations in |
---|
| 219 | postvisit() happen in postorder (bottom to top). The precise order of recursive |
---|
| 220 | operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and |
---|
| 221 | @AST/Pass.impl.hpp@ (new). |
---|
| 222 | Implementations of compilation passes need to follow certain conventions: |
---|
| 223 | \begin{itemize} |
---|
| 224 | \item |
---|
| 225 | Passes \textbf{should not} directly override the visit method (Non-virtual Interface |
---|
| 226 | principle); if a pass desires different recursion behavior, it should set |
---|
| 227 | @visit_children@ to false and perform recursive calls manually within previsit or |
---|
| 228 | postvisit procedures. To enable this option, inherit from @WithShortCircuiting@ mixin. |
---|
| 229 | \item |
---|
| 230 | previsit may mutate the node but \textbf{must not} change the node type or return null. |
---|
| 231 | \item |
---|
| 232 | postvisit may mutate the node, reconstruct it to a different node type, or delete it by |
---|
| 233 | returning null. |
---|
| 234 | \item |
---|
| 235 | If the previsit or postvisit method is not defined for a node type, the step is skipped. |
---|
| 236 | If the return type is declared as void, the original node is returned by default. These |
---|
| 237 | behaviors are controlled by template specialization rules; see |
---|
| 238 | @Common/PassVisitor.proto.h@ (old) and @AST/Pass.proto.hpp@ (new) for details. |
---|
| 239 | \end{itemize} |
---|
| 240 | Other useful mixin classes for compilation passes include: |
---|
| 241 | \begin{itemize} |
---|
| 242 | \item |
---|
| 243 | WithGuards allows saving values of variables and restore automatically upon exiting |
---|
| 244 | the current node. |
---|
| 245 | \item |
---|
| 246 | WithVisitorRef creates a wrapped entity of current pass (the actual argument |
---|
| 247 | passed to recursive calls internally) for explicit recursion, usually used together |
---|
| 248 | with WithShortCircuiting. |
---|
| 249 | \item |
---|
| 250 | WithSymbolTable gives a managed symbol table with built-in scoping rule handling |
---|
[a75d464] | 251 | (\eg on entering and exiting a block statement) |
---|
[ae45007] | 252 | \end{itemize} |
---|
[a75d464] | 253 | \NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading |
---|
[ae45007] | 254 | resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures |
---|
| 255 | to its own scope, or otherwise they will not be picked up by template resolution: |
---|
[a75d464] | 256 | \begin{C++} |
---|
[ae45007] | 257 | class Pass2: public Pass1 { |
---|
| 258 | using Pass1::previsit; |
---|
| 259 | using Pass1::postvisit; |
---|
| 260 | // new procedures |
---|
| 261 | } |
---|
[a75d464] | 262 | \end{C++} |
---|
[ae45007] | 263 | |
---|
| 264 | |
---|
| 265 | \subsection{Data Structure Change WIP (new-ast)} |
---|
| 266 | |
---|
| 267 | It has been observed that excessive copying of syntax tree structures accounts for a |
---|
| 268 | majority of computation cost and significantly slows down the compiler. In the previous |
---|
| 269 | implementation of the syntax tree, every internal node has a unique parent; therefore all |
---|
| 270 | copies are required to duplicate everything down to the bottom. A new, experimental |
---|
| 271 | re-implementation of the syntax tree (source under directory AST/ hereby referred to as |
---|
| 272 | ``new-ast'') attempts to overcome this issue with a functional approach that allows sharing |
---|
| 273 | of common sub-structures and only makes copies when necessary. |
---|
| 274 | |
---|
| 275 | The core of new-ast is a customized implementation of smart pointers, similar to |
---|
[a75d464] | 276 | @std::shared_ptr@ and @std::weak_ptr@ in \CC standard library. Reference counting is |
---|
[ae45007] | 277 | used to detect sharing and allows optimization. For a purely functional (a.k.a. immutable) |
---|
| 278 | data structure, all mutations are modelled by shallow copies along the path of mutation. |
---|
| 279 | With reference counting optimization, unique nodes are allowed to be mutated in place. |
---|
| 280 | This however, may potentially introduce some complications and bugs; a few issues are |
---|
| 281 | discussed near the end of this section. |
---|
| 282 | |
---|
[d1864da] | 283 | \subsubsection{Source: AST/Node.hpp} |
---|
[ae45007] | 284 | |
---|
| 285 | class @ast::Node@ is the base class of all new-ast node classes, which implements |
---|
| 286 | reference counting mechanism. Two different counters are recorded: ``strong'' reference |
---|
| 287 | count for number of nodes semantically owning it; ``weak'' reference count for number of |
---|
| 288 | nodes holding a mere reference and only need to observe changes. |
---|
| 289 | class @ast::ptr_base@ is the smart pointer implementation and also takes care of |
---|
| 290 | resource management. |
---|
| 291 | |
---|
| 292 | Direct access through the smart pointer is read-only. A mutable access should be obtained |
---|
| 293 | by calling shallowCopy or mutate as below. |
---|
| 294 | |
---|
| 295 | Currently, the weak pointers are only used to reference declaration nodes from a named |
---|
| 296 | type, or a variable expression. Since declaration nodes are intended to denote unique |
---|
| 297 | entities in the program, weak pointers always point to unique (unshared) nodes. This may |
---|
| 298 | change in the future, and weak references to shared nodes may introduce some problems; |
---|
| 299 | see mutate function below. |
---|
| 300 | |
---|
| 301 | All node classes should always use smart pointers in the structure and should not use raw |
---|
| 302 | pointers. |
---|
| 303 | |
---|
[d1864da] | 304 | \begin{C++} |
---|
| 305 | void ast::Node::increment(ref_type ref) |
---|
| 306 | \end{C++} |
---|
| 307 | Increments this node's strong or weak reference count. |
---|
| 308 | \begin{C++} |
---|
| 309 | void ast::Node::decrement(ref_type ref, bool do_delete = true) |
---|
| 310 | \end{C++} |
---|
| 311 | Decrements this node's strong or weak reference count. If strong reference count reaches |
---|
| 312 | zero, the node is deleted by default. |
---|
[a75d464] | 313 | \NOTE: Setting @do_delete@ to false may result in a detached node. Subsequent code should |
---|
[d1864da] | 314 | manually delete the node or assign it to a strong pointer to prevent memory leak. |
---|
| 315 | Reference counting functions are internally called by @ast::ptr_base@. |
---|
| 316 | \begin{C++} |
---|
| 317 | template<typename node_t> |
---|
| 318 | node_t * shallowCopy(const node_t * node) |
---|
| 319 | \end{C++} |
---|
| 320 | Returns a mutable, shallow copy of node: all child pointers are pointing to the same child |
---|
| 321 | nodes. |
---|
| 322 | \begin{C++} |
---|
| 323 | template<typename node_t> |
---|
| 324 | node_t * mutate(const node_t * node) |
---|
| 325 | \end{C++} |
---|
| 326 | If node is unique (strong reference count is 1), returns a mutable pointer to the same node. |
---|
| 327 | Otherwise, returns shallowCopy(node). |
---|
| 328 | It is an error to mutate a shared node that is weak-referenced. Currently this does not |
---|
[a75d464] | 329 | happen. The problem may appear once weak pointers to shared nodes (\eg expression |
---|
[d1864da] | 330 | nodes) are used; special care will be needed. |
---|
| 331 | |
---|
[a75d464] | 332 | \NOTE: This naive uniqueness check may not be sufficient in some cases. A discussion of the |
---|
[d1864da] | 333 | issue is presented at the end of this section. |
---|
| 334 | \begin{C++} |
---|
| 335 | template<typename node_t, typename parent_t, typename field_t, typename assn_t> |
---|
| 336 | const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val) |
---|
| 337 | \end{C++} |
---|
| 338 | \begin{C++} |
---|
| 339 | template<typename node_t, typename parent_t, typename coll_t, typename ind_t, |
---|
| 340 | typename field_t> |
---|
| 341 | const node_t * mutate_field_index(const node_t * node, coll_t parent_t::* field, ind_t i, |
---|
| 342 | field_t && val) |
---|
| 343 | \end{C++} |
---|
| 344 | Helpers for mutating a field on a node using pointer to member (creates shallow copy |
---|
| 345 | when necessary). |
---|
| 346 | |
---|
| 347 | \subsubsection{Issue: Undetected sharing} |
---|
| 348 | |
---|
| 349 | The @mutate@ behavior described above has a problem: deeper shared nodes may be |
---|
| 350 | mistakenly 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} |
---|
| 357 | Suppose that we are working on the tree rooted at P1, which |
---|
| 358 | is logically the chain P1-A-B and P2 is irrelevant, and then |
---|
| 359 | mutate(B) is called. The algorithm considers B as unique since |
---|
| 360 | it is only directly owned by A. However, the other tree P2-A-B |
---|
| 361 | indirectly shares the node B and is therefore wrongly mutated. |
---|
| 362 | |
---|
| 363 | To partly address this problem, if the mutation is called higher up the tree, a chain |
---|
| 364 | mutation helper can be used: |
---|
| 365 | |
---|
| 366 | \subsubsection{Source: AST/Chain.hpp} |
---|
| 367 | |
---|
| 368 | \begin{C++} |
---|
| 369 | template<typename node_t, Node::ref_type ref_t> |
---|
| 370 | auto chain_mutate(ptr_base<node_t, ref_t> & base) |
---|
| 371 | \end{C++} |
---|
| 372 | This function returns a chain mutator handle which takes pointer-to-member to go down |
---|
| 373 | the tree while creating shallow copies as necessary; see @struct _chain_mutator@ in the |
---|
| 374 | source code for details. |
---|
| 375 | |
---|
[a75d464] | 376 | For 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++} |
---|
| 379 | chain_mutate(P1.a)(&A.b) = new_value_of_b; |
---|
| 380 | \end{C++} |
---|
| 381 | Note that if some node in chain mutate is shared (therefore shallow copied), it implies that |
---|
| 382 | every node further down will also be copied, thus correctly executing the functional |
---|
| 383 | mutation algorithm. This example code creates copies of both A and B and performs |
---|
| 384 | mutation on the new nodes, so that the other tree P2-A-B is untouched. |
---|
| 385 | However, 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 |
---|
| 387 | experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up, |
---|
| 388 | this issue does not actually happen. It should be addressed in the future when other |
---|
| 389 | compilation passes are migrated to new-ast and many of them contain procedural |
---|
| 390 | mutations, 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 | |
---|
| 397 | This documentation currently covers most of the resolver, data structures used in variable |
---|
| 398 | and expression resolution, and a few directly related passes. Later passes involving code |
---|
| 399 | generation 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 |
---|
| 404 | old implementation. Hereby we will be using the name SymbolTable everywhere. |
---|
| 405 | The symbol table stores a mapping from names to declarations and implements a similar |
---|
| 406 | name 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 |
---|
| 407 | name space rule is that typedef aliases are no longer considered ordinary identifiers. |
---|
| 408 | In addition to C tag types (struct, union, enum), \CFA introduces another tag type, trait, |
---|
| 409 | which is a named collection of assertions. |
---|
| 410 | |
---|
| 411 | \subsubsection{Source: AST/SymbolTable.hpp} |
---|
| 412 | |
---|
| 413 | \subsubsection{Source: SymTab/Indexer.h} |
---|
| 414 | |
---|
| 415 | \begin{C++} |
---|
| 416 | SymbolTable::addId(const DeclWithType * decl) |
---|
| 417 | \end{C++} |
---|
| 418 | Since \CFA allows overloading of variables and functions, ordinary identifier names need |
---|
| 419 | to 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 |
---|
| 420 | making adaptations to \CFA specific features, mainly assertions and overloaded variables |
---|
| 421 | by type. Naming conflicts are handled by mangled names; lookup by name returns a list of |
---|
| 422 | declarations with the same literal identifier name. |
---|
| 423 | |
---|
| 424 | \begin{C++} |
---|
| 425 | SymbolTable::addStruct(const StructDecl * decl) |
---|
| 426 | SymbolTable::addUnion(const UnionDecl * decl) |
---|
| 427 | SymbolTable::addEnum(const EnumDecl * decl) |
---|
| 428 | SymbolTable::addTrait(const TraitDecl * decl) |
---|
| 429 | \end{C++} |
---|
| 430 | Adds a tag type declaration to the symbol table. |
---|
| 431 | \begin{C++} |
---|
| 432 | SymbolTable::addType(const NamedTypeDecl * decl) |
---|
| 433 | \end{C++} |
---|
| 434 | Adds a typedef alias to the symbol table. |
---|
| 435 | |
---|
| 436 | \textbf{C Incompatibility Note}: Since Cforall allows using struct, union and enum type names |
---|
| 437 | without the keywords, typedef names and tag type names cannot be disambiguated by |
---|
| 438 | syntax rules. Currently the compiler puts them together and disallows collision. The |
---|
| 439 | following program is valid C but not valid Cforall: |
---|
| 440 | \begin{C++} |
---|
| 441 | struct A {}; |
---|
| 442 | typedef int A; |
---|
| 443 | // gcc: ok, cfa: Cannot redefine typedef A |
---|
| 444 | \end{C++} |
---|
| 445 | In actual practices however, such usage is extremely rare, and typedef struct A A; is |
---|
| 446 | not considered an error, but silently discarded. Therefore, we expect this change to have |
---|
| 447 | minimal impact on existing C programs. |
---|
| 448 | Meanwhile, the following program is allowed in Cforall: |
---|
| 449 | \begin{C++} |
---|
| 450 | typedef int A; |
---|
| 451 | void A(); |
---|
| 452 | // gcc: A redeclared as different kind of symbol, cfa: ok |
---|
| 453 | \end{C++} |
---|
| 454 | |
---|
| 455 | \subsection{Type Environment and Unification} |
---|
| 456 | |
---|
| 457 | The core of parametric type resolution algorithm. |
---|
| 458 | Type Environment organizes type parameters in \textbf{equivalent classes} and maps them to |
---|
| 459 | actual types. Unification is the algorithm that takes two (possibly parametric) types and |
---|
| 460 | parameter mappings and attempts to produce a common type by matching the type |
---|
| 461 | environments. |
---|
| 462 | |
---|
| 463 | The 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 |
---|
| 469 | common type. |
---|
| 470 | \end{itemize} |
---|
| 471 | For 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 | |
---|
| 474 | Within inexact mode, types are allowed to differ on their cv-qualifiers; additionally, if a |
---|
| 475 | type never appear either in parameter list or as the base type of a pointer, it may also be |
---|
| 476 | widened (i.e. safely converted). As Cforall currently does not implement subclassing similar |
---|
| 477 | to object-oriented languages, widening conversions are on primitive types only, for |
---|
| 478 | example the conversion from int to long. |
---|
| 479 | |
---|
| 480 | The need for two unification modes come from the fact that parametric types are |
---|
| 481 | considered compatible only if all parameters are exactly the same (not just compatible). |
---|
| 482 | Pointer types also behaves similarly; in fact, they may be viewed as a primitive kind of |
---|
| 483 | parametric types. @int*@ and @long*@ are different types, just like @vector(int)@ and |
---|
| 484 | @vector(long)@ are, for the parametric type @vector(T)@. |
---|
| 485 | |
---|
| 486 | The resolver should use the following ``@public@'' functions:\footnote{ |
---|
| 487 | Actual code also tracks assertions on type parameters; those extra arguments are omitted here for |
---|
| 488 | conciseness.} |
---|
| 489 | |
---|
| 490 | |
---|
| 491 | \subsubsection{Source: ResolvExpr/Unify.cc} |
---|
| 492 | |
---|
| 493 | \begin{C++} |
---|
| 494 | bool unify(const Type *type1, const Type *type2, TypeEnvironment &env, |
---|
| 495 | OpenVarSet &openVars, const SymbolTable &symtab, Type *&commonType) |
---|
| 496 | \end{C++} |
---|
| 497 | Attempts to unify @type1@ and @type2@ with current type environment. |
---|
| 498 | |
---|
| 499 | If operation succeeds, @env@ is modified by combining the equivalence classes of matching |
---|
| 500 | parameters in @type1@ and @type2@, and their common type is written to commonType. |
---|
| 501 | |
---|
| 502 | If operation fails, returns false. |
---|
| 503 | \begin{C++} |
---|
| 504 | bool typesCompatible(const Type * type1, const Type * type2, const |
---|
| 505 | SymbolTable &symtab, const TypeEnvironment &env) |
---|
| 506 | bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type * |
---|
| 507 | type2, const SymbolTable &symtab, const TypeEnvironment &env) |
---|
| 508 | \end{C++} |
---|
| 509 | |
---|
| 510 | Determines if type1 and type2 can possibly be the same type. The second version ignores |
---|
| 511 | the outermost cv-qualifiers if present.\footnote{ |
---|
| 512 | In const \lstinline@int * const@, only the second \lstinline@const@ is ignored.} |
---|
| 513 | |
---|
| 514 | The call has no side effect. |
---|
| 515 | |
---|
| 516 | \NOTE: No attempts are made to widen the types (exact unification is used), although the |
---|
| 517 | function names may suggest otherwise. E.g. @typesCompatible(int, long)@ returns false. |
---|
| 518 | |
---|
| 519 | |
---|
| 520 | \subsection{Expression Resolution} |
---|
| 521 | |
---|
| 522 | The design of the current version of expression resolver is outlined in the Ph.D. Thesis from |
---|
| 523 | Aaron Moss~\cite{Moss19}. |
---|
| 524 | |
---|
| 525 | A summary of the resolver algorithm for each expression type is presented below. |
---|
| 526 | |
---|
| 527 | All overloadable operators are modelled as function calls. For a function call, |
---|
| 528 | interpretations of the function and arguments are found recursively. Then the following |
---|
| 529 | steps produce a filtered list of valid interpretations: |
---|
| 530 | \begin{enumerate} |
---|
| 531 | \item |
---|
| 532 | From all possible combinations of interpretations of the function and arguments, |
---|
| 533 | those where argument types may be converted to function parameter types are |
---|
| 534 | considered valid. |
---|
| 535 | \item |
---|
| 536 | Valid interpretations with the minimum sum of argument costs are kept. |
---|
| 537 | \item |
---|
| 538 | Argument costs are then discarded; the actual cost for the function call expression is |
---|
| 539 | the sum of conversion costs from the argument types to parameter types. |
---|
| 540 | \item |
---|
| 541 | For each return type, the interpretations with satisfiable assertions are then sorted |
---|
| 542 | by actual cost computed in step 3. If for a given type, the minimum cost |
---|
| 543 | interpretations are not unique, it is said that for that return type the interpretation |
---|
| 544 | is ambiguous. If the minimum cost interpretation is unique but contains an |
---|
| 545 | ambiguous argument, it is also considered ambiguous. |
---|
| 546 | \end{enumerate} |
---|
| 547 | Therefore, for each return type, the resolver produces either of: |
---|
| 548 | \begin{itemize} |
---|
| 549 | \item |
---|
| 550 | No alternatives |
---|
| 551 | \item |
---|
| 552 | A single valid alternative |
---|
| 553 | \item |
---|
| 554 | An ambiguous alternative |
---|
| 555 | \end{itemize} |
---|
| 556 | Note that an ambiguous alternative may be discarded at the parent expressions because a |
---|
| 557 | different return type matches better for the parent expressions. |
---|
| 558 | |
---|
| 559 | The non-overloadable expressions in Cforall are: cast expressions, address-of (unary @&@) |
---|
| 560 | expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional |
---|
| 561 | expression (@?:@). |
---|
| 562 | |
---|
| 563 | For a cast expression, the convertible argument types are kept. Then the result is selected |
---|
| 564 | by lowest argument cost, and further by lowest conversion cost to target type. If the lowest |
---|
| 565 | cost is still not unique, or an ambiguous argument interpretation is selected, the cast |
---|
| 566 | expression is ambiguous. In an expression statement, the top level expression is implicitly |
---|
| 567 | cast to void. |
---|
| 568 | |
---|
| 569 | For an address-of expression, only lvalue results are kept and the minimum cost is selected. |
---|
| 570 | |
---|
| 571 | For logical expressions @&&@ and @||@, arguments are implicitly cast to bool, and follow the rule |
---|
| 572 | of cast expression as above. |
---|
| 573 | |
---|
| 574 | For the ternary conditional expression, the condition is implicitly cast to bool, and the |
---|
| 575 | branch expressions must have compatible types. Each pair of compatible branch |
---|
| 576 | expression types produce a possible interpretation, and the cost is defined as the sum of |
---|
| 577 | expression costs plus the sum of conversion costs to the common type. |
---|
| 578 | |
---|
| 579 | TODO: Write a specification for expression costs. |
---|
| 580 | |
---|
| 581 | |
---|
| 582 | \subsection{Assertion Satisfaction} |
---|
| 583 | |
---|
| 584 | The resolver tries to satisfy assertions on expressions only when it is needed: either while |
---|
| 585 | selecting from multiple alternatives of a same result type for a function call (step 4 of |
---|
| 586 | resolving function calls), or upon reaching the top level of an expression statement. |
---|
| 587 | |
---|
| 588 | Unsatisfiable alternatives are discarded. Satisfiable alternatives receive \textbf{implicit |
---|
| 589 | parameters}: in Cforall, parametric functions are designed such that they can be compiled |
---|
| 590 | separately, as opposed to \CC templates which are only compiled at instantiation. Given a |
---|
| 591 | parametric function definition: |
---|
| 592 | \begin{C++} |
---|
| 593 | forall (otype T | {void foo(T);}) |
---|
| 594 | void bar (T t) { foo(t); } |
---|
| 595 | \end{C++} |
---|
| 596 | The function bar does not know which @foo@ to call when compiled without knowing the call |
---|
| 597 | site, so it requests a function pointer to be passed as an extra argument. At the call site, |
---|
| 598 | implicit 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 | |
---|
| 607 | Automatic test suites are located under the @tests/@ directory. A test case consists of an |
---|
| 608 | input CFA source file (name ending with @.cfa@), and an expected output file located |
---|
| 609 | in @.expect/@ directory relative to the source file, with the same file name ending with @.txt@. |
---|
| 610 | So a test named @tuple/tupleCast@ has the following files, for example: |
---|
| 611 | \begin{C++} |
---|
| 612 | tests/ |
---|
| 613 | .. tuple/ |
---|
| 614 | ...... .expect/ |
---|
| 615 | .......... tupleCast.txt |
---|
| 616 | ...... tupleCast.cfa |
---|
| 617 | \end{C++} |
---|
| 618 | If compilation fails, the error output is compared to the expect file. If compilation succeeds, |
---|
| 619 | the built program is run and its output compared to the expect file. |
---|
| 620 | To run the tests, execute the test script @test.py@ under the @tests/@ directory, with a list of |
---|
| 621 | test names to be run, or @--all@ to run all tests. The test script reports test cases |
---|
| 622 | fail/success, compilation time and program run time. |
---|
| 623 | |
---|
| 624 | |
---|
| 625 | \subsection{Performance Reports} |
---|
| 626 | |
---|
| 627 | To turn on performance reports, pass @-S@ flag to the compiler. |
---|
| 628 | |
---|
| 629 | 3 kinds of performance reports are available: |
---|
| 630 | \begin{enumerate} |
---|
| 631 | \item |
---|
| 632 | Time, reports time spent in each compilation step |
---|
| 633 | \item |
---|
| 634 | Heap, reports number of dynamic memory allocations, total bytes allocated, and |
---|
| 635 | maximum heap memory usage |
---|
| 636 | \item |
---|
| 637 | Counters, for certain predefined statistics; counters can be registered anywhere in |
---|
| 638 | the compiler as a static object, and the interface can be found at |
---|
| 639 | @Common/Stats/Counter.h@. |
---|
| 640 | \end{enumerate} |
---|
| 641 | It is suggested to run performance tests with optimized build (@g++@ flag @-O3@) |
---|
| 642 | |
---|
| 643 | |
---|
[ae45007] | 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: % |
---|