+++ /dev/null
-\documentclass{article}
-
-\usepackage[plainpages=false,colorlinks]{hyperref}
-\usepackage[style=list,toc]{glossary}
-\usepackage{alltt}
-\usepackage{times}
-\usepackage{tabularx}
-\usepackage{epsfig}
-\usepackage{epsf}
-\usepackage{amssymb}
-\usepackage{epstopdf}
-
-\pagestyle{headings}
-
-\setcounter{tocdepth}{3}
-\setcounter{secnumdepth}{3}
-
-\setlength\parskip{\medskipamount}
-\setlength\parindent{0pt}
-
-\newcommand{\bs}{\char'134}
-\newcommand{\dq}{\char'42}
-\newcommand{\tto}{\symbol{123}}
-\newcommand{\ttc}{\symbol{125}}
-\newcommand{\pound}{\char'43}
-
-\newcommand{\vocabulary}[1]{\emph{Vocabulary:} \texttt{#1}&\\}
-
-\newcommand{\parsingword}[2]{\index{\texttt{#1}}\emph{Parsing word:} \texttt{#2}&\\}
-
-\newcommand{\ordinaryword}[2]{\index{\texttt{#1}}\emph{Word:} \texttt{#2}&\\}
-
-\newcommand{\symbolword}[1]{\index{\texttt{#1}}\emph{Symbol:} \texttt{#1}&\\}
-
-\newcommand{\classword}[1]{\index{\texttt{#1}}\emph{Class:} \texttt{#1}&\\}
-
-\newcommand{\genericword}[2]{\index{\texttt{#1}}\emph{Generic word:} \texttt{#2}&\\}
-
-\newcommand{\predword}[1]{\ordinaryword{#1}{#1~( object -- ?~)}}
-
-\setlength{\tabcolsep}{1mm}
-
-\newcommand{\wordtable}[1]{
-
-%HEVEA\renewcommand{\index}[1]{}
-%HEVEA\renewcommand{\glossary}[1]{}
-
-\begin{tabularx}{12cm}{lX}
-\hline
-#1
-\hline
-\end{tabularx}
-
-}
-
-\makeatletter
-
-\makeatother
-
-\begin{document}
-
-\title{The Factor compiler}
-
-\author{Slava Pestov}
-
-\maketitle
-\tableofcontents{}
-
-\section{Stack effect inference}
-
-The stack effect inference tool checks correctness of code before it is run.
-A \emph{stack effect} is a list of input classes and a list of output classes corresponding to
-the effect a quotation has on the stack when called. For example, the stack effect of \verb|[ dup * ]| is \verb|[ [ integer ] [ integer ] ]|. The stack checker is used by passing a quotation to the \texttt{infer} word. It uses a sophisticated algorithm to infer stack effects of recursive words, combinators, and other tricky constructions, however, it cannot infer the stack effect of all words. In particular, anything using continuations, such as \texttt{catch} and I/O, will stump the stack checker.
-
-\subsection{Usage}
-
-The main entry point of the stack checker is a single word.
-
-\wordtable{
-\vocabulary{inference}
-\ordinaryword{infer}{infer ( quot -- effect )}
-}
-
-Takes a quotation and attempts to infer its stack effect. An exception is thrown if the stack effect cannot be inferred.
-
-You can combine unit testing with stack effect inference by writing unit tests that check stack effects of words. In fact, this can be automated with the \texttt{infer>test.} word; it takes a quotation on the stack, and prints a code snippet that tests the stack effect of the quotation:
-
-\begin{alltt}
-\textbf{ok} [ draw-shape ] infer>test.
-\textbf{[ [ [ object ] [ ] ] ]
-[ [ draw-shape ] infer ]
-unit-test}
-\end{alltt}
-
-You can then copy and paste this snippet into a test script, and run the test script after
-making changes to the word to ensure its stack effect signature has not changed.
-
-\subsection{The algorithm}
-
-The stack effect inference algorithm mirrors the interpreter algorithm. A ``meta data stack'' holds two types of entries; computed values, whose type is known but literal value will only be known at runtime, and literals, whose value is known statically. When a literal value is encountered, it is simply placed on the meta data stack. When a word is encountered, one of several actions are taken, depending on the type of the word:
-
-\begin{itemize}
-\item If the word has special stack effect inference behavior, this behavior is invoked. Shuffle words and various primitives fall into this category.
-\item If the word's stack effect is already known, then the inputs are removed from the meta data stack, and output values are added. If the meta data stack contains insufficient values, more values are added, and the newly added values are placed in the input list. Since inference begins with an empty stack, the input list contains all required input values when inference is complete.
-\item If the word is marked to be inlined, stack effect inference recurses into the word definition and uses the same meta data stack. See \ref{declarations}.
-\item Otherwise, the word's stack effect is inferred in a fresh inferencer instance, and the stack effect is cached. The fresh inferencer is used rather than the current one, so that type information and literals on the current meta data stack do not affect the subsequently-cached stack effect.
-\end{itemize}
-
-The following two examples demonstrate some simple cases:
-\begin{alltt}
-\textbf{ok} [ 1 2 3 ] infer .
-\textbf{[ [ ] [ fixnum fixnum fixnum ] ]}
-\textbf{ok} [ "hi" swap ] infer .
-\textbf{[ [ object ] [ string object ] ]}
-\end{alltt}
-
-\subsubsection{Combinators}
-
-A simple combinator such as \verb|keep| does not by itself have a stack effect, since \verb|call| takes an arbitrary quotation from the stack, which itself may have an arbitrary stack effect.
-\begin{verbatim}
-IN: kernel
-: keep ( x quot -- x | quot: x -- )
- over >r call r> ; inline
-\end{verbatim}
-On the other hand, the stack effect of word that passes a literal quotation to \verb|keep| can be inferred. The quotation is a literal on the meta data stack, and since \verb|keep| is marked \verb|inline|, the special inference behavior of \verb|call| receives this quotation.
-\begin{alltt}
-\textbf{ok} [ [ dup * ] keep ] infer .
-\textbf{[ [ number ] [ number number ] ]}
-\end{alltt}
-Note that if \verb|call| is applied to a computed value, for example, a quotation taken from a variable, or a quotation that is constructed immediately before the \verb|call|, the stack effect inferencer will raise an error.
-\begin{alltt}
-\textbf{ok} [ frog get call ] infer .
-\textbf{! Inference error: A literal value was expected where a
-computed value was found: \#<computed @ 716167923>
-! Recursive state:
-:s :r :n :c show stacks at time of error.
-:get ( var -- value ) inspects the error namestack.}
-\end{alltt}
-Another word with special inference behavior is \verb|execute|. It is used much more rarely than \verb|call|, but does pretty much the same thing, except it takes a word as input rather than a string.
-
-\subsubsection{Conditionals}
-
-Simpler than a stack effect is the concept of a stack height difference. This is simply the input value count subtracted from the output value count. A conditional's stack effect can be inferred if each branch has the same stack height difference; in this case, we say that the conditional is \emph{balanced}, and the total stack effect is computed by performing a unification of types across each branch.
-
-The following two examples exhibit balanced conditionals:
-\begin{verbatim}
-[ 1 ] [ dup ] ifte
-dup cons? [ unit ] when cons
-\end{verbatim}
-The following example is not balanced and raises an error when we attempt to infer its stack effect:
-\begin{alltt}
-\textbf{ok} [ [ dup ] [ drop ] ifte ] infer .
-\textbf{! Inference error: Unbalanced branches
-! Recursive state:
-:s :r :n :c show stacks at time of error.
-:get ( var -- value ) inspects the error namestack.}
-\end{alltt}
-
-\subsubsection{Recursive words}
-
-Recursive words all have the same general form; there is a conditional, and one branch of the conditional is the \emph{base case} terminating the recursion, and the other branch is the \emph{inductive case}, which reduces the problem and recurses on the reduced problem. A key observation one must make is that in a well-formed recursion, the recursive call in the inductive case eventually results in the base case being called, so we can take the stack effect of the recursive call to be the stack effect of the base case.
-
-Consider the following implementation of a word that measures the length of a list:
-\begin{verbatim}
-: length ( list -- n )
- [ cdr length 1 + ] [ 0 ] ifte* ;
-\end{verbatim}
-The stack effect can be inferred without difficulty:
-\begin{alltt}
-\textbf{ok} [ length ] infer .
-\textbf{[ [ object ] [ integer ] ]}
-\end{alltt}
-The base case is taken if the top of the stack is \verb|f|, and the base case has a stack effect \verb|[ [ object ] [ fixnum ] ]|.
-
-On the other hand if the top of the stack is something else, the inductive case is taken. The inductive case makes a recursive call to \verb|length|, and once we substitute the stack effect of the base case into this call point, we can infer that the stack effect of the recursive case is \verb|[ [ object ] [ integer ] ]|.
-
-If both branches contain a recursive call, the stack effect inferencer gives up.
-\begin{alltt}
-\textbf{ok} : fie [ fie ] [ fie ] ifte ;
-\textbf{ok} [ fie ] infer .
-\textbf{! Inference error: fie does not have a base case
-! Recursive state:
-:s :r :n :c show stacks at time of error.
-:get ( var -- value ) inspects the error namestack.}
-\end{alltt}
-
-\section{The compiler}
-
-\subsection{Basic usage}
-
-The compiler can provide a substantial speed boost for words whose stack effect can be inferred. Words without a known stack effect cannot be compiled, and must be run in the interpreter. The compiler generates native code, and so far, x86 and PowerPC backends have been developed.
-
-To compile a single word, call \texttt{compile}:
-
-\begin{alltt}
-\textbf{ok} \bs pref-size compile
-\textbf{Compiling pref-size}
-\end{alltt}
-
-During bootstrap, all words in the library with a known stack effect are compiled. You can
-circumvent this, for whatever reason, by passing the \texttt{-no-compile} switch during
-bootstrap:
-
-\begin{alltt}
-\textbf{bash\$} ./f boot.image.le32 -no-compile
-\end{alltt}
-
-The compiler has two limitations you must be aware of. First, if an exception is thrown in compiled code, the return stack will be incomplete, since compiled words do not push themselves there. Second, compiled code cannot be profiled. These limitations will be resolved in a future release.
-
-The compiler consists of multiple stages -- first, a dataflow graph is inferred, then various optimizations are done on this graph, then it is transformed into a linear representation, further optimizations are done, and finally, machine code is generated from the linear representation.
-
-\subsection{Stack effect inference}
-
-While most programming errors in Factor are only caught at runtime, the stack effect checker can be useful for checking correctness of code before it is run. It can also help narrow down problems with stack shuffling. The stack checker is used by passing a quotation to the \texttt{infer} word. It uses a sophisticated algorithm to infer stack effects of recursive words, combinators, and other tricky constructions, however, it cannot infer the stack effect of all words. In particular, anything using continuations, such as \texttt{catch} and I/O, will stump the stack checker. Despite this fault, it is still a useful tool.
-
-\begin{alltt}
-\textbf{ok} [ pile-fill * >fixnum over pref-size dup y
-\texttt{...} [ + ] change ] infer .
-\textbf{[ [ tuple number tuple ] [ tuple fixnum object number ] ]}
-\end{alltt}
-
-The stack checker will report an error if it cannot infer the stack effect of a quotation. The ``recursive state'' dump is similar to a return stack, but it is not a real return stack, since only a code walk is taking place, not full evaluation. Understanding recursive state dumps is an art, much like understanding return stacks.
-
-\begin{alltt}
-\textbf{ok} [ 100 [ f f cons ] repeat ] infer .
-\textbf{! Inference error: Unbalanced branches
-! Recursive state:
-! [ (repeat) G:54044 pick pick >= [ 3drop ]
- [ [ swap >r call 1 + r> ] keep (repeat) ] ifte ]
-! [ repeat G:54042 0 -rot (repeat) ]
-:s :r :n :c show stacks at time of error.
-:get ( var -- value ) inspects the error namestack.}
-\end{alltt}
-
-One reason stack inference might fail is if the quotation contains unbalanced branches, as above. For the inference to work, both branches of a conditional must exit with the same stack height.
-
-Another situation when it fails is if your code calls quotations that are not statically known. This can happen if the word in question uses continuations, or if it pulls a quotation from a variable and calls it. This can also happen if you wrote your own combinator, but forgot to mark it as \texttt{inline}. For example, the following will fail:
-
-\begin{alltt}
-\textbf{ok} : dip swap >r call r> ;
-\textbf{ok} [ [ + ] dip * ] infer .
-! Inference error: A literal value was expected where a
-computed value was found: \#<computed @ 679711507>
-...
-\end{alltt}
-
-However, defining \texttt{dip} to be inlined will work:
-
-\begin{alltt}
-\textbf{ok} : dip swap >r call r> ; inline
-\textbf{ok} [ [ + ] dip * ] infer .
-\textbf{[ [ number number number ] [ number ] ]}
-\end{alltt}
-
-You can combine unit testing with stack effect inference by writing unit tests that check stack effects of words. In fact, this can be automated with the \texttt{infer>test.} word; it takes a quotation on the stack, and prints a code snippet that tests the stack effect of the quotation:
-
-\begin{alltt}
-\textbf{ok} [ draw-shape ] infer>test.
-\textbf{[ [ [ object ] [ ] ] ]
-[ [ draw-shape ] infer ]
-unit-test}
-\end{alltt}
-
-You can then copy and paste this snippet into a test script, and run the test script after
-making changes to the word to ensure its stack effect signature has not changed.
-
-\subsection{Linear intermediate representation}
-
-The linear IR is the second of the two intermediate
-representations used by Factor. It is basically a high-level
-assembly language. Linear IR operations are called VOPs. The last stage of the compiler generates machine code instructions corresponding to each \emph{virtual operation} in the linear IR.
-
-To perform everything except for the machine code generation, use the \texttt{precompile} word. This will dump the optimized linear IR instead of generating code, which can be useful sometimes.
-
-\begin{alltt}
-\textbf{ok} \bs append precompile
-\textbf{<< \%prologue << vop [ ] [ ] [ ] [ ] >> >>
-<< \%peek-d << vop [ ] [ 1 ] [ << vreg ... 0 >> ] [ ] >> >>
-<< \%peek-d << vop [ ] [ 0 ] [ << vreg ... 1 >> ] [ ] >> >>
-<< \%replace-d << vop [ ] [ 0 << vreg ... 0 >> ] [ ] [ ] >> >>
-<< \%replace-d << vop [ ] [ 1 << vreg ... 1 >> ] [ ] [ ] >> >>
-<< \%inc-d << vop [ ] [ -1 ] [ ] [ ] >> >>
-<< \%return << vop [ ] [ ] [ ] [ ] >> >>}
-\end{alltt}
-
-\subsubsection{Control flow}
-
-\begin{description}
-
-\item[\texttt{\%prologue}] On x86, this does nothing. On PowerPC, at the start of
- each word that calls a subroutine, we store the link
- register in r0, then push r0 on the C stack.
-
-\item[\texttt{\%call-label}] On PowerPC, uses near calling convention, where the
- caller pushes the return address.
-
-\item[\texttt{\%call}] On PowerPC, if calling a primitive, compiles a sequence that loads a 32-bit literal and jumps to that address. For other compiled words, compiles an immediate branch with link, so all compiled word definitions must be within 64 megabytes of each other.
-
-\item[\texttt{\%jump-label}] Like \texttt{\%call-label} except the return address is not saved. Used for tail calls.
-
-\item[\texttt{\%jump}] Like \texttt{\%call} except the return address is not saved. Used for tail calls.
-
-\item[\texttt{\%dispatch}] Compile a piece of code that jumps to an offset in a
- jump table indexed by an integer. The jump table consists of \texttt{\%target-label} and \texttt{\%target} must immediately follow this VOP.
-
-\item[\texttt{\%target}] Not supported on PowerPC.
-
-\item[\texttt{\%target-label}] A jump table entry.
-
-\end{description}
-
-\subsubsection{Slots and objects}
-
-\begin{description}
-
-\item[\texttt{\%slot}] The untagged object is in \texttt{vop-out-1}, the tagged slot
- number is in \texttt{vop-in-1}.
-
-\item[\texttt{\%fast-slot}] The tagged object is in \texttt{vop-out-1}, the pointer offset is
- in \texttt{vop-in-1}. the offset already takes the type tag into
- account, so its just one instruction to load.
-
-\item[\texttt{\%set-slot}] The new value is \texttt{vop-in-1}, the object is \texttt{vop-in-2}, and
- the slot number is \texttt{vop-in-3}.
-
-\item[\texttt{\%fast-set-slot}] The new value is \texttt{vop-in-1}, the object is \texttt{vop-in-2}, and
- the slot offset is \texttt{vop-in-3}.
- the offset already takes the type tag into account, so
- it's just one instruction to load.
-
-\item[\texttt{\%write-barrier}] Mark the card containing the object pointed by \texttt{vop-in-1}.
-
-\item[\texttt{\%untag}] Mask off the tag bits of \texttt{vop-in-1}, store result in
- \texttt{vop-in-1} (which should equal \texttt{vop-out-1}!)
-
-\item[\texttt{\%untag-fixnum}] Shift \texttt{vop-in-1} to the right by 3 bits, store result in
- \texttt{vop-in-1} (which should equal \texttt{vop-out-1}!)
-
-\item[\texttt{\%type}] Intrinstic version of type primitive. It outputs an
- unboxed value in \texttt{vop-out-1}.
-
-\end{description}
-
-\subsubsection{Alien interface}
-
-\begin{description}
-
-\item[\texttt{\%parameters}] Ignored on x86.
-
-\item[\texttt{\%parameter}] Ignored on x86.
-
-\item[\texttt{\%unbox}] An unboxer function takes a value from the data stack
- and converts it into a C value.
-
-\item[\texttt{\%box}] A boxer function takes a C value as a parameter and
- converts into a Factor value, and pushes it on the data
- stack.
-
- On x86, C functions return integers in EAX.
-
-\item[\texttt{\%box-float}] On x86, C functions return floats on the FP stack.
-
-\item[\texttt{\%box-double}] On x86, C functions return doubles on the FP stack.
-
-\item[\texttt{\%cleanup}] Ignored on PowerPC.
-
- On x86, in the cdecl ABI, the caller must pop input
- parameters off the C stack. In stdcall, the callee does
- it, so this node is not used in that case.
-
-\end{description}
-
-\end{document}
projects / factor.git / commitdiff