% ---------------------------------------------------------------
% ---   FCC FORK COMPILER REFERENCE MANUAL CWK  11/1994 
% ---   last modified  23.10.97
% ---------------------------------------------------------------

\documentstyle[12pt]{article}
\pagestyle{plain}
\textwidth=16cm 
\textheight=24.8cm
\topmargin=0cm
\voffset=-0.3cm
\hoffset=-0.4mm
\headheight=0cm
\headsep=0cm
\topskip=0cm
\footskip=0.8cm
\footheight=4mm
\oddsidemargin=0cm
\evensidemargin=0cm
\parindent=0cm
\parsep=2mm
\parskip1.3mm plus0.7mm minus0.3mm

\title{\bf {\tt fcc} Fork95 Compiler Reference Manual}

\author{Christoph~W.~Ke{\ss}ler\\
        Fachbereich 4 -- Informatik\\
        Universit\"at Trier\\
        D-54286 Trier, Germany\\
        e-mail: {\tt kessler@psi.uni-trier.de}}

\date{Current version: 1.7\\[4mm] Last revision: January 29,  1998}

\renewcommand{\textfraction}{0.0}
\renewcommand{\topfraction}{1.0}
\renewcommand{\bottomfraction}{1.0}
\renewcommand{\floatpagefraction}{0.8}


\begin{document}

\maketitle

\renewcommand{\baselinestretch}{1.1}\normalsize

The SB-PRAM is a lock--step--synchronous, massively parallel computer with a 
(from the programmer's view) physically shared memory
\cite{AKP90,KPS94,Sch94}.

{\tt Fork95} \cite{KS95,KS95a,KS95b}
is a C--based redesign of the PRAM language 
{\tt FORK} proposed in \cite{HSS92}.
For an in--depth introduction to programming in Fork95
we recommend the Fork95 tutorial \cite{tutorial}.
A library of basic PRAM algorithms and data structures 
implemented in Fork95 is described in \cite{KT96,KT97}.

{\tt fcc} is the {\tt Fork95} compiler for the SB-PRAM.
The {\tt fcc} implementation is based on the {\tt lcc} 
compiler \cite{FH91a,FH91b,FH95} for ANSI-C \cite{ANSI}.
The current version of {\tt fcc} is 1.7.

This report describes installation, use, and implementation
principles of {\tt fcc}.


% ------------------------------------------------------------------
\section{Installing fcc}

\subsection{Hardware platforms}

{\tt fcc} and the SB-PRAM system tools
run on SUN workstations under SunOS and Solaris.

In principle {\tt fcc} should also compile for LINUX machines,
but the SB-PRAM assembler {\tt prass} and linker {\tt ld}
which are called by the compiler
were, up to now, not LINUX--proof.
A port of the system tools 
for LINUX is currently in a testing stage by the
SB-PRAM group at Saarbr\"ucken.

Prof.\ E.\ Mayordomo from the University of Zaragoza, Spain,
reports on a successful installation of both compiler and 
system tools on
an HP K250/3 with 3 PA8000 processors (512 MB memory
and 20 Gb disk) under HPUX 10.20.

Please notify us if you manage to install {\tt fcc} and/or the
system tools on a platform different from these listed above.


\subsection{Compatibility problems}

For the installation of {\tt fcc} and the SB-PRAM system tools
you need an ANSI C compiler like the GNU C compiler.

Make sure that you are using the version of the SB-PRAM system
tools which is distributed at the Fork web page.
Recent versions of e.g.\ the linker and the simulator 
distributed at Saarbr\"ucken
are no longer compatible with Fork, since these contain bug fixes
for the current SB-PRAM prototype and require the existence of the
SB-PRAM operating system PRAMOS, which is neither required nor
compatible with Fork95 programs.


\subsection{Installation procedure}

Extract the distribution into its own directory.
All paths below are relative to this directory.
It includes the following top-level directories;

\begin{center}
\begin{tabular}{ll}
\tt src         & source files of proper compiler and driver \\
\tt man         & man page \\
\tt doc         & documentation \\
\tt include     & include files \\
\tt examples    & example programs, example makefile \\
\tt bin         & driver \\
\tt lib         & proper compiler, libraries, compiler-specific files \\
\end{tabular}
\end{center}

Before installing, you should specify two shell variables in your 
{\tt .cshrc} file that are required to set up the paths properly:
Set {\tt PRAMDIR} to the directory where you have installed the
SB-PRAM system software, and set {\tt FORKDIR} to the directory
where you have located the Fork95 distribution, e.g.,
\begin{verbatim}
 setenv PRAMDIR /myhomedirectory/pram
 setenv FORKDIR /myhomedirectory/fork
\end{verbatim}

Add the {\tt \$FORKDIR/bin} and the {\tt \$PRAMDIR/bin} directory
to the search path in your local environment specification.

To recompile the compiler for your system, go to the {\tt fork} directory.
Run {\tt make all}. This installs {\tt rcc}, the proper Fork95 compiler,
in directory {\tt lib}, and {\tt fcc}, the driver,
in directory {\tt bin}.\footnote{Note that compilation of {\tt rcc} requires
an ANSI C compiler like the GNU C compiler. You must specify this
compiler in the {\tt Makefile} first.
If you want to change the internal directory structure, you will have to 
edit {\tt fcc.h} and maybe also the {\tt Makefile}
to adjust the paths according to your wishes.
You also will have to edit {\tt fcc.h} if you prefer, for compiling
Fork95 programs, a C preprocessor
other than the GNU preprocessor from your current {\tt gcc} installation.}
Furthermore, several library object files are created in the {\tt lib}
directory by the {\tt fcc} compiler just built,
which are required at the link phase of {\tt fcc}.
In addition, the example programs in the {\tt examples} directory are built
using {\tt fcc} (there should be warnings, but no errors), 
and this documentation is also created in the {\tt doc} directory if not 
yet available.

The resulting executables (see the section on the example programs)
should run properly on the SB-PRAM simulator {\tt pramsim}.
Call it by {\tt pramsim} {\it executable\_file}.
% We recommend to use the shell script {\tt pram-run}
% to call the simulator. A suitable {\tt pram-run}
% is contained in the {\tt bin} directory of the
% {\tt Fork95} compiler distribution.

% It may further be more comfortable to define shell macros like
% the following:
% 
% \begin{verbatim}
% alias ffcc      fcc -I$FORKDIR/include -FORK -m
% alias p1        pram-run -physnum 1 -virtnum 1 -sheap 40000 -pstack 4000000
% alias p4        pram-run -physnum 1 -virtnum 4 -sheap 40000 -pstack 1026000
% alias p16       pram-run -physnum 1 -virtnum 16 -sheap 100000 -pstack 257000
% alias p64       pram-run -physnum 2 -virtnum 32 -sheap 200000 -pstack 65536
% alias p256      pram-run -physnum 8 -virtnum 32 -sheap 400000 -pstack 16384
% alias p1024     pram-run -physnum 32 -virtnum 32 -sheap 800000 -pstack 8192
% alias p4096     pram-run -physnum 128 -virtnum 32 -sheap 4000000 -pstack 2048
% \end{verbatim}

To run {\tt pramsim} properly, you need the resource files {\tt .ldrc}
and {\tt .pramsimrc} in your current working directory.
The {\tt examples} directory contains suitable versions. 
Nevertheless you may need to adapt {\tt .ldrc} to your purposes.
Set up the resources for number of processors and sizes of
private and shared memory subspaces in the file {\tt .ldrc}
depending on your local workstation's performance and memory resources.
Note that the memory requirements are to be
indicated in PRAM words, where a word is 4 bytes.
The number $p$ of simulated 
processors can be changed interactively in the simulator
by typing the command {\tt init} $u,v$ with $1\leq u\leq 128$, 
$1\leq v\leq 32$, where $p=u\cdot v$.
A forthcoming version of {\tt pramsim} will allow to change memory
sizes interactively. A window--based user interface is in preparation.

Finally, 
install the man page by adding {\tt \$FORKDIR/man/man1} to your {\tt \$MANPATH}.



% ------------------------------------------------------------------
\section{Running fcc}

You can use {\tt fcc} in a way similar to your standard C compiler {\tt cc}.
{\tt Fork95} sources can be compiled only if the {\tt -FORK} compiler
flag is set (see the options below). For instance, you may compile
one of the demo example programs by typing
\begin{verbatim}
fcc -I$FORKDIR/include -FORK -m parprefix.c
\end{verbatim}
which generates an executable {\tt a.out}.
(To simplify this command, use {\tt make} or write a shell alias.)

After starting {\tt pramsim},
type the command
\begin{verbatim}
g
\end{verbatim}
to execute the entire program. You can stop the simulator with Ctrl-C.
The simulator automatically stops if a processor reaches the end of the
program, or if the C function {\tt exit()} is called by a processor. ---
Alternatively, you can step through the program execution 
(see the simulator {\tt help} menu for details).

%(Remark: At the end of program execution, a bus error occurs. This is a 
%preliminary feature until the PRAM
%operating system II (for single--user, single tasking with exceptions
%being masked) has been released.)


\subsection*{Example programs}

The {\tt example} directory contains several example programs:
\begin{itemize}
\item {\tt bhatt.c} is an implementation of the parallel CRCW quicksort
        algorithm taken from \cite{BDH}.
\item {\tt bus.c} is a test for the {\tt join} statement
        implementing a very simple parallel shared heap memory allocator.
\item {\tt conjgrad.c} is an implementation of a conjugate
        gradient solver. It uses the header file {\tt bpl.h}.
        No output is provided.
\item {\tt eratosthenes.c} is an implementation of the prime number sieve
        by Eratosthenes. It uses synchronous mode for the sieve itself
        and then computes prime twins using a self--scheduled parallel
        loop in asynchronous mode.
        See also the files {\tt primes.sync.c}, {\tt primes.async.c}
        and {\tt primes.balanc.c} for computation of prime twins
        using the standard algorithm in various modes.
\item {\tt fft.c} Fast Fourier Transform for complex arrays
\item {\tt gauss.c} Gaussian Elimination
\item {\tt hello.c} prints ``Hello world'' by each processor.
\item {\tt mpadd.c} is a demonstration of {\tt Fork95}'s built--in
        {\tt mpadd()}--operator. Be careful with {\tt mpadd(\&shvar,somevar)}:
        It includes
        one side--effect for each of its two parameters: {\tt shvar}
        (first parameter) is set to the global sum of all {\tt somevar}s, and 
        {\tt somevar}, if a variable, is set to the result value. 
        These side effects are part of the SB-PRAM's multiprefix operators
        and cannot be changed.
\item {\tt parprefix.c} shows, at the example of parallel prefix sum computation,
        how parallel programs should be written to
        become independent of the number of processors.
\item {\tt philo.c} is an implementation of the dining philosophers problem.
        See also {\tt philo.naiv.c} for a version that is not deadlock--free.
\item {\tt pipe.c} demonstrates how pipelining could be programmed in
        Fork95 at the problem of computing the global sum of $n$ elements.
\item {\tt quicksort.c} is a parallel quicksort implementation 
        for $n$ array elements on $p$ processors 
        which allows arbitrary values for $n$ and $p$.
\item {\tt mergesort.c} is a parallel divide--and--conquer implementation
        of mergesort. This implementation assumes for simplicity
        that all array elements are different.
\item {\tt quickhull.c} is a parallel divide--and--conquer algorithm
        that computes the convex hull of $n$ points in the 2D Euclidean plane.
        It also demonstrates the usage of the simple graphics interface:
        it plots the points, the edges of the resulting 
        hull, and all bisection lines at recursive calls, 
        visualizing the quality
        of pivoting. You may view {\tt HULL.xpm} e.g.\ by {\tt xv}.
\item {\tt koch.c} is a parallel implementation of a recursive plotting
        algorithm for fractals known as Koch curves.
        View the resulting picture {\tt KOCH.xpm} using {\tt xv}.
\item {\tt qsort.c} demonstrates the random number generator 
        (seed it, if at all,
        only by a large, odd, processor--individual number, please!) 
        and the (sequential) {\tt qsort()} routine from \verb|<stdlib.h>|.
\item {\tt strassen.c} implements Strassen's well--known recursive algorithm
        for matrix--matrix--multiplication. The divide--and--conquer step
        is parallelized using the {\tt fork} statement.
\item {\tt pqueue.c} implements a parallel queue with {\tt put} and {\tt get}
        operations. It can be used e.g.\ 
        for programming task queues which can
        be accessed at low overhead and with practically no sequentialization.
\item {\tt mandel.c} computes the Mandelbrot set and generates a graphical
        output in {\tt X-pixmap} format. Julia sets are computed and drawn by
       {\tt julia.c}.
\item {\tt queens.c} is a synchronous implementation of the $N$-Queens problem.
        The {\tt join} statement is used to aggregate a fixed number (8)
        of solutions for synchronous line--wise graphical output.
\end{itemize} 
 
Possible extensions to multiprefix operators are discussed in the files
{\tt mpmax.c} and {\tt incl\_mpadd.c}. Thanks go to Marcus Marr from Edinburgh
for providing these.

More complex Fork95 software (library routines for sorting, searching, etc.)
is available in the PAD library \cite{KT96,KT97}; see the PAD web page

\centerline{\tt http://www.mpi-sb.mpg.de/guide/activities/alcom-it/PAD/}

or ask Jesper L.\ Tr\"aff at MPI Saarbr\"ucken 
(email: {\tt traff@mpi-sb.mpg.de}).


% ------------------------------------------------------------------
\section{Options}

\begin{itemize}
\item {\tt -FORK} indicates that the source to be compiled is a Fork95
      source. If {\tt -FORK} is not specified,
      the source file will be interpreted as an ANSI C source, with
      the Fork95 language extensions being forbidden.
\item {\tt -g0} drops debugging directives; 
      {\tt -g}, {\tt -g2}...{\tt -g9} emit
      several levels of dbx--type debugger directives.
      Breakpoints for J.\ Gierend's planned Fork95--Debugger are generated
      as special {\tt NOP}'s.
\item {\tt -G}{\it path} tells the compiler the path of the source program
      which is required when {\tt -g} is set.
\item {\tt -K} generates code that checks for stack overflow.
\item {\tt -m} generates code for alignment according to the MODULO flag
      of the SB-PRAM. This should be switched on if you use concurrent
      write facilities or multiprefix operators.
\item {\tt -P} prints full type headers for each function declaration.
\end{itemize}

Further options taken from {\tt lcc} can be looked up in the {\tt fcc} or
{\tt lcc} manpage.

% ------------------------------------------------------------------
\section{Library Functions}

\begin{table}
\begin{small}
\begin{tabular}{|l|l|}
\hline
header file & type of library functions \\
\hline\hline
{\tt fork.h}  & parallelism--handling routines; locks; {\tt join} macro \\
\hline
{\tt assert.h} & the {\tt assert()} macro \\
\hline
{\tt stdlib.h} & as in C ({\tt rand()}, {\tt qsort()}, etc.\ \\
\hline
{\tt string.h} & string handling functions \\
\hline
{\tt math.h}   & mathematical functions (only single precision)\\
\hline
{\tt ctype.h}  & character classification (as in C)\\
\hline
{\tt stdarg.h} & macros for handling a variable number of function arguments\\
\hline
{\tt io.h}     & input/output routines\\
\hline
{\tt graphic.h} & graphics routines\\
\hline
{\tt myfcntl.h}& file I/O flags from PRAM-OS\\
{\tt syscall.h}& routines for interaction with PRAM-OS\\
\hline
\end{tabular}
\end{small}
\caption{The library header files for the Fork95 compiler.
         In the present stage not all functions known from usual
         ANSI C libraries are available yet.}
\vspace*{2mm}\hrule\vspace*{2mm}
\end{table}

The file {\tt forklib2.asm} contains the PRAM assembler source of 
the startup code and several functions closely related to the Fork95 language:
\begin{itemize}
\item
{\tt malloc} (private malloc on permanent private heap, asynchronous),\\
%{\tt sync\_malloc} (private malloc, synchronous), abgeschafft 9608 CWK
{\tt shalloc} (shared malloc on automatic group--local shared heap),\\
{\tt shmalloc} (allocate on global permanent shared heap),\\
{\tt realloc} (realloc on permanent private heap, dummy),\\
{\tt free} (free malloc objects, dummy),\\
{\tt shallfree()} (free all shalloc'ed objects in current function),\\
{\tt shfree} (free shmalloc'ed objects).

The {\tt shalloc()}ed objects generally
live until the group defining them terminates,
although there is also a possibility for explicit release: \\
{\tt shallfree()} releases all objects {\tt shalloc()}ed so far in the
current function (both for synchronous and asynchronous functions).

{\tt pravail} returns the number of free private memory words for this
processor, and {\tt shavail} returns the number of free shared memory
words for the current group.
\item
{\tt exit} and {\tt \_exit} to leave the program,
\item
{\tt barrier} (internally called {\tt forklib\_sync}) synchronizes the leaf groups.
\item
{\tt groupsize} (number of processors in current group, synchronous, by inspecting 
the synchronization cell),
{\tt async\_groupsize} (same as {\tt groupsize} but asynchronous), and
{\tt parentgroupsize} 
(contents of parent group's synchronization cell, synchronous).
Note that {\tt parentgroupsize} indicates the actual number of
the parent group's processors only when the parent group
has only one child group, e.g.\ at a loop.
The same caveat holds for the more general routine {\tt \_groupsize($k$)} 
that allows to inspect the synchronization cell of the $k$th 
ancestor group.
\item
{\tt forklib\_divi} (integer division), 
{\tt forklib\_divu} (unsigned integer division),  and
{\tt forklib\_fdiv} (floatingpoint division) are
for compiler--internal use only;
{\tt itof}, {\tt ftoi} (conversions int--float),
\item {\tt memcpy} (internally: {\tt forklib\_movb}) for block copy,
{\tt strcpy}, {\tt strcmp}, {\tt strncmp}, {\tt memcmp}, {\tt strlen}.
\item
{\tt srand}, {\tt rand}, {\tt random}; the latter routine takes 
the address of the seed as parameter and stores the new random number
there as a side effect. 
\item
{\tt read}, {\tt write}, {\tt open}, {\tt close}: the syscalls.
\item
{\tt reltoabs} computes the absolute address of a private
variable.
\item
{\tt getct} returns the current value of the (global) round counter of the
SB-PRAM, giving 256 times the parallel execution time (consumed since start
of the program) in milliseconds.
\end{itemize}
These functions take their parameters from parameter registers, not from
the (private) stack. This is recognized automatically by the compiler
by inspecting the file {\tt libfnames}.

Four different kinds of locks have been implemented:
simple locks, safe locks, fair locks, and reader-writer-locks, as
suggested by Jochen R\"ohrig at Saarbr\"ucken University.
The locks are documented in \verb|<fork.h>|.
To use them for mutual exclusion in asynchronous mode, 
we recommend the macros given in \verb|<fork.h>|.

I/O routines are declared in the {\tt io.h} header file.
Input/Output to/from screen can be done using the usual
{\tt scanf()} and {\tt printf()} functions.
File--I/O has been newly implemented, but
{\tt fscanf()} works but {\tt sscanf()} still does not work properly.
Buffering is not provided.
{\tt sprintf()} and {\tt vsprintf()} are still missing.
All I/O routines are asynchronous.
Make sure to place I/O functions in critical sections
to keep your screen display readable.
A unified locking mechanism for {\tt FILE} I/O is planned.
For faster printing of strings and floatingpoint numbers
you can use the routines {\tt puts()} resp.\ {\tt prF()},
see {\tt io.h}.
In addition, there is the routine {\tt pprintf()} which 
works like {\tt printf()} (no floatingpoint output) but emits
the physical processor ID at the beginning of the printed line.
This may be useful for debugging.

The mathematical library still needs much work to be done,
see the {\tt math.h} header file.
The implemented functions work for single precision
floatingpoint numbers (IEEE 754 format); the {\tt double}
keyword is automatically converted to {\tt float} in order
to make things work at least for single precision.
The available functions are: {\tt fabs()}, {\tt ceil()},
{\tt floor()}, {\tt modf()}, {\tt ftoi()} and {\tt itof()}.
The trigonometric functions {\tt sin()}, {\tt cos()},
{\tt asin()}, {\tt acos()}, {\tt atan()} are available
as well as the base 10 logarithm {\tt log10()} and the
base $e$ logarithm {\tt ln()}. Most domain errors are checked for.
The routines have been tested; though
no guarantee is given for the accuracy.

We have also provided some simple graphics routines.
A two--dimensional array of 32-bit pixels with extents $x$ and $y$ 
is allocated by 
{\tt init\_pict($x$,$y$)}.
One may switch between several pixel arrays with
{\tt switch\_to\_pict($cp$)} to $cp$ as the current pixel array.
The picture can be cleared by 
{\tt clear\_pixels()} in parallel.
A single pixel $(u,v)$ may be set by 
{\tt set\_pixel($u$,$v$,1)} and its color be
inspected by {\tt get\_pixel($u$,$v$)}.
The parallel routine {\tt line()} plots lines.
The parallel routine {\tt write\_pixmap(}{\it filename}{\tt )}, 
writes the pixel array to a file in 
monochromatic X-Bitmap
format (which may be viewed e.g.\ using {\it xv}).
The origin (0,0) of the pixel array is
mapped to the upper left corner of the picture.
For more details please see the tutorial \cite{tutorial}.
An advanced graphics library for Fork95 is currently in preparation.




% ------------------------------------------------------------------
\section{Reserved key words}

Additionally to the ANSI C key words,
the words {\tt sh}, {\tt pr},
{\tt start}, {\tt fork}, {\tt farm}, {\tt sync}, {\tt async},
{\tt ilog2}, {\tt mpadd}, {\tt mpmax}, {\tt mpor} and {\tt mpand}
are reserved key words, and this holds also for C sources that are
compiled with {\tt fcc} (in asynchronous mode).

The sign \verb/$/ denotes the (relative) process ID, the sign \verb/@/ the
group ID of the processor executing this expression. Both of them
are private integer variables that can be assigned any integer value.

The number of processors started in the simulator
can be accessed by the programmer in the variable \verb/__STARTED_PROCS__/.
The variable \verb/__PROC_NR__/ contains a unique (absolute) processor number
for each processor, ranging from 0 to \verb/__STARTED_PROCS/ -- 1.
The group--relative process ID \verb/$/ is initialized to \verb/__PROC_NR__/ at the
beginning of the program execution.
Although \verb/__PROC_NR__/ may later be assigned a (different)
value by the programmer, he should not change it; there is 
 \verb/$/ for this purpose.

The header file \verb|<fork.h>| which should be included into each Fork95 source
program contains also a useful macro:
\begin{verbatim}
forall(i,lb,ub) <statement>
\end{verbatim}
executes \verb/<statement>/ within a parallel loop with loop variable {\tt i},
ranging from {\tt lb} to {\tt ub}, using all \verb/__STARTED_PROCS__/ 
started processors. This is especially useful for dataparallel applications.


\section{The bus concept: {\protect\tt join}}

The {\tt join} construct \cite{joinreport}
is currently implemented as a {\em macro} in {\tt fork.h}.
Thus you must code
\begin{verbatim}
join ( delaystmt; springoffcond; SMalloc ) <statement> else <useful_work>
\end{verbatim}
with a possible {\tt retry} statement inside the {\tt else} part,
as
\begin{verbatim}
join ( joinID, delaystmt, jumpoffcond, SMsize, retry, statement, elsestatement );
\end{verbatim}
with {\tt joinID} denoting a unique integer constant from 0 to {\tt MAXJOINS-1};
the value {\tt MAXJOINS} can be modified in {\tt fork.h}.
{\tt retry} has to be 0 if there should be no retry after the {\tt else} part, and 
$\neq 0$ otherwise. For {\tt SMsize} you should provide an integer constant of 
at least 100, specifying the size of the bus's new shared memory to be allocated
on the driver's private heap. ---
An example is given in {\tt bus.c}.
Note that this offers several entries for the same bus!
A future compiler implementation of {\tt join} is planned.


% ------------------------------------------------------------------
\section{Reserved registers}

{\tt fcc} generates symbolic names for the special-purpose-registers.
Registers {\tt r18},...,{\tt r29} are general--purpose registers that
can be used for expression evaluation.

\begin{center}
\begin{small}
\begin{tabular}{|l|l|l|l|}
\hline
number & symbolic & name & comment \\
\hline\hline
0      & {\tt sr},{\tt R0} & status register, Zero & depending on the instruction\\ \cline{3-4}
1      & {\tt pc}   & program counter      & ignored as target of compute \\ \cline{3-4}
2      & {\tt sp}   & system stack pointer & do not change it! \\
\hline
3      & {\tt fpp}  & frame pointer, private& \\
4      & {\tt app}  & argument pointer, private& \\
\hline
5      & {\tt Ret}  & value/address of function return value & \\
\hline
6      & {\tt spp}  & stack pointer, private& \\
\hline
7      & {\tt par1} & first parameter register & \\
8      & {\tt par2} & second parameter register & \\
9      & {\tt par3} & third parameter register & \\
10     & {\tt par4} & fourth parameter register & \\
\hline
11     & {\tt epp}  & heap pointer, private & \\
12     & {\tt sps}  & stack pointer, shared & \\
13     & {\tt fps}  & frame pointer, shared & \\
14     & {\tt eps}  & heap pointer, shared & \\
15     & {\tt gpp}  & group pointer, private & \\
16     & {\tt gps}  & group pointer, shared & \\
17     & {\tt aps}  & argument pointer, shared& \\
\hline
18...29& {\tt r18},..., {\tt r29}& general purpose registers& saved at function calls\\
\hline
30,31  & {\tt r30}, {\tt r31} & scratch registers      & not saved at function calls\\
\hline
\end{tabular}
\end{small}
\end{center}


\section{Frame layout}

\subsection{Procedure frames}

\subsubsection{Parameter passing at function calls}

Functions listed in the file {\tt libfnames} pass their first four
private parameters in registers {\tt par1},...,{\tt par4} (this is mainly
to optimize calls to library routines).
The {\tt fcc} user can take advantage of this scheme by adding own
function's names to this file. The first line in {\tt libfnames}
contains the total number of its entries, with each line containing one
function name.

Functions with a variable number of arguments pass their private parameters
located on variable argument positions via the private stack. Shared parameters
must not be located on variable positions.

A function using shared parameters must have an ANSI--style prototype.

{\tt fpp} and {\tt fps} are set even if the callee has no
(shared) local variables. This is to restore the group pointers properly
after a {\tt return} statement in the callee. There is an exception of this,
however, if the callee is an asynchronous function.


\subsubsection{Private procedure frame for synchronous functions}

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
{\tt spp}$\longrightarrow$ &                                    & \\
\cline{2-3} %------------------------------------------
    & last private local variable        & \\
    & $\vdots$                           & not initialized\\
    & first private local variable                & \\
\cline{2-2}
{\tt fpp}$\longrightarrow$ & (reserved for returning a struct)   & \\
\cline{2-3} %-----------------------------------------
    & old {\tt eps} & \\
\cline{2-2} % ^-- wieder drin 960815 fuer shallfree()
    & old {\tt gps} & \\
\cline{2-2}
    & old {\tt gpp} & callee--saved \\
\cline{2-2}
    & old {\tt fps} & \\
\cline{2-2}
    & old {\tt fpp} & \\
\cline{2-3} %------------------------------------------
    & old {\tt pc}  & call--saved \\
\cline{2-3} %------------------------------------------
    & last saved register & \\
    & $\vdots$            & caller--saved \\
    & first saved register& \\
\cline{2-3} %------------------------------------------
    & last private argument & only if the callee\\
    & $\vdots$              & has private arguments \\
    & first private argument& not passed in registers;\\
\cline{2-2}
{\tt app}$\longrightarrow$ & old {\tt app}               & caller--saved\\
\cline{2-3} %------------------------------------------
\end{tabular}
\end{footnotesize}
\end{center}


\subsubsection{Private procedure frame for asynchronous functions}

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
{\tt spp}$\longrightarrow$ &                                    & \\
\cline{2-3} %------------------------------------------
    & last private local variable        & \\
    & $\vdots$                           & not initialized\\
    & first private local variable                & \\
\cline{2-2}
{\tt fpp}$\longrightarrow$ & (reserved for returning a struct)   & \\
\cline{2-3} %-----------------------------------------
    & old {\tt fpp} & callee--saved \\
\cline{2-3} %------------------------------------------
    & old {\tt pc}  & call--saved \\
\cline{2-3} %------------------------------------------
    & last saved register & \\
    & $\vdots$            & caller--saved \\
    & first saved register& \\
\cline{2-3} %------------------------------------------
    & last private argument & only if the callee\\
    & $\vdots$              & has private arguments \\
    & first private argument& not passed in registers;\\
\cline{2-2}
{\tt app}$\longrightarrow$ & old {\tt app}               & caller--saved\\
\cline{2-3} %------------------------------------------
\end{tabular}
\end{footnotesize}
\end{center}

The compiler uses the most significant bit of the pointer stored
in {\tt fpp,-1} to allow for run--time inspection 
whether this is a synchronous
({\tt eps}, i.e.\ an absolute address) or asynchronous
(old {\tt fpp}, i.e.\ a private address) function.


\subsubsection{Shared procedure frame}

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
{\tt sps}$\longrightarrow$ &                                    & \\
\cline{2-3} %------------------------------------------
    & last shared local variable         & the shared locals\\
    & $\vdots$                           & defined at top level\\
    & first shared local variable        & of the function\\
\cline{2-3} %------------------------------------------
          & synchronization cell         & this function's\\
\cline{2-2}
{\tt fps},
{\tt gps}$\longrightarrow$ & old gps     & group frame\\
\cline{2-3} %------------------------------------------
\cline{2-3} %-----------------------------------------
    & last shared argument  & only if the callee\\
    & $\vdots$              & has shared arguments;\\
    & first shared argument & \\
\cline{2-2}
{\tt aps}$\longrightarrow$ & old {\tt aps}               & caller--saved\\
\cline{2-3} %------------------------------------------
\end{tabular}
\end{footnotesize}
\end{center}

For each synchronous function an extra group frame 
(see next subsection) is allocated.
This is technically required 
in order to re-synchronize at the end of function execution
when some processors {\tt return}ed earlier.

An asynchronous function does not have a shared procedure frame.
Note that it can nevertheless allocate shared variables inside
a {\tt start} body, since these are local to the group frame
built by {\tt start}.


\subsection{Group frames}

Group--forming operations are {\tt start} and {\tt fork}, 
and the constructs {\tt if}, {\tt for}, {\tt while}, {\tt do}
with (maybe) private branch condition.

\subsubsection{Private group frame built by {\protect\tt if} and {\protect\tt fork}}

The loops ({\tt for}, {\tt while}, {\tt do}) 
build only shared group frames.

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
    &                                    & \\
\cline{2-3} %-----------------------------------------
    & (new) process ID {\tt \$} & copied from parent group\\
\cline{2-2}
    & (new) group ID {\tt @}  & copied from parent group\\
\cline{2-3}
{\tt gpp}$\longrightarrow$ & old {\tt gpp} & points to parent priv.\ group frame\\
\cline{2-3} %-----------------------------------------
    & IF: split cell; FORK: group's shared memory size & debug info\\
\cline{2-2}
    & IF: 0; FORK: \# new groups opened & debug info\\
\cline{2-3}
    & old sps & \\
\cline{2-2}
    & old eps & \\
\cline{2-3} %------------------------------------------
\end{tabular}
\end{footnotesize}
\end{center}

\subsubsection{Private group frame built by {\protect\tt start}}

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
    &                                    & \\
\cline{2-3} %-----------------------------------------
    & (new) process ID {\tt \$} & numbered 0...{\tt \_\_STARTED\_PROCS\_\_-1}\\
\cline{2-3}
    & {\tt @} = 0 & the only group's ID \\
\cline{2-3}
{\tt gpp}$\longrightarrow$ & old {\tt gpp} & points to parent priv.\ group frame\\
\cline{2-3} %-----------------------------------------
    & old sps & \\
\cline{2-2}
    & old eps & \\
\cline{2-2}
    & old fps & \\
\cline{2-3} %------------------------------------------
\end{tabular}
\end{footnotesize}
\end{center}


\subsubsection{Shared group frame}

\begin{center}
\begin{footnotesize}
\begin{tabular}{r|c|l}
{\tt sps}$\longrightarrow$ &                                    & \\
\cline{2-3} %------------------------------------------
    & last group-local shared variable         & the shared variables\\
    & $\vdots$                           & defined locally to the \\
    & first group-local shared variable        & construct building this group\\
\cline{2-3} %-----------------------------------------
    & synchronization cell & initialized by \# processors in this group\\
\cline{2-2}
{\tt fps}$^\ast$, {\tt gps}$\longrightarrow$ & old gps & points to parent shared group frame\\
\cline{2-3} %-----------------------------------------
\end{tabular}

\vspace*{1mm}

$\ ^\ast$ The {\tt fps} is set only by {\tt start} and {\tt join}.

\vspace*{2mm}
\end{footnotesize}
\end{center}

Note that the cost of adressing 
a local shared variable depends on the site of definition
as well as of the site of the access.

\begin{verbatim}
sync void foo( ... )
{  sh int i;  /*exists once for each group entering this function*/
   fork (...)  {
      sh int j;  /*exists once for each subgroup*/
      fork (...) {
         sh int k;  /*exists once for each subgroup*/
         k = i * j ... ;
      }
   }
}
\end{verbatim}

In synchronous functions, the shared variables defined at top
level of the function 
(e.g., variable {\tt i} in the example code above)
are addressed via the {\tt fps} and thus
one instruction is sufficient. 

In the other cases, the chain of {\tt gps} pointers has to be
traversed backwards from the current group frame to the group
frame of the group that defined that variable.
The cost of addressing 
is $2x+1$ where $x$ denotes the number of group frames
between the current and the defining group frame (including the
defining frame).
Thus, in the example above, calculation of the address of {\tt j} 
costs 3 instructions while 
the calculation of the address of {\tt k} can be done in one instruction.



%---------------------------------------------------------------------
\section{Optimizations}

{\tt fcc} performs a limited set of optimizations automatically.
\begin{itemize}
\item Integer division and modulo computation are very expensive.
      Divisions and Modulo--computations are realized by shifts
      if the value of the divisor (or modulus) at run-time
      is a power of two.
\item Synchronization after synchronous divisions is suppressed
      if the divisor is shared or constant.
\item Alignment to the MODULO flag is suppressed for accesses to
      the private stack.
\item Small integer (char, pointer, short, unsigned int) constants
      are loaded by a {\tt getlo} instead of two instructions.
\end{itemize}

The following further optimizations may be useful, but cannot be
implemented due to the one-pass-nature of the {\tt lcc}:
\begin{itemize}
\item The group synchronization immediately after a user function call is not
      necessary if the callee does not contain {\tt return}
      statements other than at its end.
\item opening a loop group also for a shared loop exit condition
      is not necessary if the loop body contains no {\tt break}
      or {\tt return} statement inside a one-sided {\tt if} statement.
\end{itemize}

%---------------------------------------------------------------------
\section{Limitations}

The maximal number of processors used is a compile-time constant and 
must be at most 4096 for the SB-PRAM prototype at Saarbr\"ucken.

Conditional expressions $e? l:r$ do --- unlike the private {\tt if}
statement --- not build group frames. As a private condition $e$
may introduce a deadlock, a warning is emitted in this case.
This is due to the strange construction of expression DAGs in the
{\tt lcc}. Nevertheless, this does not prohibit the programmer ---
he can use the {\tt if} statement instead.

The same holds for {\tt switch} statements: Currently, there are
no group frames provided. Thus, a private selector may introduce
a deadlock (warning is given). If a synchronous
switch over a private selector cannot be avoided,
the programmer should replace it by a (if possible, balanced)
{\tt if} cascade.

Attention must be paid if {\tt continue} is used in a loop. If
between the {\tt continue} and the end of the loop body some
synchronization will take place (e.g., at the end of a private {\tt if},
of a private loop, of a {\tt sync} function call or of a {\tt farm}),
a deadlock may be introduced.
This problem will disappear in a future release of {\tt fcc} by enabling
the user to indicate such situations a priori by specifying
a compiler option that introduces an extra shared group frame for each loop.
A general implementation of {\tt continue}
is not sensible for a one--pass--compiler like {\tt fcc}.

It is illegal to access within a {\tt start} or {\tt join} body
a shared local variable declared outside the {\tt start} (the
effects are undetermined, the compiler does not warn). We
generally discourage nesting of more than one {\tt start} or {\tt join}
within the same function.

\section{Known Bugs}

\begin{itemize}

\item Never use old--style function definitions such as

\begin{verbatim}
void foo( x, y, z ) char x; int y, z; { .... }
\end{verbatim}

this will often cause the compiler to crash with a segmentation fault.
Rather use the more convenient new--style declaration
(which is the only possibility if shared parameters occur!):

\begin{verbatim}
void foo( char x, int y, int z ) { .... }
\end{verbatim}

Note that also for equal types of subsequent parameters
the type identifier (here: {\tt int}) has to be replicated.


\item Initializers consisting of string or array constants should not be 
 declared locally, as in
\begin{verbatim}
int foo() { pr char string[] = "Hello World\n";   ... }
\end{verbatim}
This is a bug of {\tt lcc 1.9}; it will result in an endless loop. 
As it seems not to be essential to declare string constants locally 
(immediate uses like {\tt write(1,"Hello",5)} work properly) we postpone
this issue for later debugging.

\item Structures cannot be returned by functions.
      This may be possible in a future release of {\tt fcc};
      for now, you can work around by returning a pointer to the
      structure, which is, by the way, more efficient since 
      calling the copy routine is not required.

\item Something is wrong with switches (a {\tt lcc 1.9} bug), please avoid them.

\item {\tt pprintf()} and {\tt fpprintf()} do not work for floatingpoint
      numbers; use instead either usual {\tt printf()} or the fast and simple
      {\tt prF} routine (see {\tt io.h}).

\item Passing {\tt struct}s as arguments or returning a {\tt struct} from
      a function doesn't work. This also causes function
      {\tt ldiv()} to crash.

\item Sometimes {\tt fcc} refuses to compile certain constructs involving
      pointers to functions. In particular, pointers to synchronous functions
      are assumed to point to asynchronous functions.
      In most cases you can simply work around by
      declaring a temporary pointer to a function, such as in
\begin{verbatim}
sync void foo(sh int n) {
    sh sync void (*local_fn_array[32])( void );
    sh sync void (*help)( void );
    ...
    for (arg_ptr=0;arg_ptr<n;arg_ptr++) {
        help = local_fn_array[arg_ptr];
        help();
    }
}
\end{verbatim}

\end{itemize}


\section{Reporting Bugs}\label{bugs}


Bugs can be reported by sending mail with the shortest program
that exposes them and the details reported by \verb|fcc|'s \verb|-v|
option to \verb|kessler@psi.uni-trier.de|.
Other questions, comments, and requests
can be sent to the same address.
If you wish that we notify you on future releases of {\tt fcc},
please send a short email message.


\renewcommand{\baselinestretch}{1.0}\normalsize
% ------------------------------------------------------------------
% B I B L I O G R A P H I E : 
% ------------------------------------------------------------------
%
\begin{thebibliography}{1}

\bibitem{AKP90}
F.~Abolhassan, J.~Keller, and W.J. Paul.
\newblock On {P}hysical {R}ealizations of the {T}heoretical {PRAM} {M}odel.
\newblock Technical Report 21/1990, Sonderforschungsbereich 124 {VLSI}
  {E}ntwurfsmethoden und {P}arallelit\"at, Universit\"at Saarbr\"ucken, 1990.

\bibitem{ANSI}
American National Standard Institute, Inc., New York.
\newblock {\em American National Standards for Information Systems, Programming
  Language C {ANSI} X3.159--1989}, 1990.

\bibitem{BDH}
Bhatt, Diks, Hagerup, Prasad, Saxena, and Radzik:
\newblock Improved Deterministic Integer Sorting.
\newblock Information and Computation, to appear.

\bibitem{FH91a}
C.~W. Fraser and D.~R. Hanson.
\newblock A code generation interface for {ANSI C}.
\newblock {\em Software---Practice \& Experience}, 21(9):963--988, Sept. 1991.

\bibitem{FH91b}
C.~W. Fraser and D.~R. Hanson.
\newblock A retargetable compiler for {ANSI C}.
\newblock {\em SIGPLAN Notices}, 26(10):29--43, Oct. 1991.

\bibitem{FH95}
C.~W. Fraser and D.~R. Hanson.
\newblock Book on compiler construction, based on lcc.
\newblock To appear 1995.

\bibitem{HSS92}
T. Hagerup and A. Schmitt and H. Seidl.
\newblock {FORK}: A High--Level {L}anguage for {PRAM}s.
\newblock Future Generation Computer Systems 8 (1992), 379--393.

\bibitem{KPS94}
J. Keller and W.~J. Paul and D. Scheerer.
\newblock Realization of {PRAM}s: {P}rocessor {D}esign.
\newblock Proc.\ {WDAG}'94, 8th Int.\ Workshop on Distributed Algorithms,
          {S}pringer {LNCS} vol.\ 857, 17--27, 1994

\bibitem{KS95}
C.~W. Kessler and H. Seidl.
\newblock Making {FORK} Practical.
\newblock Technical Report 95-01, SFB 124, Universit\"at Saarbr\"ucken.

\bibitem{KS95a}
C.~W. Kessler and H. Seidl.
\newblock Fork95 language and compiler for the SB-PRAM.
\newblock Proceedings of 5th Workshop on Compilers for Parallel Computers,
          Malaga, Spain, June 28--30, 1995. Technical Report UMA-DAC-95/09,
          University of Malaga, Department of Computer Architecture.

\bibitem{KS95b}
C.~W. Kessler and H. Seidl.
\newblock Integrating synchronous and asynchronous paradigms: The Fork95 programming
          language.
\newblock Technical Report 95-05, Universit\"at Trier. See also: Proceedings
          of MPPM-95 Int. IEEE Conference on Massively Parallel Programming Models,
          Berlin, Germany,  Oct. 9--12, 1995.

\bibitem{KT96}
C.~W.~Kessler and J.~L.~Tr\"aff. 
\newblock {A {L}ibrary of {B}asic {PRAM} {A}lgorithms and its
          {I}mplementation in {FORK}}.
\newblock {8th} Annual {ACM} {S}ymposium on 
          {P}arallel {A}lgorithms and {A}rchitectures.
          pp.\ {193--195}, ACM press, 1996.



\bibitem{KT97}
C.~W.~Kessler and J.~L.~Tr\"aff.
\newblock Language and Library Support for Practical PRAM Programming.
\newblock {5th {EUROMICRO} {W}orkshop on {P}arallel and {D}istributed
          {P}rocessing, {L}ondon}, IEEE CS Press, Jan.\ 1997.

\bibitem{joinreport}
C.~W. Kessler and H. Seidl.
\newblock Language Support for Synchronous Parallel Critical Sections.
\newblock Technical Report 95-23, Universit\"at Trier, Nov.\ 1995. 
          To appear in: Proc. Int. Conf. on Advances in Parallel and 
          Distributed Computing (APDC'97), Shanghai, China, 1997.
          IEEE CS Press.

\bibitem{tutorial}
C.~W. Kessler.
\newblock Practical PRAM Programming with Fork95 --- A Tutorial.
\newblock Technical Report 97-12, Universit\"at Trier, 1997. 
          Regularly updated and contained in the {\tt doc} directory
          of the {\tt fcc} distribution.
          To appear as a chapter in a forthcoming textbook
          {\sl Parallel PRAM Programming} by J.\ Keller, C.\ Kessler,
          and J.\ Tr\"aff.

\bibitem{Sch94}
D. Scheerer.
\newblock Der {SB-PRAM} Prozessor.
\newblock PhD dissertation, Universit\"at Saarbr\"ucken, 1995.

\end{thebibliography}

\end{document}
