=================== Calling conventions =================== What is shown here is a simple and efficient way for realizing a __function call convention__. However, there is a serious catch to it. It only works for so called _leaf functions_, i.e. functions that do not call another functions. So in particular something like recursive function calls will not work with that. At the moment we develop concepts for programming a computer in general and do not really focus on efficiency. In Session 8 you saw how difficult it can get to write fairly complex programs without having a possibility to break components into reusable functions (for reading an integer, computing something, printing an integer). What we did there was thinking about a program that consisted of such parts (i.e. functions) but instead of calling a function we just inserted its code where it was needed. In the real world this is an optimization called _function inlining_. This is an optimization because function calls always have some overhead. You will see here that this overhead consists of additional code for passing arguments, calling the function, returning form the function etc. With respect to efficiency the function call convention would be the next best thing compared to inlining the call. But again, efficiency is not our main concern here, it is still about programming the ULM in general. So let's say we look at this convention because compared to the general case (which includes non-leaf functions) it is easier to deal with the special case and for this case we seek the simplest, possible solution. Using the instruction `jmp %CALL, %RET` for function calls =========================================================== Key for supporting functions calls on the ULM is the __jmp__ instruction with Opcode 0x40. It has two register operands to which we refer as `%CALL` and `%RET` respectively. When executed it does two things: - It jumps to the address in `%CALL` and - stores the return address `%RET`. So what does _return address_ mean? It is the address of the instruction that follows the jump instruction in memory. For example, when the jump instruction is at address 0x20 then the return address is 0x24. ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{memory.tex} \renewcommand\MemCellWidth { 1 } \DrawMemArrayOpen{0}{15} \DrawLongVariable{4}{ {\small ldzwq func, \%CALL} } \DrawLongVariable[blue!20]{8}{ {\small jmp \%CALL, \%RET} } \DrawMemAddress{8}{0x24} \DrawMemAddress{12}{0x28} \end{tikzpicture} -------------------------------------------------------------------------------- The sequential execution and the implementation pattern for a program that calls a leaf-function `func` twice can be visualised as follows: ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{flowchart.tex} \SetMargin{5}{10}{0}{5} \renewcommand\BoxWidth {5} \PutStatement{0}{A} \PutStatement{1}{ldzwq func, \%CALL} \PutCallStatement[red]{2}{ jmp \%CALL, \%RET} \PutStatement{3}{B} \PutStatement{4}{ldzwq func, \%CALL} \PutCallStatement[blue]{5}{jmp \%CALL, \%RET} \PutStatement{6}{C} \AddPath{0}{1} \AddPath{1}{2} \AddPath{2}{3} \AddPath{3}{4} \AddPath{4}{5} \AddPath{5}{6} \PutAnnotation{0}{\text{Entry point}} % next flow chart column \renewcommand\FlowCol{1} \PutStatement{0}{x} \PutLabel{0}{func} \PutStatement{1}{jmp \%RET} \AddPath{0}{1} \DrawCallPointer[red]{0}{2}{1}{0} \DrawReturnPointer[red]{0}{2}{1}{1} \renewcommand{\CallPointerPadToY}{1} \DrawCallPointer[blue]{0}{5}{1}{0} \DrawReturnPointer[blue]{0}{5}{1}{1} \end{tikzpicture} -------------------------------------------------------------------------------- And analogously cases where different functions are called the flow chart can be represented like this: ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{flowchart.tex} \SetMargin{5}{10}{0}{5} \renewcommand\BoxWidth {5} \PutStatement{0}{A} \PutStatement{1}{ldzwq funcA, \%CALL} \PutCallStatement[red]{2}{ jmp \%CALL, \%RET} \PutStatement{3}{B} \PutStatement{4}{ldzwq funcB, \%CALL} \PutCallStatement[blue]{5}{jmp \%CALL, \%RET} \PutStatement{6}{C} \AddPath{0}{1} \AddPath{1}{2} \AddPath{2}{3} \AddPath{3}{4} \AddPath{4}{5} \AddPath{5}{6} \PutAnnotation{0}{\text{Entry point}} % next flow chart column \renewcommand\FlowCol{1} \PutStatement{0}{x} \PutLabel{0}{funcA} \PutStatement{1}{jmp \%RET} \AddPath{0}{1} % next flow chart column \renewcommand\FlowCol{2} \PutStatement{0}{y} \PutLabel{0}{funcB} \PutStatement{1}{jmp \%RET} \AddPath{0}{1} \DrawCallPointer[red]{0}{2}{1}{0} \DrawReturnPointer[red]{0}{2}{1}{1} \renewcommand{\CallPointerPadToY}{1} \DrawCallPointer[blue]{0}{5}{2}{0} \DrawReturnPointer[blue]{0}{5}{2}{1} \end{tikzpicture} -------------------------------------------------------------------------------- You want a more technical explanation? -------------------------------------- Recall that the ULM implements this simple von Neumann cycle for executing a program. So when an instruction gets executed it was loaded from address `%IP` (instruction pointer) into the `%IR` (instruction register). So what the instruction does when it gets executed is ---- LATEX --------------------------------------------------------------------- \left( u(\%\text{ip}) + 4 \right) \bmod 2^{64} \to u(\%\text{RET}) \quad\text{and} \quad u(\%\text{CALL}) \to u(\%\text{ip}) -------------------------------------------------------------------------------- Returning from a function is then possible with a `jmp %RET, %0` instruction. Of course this requires that `%RET` by then still (or again) contains the original return address. So when you program you should know that you can not simply use register `%RET` without care. So you see that we need some rules, a protocol or call it convention for function calls. ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{memory.tex} \renewcommand\MemCellWidth { 1 } \DrawMemArrayOpenRight{0}{20} \DrawMemLabel{0}{Entry Point} \DrawMemVariable[green!20]{0}{8}{ Main program (Caller) } \DrawMemVariable[orange!20]{8}{13}{ Leaf function A (Callee) } \DrawMemVariable[orange!20]{13}{18}{ Leaf function B (Callee) } \end{tikzpicture} -------------------------------------------------------------------------------- Descriptions of such conventions usually the terms _caller_ and _callee_. As long as we only deal with leaf functions these terms have a simple meaning. The program text can be divided into a main program and functions. In the main program we only have code that eventually calls a function, i.e. caller code. In the functions we only have code that gets executed when a function was called, i.e. callee code. Now think of two persons (caller and callee) writing a program together. The caller is writing the main program, the callee all the functions. The function call conventions are a contract between the caller and callee and allows to collaborate almost independently from each other. Actually the contract specifies what information one has to provide to another. Caller ------ The caller has to know the address of the function, how to pass arguments and eventually how to get a result back from the function. The caller also has to know what registers the function might modify. In the simplest form the function does not expect any arguments and does not return a result. In this case the caller just loads the address of the function into `%CALL` and does the (function) jump: ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{memory.tex} \renewcommand\MemCellWidth { 1 } \DrawMemArrayOpenRight{0}{20} \begingroup \renewcommand\PaddingMemVariable {0.05} \DrawMemVariable[green!20]{0}{20} \par\endgroup \DrawLongVariable{4}{ {\small ldzwq func, \%CALL} } \DrawLongVariable[blue!20]{8}{ {\small jmp \%CALL, \%RET} } \DrawMemLabel{0}{Entry point} \end{tikzpicture} -------------------------------------------------------------------------------- Also shown in this picture is the _entry point_ of the program. The entry point is the address of the instruction that gets executed first when execution of the program starts. Of course a correct program should also have at least one exit point, i.e. some halt instruction. As a programmer you have to make sure that at least on of these exit points gets reached. Callee ------ Accordingly the callee needs to know how to receive arguments, how to return and eventually how to give back a result. And of course, what registers can be used and modified for computations. Again we first consider that the function does not receive any arguments and does not return any result. Then we basically have this (we talk about what registers the function implementation is allowed to modify below): ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{memory.tex} \renewcommand\MemCellWidth { 1 } \DrawMemArrayOpen{0}{20} \begingroup \renewcommand\PaddingMemVariable {0.05} \DrawMemVariable[orange!20]{0}{10}{} \DrawMemVariable[orange!20]{0}{5}{Leaf function A } \renewcommand\PaddingMemVariable {0.05} \DrawMemVariable[orange!20]{10}{20}{} \DrawMemVariable[orange!20]{10}{14}{Leaf function B } \par\endgroup \DrawLongVariable[blue!20]{6}{ {\small jmp \%RET, \%0} } \DrawLongVariable[blue!20]{16}{ {\small jmp \%RET, \%0} } \DrawMemLabel{0}{A} \DrawMemLabel{10}{B} \end{tikzpicture} -------------------------------------------------------------------------------- Example ------- So here another "hello, world" program: ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o func01 func01.s ulm func01 -------------------------------------------------------------------------------- This time it uses functions. For the sake of simplicity we first stick to the case where the function does not receive arguments, does not return a result and not even uses any registers. But it has two functions and does four function calls: :import: session09/func/func01.s Callee, the perfect roomer ========================== The caller and callee need a protocol that specifies what registers (and as we talk about later what memory region) can be used without conflicts. We keep it simple here: The callee is only allowed to modify registers that we denote as `%CALLEE0`, `%CALLEE1`, etc. This will be defined through some `.equ` directives. For example in the next example we define ---- CODE (type=s) -------------------- .equ CALLEE0, 1 .equ CALLEE1, CALLEE0 + 1 --------------------------------------- Think of this like a contract between you and a roomer that lives in your apartment. This contract specifies what the roomer is allowed to use in your apartment. In other examples we give the callee access to more registers but it always will be limited. Of course the ULM would have enough registers to share the registers more equally. But first of all, we want to keep it close enough to reality where most computers have much fewer registers and they can live with that (And so can we: The ULM has only 256 registers because that makes it simple to read the machine code). Next, a callee can actually use any register as long as the callee can restore them after usage. That means before returning to the caller all registers that do not belong to the callee must have their original value. So no harm done. Like in the example with the roomer in your apartment. You certainly don't mind if someone uses your stuff if it is guarantied that you will never notice ;-) Furthermore, sooner or later we want to think about functions that are non-leaf functions, i.e functions that call other functions. In this case the callee becomes a caller (and then again a callee before it returns). So just equally sharing registers between caller and callee would be a dead end. But let's talk about here and now. We still have to specify how arguments are passed and results returned. Passing arguments ----------------- A function receives its arguments (if any) in the callee registers: The first argument in `%CALLEE0`, the second in `%CALLEE1`, etc. The caller has to know how many arguments are expected by the callee. There is no way that the assembler can check if you are passing to few or too many arguments. So the programmer of the function has to document this (or the caller would have to look at the code and figure that out). Receiving results ----------------- If a function returns a value this value will be store in `%CALLEE0` after the return. So the callee has to put it there before returning. Example for a `puts` function ============================= We continue with a multilingual version of the "hello, world" program ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o func02 func02.s ulm func02 -------------------------------------------------------------------------------- In this example the function `puts` expects one argument (in `%CALLEE0`) which is a pointer to a string that will be printed by the function: :import: session09/func/func02.s Example with functions `puts`, `readuint` and `printuint` ========================================================= In general our functions need more than just two registers. Until we don't know how to use a stack to save and restore registers that do not belong to a callee we have to provide more registers to the callee. The following program reads in an integer and then prints it. The callee can now use up to 4 registers. If you use it interactively it looks like that: ---- CODE (type=txt) ----------------------------------------------------------- theon$ ulm func03 Type in some unsigned integer (that fits in 64 bits): 1234567890123 You typed in: 1234567890123 bye! -------------------------------------------------------------------------------- When I create this web pages automatically (which has the advantage that you can be sure that what you see in the shell box below is no fake) I can not type in numbers. So I generate the input by piping the output of an `echo` like here: ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o func03 func03.s echo 1234567890123 | ulm func03 -------------------------------------------------------------------------------- :import: session09/func/func03.s :links: function call convention -> https://en.wikipedia.org/wiki/Calling_convention jmp -> http://www.mathematik.uni-ulm.de/numerik/hpc/ss20/hpc0/ulm.pdf#page=25 :navigate: up -> doc:index back -> doc:session09/page01 next -> doc:session09/page03