Changeset 3664


Ignore:
Timestamp:
Mar 16, 2017, 4:39:57 PM (5 months ago)
Author:
mulligan
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Papers/jar-cerco-2017/architecture.tex

    r3663 r3664  
    8282Within 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.
    8383
    84 \begin{table}
     84\begin{table}[t]
    8585{\footnotesize
    8686\[
     
    162162Parameters are now passed in fixed hardware registers, tied directly to our target hardware.
    163163If there are too many parameters, the remaining arguments to be passed are spilled, and are stored in the stack.
     164Pseudo registers are not entirely eliminated at this point: they are still used for all other storage barring passing arguments to functions.
    164165
    165166Further, we now enforce a convention that certain other now-explicit hardware registers are used for certain tasks.
     
    175176This is exploited in certain optimisations.
    176177
    177 \begin{table}
     178\begin{table}[t]
    178179{\footnotesize
    179180\[
     
    256257The 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.
    257258
    258 \paragraph{LTL}
    259 
    260 \paragraph{LIN}
    261 
    262 \subsection{Target hardware}
    263 
    264 \subsubsection{LTL}
    265 
    266 As in ERTL, the structure of LTL programs is based on CFGs. Pseudo
    267 registers are not used anymore; instead, they are replaced by physical locations
    268 (a hardware register or an address in the stack).
    269 
    270 \paragraph{Syntax.}
    271 Except for a few exceptions, the instructions of the language are those of
    272 ERTL with hardware registers replacing pseudo registers. Calling and
    273 returning conventions were explicited in ERTL; thus, function calls and
    274 returns do not need parameters in LTL. The syntax is defined in table
    275 \ref{LTL:syntax}.
    276 
    277 \begin{table}
     259\paragraph{LTL} is another CFG-based intermediate language.
     260Pseudo registers are now completely eliminated in favour of physical locations---both hardware registers and stack addresses.
     261
     262Except for a few exceptions, the instructions of the language are those of ERTL with hardware registers replacing pseudo registers.
     263Calling and returning conventions were explicited in ERTL; thus, function calls and returns do not need parameters in LTL.
     264The syntax of LTL is presented in Table~\ref{LTL:syntax}.
     265
     266\begin{table}[t]
    278267{\footnotesize
    279268\[
     
    335324\end{table}
    336325
    337 \paragraph{Translation of ERTL to LTL.} The translation relies on the
    338 results of the liveness analysis and of the register allocation. Unused
    339 instructions are eliminated and each pseudo register is replaced by a physical
    340 location. In LTL, the size of the stack frame of a function is known;
    341 instructions intended to load or store values in the stack are translated
    342 using regular load and store instructions.
    343 
    344 \paragraph{Optimizations.} A \emph{graph compression} algorithm removes empty
    345 instructions generated by previous compilation passes and by the liveness
    346 analysis.
    347 
    348 \subsubsection{LIN}
    349 
    350 In LIN, the structure of a program is no longer based on CFGs. Every function
    351 is represented as a sequence of instructions.
    352 
    353 \paragraph{Syntax.}
    354 The instructions of LIN are very close to those of LTL. \emph{Program
    355   labels}, \emph{gotos} and branch instructions handle the changes in the
    356 control flow. The syntax of LIN programs is shown in table \ref{LIN:syntax}.
    357 
    358 \begin{table}
     326Translating ERTL to LTL relies on the results of the liveness analysis performed on ERTL, and mentioned above, and of the register allocation process.
     327Unused instructions are eliminated and each pseudo register is replaced by a physical location.
     328In LTL, the size of the stack frame of a function is now known.
     329As 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.
     330
     331We use a \emph{graph compression} algorithm to remove empty instructions generated by previous compilation passes and by the liveness analysis.
     332
     333\paragraph{LIN} is a linearised intermediate language, and the final intermediate language before assembly language is produced.
     334The body of every function within LIN is now represented as a sequence of instructions.
     335Despite one being a CFG language, and the other being linear, the instructions of LIN are very close to those of LTL.
     336\emph{Program labels}, \emph{gotos} and branch instructions handle the changes in the control flow.
     337The syntax of LIN programs is presented in Table~\ref{LIN:syntax}.
     338
     339\begin{table}[t]
    359340{\footnotesize
    360341\[
     
    411392\end{table}
    412393
    413 \paragraph{Translation of LTL to LIN.}
    414 This translation amounts to transform in an efficient way the graph structure of
    415 functions into a linear structure of sequential instructions.
    416 
    417 \subsubsection{ASM}
     394Translating 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.
     395Some dead-code elimination is implemented here, as functions that are never called are eliminated entirely.
     396
     397\subsection{Target hardware}
     398
     399\paragraph{MCS-51 assembly language}
Note: See TracChangeset for help on using the changeset viewer.