%
% File: dbplenv2.tex
% Author: FM
% Date: 5.8.1991
% Included by: dbplenv.tex
%
\section{The Optimizing DBPL Compiler}

Since DBPL is an upward compatible extension of Modula-2, a language processor
for DBPL has to address all aspects of state-of-the-art compilation
technology, ranging from lexical, syntactic and semantic analysis over error
handling to program translation and optimization \cite{ASU86,KMP82,ReDi83}. 

In this section, the focus will be on \e{extensions to programming language
technology} to adequately support specific requirements of large scale,
long-lived and data-intensive applications. Generally speaking, it turns out
that traditional programming language technology provides well-engineered and
systematic approaches to local program analysis and standardizable static
translation tasks, whereas some specific database system tasks rely heavily on
``global'', program-wide (or even system-wide) information gathering, possibly
during program execution. Therefore, an important task in the design of the
DBPL system was the division of labour between the various DBPL system
components. Program analysis and code optimization is performed statically by
the DBPL compiler, the linker verifies the overall consistency between
separately developed system components at application link-time, while the run
time system \kw{DBPLRTS} cares for dynamic aspects of database applications like
query optimization, storage management, serialization of transactions and failure
recovery for persistent data.

\subsection{Input to the Compiler}

The languages Modula-2 and DBPL support the partition of large programs
into independent modules. Each module consists of the definition of an
interface and an implementation. Both parts are called \e{compilation units}
as they can be modified and compiled independently. The DBPL compiler checks the
consistency between the imports and exports of the individual modules.  The
compiler accepts also interface descriptions for modules that were implemented in
other programming languages (\kw{C}, \kw{FORTRAN}, \kw{Pascal}, \kw{Ada}, \ldots).
Thus, DBPL programs can also be linked with modules of these other languages. 

The built-in compiler rules that determine the mapping from DBPL modules to their
persistent representations (source code, object code, compiled interface
definition, database files, executable files) can be overriden by means of
arguments passed to the compiler or environment variables managed by the operating
system.
     

\subsection{Output Generated by the Compiler}

A \e{symbol file} results from the compilation of a module interface definition.
This file contains, besides of a compact representation of the interface
declaration, additional information necessary for type checking between various
modules, compatibility tests, and the allocation of variables, procedures, and
constants. 
     
The result of the compilation of an implementation module is a \e{machine
program} containing references to data objects and code segments of other
modules. If a program includes database operations, the DBPL compiler
creates additional, external references to operations of the run time support 
(see Sec.~\ref{DBPLRTS}). The VAX DBPL compiler directly creates relocatable
object code while the Sun DBPL compiler generates a portable intermediate
representation of abstract machine instructions. This proprietary Sun IR code
is shared by all Sun compiler front ends (\kw{FORTRAN}, \kw{C}, \kw{C++},
\kw{Pascal}) and provides a machine-independent common basis for highly optimizing
compiler back ends for Motorola, Intel and Sparc target architectures 
\cite{Much90}.

The VAX and the Sun compiler both extract detailed information about linguistic
objects (variables, types, procedures, statements) occuring in a DBPL
program. This information is made accessible (in various formats) to other
tools in the DBPL environment, for example to support automatic inter-module
dependency checking, high-level interactive debugging, effective source code
browsing or sophisticated program profiling.
     
While a database module is being translated, the compiler creates, if
necessary, an empty database and an internal description of the database
scheme in the \e{data dictionary} via calls to the DBPL database system (see
Sec.~\ref{DBPLRTS}).

\subsection{Overall Compiler Structure}


The DBPL compiler front end (see Fig.~\ref{dbpl-system}) translates a module
in four passes. Each pass is being executed by completely independent parts of
the compiler. The communication between the passes takes place via main
memory data structures containing a compressed representation of all objects
(constants, types, variables, and procedure signatures) declared in the
program and its system environment, and via sequential interpass files.
Thereby, the output of pass $i$ is the input for pass  $i+1$. The output of
pass $4$ is either an object program in the VAX-11 link format, extended by
information for the run time debugger or a file in the Sun IR format. The
individual passes have the following functions: 
\begin{description}
 \item[Pass 1:] Lexical and syntactical analysis. The source text is
       partitioned into individual symbols, stored as {\em tokens} in the
       interpass file. Identifiers are collected in a symbol table
       and substituted by unique tokens as well. The output of pass 1 is
       a syntactically correct DBPL program, augmented by declarations 
       of the imported modules.
       
 \item[Pass 2:] Analysis of all declarations within the imported definition
       modules and within the module that actually has to be compiled. For
       variables and constants, memory is allocated in the address space
       of the compiled program.
       Simultaneously, the compiler creates pointer structures as a one to one
       image of all declarations within the program, such that type
       and address information are available in the following passes.
       Statements are left unchanged and simply passed on to pass 3.
       
 \item[Pass 3:]  For definition modules, the compilation ends with the
       output of a symbol file. Otherwise, the actual statements (procedure
       bodies) are analyzed. This includes the check of type
       compatibilities within expressions, statements, and procedure parameters.
              
 \item[Pass 4:] The DBPL front end does not perform any significant
       optimizations. Therefore,
       the code generation can be executed by means of a single scan, one 
       statement at a time. Basically, the input of pass 4 is a copy of the 
       bodies of the different procedures and modules of a program unit.

  \item[Back End:] The Sun DBPL compiler utilizes Sun's
       compiler-back end that not only supports code generation for various
       target architectures but that also applies state-of-the-art code
       optimizations like tail call optimization, automatic inlining, aggregate
       breaking, loop-invariant code motion, strength reduction, common
       subexpression elimination, copy and constant propagation, register allocation,
       loop unrolling or unused code elimination.
 \end{description}       

The DBPL front end has to perform a careful program analysis to support the
aggressive optimization technologies employed in the back end. The clean
separation between the DBPL compiler and its run time support (as described
in Sec.~\ref{run-time}) turned out to greatly simplify this task, e.g. by shielding
the compiler from possible aliasing of cursor variables, sharing of buffer
frames or concurrent updates on shared variables.

The following two subsections give some insight into the novel problems arising in
the analyisis and translation of a database language and approaches to their solution
in the DBPL compiler.

\subsection{Program Analysis}

Besides of trivial changes to the \e{scanner} for the recognition of
the new keywords (\kw{CONSTRUCTOR, ON} etc.), the \e{parser}, which is based on the
principle of \e{recursive descent}, had to be extended by procedures to identify
the  various new productions of DBPL.
          
Although DBPL has a \e{LL(1)-grammar} (i.e., can be analyzed with a one
symbol lookahead without backtracking), symbol sequences within construction
predicates are rearranged in pass 1 in order to simplify the (strictly
sequential) code analysis. Since the exertion of these rearrangements can also
be nested (nested relational expressions for \nfnf-relations), pass 1
was extended by a stack, its elements being lists of symbols. 

The internal data structures of the compiler had to be expanded in
order to describe the following objects:  
\begin{description}
 \item[Variant Records:] Code generation for aggregates and the analysis of
      relational queries requires more detailed information about the
      branches of a variant record than present in Modula-2 compilers.
 \item[Relations:] A relation type representation consists of the relation element
      type and a fully expanded list of atomic key components.
 \item[Selectors, Constructors:] In opposition to a procedure, the signature of a
      selector or a constructor is described by two parameter lists, by a
      result type and by a set of access restrictions in case of a
      selector. 
 \item[Modules:] Global modules can have the additional attribute \e{database}.
 \item[Variables:] The compiler distinguishes internally between variable 
      parameters, value parameters, ON-parameters, WITH-parameters and 
      ``normal variables''. The latter are further divided into
       global variables (static allocation),
       local variables (automatic allocation),
       variables at absolute addresses (no allocation),
       variables in separate compilation units,
       persistent variables in database modules and
       variables in quantified boolean expressions and selective
             access expressions.

\end{description}

In addition to obvious type checking extensions for relation, selector and
constructor types, the step from Modula-2 to DBPL introduces the following
three qualitatively new program analysis tasks:
\begin{enumerate}
 \item Loop variables in \k{for each} statements and quantified expressions
       have a scope that is local to a statement or a subexpression. The compiler
       has to resolve bindings for such (overlapping) scopes.
 \item In particular cases, the type of an aggregate or of a constructor
       can only be determined based on information about the context in which it
       is to be used. This requires a limited form of ``target typing'', as
       found, for example, in compilers for the programming language ADA.
 \item The possibility to attach access restrictions (``read'', ``insert'',
       ``update'', \ldots) to selected relation variables requires a more detailed
       \e{mode} checking than in traditional Modula-2 compilers that
       essentially distinguish between immutable values and 
       mutable variables only. Compared with the cost of traditional dynamic
run-time
       access control in database management systems (measured in system complexity
       and execution time), the mode checking extensions to the compiler incurred a
       negligible overhead. 
\end{enumerate}


\subsection{Program Translation}

Virtually all extensions from Modula-2 to DBPL were undertaken without interference
with the machine dependent parts of the code generation in order to obtain a high
portability of the compiler. Therefore, many operations of DBPL are (conceptually)
implemented by sequences of equivalent statements of Modula-2, containing calls to
the runtime support module \kw{DBPLRTS} (see~\ref{DBPLRTS}). Accordingly, the VAX
DBPL and the Sun DBPL compiler utilize the same compilation strategies
despite significant differences in details  of the compilation process
(register allocation, code generation).

Each of the following sections deals only with one particular aspect of the
compilation of DBPL programs. However, the reader should be aware of the fact that
the language principle of \e{orthogonality} stressed by the DBPL language definition
requires implementation strategies that cover arbitrary combinations of these
individual compilation patterns. 
                    
        
\subsubsection{Aggregates} 

For the construction of an aggregate, the compiler reserves storage in the local
address space of the currently compiled procedure. The elements of a record
or an array are stored consecutively in this storage space. Subsequently, the
aggregate can be delivered directly to a procedure or stored in a variable.
Nested aggregates are created in place. 
          
\subsubsection{Run Time Type Descriptions} 

\begin{figure}
\begin{center}
\setlength{\unitlength}{1.1mm}\small
\begin{picture}(70,65)
\put(5,0){\framebox(15.3,5){cardinal}}
\put(25,0){\framebox(15.3,5){cardinal}}
\put(45,0){\framebox(15.3,5){cardinal}}
\put(5,10){\framebox(15.3,5){\em Day}}
\put(25,10){\framebox(15.3,5){\em Month}}
\put(45,10){\framebox(15.3,5){\em Year}}
\put(5,20){\framebox(15.3,5){\bf record}}
\put(30,20){\framebox(15.3,5){real}}
\put(5,30){\framebox(15.3,5){\em Delivery}}
\put(30,30){\framebox(15.3,5){\em Price}}
\put(5,40){\framebox(15.3,5){\bf record}}
\put(25,40){\framebox(15.3,5){Key \em Day}}
\put(45,40){\framebox(15.3,5){Key \em Month}}
\put(65,40){\framebox(15.3,5){Key \em Year}}
\put(15,50){\framebox(15.3,5){\bf relation}}
\put(15,60){\framebox(15.3,5){\bf array}}
\put(12.7,10){\vector(0,-1){5}}
\put(33.7,10){\vector(0,-1){5}}
\put(53.7,10){\vector(0,-1){5}}
\put(12.7,20){\vector(0,-1){5}}
\put(12.7,30){\vector(0,-1){5}}
\put(37.7,30){\vector(0,-1){5}}
\put(12.7,40){\vector(0,-1){5}}
\put(21,50){\vector(-4,-3){6.7}}
\put(25.7,50){\vector(3,-2){7.3}}
\put(22.7,60){\vector(0,-1){5}}
\put(40,42.3){\vector(1,0){5}}
\put(60,42.3){\vector(1,0){5}}
\put(20,33){\vector(1,0){10}}
\put(20,12.3){\vector(1,0){5}}
\put(40,12.3){\vector(1,0){5}}
\end{picture}
\end{center}
\caption{Run-time type descriptions}
\label{Abb:Typbaum}
\end{figure}

Many operations of the DBPL run time system are \e{generic} (i.e., their
operands can pertain to different types). For example, the operation
\kw{DBPLRTS.CreateRelation} is generic in the sense that it can be used to
create relations of parts, relations of suppliers or sets of integers. The
actual type is defined by a supplementary type description generated by the
compiler. Such a type description has a tree structure as shown in figure
\ref{Abb:Typbaum}. Thereby, type constructors are identified by inner nodes,
their sons represent the corresponding element types, whereas leaves are
formed by the built-in simple types (\kw{CARDINAL}, \kw{INTEGER} etc.). 
          
\begin{xple}
\k{type} Date = \k{record} Day, Month, Year: CARDINAL \k{end};
  Receipts = \k{relation} Delivery \k{of} \k{record} Delivery: Date; Price: REAL; \k{end};
  Table = \k{array} [1..20] \k{of} Receipts;
\end{xple}\label{xple-Table}
The generation of such a hierarchical type description is exerted once
at runtime in postorder (i.e., starting at the leaves). Each node contains
additional information, depending on its type, e.g. the byte size of a simple type
value, offset, name and size of a record component, index bounds and element sizes of
an array, order of succession and position of the primary key components of a
relation.

\subsubsection{Persistent Variables} 

The compiler employs the operations \kw{CreateDB} and \kw{CreateDBVar} of the
runtime system (\kw{DBPLRTS}) in order to create a new database during
compilation. Thereby, the structure of a database variable is defined by a
type description (see previous section). 
    
The compiler inserts code at the beginning of the module initialization to
open the databases that belong to an application program. It also generates code to
perform the user-defined initialization operations for a database that is opened
for the first time. The compa\-tibility between the persistent variables at run
time and the database description utilized at compile time is checked by means of a
time stamp. 
    
Every access to a non-relational persistent variable is indirect (i.e., the
application program utilizes a pointer to the value of the persistent variables). In
order to enable a synchronized multi-user access and an efficient buffer management,
every access to a database variable via these pointers is enclosed by the operations
\kw{GetDBVar} and \kw{ReleaseDBVar} generated by the compiler.
    
\subsubsection{Temporary Variables} 

Values of relation, selector and constructor types are implemented as instances of
\e{abstact data types} (ADTs). Thus, for objects of these types, the compiler merely
allocates pointer variables. The creation, deletion and modification of these
objects is accomplished by means of runtime system calls. For example, local
relations are created at the beginning and deleted at the end of a procedure, so
that relations are allowed within recursive procedures as well. The parameter
passing of relations, selectors, and constructors may require the generation of
temporary copies of these objects. 
    
\subsubsection{Transactions} 

Transactions are translated by the compiler like procedures, extended by an
additional \e{prologue} and \e{epilogue}. By means of the prologue, the runtime
system is provided with the operation \kw{BeginTransaction} and possibly with
supplementary information concerning persistent variables (e.g., database relations)
that may be accessed by the transaction in read or write operations. This
information gives rise to important optimizations in the DBPL system, e.g. deadlock
prevention by preclaiming or special treatment of read-only transactions.

An \kw{EndTransaction} operation is generated in the epilogue of a transaction to
initiate a transaction commit. The implementation of DBPL transactions requires a
limited form of \e{exception handling}. During the execution of a transaction body,
application-generated exceptions (division by zero, user abort) lead to a controlled
abort of the transaction (UNDO). Exceptions generated by the DBPL runtime system
provide a mechanism to restart a transaction at arbitrary points in time (e.g. if a
deadlock is detected). The compiler generates appropriate information needed by the
VMS / Unix operating system to perform the necessary procedure stack unwinding
operations for such exceptions.
    
\subsubsection{Identification of Relations}

The existence of \nfnf -relations and selected relation variables requires a
uniform and efficient identification mechanism for relation variables at the
interface to the runtime system. The chosen mechanism (ADT \kw{Relation} in the
layer \kw{DBPLRTS}, see Sec.~\ref{DBPLRTS}) satisfies the following demands: 
\begin{itemize}
 \item The actual operations on relations are separated from the selection
       of subvariables in hierarchical objects.
 \item Nested \nfnf -relations are treated exactly like normalized relations.
 \item Selected relation variables defined by selector applications can
       occur as operands in relational operations.
\end{itemize}

\subsubsection{Relation-Valued Operations}

DBPL operations on individual relation elements (\kw{GetTuple}, \kw{UpdateTuple}
etc.) and navigational operations (\kw{Lowest}, \kw{Next} etc.) are mapped
directly to operations of the runtime system. Relation-valued operations
(quantified predicates, calculus expressions, assignments of entire relations to
relation variables, applications of selectors), however, are not realized by means
of (nested) loops in the object code. Instead, the runtime system receives a
compact internal representation of the operation(s) in form of a \e{predicate tree}
containing attributes. The execution of an arbitrarily complex relation-valued
operation is accomplished in three steps: 
\begin{enumerate}
 \item Evaluation of simple (non-relational) parts of the expression and address
       computations, utilizing \e{inline code}.
 \item Generation of a predicate tree by means of a sequence of operations
       of the runtime system, thereby binding operands to program variables.
 \item Evaluation of the operations on the dynamically bound operands as defined
       by the predicate tree.
\end{enumerate}
                                                               
The predicate tree generated in step 2 (see Fig.~\ref{Abb:Syntaxbaum},
p.~\pageref{Abb:Syntaxbaum}) contains, if necessary, additional references to type
structures as in Fig.~\ref{Abb:Typbaum}. The generation of a predicate is performed
node by node in a preorder traversal.

\subsubsection{Selectors and Constructors}

Selectors and constructors are represented at runtime exclusively by means of
predicate trees. Therefore, predicate trees are allowed to contain parameters as
well as (possibly cyclic) references to other predicate trees, together with a list
of actual parameters. The runtime system provides symbolic operations for the
manipulation of predicate trees (copy, delete, expand, \ldots; see
Sec.~\ref{PSMS}). With the help of these elementary operations, the compiler can
implement selector and constructor declarations as well as variables, partial
parameter substitution, selector applications and the usage of selectors and
constructors in relational constructors and iterators.
    
\subsubsection{Iterators}

In DBPL, iterations over relations that are selected by predicates may modify the
value of the range relation by assignments to the control variable. Already at the
beginning of the iteration, the runtime system receives not only the identification
of the range relation variable and the description of the predicate that has to
hold for every element of the iteration, but also information about the kind of
access that is performed on the iteration loop variable (read and/or write access).
Again, this static compile-time information turns out to be extremely valuable for
bulk iteration optimizations in the runtime system.  

