% l2h ignore change { \chapter[Encoding applications and library] {Encoding applications and the toolkit's library} \label{ch:library} Encoding applications generate instructions in binary form by calling two kinds of toolkit procedures: machine-dependent encoding procedures that are generated from a machine description, and machine-independent procedures that are part of the toolkit's library. These procedures require some support from the application, for example, to allocate space for the relocatable blocks into which instructions are emitted. %The toolkit's library provides most of the %support required by the encoding procedures; %the library procedures are called by the application %to create the state necessary for the encoding procedures. This support is explained in Section~\ref{section:appl-oblig}. Since version~0.2, the toolkit has also been able to generate encoding procedures that emit assembly language. These procedures require additional support from the application, e.g., a method of printing. This chapter specifies the library functions that are used by the toolkit-generated encoding procedures and by the application program. The library includes support for instruction and data streams, in the form of relocatable blocks, and for reading and writing the streams. If the application writer chooses to use his own implementation of streams, the implementation must conform to the specifications given here. The library is written in C, we specify it by writing ANSI~C prototypes for its procedures. Some of the library ``procedures'' are actually implemented as macros; for such macros, we provide prototypes that describe the equivalent procedures. \section{Varieties of encoding procedures} \label{section:encoding} The toolkit can generate two kinds of encoding procedures for untyped constructors: one emits the binary representation of instructions and the other emits the assembly representation. By default, binary encoding procedures call the procedure [[emitm]], which emits tokens in the byte order of the host machine into the current instruction stream. The toolkit's library provides an implementation of \texttt{emitm}, as well as \texttt{emitb}, which emit tokens in big-endian order, and \texttt{emitl}, which emits in little-endian. A user can provide alternative implementations. At toolkit execution time, the [[-byteorder X]] option specifies an alternate emitter function named \texttt{emitX}; [[l]] and [[b]] are reasonable alternatives for [[X]]. The user can delay choosing an emitter function until compile time, by compiling the binary encoding procedures with {\tt cc -DemitX=}{\em emitter-name}. This trick avoids running the generator multiple times, which can be expensive. Assembly encoding procedures call the [[asmprintf]] procedure to emit assembly code onto [[asmprintfd]]. They call [[asmprintreloc]] to print relocatable addresses. The library initializes [[asmprintfd]] to standard output and [[asmprintf]] to [[fprintf]] (or an equivalent procedure). [[asmprintreloc]] prints relocatable addresses in the format {\em label-name+offset}, if the address' label is defined, otherwise it prints {\tt ???{\em +offset}}. Applications can choose alternative print procedures by overriding these values. Unless a field is specified as [[unchecked]], both binary and assembly encoding procedures check that the values of the field's operands are in its range. If unchecked, they do not check an operand's value, but they do mask out the operand's high bits, ensuring that the token is not corrupted by a bad value. If a field is specified as [[guaranteed]], the encoding procedure does not check or mask the operand's value. Encoding procedures are declared external by default and therefore, their names are in the global-name space of the application program that uses them. Often this is inconvenient: encoding procedures' names may conflict with procedure names in the application or the application may need to invoke dynamically multiple sets of encoding procedures, e.g., both binary and assembly. To avoid these problems, the user can invoke the toolkit with {\tt -indirect name[:type]} option, which isolates encoding procedures in a single compilation unit and provides indirect access to them through a structure of procedure pointers. {\tt name} gives the name of the structure and {\tt type} is its type; if {\tt type} is omitted, we use {\tt name}. This permits an application, like the toolkit's checker, to use multiple sets of encoding procedures and to switch between them dynamically. For example, the toolkit checker for the MIPS includes two structures: [[mips_asm]] for assembly encoding procedures and [[mips_bin]] for binary. They are generated by using [[-indirect mips_asm]] and [[-indirect mips_bin:mips_asm]]; the latter option guarantees that both structures have the same type and therefore, can be used interchangeably. \section{Building an encoding application} The toolkit generator transforms a machine description [[m.spec]] into encoding procedures and their interfaces. The interface and implementation are written to different files. The following rules for a Makefile specify how to create and use encoding procedures. The first rule emits encoding procedures into the file [[encoder.c]] and the interface into file [[encoder.h]]: \begin{verbatim} encoder.c encoder.h: m.spec tools -encoder encoder m.spec \end{verbatim} Application source that includes calls to the encoding procedures must include the encoding procedures' header file as well as [[mclib.h]], the header file for the toolkit library. \begin{verbatim} app.o: app.c encoder.h mclib.h cc -c app.c \end{verbatim} Users may have to add an {\tt -I} option so the C~preprocessor can find {\tt mclib.h}. The application executable must include the encoding procedures and the library itself. The last three rules compile the encoding procedures and library source and link the complete application. \begin{verbatim} encoder.o: encoder.c encoder.h mclib.h cc -c encoder.c mclib.o: mclib.c mclib.h cc -c mclib.c app: app.o encoder.o mclib.o cc app.o encoder.o mclib.o -o app \end{verbatim} When compiling \texttt{mclib.c}, compilers for 32-bit hosts may issue warnings about a ``shift count larger than the size of the type.'' These warnings are to be expected and should be ignored. @ The rest of this chapter describes the types, functions, and macros that appear in [[mclib.h]]. \vskip 0pt plus 0.3in % help for underfull \vbox \section{Labels and relocatable blocks} A {\em relocatable block} is the smallest unit of information relocatable by the library and is used to represent a stream of instructions or data. Relocatable blocks can represent information of various types. A traditional linker, for example, might associate one relocatable block with each section in an object file. An incremental linker might associate one relocatable block with each procedure, which would facilitate relocation of individual procedures at link time. % l2h letenv fields* quote A relocatable block [[rb]] has the following fields: \begin{fields*} rb.lc&the current location counter (offset) in [[rb]].\\ rb.size&the size of the relocatable block.\\ rb.low&the lowest value of [[rb.lc]] for which the contents of [[rb]] are known, or null if nothing is known of the contents of [[rb]].\\ rb.address&the absolute address of [[rb]] if that address is known, otherwise null.\\ rb.contents&a buffer storing the contents of [[rb]]. Clients may refer to the elements [[0..rb.size-1]] of [[rb.contents]]. The values of [[rb.contents[0..rb.low-1] ]]are undefined, and it is illegal to attempt to write these values. (This restriction enables an implementation that handles completely uninitialized blocks without allocating any memory.)\\ rb.label&an unnamed label that always refers to the location of the beginning of ([[rb.contents[0]]]).\\ \end{fields*} Because of performance optimizations within the library, it is not safe for applications to read or write these fields directly. Most fields may be read using one of these macros: <>= typedef struct reloc_block *RBlock; <>= extern unsigned block_lc(RBlock rb); extern unsigned block_size(RBlock rb); extern unsigned block_low(RBlock rb); extern int block_address_known(RBlock); extern unsigned block_address(RBlock); extern RLabel block_label(RBlock); @ The [[contents]] aren't directly accessible as values; instead, we provide procedures to copy them into a buffer or a file (see Section~\ref{sec:accessrblocks}). Except for the [[address]] field, this interface provides no way to tell whether fields are [[null]]. These macros return implementation-dependent values instead of [[null]]. The fields of a relocatable block can be written using the procedures defined below. A {\em label} is a location in a relocatable block. All undefined labels are located in a distinguished relocatable block, [[undef]], whose [[address]] field is always null. A label [[l]] has the following fields: \begin{fields*} l.block&the relocatable block in which [[l]] is located\\ l.offset&[[l]]'s offset from the beginning of [[l.block]]\\ l.name&a string associated with [[l]]\\ \end{fields*} The name field may be used by the application to associate labels with names of important objects, e.g., procedures and global symbols. <>= typedef struct label *RLabel; @ \subsection{Operations on relocatable blocks} [[block_new]] creates a new relocatable block, [[rb]], with [[rb.lc = rb.size = 0]], null [[rb.address]] and [[rb.low]], and empty [[rb.contents]]. If the argument [[size]] passed to [[block_new]] is non-zero, the library uses it as a hint about the maximum size the relocatable block is expected to reach. If the hint is accurate, the library will make more efficient use of memory. [[block_new]] adds each newly created block to [[defined_rbs]], the set of all relocatable blocks created, excluding [[undef]]. [[block_defined]] succeeds if the given block is defined, i.e. it is not [[undef]]. <>= extern RBlock block_new(unsigned size); <>= extern int block_defined(RBlock rb); @ [[set_lc]] sets the value of [[rb.lc]] and also updates [[rb.size]] if it is lower than [[rb.lc]]; [[rb.size]] is the ``high-water mark'' of [[rb.lc]]. <>= extern void set_lc(RBlock rb, unsigned lc); @ In order to accomodate traditional assembly languages, the library maintains a current relocatable block [[crb]]. Many of the procedures in this interface have side effects on [[crb]]. Initially, [[crb]] is undefined. [[set_block]] sets the current relocatable block to [[rb]] and [[crb]] produces the current relocatable block. <>= extern void set_block(RBlock rb); <>= extern RBlock crb(void); <>= void (*set_block)(RBlock rb); /* .seg */ void (*crb)(RBlock rb); /* no analog in assembly language */ @ Relocation occurs when an absolute address is assigned to a relocatable block. [[set_address]] sets the address of a block. It can be called multiple times to to change the address.% \footnote{For efficiency, some applications may want to discard relocation information associated with a relocatable block [[rb]]. That would require the ability to mark [[address]] read-only. Let us know if you are interested.} [[block_address]] produces the address. Its value is meaningful if and only if [[block_address_known]] returns nonzero; otherwise the address is null. <>= extern void set_address(RBlock, unsigned); <>= extern int block_address_known(RBlock); extern unsigned block_address (RBlock); @ An application may want to reserve a register to point into a relocatable block. For example, the MIPS short-data ([[.sdata]]) section could be treated as a relocatable block, in which case the reserved register is the global pointer ([[gp]]). If an application wants to reserve more than one register, it should split the relocatable block into multiple blocks. The following two fields make it possible to reserve registers: \begin{fields*} rb.reg&if non-null, it identifies the register that points to [[rb.contents[rb.reglc].]]\\ rb.reglc&the offset within the block to which [[rb.reg]] points.\\ \end{fields*} @ The application notifies the library that a register points into a relocatable block by calling [[set_register]]. The application or toolkit can query the value of the register or its absolute address by calling [[block_reg]] or [[block_regaddr]]. Note that the value of [[reg]] is undefined if [[set_register]] has not been called; [[regaddr]] is similarly undefined if [[reg]] or [[address]] is undefined. It might be desirable to have some error checking to avoid binding two different registers to the same relocatable block; an [[unset_register]] procedure might help but we don't have one right now. <>= extern void set_register(RBlock rb, unsigned reg, unsigned regaddr); extern unsigned block_reg(RBlock rb); extern unsigned block_regaddr(RBlock rb); @ @ \subsection{Operations on labels} [[label_new]] creates a new label located in [[undef]] and assigns [[name]] to [[l.name]]. [[label_define]] binds a label to the given [[offset]] in the current relocatable block. Once a label is defined, it can't be redefined.% \footnote{For most applications (e.g., an assembler, [[mld]]), it is wrong to redefine a label, but an incremental linker might want to redefine a label when a relocatable block is replaced. We're willing to reconsider this decision.} [[label_define_at]] lets you name the block and offset explicitly. <>= extern RLabel label_new(char *name); extern void label_define(RLabel lbl, int offset); extern void label_define_at(RLabel lbl, RBlock block, unsigned lc); <>= void (*label_define)(RLabel lbl, int offset); /* L: */ @ Because [[label_define]] uses an offset, the first pass of an assembler can maintain its own location counter in a register, using that counter to define labels. This trick means one library call per label instead of one per instruction. The absolute address of a label is returned by [[label_location]]. Its value is defined only if [[label_location_known]] is true. <>= extern int label_location_known(RLabel lbl); extern unsigned label_location (RLabel lbl); @ \section{Emitting information} \label{sec:emitinfo} The library is set up to make it easy and efficient to emit instructions or data at the current location in the current relocatable block. Such emission automatically advances the current relocatable block's location counter ([[crb.lc]]). Most applications emit information one word at a time, not one byte at a time, raising the spectre of byte order.\index{byte order} Byte order could be made part of the global state of the library, or it could be selected by supplying a parameter to an emitter procedure, but we have chosen to provide different emitter procedures for different byte orders. Applications that use only one byte order enjoy maximum efficiency; others can get reasonable efficiency by using procedure variables. We provide two procedures that use fixed byte orders, plus a pointer to a third procedure that detects the byte order of the host machine and selects the matching procedure. [[*emitm]], [[emitl]], and [[emitb]] convert the least significant $8 \mathtt n$ bits of [[value]] to a string of bytes, using the endianness requested ([[m]]achine, [[l]]ittle, or [[b]]ig). The [[contents]] of the current relocatable block is extended if it is not big enough to hold the new bits, and the bits are written to that [[contents]] starting at the current location. The location counter is incremented by [[n]]. <>= extern void (*emitm)(unsigned long value, unsigned n); extern void emitl(unsigned long value, unsigned n); extern void emitb(unsigned long value, unsigned n); <>= void (*emitm)(unsigned long value, unsigned n); /* .byte, .short, .word */ void (*emitl)(unsigned long value, unsigned n); void (*emitb)(unsigned long value, unsigned n); @ Emitting bytes sets the low-water mark of the current relocatable block if it isn't set already. It's illegal to emit bytes below the low-water mark. Generated encoding procedures call one of these procedures to emit instructions, as selected by the generator's {\tt -byteorder} option. @ In some applications, the overhead required by the emitting procedures can be significant. This overhead includes not only the cost of a procedure call, but also the costs of manipulating bytes in a well-defined order. For example, it is in general unsafe to use a full-word store to place a full word into a relocatable block, even when the target byte order matches that of the host machine, because the alignment may not be correct. Some applications (e.g., RISC code generators) always maintain proper alignment. Such applications can achieve significant speedups by using the [[emitfast]] macro, which has the same effect as [[emitm]], provided that the location counter is properly aligned to the size of the token being emitted. When the location counter is not properly aligned, the effect of [[emitfast]] is undefined, so it is in general unsafe. <>= extern void emitfast(unsigned long value, unsigned n); @ For convenience, we provide macros that emit full and half words and individual bytes using the byte order of the machine. They are simply abbreviations for calls to [[emitm]]. <>= extern void emitu(unsigned value); extern void emitus(unsigned short value); extern void emituc(unsigned char value); @ It would also be convenient to have a procedure for emitting relocatable addresses, but that one would be hard to write. Luckily, users can generate it from a specification like this one: <>= fields of addrword (32) addr32 0:31 placeholder for addrword is addr32 = 0xbadbad constructors emit_raddr reloc is addr32 = reloc @ \section{Manipulating the location counter} The current location counter can be changed by [[align]], [[org]], and [[addlc]]. [[align]] aligns the current location counter on an [[n]]-byte boundary, [[org]] sets the location counter to [[lc]], and and [[addlc]] adds [[n]] bytes to the location counter's current value. <>= extern void align(unsigned n); <>= extern void org(unsigned lc); extern void addlc(unsigned n); <>= void (*align)(unsigned n); /* .align */ void (*org)(unsigned lc); /* .org */ void (*addlc)(unsigned n); /* .space */ @ Applications may also change the location counter of any relocatable block using [[set_lc]], as described above. The application can read [[crb]]'s location counter using [[lc]]. <>= extern unsigned lc(void); @ The toolkit is optimized for advancing location counters, so it is more efficient to use [[addlc(n)]] than to use \mbox{[[set_lc(crb(), lc()+n)]]}, because [[set_lc]] must handle the general case. @ \section{Relocation and closures} Computation involving relocatable addresses may be delayed until the location of a relocatable block is fixed. For example, the [[emit_raddr]] constructor specified above emits a 32-bit relocatable address into the current relocatable block. If [[reloc]] is unknown when [[emit_raddr]] is applied, the toolkit generator emits the place-holder pattern [[addr32 = 0xbadbad]] and creates a {\em relocation closure} ([[RClosure]]). In general, the toolkit generator emits a place-holder and creates a relocation closure for any instruction that refers to a relocatable address whose value is unknown. A closure captures the information necessary for delayed evaluation of expressions involving relocatable addresses. When a relocation closure is applied, it overwrites the place-holder instruction with the relocated instruction. @ Each relocation closure writes a sequence of tokens starting at a single location in a single relocatable block. Every closure uses, or {\em depends on}, at least one relocatable address. A relocation closure [[cl]] has the following fields: \begin{fields*} cl.dest_block&the relocatable block to be written by [[cl]]\cr cl.dest_lc&the location written\cr cl.depends_on&the set of relocatable addresses on which the closure depends\cr cl.apply&a function that writes to [[cl.dest_lc]], using the values of all the addresses in [[cl.depends_on]]\cr \end{fields*} @ Applications may apply closures individually, as the relocatable addresses on which they depend become known, or all at once, after all relocatable blocks have known addresses. Because time of relocation is application-dependent, the library relies upon the application to save relocation closures in whatever manner it finds most convenient and then to apply the closures when ready. The toolkit requires the application to implement [[mc_alloc_closure]], which allocates space for a closure and saves it in an application-dependent data structure; see Section~\ref{section:appl-oblig}. The library provides [[apply_closure]], a closure-independent procedure that applies the closure [[cl]]. <>= typedef struct rclosure *RClosure; typedef void (*Emitter) (RBlock, unsigned dest_lc, unsigned long bits, unsigned size); typedef void (*FailCont)(char *fmt, ...); @ %def FailCont Emitter <>= extern void apply_closure(RClosure cl, Emitter emitter, FailCont failc); @ If any of the addresses on which [[cl]] depends is unknown, the failure continuation [[failc]] is applied. It should not return (see Section~\ref{sec:fail}). The [[Emitter]] procedure performs the same functions as the [[emit]] procedures specified above, but instead of writing the current relocatable block, it updates the relocatable block [[dest_block]] at the location [[dest_lc]]. The library provides [[Emitter]] procedures in three byte orders: machine order, little-endian, and big-endian. <>= extern void (*cl_emitm)(RBlock dest_block, unsigned dest_lc, unsigned long bits, unsigned size); extern void cl_emitl (RBlock dest_block, unsigned dest_lc, unsigned long bits, unsigned size); extern void cl_emitb (RBlock dest_block, unsigned dest_lc, unsigned long bits, unsigned size); @ %def cl_emitm cl_emitl cl_emitb If the application writer provides an [[Emitter]] procedure to [[apply_closure]], its action must not depend on the values of the current relocatable block or current location counter used by the library's [[emit]] procedures. @ \section{Application's obligations} \label{section:appl-oblig} The library relies on the application to allocate and store relocation closures, apply closures once the relocatable addresses on which they depend are known, and provide memory-management services to the library, which needs to allocate relocatable blocks, labels, relocatable addresses (fixed size) and contents of blocks (variable size). @ The application must provide an allocator named [[mc_alloc]], which accepts two parameters. The first is the size of the object to be allocated, and the second indicates what is being allocated. The second parameter may be used by the application to allocate objects from different memory pools; it tells the application whether memory is being allocated for a relocatable block, the contents of a relocatable block, a label, or a relocatable address. <>= typedef enum mc_alloc_pool { RBlock_pool=1, RBlock_data_pool, RLabel_pool, RAddr_pool } Mc_alloc_pool; <>= extern void *mc_alloc(int size, Mc_alloc_pool pool); @ Applications must also provide [[mc_alloc_closure]] procedure to allocate memory for a new closure. We use a separate procedure because applications might want to use the destination block and location as hints to determine from what memory to allocate the closure:\change{7} <>= extern RClosure mc_alloc_closure(unsigned size, RBlock dest_block, unsigned dest_lc); @ %def mc_alloc_closure [[mc_alloc_closure]] is called by generated encoding procedures, which fill in the fields of the new closure. @ Generated encoding procedures call [[*fail]] if they are called upon to do something they can't, i.e., if their equations can't be solved. For example, the MIPS encoding procedures call [[*fail]] if asked to branch to an address that is not aligned to a 4-byte boundary. Applications must initialize [[fail]] to point to a suitable procedure (e.g., one that prints an error message, and maybe exits or [[longjmp]]s).\label{sec:fail} <>= extern void (*fail)(char *fmt, ...); @ [[*fail]] may be used as a failure continuation when calling [[apply_closure]]. @ The application is not obligated to provide code used to print assembly language, but it can override the toolkit's choice if it wants to. See \secn{asmprintf}. \section{Accessing contents of relocatable blocks} \label{sec:accessrblocks} To access data already emitted in a relocatable block, applications may call [[block_write]] or [[block_copy]]. [[block_write]] writes the [[n]] bytes of [[rb]]'s [[contents]] beginning at offset [[start]] to the file descriptor [[fd]]; [[block_copy]] is similar but copies into the buffer [[buf]] instead of writing to [[fd]]; the application must allocate memory for [[buf]] before calling [[block_copy]]. <>= extern void block_write(int fd,RBlock rb,unsigned start,unsigned n); extern void block_copy(unsigned char *buf, RBlock rb, unsigned start, unsigned n); @ %def block_copy We also provide individual access to the contents of relocatable blocks, in three byte orders: machine order, little-endian, and big-endian. <>= extern unsigned long (*block_fetchm)(RBlock dest_block, unsigned dest_lc, unsigned size); extern unsigned long block_fetchl (RBlock dest_block, unsigned dest_lc, unsigned size); extern unsigned long block_fetchb (RBlock dest_block, unsigned dest_lc, unsigned size); @ %def block_fetchm block_fetchl block_fetchb \ifx\refman\undefined\else \begingroup \let\chapter=\section \input{manreloc} \input{mld-excerpts} \endgroup \fi \section{Emitting assembly language} \label{section:asmprintf} The details of getting the generator to create encoding procedures that emit assembly language are covered in Section~\ref{section:encoding}. A toolkit application must provide a \texttt{printf}-like procedure plus a procedure for printing relocatable addresses: <>= extern void (*asmprintf)(void *closure, const char *fmt, ...); extern void *asmprintfd; /* closure */ extern void (*asmprintreloc)(RAddr reloc); /* calls asmprintf */ @ The toolkit initializes these variables to print something sensible on standard output. Applications can change behavior by overwriting them.