;-*- Mode:Text; Fonts:(TR12 CPTFONT TR12I HL12B TR12B TR12BI) -*- This is the file 1SYS:DOC;MCDOC.TEXT* Last edited: 28 January 1985 The micro-compiler, a system for compiling LISP directly to LAMBDA microcode, is now available for experimental use. One must be aware of a number of restrictions and cautions, some of which will be relaxed as the system is further developed. 3Contents of this file*: 1[A]* How to Give the Micro-Compiler a First Try. 1[B]* When to micro-compile. 1[C]* Making 1QFASL* files with micro-compiled functions. 1[D]* Restrictions. 1[E]* The MICRO-MICRO call. 1[F]* User-Defined Instructions 1[G]* Type declarations and open coded functions. 1[H]* Additional Source->Source optimizations. 1[I]* A little bit about how it works. 1[J]* Random notes yet to be included above. 3[A] How to Give the Micro-Compiler a First Try.* 1. Load the micro-compiler with3 (MAKE-SYSTEM 'MICRO-COMPILER)* 2. Edit the definition of the function you want to micro-compile. You should already have gotten it debugged with the normal compiler. To micro-compile it, type meta-x MICROCOMPILE REGION. 3. Though we do not expect the micro-compiler to produce code that will crash the machine, it is new enough that such bugs may still exist. To be on the safe side, write out your editor buffers. 4. To load the output of the micro-compiler, type 3(compiler:ma-load ')*. 5. Your function can now be tested. 6. To return to the non-micro-compiled definition of your functions, type 1 * 1 3(compiler:ma-reset)**, which unloads all micro-compiled functions. Also, there is the function 3compiler:micro-compile*, which is just like the 3compile* function, except that the micro-compiler is used. 3[B]* 3When to micro-compile.* The motivation for micro-compiling is increased speed of execution. An important limitation is that all the functions that are micro-compiled at once must fit in available (paged) control memory. Thus, to benefit, a system must spend a large amount of execution time in a relatively small number of functions. Programs which spend most of their time in hand-microcoded functions such as3 assq*, 3get*, etc. will obtain slight benefit, there being little room for improvement. To see if a particular function is already microcoded in the initial system, type 1(FUNCTION FOO).* The value of this expression will be either something like 1#* if the function is already in microcode, or1 #* if it is a normal function. If you program spends most of its time in a system function that is not microcoded, you may want to copy its source into your progam so you can mirco-compile a private version. As usual, to find the source code for a system function, just type its name to the command 1Meta-.* in the editor. The amount of speedup is critically dependent on exactly what the function in question does. Preliminary results are that execution within the micro-compiled function itself is sped up at least 50% and frequently more. These improvement factors may be expected to increase with further development of the micro-compiler. Factors of ten or more are theoretically possible in some cases, however, it remains to be seen how often, if ever, such large factors are obtained in practice. 3[C]* 3Making QFASL files with micro-compiled functions.* Micro-compiling a function does not directly result in the function appearing in control memory. Instead, the micro-compilation results in a 1COMPILER:MCLAP* property appearing on the property list of the function name. 1COMPILER:MA-LOAD* is given the function name as argument to actually put things in control memory, or 1(COMPILER:MA-LOAD-ALL)* will load all micro-compiled functions. To specify that a function should be micro-compiled every time an entire file is compiled with 1QC-FILE*, put the line 1(DEFDECL FOO COMPILER:MICROCOMPILE T)* before the function, or write a 1LOCAL-DECLARE* like 1(LOCAL-DECLARE ((COMPILER:MICROCOMPILE FOO T))* 1(DEFUN FOO (A B C)* 1 ...)* 1).* Another way to get a function to be micro-compiled, and have some other things done to the function, is the use the macro 3compiler:define-micro-properties*. To simpiy arrange for a function to be micro copiled, supply the function name and the argument list of the function: 1(compiler:define-micro-properties some-function (a b))* Supplying additional keywords allows for more things to be specified. For example, micro-micro calls (see the section 4The Micro-Micro Call*) can be specifed with the 3:micro->micro* keyword: 1(compiler:define-micro-properties some-function (a b)* 1 :micro->micro :dynamic)* If the user wishes to make the function with no optional arguments a MISC instruction, the 3:opcode* keyword is used: 1(compiler:define-micro-properties some-lowlevel-function (a b)* 1 :opcode #o1777)* For more information on defining instructions as micro-compiled functions, refer to the section 4User Defined Instructions*. When the user directs the compiler to micro-compile a function in one of the ways described above, the function will be compiled 2twice*, once the regular way and once micro-compiled. When the 1QFASL* file is loaded, the regular macro-compiled definition will go in the function cell, while the results of the micro-compilation will show up on the 1MCLAP* property. The micro-compiled version can then be loaded in the usual way by 1(COMPILER:MA-LOAD ')*, etc. Since the system does an 1MA-RESET* after every warm and cold boot, you will have to arrange to call 1MA-LOAD* the first time your program is called after booting. [See XXXX for information about programs that need to be initialized after booting.] Functions can also be micro-compiled from1 ZWEI* by typing MICROCOMPILE-REGION which works the same way as COMPILE-REGION. This does one compilation which results in a1 MCLAP* property as above and the function cell is not affected. Therefore, you still have to do 1(COMPILER:MA-LOAD ')* to actually use the new definition. Sequence breaks are not polled during micro-compiled functions. For the time being, one should insert an occational call to a macro-compiled function if this is a problem. This also means you have to warm boot to get out of an infinite loop which is entirely within microcode. A future version of the micro-compiler will have an 1(ALLOW-SEQUENCE-BREAK)* operation. 3[D] Restrictions.* You cannot micro-compile a function that calls any of these functions: 1MULTIPLE-VALUE-LIST* 1CATCH* 1THROW*, but you can call a function that calls 1THROW*. 1%OPEN*-1CALL-BLOCK*,1 %PUSH*, and other stack manipulating sub-primitives. The micro-compiled function can have 1&OPTIONAL* arguments but cannot have 1&REST* or &KEY arguments. Constructs other than 1MULTIPLE-VALUE-LIST* to receive or return multiple values are supported, except that multiple values cannot be transmitted through MICRO-MICRO calls (see below.) The micro-compiler does not currently know about lexical variables, so functions which involve lexical closures are not supported. (However, a lexical closure will not actually be created unless ``needed.'' Thus pre-Common-Lisp constructs will work fine.) Finally, the micro-compiler only knows how to compile 1DEFUN*'s, so you can't use it directly with 1DEFMETHOD*, however, you can call micro-compiled functions from methods. As we continue development of the micro-compiler, we will lift as many restrictions as possible, so check the latest release documentation for updates. 3[E] The MICRO-MICRO call.* In the default mode, micro-compilation will not affect linkage ``visibility'' as compared to regular compiling (macro-compilation). 1TRACE*, for example, can be used with its regular effect. However, there does exist a special high-efficiency calling mode which can be used between micro-compiled functions, called the MICRO-MICRO call. Such calls will be generated only in the presence of user supplied declarations, and special considerations and restrictions apply to them. If one micro-compiled function is to call another, a great increase in efficiency can be sometimes be gained by a MICRO-MICRO call. The MICRO-MICRO call itself takes only a single microinstruction, so the increase in efficiency in the call operation itself can be a factor of 50 or more. However, the net speedup factor seen by the user almost always much less due to constant costs not related to function calling. Generation of MICRO-MICRO calls is enabled by putting a 1:DEPEND-ON-BEING-MICROCOMPILED* property on the called function. 1(DEFDECL FOO :DEPEND-ON-BEING-MICROCOMPILED :DYNAMIC)* 1(DEFDECL FOO COMPILER:MICROCOMPILE* 1T)* 1(DEFUN FOO (X)* 1 ...)* 1(DEFUN BAR ()* 1 ...* 1 (FOO X)* 2;this is a MICRO-MICRO call* 1 ...)* MICRO-MICRO calls are invisible to1 TRACE*, etc. 1&REST* arguments will never be supported MICRO-MICRO calls. 2Stack Considerations for MICRO-MICRO Calls:* A MICRO-MICRO call does not involve building a new stack frame, instead the current frame is simply added to. Stack frames, however, have a certain maximum size, which must not be exceeded. In addition the stack used for saving microcode PCs has a hardware limited length (256. levels of which 20 or so are used by the system). Thus it is the programmer's responsibility, to strictly limit the depth of recursion in MICRO-MICRO calls. Note that only MICRO-MICRO calls in recursive sequence count; an intervening MICRO-MACRO (2i.e.* ordinary) call unbuffers both stacks and a new group of MICRO-MICRO calls can begin. In many cases, the functions being micro-compiled are not deeply recursive, so the user can determine that there is no problem along these lines. In this case, the 1:DEPEND-ON-BEING-MICROCOMPILED *property should be 1T*. Otherwise, the two means below are provided to deal with the situation. If the1 :DEPEND-ON-BEING-MICROCOMPILED* property is a list, MICRO-MICRO calls are enabled only when compiling functions on that list. This may allow the user to ``break'' the recursion. If the 1:DEPEND-ON-BEING-MICROCOMPILED* property is 1:DYNAMIC*, the system will compile BOTH a MICRO-MICRO and a MICRO-MACRO call, with a runtime test on the depth of MICRO-MICRO recursion to choose between them. This involves compiling two copies of all of the expressions that generate the arugments for the call. Thus, in the interest of conserving control memory, lengthy computations should be moved outside the call if this option is selected. For example, when the2 1:DYNAMIC** option is in effect for the function call to 1HACK*, write 1(LET ((FOO (BAR A B C (...))))* 1 (HACK FOO))* instead of 1(HACK (BAR A B C (...))). 2MICRO-MICRO calls and multiple values.** Multiple values cannot be transmitted though a MICRO-MICRO call. The current system does not check for this case, and its behavior is unpredictable. Therefore, when you set the 1:DEPEND-ON-BEING-MICROCOMPILED* property on a function, then that function cannot call any functions that may return multiple values. See the2 Lisp Machine Manual* for information about how multiple values are transmitted. A simple way to make an expression return only one value is to use the special form1 VALUES with one argument:* 1(DEFDECL FOO :DEPEND-ON-BEING-MICROCOMPILED T)* 1(DEFDECL FOO COMPILER:MICROCOMPILE* 1T)* 1(DEFUN FOO (X)* 1 ... (BAR))* 1;BAR must return only one value, but* 1;TRUNCATE returns 2* 1(DEFUN BAR () ...* 1 (VALUES (TRUNCATE A B))) 3[F] User-Defined Instructions** A user can define a micro-compiled function as a MISC instruction by using the 3:opcode* keyword of 3compiler:define-micro-properties*. If a function to be called is defined as a MISC instruction, then it is called in a different way which does in use the 1CALL* instruction. The value of the 3:opcode* argument is an integer between (octal) 200 and 1777, although, the typical value passed will usually be somewhat more than 1000 octal, since many of the opcodes below that number are used by the system's MISC instructions such as 3cons*. To determine an opcode to use, you need to make sure that nothing else (the system or another user program) is using it. 1compiler:describe-misc-map* &optional2 bp* This function prints out a map of the opcodes currently used by the MISC instructions. Opcodes that are marked as 1ILLOP*s are ``free'' to be used. 1compiler:describe-mid-ram-map* This function prints out the macroinstruction decode RAM, which is basically a lower-level description of the instruction allocation, at the hardware level. 1compiler:enable-micro-misc* 2function-name* Enable 2function-name* to be actually called as a MISC instruction, using the opcode assigned with the 3:opcode* option of 3compiler:define-micro-properties*. The function must have already been installed in the micro-store with 3compiler:ma-load*. Note that MISC instructions inheritly cannot have optional arguments or return multiple values. 3[G] Type declarations and open coded functions.* The micro-compiler open compiles arithmetic when the operands and results involved have been declared to be 1FIXNUM*s. Since this eliminates the run time type check, the operation can be performed in one micro-instruction. Of course, the system is now trusting you to be careful with types. If you make a mistake, the machine is likely to crash. Type declarations are specified in Common Lisp style, using the special forms 3declare* or 3the*. 1(DEFUN FOO (A)* 1 (DECLARE (FIXNUM A))* 1 ...)* To open compile a specific expression you can use the Common Lisp special form 1THE*. 1(SETQ FOO (THE FIXNUM (+ (THE FIXNUM A) (THE FIXNUM B))))* For convenience, declaring the result of an arithmetic expression to be a 1FIXNUM* implies a declaration that the arguments are1 FIXNUM*s. Therefore, the above expression is equivalent to 1(SETQ FOO (THE FIXNUM (+ A B)))*. The micro-compiler is smart enough to notice if a result is being stored into a fixnum-declared variable. So, if the variable 1FOO*, above, had been declared a 1FIXNUM*, no additional declaration is needed to produce an open-compiled 1+*. Currently, the RESULT type declaration only ``works'' with two operands. 1(THE FIXNUM (+ A B C)) * would only declare the final result, not the intermediate ones. Thus, only one addition would be open compiled. Comparison operations, however, compile open only if their arguments are declared 1FIXNUM*s. 1(< (THE FIXNUM A) (THE FIXNUM B)) * The microcode that is produced to handle open coded arithmetic sometimes inserts the data type explicitly, and other times copies the type from one of the arguments. Therefore, if a variable that is declared to contain a 1FIXNUM* really contains some other data type, an illegal pointer may very well be produced, and that can easily lead to a machine crash. 1FIXNUM* arithmetic is coded such that an overflow will ``wrap around'' at 25. bits, but is guarenteed not to carry into the data type field. Therefore, any operation that takes 1FIXNUM* arguments will produce a 1FIXNUM* result. Single dimension array references are specially optimized by the micro-compiler. Since type checking of the index argument is ommitted in this process, the micro-compiler must be able to determine at compile time that the index is indeed a fixnum. This is usually done with a declaration, as above. Large additional savings can sometimes be obtained if serveral consecutive references are made to the same array. We plan furthur optimazations in this area. 3[H]* 3Additional Source->Source optimizations.* Optimizations discussed here are applicable to both regular compiled programs and micro-compiled programs. It is convenient to talk about it them because in considering micro-compilation we are asking: ``Now that my program is running, what facilities does the system provide to allow it to compute useful results in as short a time as possible?'' This is part of a deeper question: ``What programming style gives me a working program most quickly, vs. what programming style gives me a more efficient program?'' and is heavily dependent on what programming facilities a system provides. Load the additional source->source optimizations by 3(MAKE-SYSTEM 'META-EVAL)*. Once loaded, additional optimizations are enable during compilation by the use of the attribute3 "SOURCE->OPTIMIZATIONS" *in the file mode line, 1;;;-*- Mode:LISP; Package:MY-PACKAGE; Base:10;* 1Source->Optimizations:T -*-* The value of the attribute may be a symbol or a list of symbols specifying which optimizations to enable. The most useful values are 3T* and 3UCODE*. When in mode 3T* a tail-recursive-call-to-self conversion to a goto style optimization is done, while in mode 3UCODE* all of the optimizations in mode 3T* are done plus some additional 1MAP* and1 MAPCAR* open coding optimizations. 3[I] A little bit about how it works.* The first phase of micro-compilation is regular macro-compiliation, so all macro-expansions and other compile-time operations occur in the usual way. The resulting stack machine oriented LISP machine macrocode is then transformed into an intermediate stack-and-register oriented notation by the micro-compiler itself. This output is then operated on by an elaborate optimizing assembler. The complete data and control flow of the function is charted out, including loop analysis, etc. Then a pattern language driven optimizer is applied. This optimizer is more general than the usual ``peephole'' optimizer, in that predicates involving control and data flow as well as the code representation itself can be tested. In addition, there is no requirement for the matched instructions to be textually consecutive; one can match against all instructions which branch to a particular point, for example. (As an aside, the pattern matcher incorporates an interesting name-chaining feature for pattern variables). Also during optimization phase, functions to be ``open-coded'' can be recognized, and appropriate substitutions made. If any changes were made by the optimizer, the control and data analysis is repeated, and the optimizer applied again. Finally, when no further optimizations can be made, a conversion phase produces LAMBDA microcode storage words, which are stored on the 1MCLAP* property of the function symbol. The1 MCLAP* property is an S-expression form independent of absolute addresses in a particular version of the microcode; it can be written out then read back into a different system, possibly with a different microcode version, with good results. The compiled microcode can be printed out by 1(COMPILER:MA-PRINT )*, and the optimized intermediate code for the last function micro-compiled can be printed by1 (COMPILER:MA-PRINT-CODE)*. [1MA-PRINT* may not be present in eary versions of the micro-compiler.] The micro-compiled definition can be installed by 1(COMPILER:MA-LOAD ..)*. Write out your buffers before doing this for the first time! 1MA-LOAD* saves any previous definition on the 1DEFINITION-BEFORE-MICROCODED* property of the function symbol; this definition can be reinstated by 1(COMPILER:MA-UNLOAD 2function*)*. All micro-compiled definitions can be unloaded by 1(COMPILER:MA-RESET).* Control memory (and two other kinds as well) are allocated in push down list fashion; thus, if function1 FOO* is unloaded, all other functions loaded since1 FOO* was loaded will also be unloaded. If any micro-compiled function does a MICRO-MICRO call to1 FOO*, that function and all ``after'' it will also be unloaded. When functions are unloaded, the function cell is replaced with its previous contents, thus preventing new calls from using the micro-compiled definition; however, 2NO PROTECTION IS PROVIDED TO SUSPENDED INVOCATIONS*. If1 FOO* does a MICRO-MICRO call to1 BAR, MA-LOAD* will refuse to load1 FOO* unless 1BAR* is loaded; thus, if1 FOO* and 1BAR* MICRO-MICRO call each other, they must both be loaded by the same call to1 MA-LOAD*. 3[J] Random notes yet to be included above. * Hardware interrupts are polled during main memory references generated by micro-compiled functions.