# Changeset 3664

Ignore:
Timestamp:
Mar 16, 2017, 4:39:57 PM (6 weeks ago)
Message:

finished description of intermediate languages, will now move on to describing assembly and mcs-51 hardware

File:
1 edited

### Legend:

Unmodified
 r3663 Within the grammar $\textit{unop}$, $\textit{binop}$, $\textit{uncon}$, and $\textit{bincon}$, represent the sets of unary operations, binary operations, unary conditions and binary conditions of the MCS-51 machine code language, lifted into RTL, respectively. \begin{table} \begin{table}[t] {\footnotesize \[ Parameters are now passed in fixed hardware registers, tied directly to our target hardware. If there are too many parameters, the remaining arguments to be passed are spilled, and are stored in the stack. Pseudo registers are not entirely eliminated at this point: they are still used for all other storage barring passing arguments to functions. Further, we now enforce a convention that certain other now-explicit hardware registers are used for certain tasks. This is exploited in certain optimisations. \begin{table} \begin{table}[t] {\footnotesize \[ The result of this liveness analysis is also exploited by the \emph{register allocation} algorithm whose result is to efficiently associate a physical location (a hardware register or an address in the stack) to each pseudo register of the input RTL program. \paragraph{LTL} \paragraph{LIN} \subsection{Target hardware} \subsubsection{LTL} As in ERTL, the structure of LTL programs is based on CFGs. Pseudo registers are not used anymore; instead, they are replaced by physical locations (a hardware register or an address in the stack). \paragraph{Syntax.} Except for a few exceptions, the instructions of the language are those of ERTL with hardware registers replacing pseudo registers. Calling and returning conventions were explicited in ERTL; thus, function calls and returns do not need parameters in LTL. The syntax is defined in table \ref{LTL:syntax}. \begin{table} \paragraph{LTL} is another CFG-based intermediate language. Pseudo registers are now completely eliminated in favour of physical locations---both hardware registers and stack addresses. Except for a few exceptions, the instructions of the language are those of ERTL with hardware registers replacing pseudo registers. Calling and returning conventions were explicited in ERTL; thus, function calls and returns do not need parameters in LTL. The syntax of LTL is presented in Table~\ref{LTL:syntax}. \begin{table}[t] {\footnotesize \[ \end{table} \paragraph{Translation of ERTL to LTL.} The translation relies on the results of the liveness analysis and of the register allocation. Unused instructions are eliminated and each pseudo register is replaced by a physical location. In LTL, the size of the stack frame of a function is known; instructions intended to load or store values in the stack are translated using regular load and store instructions. \paragraph{Optimizations.} A \emph{graph compression} algorithm removes empty instructions generated by previous compilation passes and by the liveness analysis. \subsubsection{LIN} In LIN, the structure of a program is no longer based on CFGs. Every function is represented as a sequence of instructions. \paragraph{Syntax.} The instructions of LIN are very close to those of LTL. \emph{Program labels}, \emph{gotos} and branch instructions handle the changes in the control flow. The syntax of LIN programs is shown in table \ref{LIN:syntax}. \begin{table} Translating ERTL to LTL relies on the results of the liveness analysis performed on ERTL, and mentioned above, and of the register allocation process. Unused instructions are eliminated and each pseudo register is replaced by a physical location. In LTL, the size of the stack frame of a function is now known. As a result, instructions intended to load or store values in the stack can be translated using regular load and store instructions of the hardware target. We use a \emph{graph compression} algorithm to remove empty instructions generated by previous compilation passes and by the liveness analysis. \paragraph{LIN} is a linearised intermediate language, and the final intermediate language before assembly language is produced. The body of every function within LIN is now represented as a sequence of instructions. Despite one being a CFG language, and the other being linear, the instructions of LIN are very close to those of LTL. \emph{Program labels}, \emph{gotos} and branch instructions handle the changes in the control flow. The syntax of LIN programs is presented in Table~\ref{LIN:syntax}. \begin{table}[t] {\footnotesize \[ \end{table} \paragraph{Translation of LTL to LIN.} This translation amounts to transform in an efficient way the graph structure of functions into a linear structure of sequential instructions. \subsubsection{ASM} Translating LTL to LIN amounts to walking the CFG representation of each LTL function, starting from the `main' function, and producing a series of lists of instructions from each function body. Some dead-code elimination is implemented here, as functions that are never called are eliminated entirely. \subsection{Target hardware} \paragraph{MCS-51 assembly language}