<html><title>data</title><body BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#330088" ALINK="#FF0044"><H1>Plan 9 C Compilers</H1><DL><DD><I>Ken Thompson<br>ken@plan9.bell-labs.com<br></I></DL><DL><DD><H4>ABSTRACT</H4><DL><DT><DT> <DD>NOTE:<I> Originally appeared, in a different form, inProceedings of the Summer 1990 UKUUG Conference,pp. 41-51,London, 1990.</I><DT> <DD></dl><br>This paper describes the overall structure and function of the Plan 9 C compilers.A more detailed implementation documentfor any one of the compilersis yet to be written.</DL><H4>1 Introduction</H4><br> <br>There are many compilers in the series.Six of the compilers (MIPS 3000, SPARC, Intel 386, Power PC, DEC Alpha, and Motorola 68020)are considered active and are used to compilecurrent versions of Plan 9.Several others (Motorola 68000, Intel 960, ARM 7500, AMD 29000) have had only limited use, such asto program peripherals or experimental devices.<H4>2 Structure</H4><br> <br>The compiler is a single program that produces anobject file.Combined in the compiler are the traditionalroles of preprocessor, lexical analyzer, parser, code generator,local optimizer,and first half of the assembler.The object files are binary forms of assemblylanguage,similar to what might be passed betweenthe first and second passes of an assembler.<br> <br>Object files and librariesare combined by a loaderprogram to produce the executable binary.The loader combines the roles of second halfof the assembler, global optimizer, and loader.The names of the compliers, loaders, and assemblersare as follows:<DL><DT><DD><TT><PRE>SPARC <TT>kc</TT> <TT>kl</TT> <TT>ka</TT>Power PC <TT>qc</TT> <TT>ql</TT> <TT>qa</TT>MIPS <TT>vc</TT> <TT>vl</TT> <TT>va</TT>Motorola 68000 <TT>1c</TT> <TT>1l</TT> <TT>1a</TT>Motorola 68020 <TT>2c</TT> <TT>2l</TT> <TT>2a</TT>ARM 7500 <TT>5c</TT> <TT>5l</TT> <TT>5a</TT>Intel 960 <TT>6c</TT> <TT>6l</TT> <TT>6a</TT>DEC Alpha <TT>7c</TT> <TT>7l</TT> <TT>7a</TT>Intel 386 <TT>8c</TT> <TT>8l</TT> <TT>8a</TT>AMD 29000 <TT>9c</TT> <TT>9l</TT> <TT>9a</TT></PRE></TT></DL>There is a further breakdownin the source of the compilers intoobject-independent andobject-dependentparts.All of the object-independent partsare combined into source files in thedirectory<TT>/sys/src/cmd/cc</TT>.The object-dependent parts are collectedin a separate directory for each compiler,for example<TT>/sys/src/cmd/vc</TT>.All of the code,both object-independent andobject-dependent,is machine-independentand may be cross-compiled and executed on anyof the architectures.<H4>3 The Language</H4><br> <br>The compiler implements ANSI C with somerestrictions and extensions[ANSI90].Most of the restrictions are due topersonal preference, whilemost of the extensions were to help inthe implementation of Plan 9.There are other departures from the standard,particularly in the libraries,that are beyond the scope of thispaper.<H4>3.1 Register, volatile, const</H4><br> <br>The keyword<TT>register</TT>is recognized syntacticallybut is semantically ignored.Thus taking the address of a<TT>register</TT>variable is not diagnosed.The keyword<TT>volatile</TT>disables all optimizations, in particular registerization, of the corresponding variable.The keyword<TT>const</TT>generates warnings (if warnings are enabled by the compiler's<TT>-w</TT>option) of non-constant use of the variable,but does not affect the generated code.<H4>3.2 The preprocessor</H4><br> <br>The C preprocessor is probably thebiggest departure from the ANSI standard.<br> <br>The preprocessor built into the Plan 9 compilers does not support<TT>#if</TT>,although it does handle<TT>#ifdef</TT>and<TT>#include</TT>.If it is necessary to be more standard,the source text can first be run through the separate ANSI Cpreprocessor,<TT>cpp</TT>.<H4>3.3 Unnamed substructures</H4><br> <br>The most important and most heavily used of theextensions is the declaration of anunnamed substructure or subunion.For example:<DL><DT><DD><TT><PRE> typedef struct lock { int locked; } Lock; typedef struct node { int type; union { double dval; float fval; long lval; }; Lock; } Node; Lock* lock; Node* node;</PRE></TT></DL>The declaration of<TT>Node</TT>has an unnamed substructure of type<TT>Lock</TT>and an unnamed subunion.One use of this feature allows references to elements of thesubunit to be accessed as if they were inthe outer structure.Thus<TT>node->dval</TT>and<TT>node->locked</TT>are legitimate references.<br> <br>When an outer structure is usedin a context that is only legal foran unnamed substructure,the compiler promotes the reference to theunnamed substructure.This is true for references to structures andto references to pointers to structures.This happens in assignment statements andin argument passing where prototypes have beendeclared.Thus, continuing with the example,<DL><DT><DD><TT><PRE> lock = node;</PRE></TT></DL>would assign a pointer to the unnamed<TT>Lock</TT>inthe<TT>Node</TT>to the variable<TT>lock</TT>.Another example,<DL><DT><DD><TT><PRE> extern void lock(Lock*); func(...) { ... lock(node); ... }</PRE></TT></DL>will pass a pointer to the<TT>Lock</TT>substructure.<br> <br>Finally, in places where context is insufficient to identify the unnamed structure,the type name (it must be a<TT>typedef</TT>)of the unnamed structure can be used as an identifier.In our example,<TT>&node->Lock</TT>gives the address of the anonymous<TT>Lock</TT>structure.<H4>3.4 Structure displays</H4><br> <br>A structure cast followed by a list of expressions in braces isan expression with the type of the structure and elements assigned fromthe corresponding list.Structures are now almost first-class citizens of the language.It is common to see code like this:<DL><DT><DD><TT><PRE> r = (Rectangle){point1, (Point){x,y+2}};</PRE></TT></DL><H4>3.5 Initialization indexes</H4><br> <br>In initializers of arrays,one may place a constant expressionin square brackets before an initializer.This causes the next initializer to assignthe indicated element.For example:<DL><DT><DD><TT><PRE> enum errors { Etoobig, Ealarm, Egreg }; char* errstrings[] = { [Ealarm] "Alarm call", [Egreg] "Panic: out of mbufs", [Etoobig] "Arg list too long", };</PRE></TT></DL>In the same way,individual structures members maybe initialized in any order by preceding the initialization with<TT>.tagname</TT>.Both forms allow an optional<TT>=</TT>,to be compatible with a proposedextension to ANSI C.<H4>3.6 External register</H4><br> <br>The declaration<TT>extern</TT><TT>register</TT>will dedicate a register toa variable on a global basis.It can be used only under special circumstances.External register variables must be identicallydeclared in all modules andlibraries.The feature is not intended for efficiency,although it can produce efficient code;rather it represents a unique storage class thatwould be hard to get any other way.On a shared-memory multi-processor,an external register isone-per-processor and neither one-per-procedure (automatic)or one-per-system (external).It is used for two variables in the Plan 9 kernel,<TT>u</TT>and<TT>m</TT>.<TT>U</TT>is a pointer to the structure representing the currently running processand<TT>m</TT>is a pointer to the per-machine data structure.<H4>3.7 Long long</H4><br> <br>The compilers accept<TT>long</TT><TT>long</TT>as a basic type meaning 64-bit integer.On all of the machinesthis type is synthesized from 32-bit instructions.<H4>3.8 Pragma</H4><br> <br>The compilers accept<TT>#pragma</TT><TT>lib</TT><I>libname</I>and pass thelibrary name string uninterpretedto the loader.The loader uses the library name tofind libraries to load.If the name contains<TT>%O</TT>,it is replaced withthe single character object type of the compiler(e.g.,<TT>v</TT>for the MIPS).If the name contains<TT>%M</TT>,it is replaced withthe architecture type for the compiler(e.g.,<TT>mips</TT>for the MIPS).If the name starts with<TT>/</TT>it is an absolute pathname;if it starts with<TT>.</TT>then it is searched for in the loader's current directory.Otherwise, the name is searched from<TT>/%M/lib</TT>.Such<TT>#pragma</TT>statements in header files guarantee that the correctlibraries are always linked with a program without theneed to specify them explicitly at link time.<br> <br>They also accept<TT>#pragma</TT><TT>hjdicks</TT><TT>on</TT>(or<TT>yes</TT>or<TT>1</TT>)to cause subsequently declared data, until<TT>#pragma</TT><TT>hjdicks</TT><TT>off</TT>(or<TT>no</TT>or<TT>0</TT>),to be laid out in memory tightly packed in successive bytes, disregardingthe usual alignment rules.Accessing such data can cause faults.<br> <br>Two<TT>#pragma</TT>statements allow type-checking of<TT>print</TT>-likefunctions.The first, of the form<DL><DT><DD><TT><PRE>#pragma varargck argpos error 2</PRE></TT></DL>tells the compiler that the second argument to<TT>error</TT>is a<TT>print</TT>format string (see the manual page<A href="/magic/man2html/2/print"><I>print</I>(2))</A>that specifies how to format<TT>error</TT>'ssubsequent arguments.The second, of the form<DL><DT><DD><TT><PRE>#pragma varargck type "s" char*</PRE></TT></DL>says that the<TT>print</TT>format verb<TT>s</TT>processes an argument oftype<TT>char*</TT>.If the compiler's<TT>-F</TT>option is enabled, the compiler will use this informationto report type violations in the arguments to<TT>print</TT>,<TT>error</TT>,and similar routines.<H4>4 Object module conventions</H4><br> <br>The overall conventions of the runtime environmentare importantto runtime efficiency.In this section,several of these conventions are discussed.<H4>4.1 Register saving</H4><br> <br>In the Plan 9 compilers,the caller of a procedure saves the registers.With caller-saves,the leaf procedures can use all theregisters and never save them.If you spend a lot of time at the leaves,this seems preferable.With callee-saves,the saving of the registers is donein the single point of entry and return.If you are interested in space,this seems preferable.In both,there is a degree of uncertaintyabout what registers need to be saved.Callee-saved registers make it difficult tofind variables in registers in debuggers.Callee-saved registers also complicatethe implementation of<TT>longjmp</TT>.The convincing argument isthat with caller-saves,the decision to registerize a variablecan include the cost of saving the registeracross calls.For a further discussion of caller- vs. callee-saves,see the paper by Davidson and Whalley [Dav91].<br> <br>In the Plan 9 operating system,calls to the kernel look like normal procedurecalls, which meansthe callerhas saved the registers and the systementry does not have to.This makes system calls considerably faster.Since this is a potential security hole,and can lead to non-determinism,the system may eventually save the registerson entry,or more likely clear the registers on return.<H4>4.2 Calling convention</H4><br> <br>Older C compilers maintain a frame pointer, which is at a known constantoffset from the stack pointer within each function.For machines where the stack grows towards zero,the argument pointer is at a known constant offsetfrom the frame pointer.Since the stack grows down in Plan 9,the Plan 9 compilerskeep neither anexplicit frame pointer noran explicit argument pointer;instead they generate addresses relative to the stack pointer.<br> <br>On some architectures, the first argument to a subroutine is passed in a register.<H4>4.3 Functions returning structures</H4><br> <br>Structures longer than one word are awkward to implementsince they do not fit in registers and mustbe passed around in memory.Functions that return structuresare particularly clumsy.The Plan 9 compilers pass the return address ofa structure as the first argument of afunction that has a structure return value.Thus<DL><DT><DD><TT><PRE> x = f(...)</PRE></TT></DL>is rewritten as<DL><DT><DD><TT><PRE> f(&x, ...).</PRE></TT></DL>This saves a copy and makes the compilationmuch less clumsy.A disadvantage is that if you call thisfunction without an assignment,a dummy location must be invented.<br> <br>There is also a danger of calling a functionthat returns a structure without declaringit as such.With ANSI C function prototypes,this error need never occur.<H4>5 Implementation</H4><br> <br>The compiler is divided internally intofour machine-independent passes,Lines 1–500 of 1093. Load more
<html> <title> data </title> <body BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#330088" ALINK="#FF0044"> <H1>Plan 9 C Compilers </H1> <DL><DD><I>Ken Thompson<br> ken@plan9.bell-labs.com<br> </I></DL> <DL><DD><H4>ABSTRACT</H4> <DL> <DT><DT> <DD> NOTE:<I> Originally appeared, in a different form, in Proceedings of the Summer 1990 UKUUG Conference, pp. 41-51, London, 1990. </I><DT> <DD></dl> <br> This paper describes the overall structure and function of the Plan 9 C compilers. A more detailed implementation document for any one of the compilers is yet to be written. </DL> <H4>1 Introduction </H4> <br> <br> There are many compilers in the series. Six of the compilers (MIPS 3000, SPARC, Intel 386, Power PC, DEC Alpha, and Motorola 68020) are considered active and are used to compile current versions of Plan 9. Several others (Motorola 68000, Intel 960, ARM 7500, AMD 29000) have had only limited use, such as to program peripherals or experimental devices. <H4>2 Structure </H4> <br> <br> The compiler is a single program that produces an object file. Combined in the compiler are the traditional roles of preprocessor, lexical analyzer, parser, code generator, local optimizer, and first half of the assembler. The object files are binary forms of assembly language, similar to what might be passed between the first and second passes of an assembler. <br> <br> Object files and libraries are combined by a loader program to produce the executable binary. The loader combines the roles of second half of the assembler, global optimizer, and loader. The names of the compliers, loaders, and assemblers are as follows: <DL><DT><DD><TT><PRE> SPARC <TT>kc</TT> <TT>kl</TT> <TT>ka</TT> Power PC <TT>qc</TT> <TT>ql</TT> <TT>qa</TT> MIPS <TT>vc</TT> <TT>vl</TT> <TT>va</TT> Motorola 68000 <TT>1c</TT> <TT>1l</TT> <TT>1a</TT> Motorola 68020 <TT>2c</TT> <TT>2l</TT> <TT>2a</TT> ARM 7500 <TT>5c</TT> <TT>5l</TT> <TT>5a</TT> Intel 960 <TT>6c</TT> <TT>6l</TT> <TT>6a</TT> DEC Alpha <TT>7c</TT> <TT>7l</TT> <TT>7a</TT> Intel 386 <TT>8c</TT> <TT>8l</TT> <TT>8a</TT> AMD 29000 <TT>9c</TT> <TT>9l</TT> <TT>9a</TT> </PRE></TT></DL> There is a further breakdown in the source of the compilers into object-independent and object-dependent parts. All of the object-independent parts are combined into source files in the directory <TT>/sys/src/cmd/cc</TT>. The object-dependent parts are collected in a separate directory for each compiler, for example <TT>/sys/src/cmd/vc</TT>. All of the code, both object-independent and object-dependent, is machine-independent and may be cross-compiled and executed on any of the architectures. <H4>3 The Language </H4> <br> <br> The compiler implements ANSI C with some restrictions and extensions [ANSI90]. Most of the restrictions are due to personal preference, while most of the extensions were to help in the implementation of Plan 9. There are other departures from the standard, particularly in the libraries, that are beyond the scope of this paper. <H4>3.1 Register, volatile, const </H4> <br> <br> The keyword <TT>register</TT> is recognized syntactically but is semantically ignored. Thus taking the address of a <TT>register</TT> variable is not diagnosed. The keyword <TT>volatile</TT> disables all optimizations, in particular registerization, of the corresponding variable. The keyword <TT>const</TT> generates warnings (if warnings are enabled by the compiler's <TT>-w</TT> option) of non-constant use of the variable, but does not affect the generated code. <H4>3.2 The preprocessor </H4> <br> <br> The C preprocessor is probably the biggest departure from the ANSI standard. <br> <br> The preprocessor built into the Plan 9 compilers does not support <TT>#if</TT>, although it does handle <TT>#ifdef</TT> and <TT>#include</TT>. If it is necessary to be more standard, the source text can first be run through the separate ANSI C preprocessor, <TT>cpp</TT>. <H4>3.3 Unnamed substructures </H4> <br> <br> The most important and most heavily used of the extensions is the declaration of an unnamed substructure or subunion. For example: <DL><DT><DD><TT><PRE> typedef struct lock { int locked; } Lock; typedef struct node { int type; union { double dval; float fval; long lval; }; Lock; } Node; Lock* lock; Node* node; </PRE></TT></DL> The declaration of <TT>Node</TT> has an unnamed substructure of type <TT>Lock</TT> and an unnamed subunion. One use of this feature allows references to elements of the subunit to be accessed as if they were in the outer structure. Thus <TT>node->dval</TT> and <TT>node->locked</TT> are legitimate references. <br> <br> When an outer structure is used in a context that is only legal for an unnamed substructure, the compiler promotes the reference to the unnamed substructure. This is true for references to structures and to references to pointers to structures. This happens in assignment statements and in argument passing where prototypes have been declared. Thus, continuing with the example, <DL><DT><DD><TT><PRE> lock = node; </PRE></TT></DL> would assign a pointer to the unnamed <TT>Lock</TT> in the <TT>Node</TT> to the variable <TT>lock</TT>. Another example, <DL><DT><DD><TT><PRE> extern void lock(Lock*); func(...) { ... lock(node); ... } </PRE></TT></DL> will pass a pointer to the <TT>Lock</TT> substructure. <br> <br> Finally, in places where context is insufficient to identify the unnamed structure, the type name (it must be a <TT>typedef</TT>) of the unnamed structure can be used as an identifier. In our example, <TT>&node->Lock</TT> gives the address of the anonymous <TT>Lock</TT> structure. <H4>3.4 Structure displays </H4> <br> <br> A structure cast followed by a list of expressions in braces is an expression with the type of the structure and elements assigned from the corresponding list. Structures are now almost first-class citizens of the language. It is common to see code like this: <DL><DT><DD><TT><PRE> r = (Rectangle){point1, (Point){x,y+2}}; </PRE></TT></DL> <H4>3.5 Initialization indexes </H4> <br> <br> In initializers of arrays, one may place a constant expression in square brackets before an initializer. This causes the next initializer to assign the indicated element. For example: <DL><DT><DD><TT><PRE> enum errors { Etoobig, Ealarm, Egreg }; char* errstrings[] = { [Ealarm] "Alarm call", [Egreg] "Panic: out of mbufs", [Etoobig] "Arg list too long", }; </PRE></TT></DL> In the same way, individual structures members may be initialized in any order by preceding the initialization with <TT>.tagname</TT>. Both forms allow an optional <TT>=</TT>, to be compatible with a proposed extension to ANSI C. <H4>3.6 External register </H4> <br> <br> The declaration <TT>extern</TT> <TT>register</TT> will dedicate a register to a variable on a global basis. It can be used only under special circumstances. External register variables must be identically declared in all modules and libraries. The feature is not intended for efficiency, although it can produce efficient code; rather it represents a unique storage class that would be hard to get any other way. On a shared-memory multi-processor, an external register is one-per-processor and neither one-per-procedure (automatic) or one-per-system (external). It is used for two variables in the Plan 9 kernel, <TT>u</TT> and <TT>m</TT>. <TT>U</TT> is a pointer to the structure representing the currently running process and <TT>m</TT> is a pointer to the per-machine data structure. <H4>3.7 Long long </H4> <br> <br> The compilers accept <TT>long</TT> <TT>long</TT> as a basic type meaning 64-bit integer. On all of the machines this type is synthesized from 32-bit instructions. <H4>3.8 Pragma </H4> <br> <br> The compilers accept <TT>#pragma</TT> <TT>lib</TT> <I>libname</I> and pass the library name string uninterpreted to the loader. The loader uses the library name to find libraries to load. If the name contains <TT>%O</TT>, it is replaced with the single character object type of the compiler (e.g., <TT>v</TT> for the MIPS). If the name contains <TT>%M</TT>, it is replaced with the architecture type for the compiler (e.g., <TT>mips</TT> for the MIPS). If the name starts with <TT>/</TT> it is an absolute pathname; if it starts with <TT>.</TT> then it is searched for in the loader's current directory. Otherwise, the name is searched from <TT>/%M/lib</TT>. Such <TT>#pragma</TT> statements in header files guarantee that the correct libraries are always linked with a program without the need to specify them explicitly at link time. <br> <br> They also accept <TT>#pragma</TT> <TT>hjdicks</TT> <TT>on</TT> (or <TT>yes</TT> or <TT>1</TT>) to cause subsequently declared data, until <TT>#pragma</TT> <TT>hjdicks</TT> <TT>off</TT> (or <TT>no</TT> or <TT>0</TT>), to be laid out in memory tightly packed in successive bytes, disregarding the usual alignment rules. Accessing such data can cause faults. <br> <br> Two <TT>#pragma</TT> statements allow type-checking of <TT>print</TT>-like functions. The first, of the form <DL><DT><DD><TT><PRE> #pragma varargck argpos error 2 </PRE></TT></DL> tells the compiler that the second argument to <TT>error</TT> is a <TT>print</TT> format string (see the manual page <A href="/magic/man2html/2/print"><I>print</I>(2)) </A>that specifies how to format <TT>error</TT>'s subsequent arguments. The second, of the form <DL><DT><DD><TT><PRE> #pragma varargck type "s" char* </PRE></TT></DL> says that the <TT>print</TT> format verb <TT>s</TT> processes an argument of type <TT>char*</TT>. If the compiler's <TT>-F</TT> option is enabled, the compiler will use this information to report type violations in the arguments to <TT>print</TT>, <TT>error</TT>, and similar routines. <H4>4 Object module conventions </H4> <br> <br> The overall conventions of the runtime environment are important to runtime efficiency. In this section, several of these conventions are discussed. <H4>4.1 Register saving </H4> <br> <br> In the Plan 9 compilers, the caller of a procedure saves the registers. With caller-saves, the leaf procedures can use all the registers and never save them. If you spend a lot of time at the leaves, this seems preferable. With callee-saves, the saving of the registers is done in the single point of entry and return. If you are interested in space, this seems preferable. In both, there is a degree of uncertainty about what registers need to be saved. Callee-saved registers make it difficult to find variables in registers in debuggers. Callee-saved registers also complicate the implementation of <TT>longjmp</TT>. The convincing argument is that with caller-saves, the decision to registerize a variable can include the cost of saving the register across calls. For a further discussion of caller- vs. callee-saves, see the paper by Davidson and Whalley [Dav91]. <br> <br> In the Plan 9 operating system, calls to the kernel look like normal procedure calls, which means the caller has saved the registers and the system entry does not have to. This makes system calls considerably faster. Since this is a potential security hole, and can lead to non-determinism, the system may eventually save the registers on entry, or more likely clear the registers on return. <H4>4.2 Calling convention </H4> <br> <br> Older C compilers maintain a frame pointer, which is at a known constant offset from the stack pointer within each function. For machines where the stack grows towards zero, the argument pointer is at a known constant offset from the frame pointer. Since the stack grows down in Plan 9, the Plan 9 compilers keep neither an explicit frame pointer nor an explicit argument pointer; instead they generate addresses relative to the stack pointer. <br> <br> On some architectures, the first argument to a subroutine is passed in a register. <H4>4.3 Functions returning structures </H4> <br> <br> Structures longer than one word are awkward to implement since they do not fit in registers and must be passed around in memory. Functions that return structures are particularly clumsy. The Plan 9 compilers pass the return address of a structure as the first argument of a function that has a structure return value. Thus <DL><DT><DD><TT><PRE> x = f(...) </PRE></TT></DL> is rewritten as <DL><DT><DD><TT><PRE> f(&x, ...). </PRE></TT></DL> This saves a copy and makes the compilation much less clumsy. A disadvantage is that if you call this function without an assignment, a dummy location must be invented. <br> <br> There is also a danger of calling a function that returns a structure without declaring it as such. With ANSI C function prototypes, this error need never occur. <H4>5 Implementation </H4> <br> <br> The compiler is divided internally into four machine-independent passes,