The Datafile PD-CD 5

home *** CD-ROM | disk | FTP | other *** search

/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / f / forthmac / !Forthmacs / docs / html / RO_impleme < prev next >

Wrap

Text File | 1997-05-01 | 25.4 KB | 537 lines

<html> <head> <title>Forthmacs Implementation</title> </head> <body> <h1>Forthmacs Implementation</h1> <hr> This chapter describes how RISC OS Forthmacs implements the Forth virtual machine on the ARM processors. It assumes that you have a fairly good knowledge of conventional Forth implementations; it does not attempt to be a tutorial on how Forth works. <h2>Dialect</h2> RISC OS Forthmacs has been an implementation of the Forth-83 standard, with a few exceptions. It is now far on it's way to be an ANS compliant implementation. It is still rather compatible with the other implementations for Sun-68k, Sparc, Atari, Macintosh and OS-9 computers. <h2>Stack Width and Addressing</h2> In RISC OS Forthmacs, all stack items as well as memory cells are 32-bit wide, remember this when writing portable programs. Use the portable ANS operators like <code><A href="_smal_BP#177">cell+</A></code> <code><A href="_smal_BR#179">cells</A></code> or the RISC OS Forthmacs specific words like <code><A href="_smal_BO#E6">/cell</A></code> <code><A href="_smal_BT#17B">cells+</A>.</code> The address could conceivably grow to 2 to the 32nd power (4 gigabytes), but this is restricted by the current CPU/MMU versions to 16/256 MBytes. 16-bit or 2-byte memory accesses are not supported any longer and must be emulated if necessary. Note: word accesses are simulated by two byte accesses, take care about interrupts occurring here! The current ARM MMUs don't support non-aligned memory accesses. Note: They don't abort or run any exception vector but just do something undefined and CPU core dependent. Take care of this, it took me hours to find a bug! All accesses must be one of: 1) byte-wide access to any address in the address area 2) cell-wide ( 32-bit ) access to any aligned address The word wide access possible at least on StrongARM and ARM8 cpus is not supported by the RiscPC platforms. Special source extensions are available for single-board platforms. Both stacks are pre-decrementing/post-incrementing. The parameter stack holds its top-of-stack in the top-register <code><A href="_smal_BE#1C">top</A></code> - r10, this allows much faster code definitions because of the CPUs load-and-store architecture. <h2>Register Usage</h2> <pre> r9 user area pointer up</pre> <pre> r10 top-of-stack register top</pre> <pre> r11 returnstack pointer rp</pre> <pre> r12 instruction pointer ip</pre> <pre> r13 stack pointer sp</pre> <pre> r14 link register lk</pre> <pre> r15 pc + status + flags pc</pre> <pre> r15 sr sr hold the flags part of r15</pre> Note: The internal structure of the pc and flags registers differs between cpus. It seems to be better, to generally imagine pc and status register as two registers. The hardware-errors and the <code><A href="_smal_AT#43">.registers</A></code> instruction know about this. r0, r1, r2, r3, r4, r5, and r6 are available for use within code definitions. Don't try to use them for permanent storage, because they are used by many code words with no attempt to preserve the previous contents. Registers r7-r14 can be used within code definitions with great care, but you have to save and restore their values at the beginning/end of the definition. <h2>Inner <address> Interpreter</h2> The inner interpreter <code><A href="_smal_AG#36">next</A></code> is direct threaded, post incrementing. The compilation address of all definitions contain machine code to be executed, not a pointer. Each <code><A href="_smal_AC#182">code</A></code> definition ends with the <code><A href="_smal_AG#36">next</A></code> code, assembled in-line. The <code><A href="_smal_AG#36">next</A></code> code is: <pre> pc ip )+ ldr</pre> This means: Load the program-counter <code><A href="_smal_BI#50">pc</A></code> ( don't affect the CPU status ) from the 4-byte cell pointed to by the instruction pointer ip, postincrement the instruction-pointer. So the <code><A href="_smal_AG#36">next</A></code> is only one CPU instruction and very fast. It is much faster than <pre> address dolink branch</pre> <pre> ...</pre> <pre> pc link mov</pre> constructions because of only one pipeline reload per <code><A href="_smal_AG#36">next</A>.</code> But on the other hand, there is definitely a larger overhead for calling secondaries. RISC OS Forthmacs versions <code><A href="_smal_BN#115">>=</A></code> 3.1/2.70 can switch to another <code><A href="_smal_AG#36">next</A></code> scheme. The first 8 <code><A href="_smal_BR#179">cells</A></code> in the user area are free debugging purposes. slow-next ( you find this in lib.arm.debugm ) patches all <code><A href="_smal_AG#36">next</A></code> as well as conditional <code><A href="_smal_AG#36">next</A></code> calls to <pre> pc up mov</pre> Normall there is a normal <code><A href="_smal_AG#36">next</A></code> instruction at <code><A href="_smal_BE#31C">up@</A></code> but may install any service routine there to do additional checking at run time. The new debugger uses this to branch into the debugger handler. After 'debugging' you switch back to the normal <code><A href="_smal_AG#36">next</A></code> with fast-next If you want to use this scheme, there is one thing to remember. As slow-next patches all instructions <pre> pc ip )+ condition ldr</pre> your handler might be patches as well. In these cases you should use <pre> pc 1 ip ia! ldm</pre> instead. This does the same - at least from RISC OS Forthmacs point of view - but isn't patched. See lib.arm.debugm again for an example in the debugger. For discussions about subroutine threaded ( macro extended ) versus threaded code implementations see the Forth literature. Generally, macros do bring some advantage in execution speed but give less information about the code itself, so debuggers are less useful. The penalty for direct threaded code is hard to predict, it depends very much on the type of application. Something like 50% sounds reasonable, so optimising the bottlenecks could bring big advantages. The runtimer utilities might help you doing this. The assembler macro <code><A href="_smal_BD#16B">c;</A></code> assembles the <code><A href="_smal_AG#36">next</A></code> instruction and ends assembling by <code><A href="_smal_BT#1DB">end-code</A>.</code> A fast conditional next can be done by <pre> ...</pre> <pre> r2 0 cmp</pre> <pre> eq next</pre> <pre> ...</pre> <h2>Other Definitions</h2> Any word that is not a code definition contains a branch+link instruction at the code-field, this makes a relative branch to an inline-address and saves the pc+sr to the lk register. <pre> runtime-addr dolink branch</pre> The inline address points to a code fragment (headerless in most cases) that implements the run-time action of the word. The parameter field starts just after this branch+link instruction and can be found by clearing the flags in the link register like this: <pre> r0 lk th fc000003 # bic</pre> <pre> r0 get-link</pre> The run-time codes may have to push the top-register to the stack, save the return pointer to the return-stack and set the instruction or stack pointer to the parameter field address. All standard runtime codes (those of variables, constants, colon definitions, user variables ...) have been optimized for best cache-hit rates. Note: <code><A href="_smal_AI#338">word-type</A></code> ( cfa -- addr ) finds the address of the words runtime code in this implementation. <h2>Colon definitions</h2> The runtime code: <pre> mlabel docolon assembler</pre> <pre> ip rp push</pre> <pre> ip get-link c;</pre> The body of a Colon Definition starts 4 bytes after the compilation address. The body contains a list of compilation addresses of other words. Each such compilation address is a 32-bit number which is an absolute address. <h2>Variable</h2> The Parameter Field of a <code><A href="_smal_BN#325">variable</A></code> contains a 32-bit number which is the value of the variable. The runtime code: <pre> mlabel dovariable assembler</pre> <pre> top sp push</pre> <pre> top get-link c;</pre> <h2>Constants</h2> The Parameter Field of a <code><A href="_smal_AP#18F">constant</A></code> contains the 32-bit value of the constant. The runtime code: <pre> mlabel doconstant assembler</pre> <pre> top sp push</pre> <pre> r0 get-link</pre> <pre> top r0 ) ldr c;</pre> <h2>User Variables</h2> The value of a <code><A href="_smal_BK#322">user</A></code> variable is stored in the <code><A href="_smal_BK#322">user</A></code> area as a 32-bit number. The Parameter Field of a user variable contains a 32-bit offset into the user area of the current task. r8 contains the base address of the current user area. r8 is symbolically defined as <code><A href="_smal_BD#31B">up</A></code> in the assembler. The runtime code: <pre> mlabel douser assembler</pre> <pre> top sp push</pre> <pre> r0 get-link</pre> <pre> r0 r0 ) ldr</pre> <pre> top r0 up add c;</pre> <h2>Deferred words</h2> The compilation address of the word to be executed by a <code><A href="_smal_AA#1B0">defer</A></code> word is stored as a 32-bit absolute address in the <code><A href="_smal_BK#322">user</A></code> area. The Parameter Field of a deferred word contains a 32-bit number which is an offset into the user area of the current task. The runtime code: <pre> mlabel dodefer assembler</pre> <pre> r0 get-link</pre> <pre> r0 r0 ) ldr</pre> <pre> pc r0 up ib ldr end-code</pre> The last line holds a somewhat optimized <code><A href="_smal_AG#36">next</A></code> instruction, it means: Load the pc from the address in the user area with the offset r0. <h2>;code</h2> The compilation address of a word created by a <code><A href="_smal_AX#197">create</A></code> ... <code><A href="_smal_BE#10C">;code</A></code> data type construction contains the standard branch+link instruction that branches to the runtime code. The runtime code is defined by the programmer in the <code><A href="_smal_BE#10C">;code</A></code> part of the definition. In versions up to 3.1/2.62 <code><A href="_smal_BE#10C">;code</A></code> assembled two instructions for your convenience <pre> top sp push</pre> <pre> top get-link</pre> this is not the case any more. I changed this to be more portable with the FirmWorks implementation and i feel that all Forth programmers using <code><A href="_smal_BE#10C">;code</A></code> should be able to handle this. <h2>does></h2> <pre> mlabel dodoes assembler</pre> <pre> ip rp push</pre> <pre> ip get-link c;</pre> The runtime code is defined by the programmer in the <code><A href="_smal_BC#1CA">does></A></code> part of the definition. Before branching to the dodoes code, the does> instruction assembles <pre> top sp push</pre> <pre> top lk th fc000003 # bic</pre> to get the parameter field address. <h2>local variables</h2> RISC OS Forthmacs has built in ANS Forth conforming local variables spending their lifetime on the return-stack in stack-frames. The stack-frames are linked via a <code><A href="_smal_BK#322">user</A></code> variable local-frame which is also used to locate a local variables value. The frame structure is like: <pre> | cfa:frame> | old-frame | old-rs | loc | loc | .........</pre> with cfa:pop-frame on top of the return-stack. pop-frame removes the current frame and switches to the last frame. <pre> headerless code pop-frame \ this routine is pushed on return stack by push-locals</pre> <pre> here /cell+ token,</pre> <pre> r0 rp 2 rp ia ldm</pre> <pre> r0 'user local-frame str</pre> <pre> ip rp pop c;</pre> <pre> </pre> The local variables are accessed using (loc) followed by an stack frame index. <pre> code (loc) \ ( -- n ) runtime-code of any local</pre> <pre> r0 'user local-frame ldr</pre> <pre> r1 ip )+ ldr</pre> <pre> top sp push</pre> <pre> top r0 r1 2 #asl db ldr c;</pre> Note: The decompiler can <code><A href="_smal_AJ#279">not</A></code> know the local variables names, so it assumes names like ( v0 v1 ...). <h2>Tokens</h2> Within the body of a colon definition, calls to other Forth words are compiled as the 32-bit absolute compilation address of those words. These tokens have a corresponding bit in the relocation table. <h2>Branching</h2> Branch targets are offsets relative to the location that contains the branch offset. They are stored as 32-bit twos-complement numbers representing the number of bytes between the offset location and the branch target. For example, a branch to the following location could be compiled with: <pre> postpone branch 4 ,</pre> Note: This is implemented different in version 3.1/2.00. The relative offset is replaced by an immediate absolute relocated address. <h2>Doubles</h2> RISC OS Forthmacs versions newer than 1.83 have full double number support, all conversion tools <code><A href="_smal_AS#192">convert</A>,</code> <code><A href="_smal_AO#27E">number?</A>,</code> <code><A href="_smal_BM#1A4">d.</A></code> use doubles, the 'scaling' words <code><A href="_smal_AA#C0">*/</A></code> <code><A href="_smal_AB#C1">*/mod</A></code> <code><A href="_smal_AU#314">um/mod</A></code> use double intermediate results. Also the text-interpreter and compiler accept literals as doubles when there is a period at the end of it. <pre> : test 1234. d. ;</pre> 1234. is a double number and <code><A href="_smal_BM#1A4">d.</A></code> displays it. This could only be achieved with changing stack effects in a number of words. So these new RISC OS Forthmacs versions are no longer compatible when these words are used. The lib.compatible tool does <code><A href="_smal_AJ#279">not</A></code> cover these changes. The advantage of the new stack behaviour is it's ANS compliancy and the improved arithmetic capabilities. <h2>Floats</h2> RISC OS Forthmacs versions newer than 3.1/2.13 have the ANS Floating and Floating Extended wordsets included. There isn't any further documentation available so far, please use the ANS docs for this purpose. <h2>StrongARM compatibility</h2> Versions from 3.1/2.30 run on StronARM based machines but optimized code is available from 3.1/2.40 onwards. <h2>Cache</h2> The newer ARM based cpus ( ARM8, StrongARM ) have a different cache structure than the elder versions. Separate instruction- and data caches are used and code synchronizing has to be done after change of the code space. <code><A href="_smal_BO#206">flush-cache</A></code> and <code><A href="_smal_AV#2E5">sync-cache</A></code> are both implemented in current RISC OS Forthmacs versions >3.1/2.40 in such a way, that the compiler is not significantly slowed down, in fact a StrongARM compilation is much faster than on the older ARM710. <h2>Header format - # of bytes in parentheses</h2> Source Field (4), Link Field (4), Name Field (n), Padding (0 to 3), Flags (1), Code Field (4), Parameter Field (n). As all addresses need to be, the Link Field, Name Field, and Code Field are all aligned. Links point to links ( <code><A href="_smal_AJ#279">not</A></code> to Name Fields, as in FIG Forth! ) The name field is a normal Forth packed string. (Many Forth implementations set the high bit in the first and last characters of the name field; RISC OS Forthmacs does not). Name Field: length-byte, 0-31 character name. <h2>Vocabularies</h2> Vocabularies have <code><A href="_smal_BG#7E">#threads</A></code> - way hashing. This means that each vocabulary has 16 separate linked lists of words. The threads are stored in the <code><A href="_smal_BK#322">user</A></code> area. The Parameter Field of a <code><A href="_smal_BR#329">vocabulary</A></code> contains the 32-bit offset of the threads in the <code><A href="_smal_BK#322">user</A></code> area, followed by the vocabulary-link, a 32-bit pointer to the previous <code><A href="_smal_BR#329">vocabulary</A>.</code> The runtime high-level code is: <pre> does> body> context token!</pre> Before searching a vocabulary, a hashing function is applied to the name to be located. The hashing function selects one of the 16 linked lists to search. The hashing function is very simple. The lower 4 bits of the first character in the name (the first name character, not the length byte) are interpreted as a number from 0 to 15, selecting a linked list. Vocabularies are not chained to one another. Search order is implemented using the <code><A href="_smal_BN#145">also</A></code> / <code><A href="_smal_AW#286">only</A></code> scheme. Each vocabulary thread is terminated with a special link field in the final word. The special link address is the address of the origin of the Forth system (which may change from session to session due to the relocation that the operating system applies when loading and executing the Forth system. The parameter field for a vocabulary looks like: User number (/cell), Voc-link (/cell) The user number selects the place in the user area where the head of list pointers for the 16 vocabulary threads are stored. Each vocabulary requires 16 <code><A href="_smal_BR#179">cells</A></code> bytes of user area storage for these 16 threads. The values stored in the user area are the Link field Addresses for the top word in each thread. <h2>Relocation</h2> In the RISC OS environment all programs of the absolute type are loaded at $8000 and executed from there. So on first sight the relocation table doesn't make much sense in this version if you don't care about being portable to other RISC OS Forthmacs implementations. But the relocation table can be used for target/meta-compiling or for relocating code during run-time. This is necessary for producing turnkey applications with an 'Application Stripper', use of the application stripper requires strict adherence to the rules of relocatability. If the program is not relocatable, then a file saved with <code><A href="_smal_BI#2C0">save-forth</A></code> will work only if it is later executed at the same address where it was executing when it was saved. If saved with <code><A href="_smal_BI#2C0">save-forth</A>,</code> a program that is not relocatable will not work at all, regardless of the address where it is later executed. Consequently, use of the application stripper requires strict adherence to the rules of relocatability. In most cases, the relocation bitmap is maintained automatically, without requiring any special effort on the part of the programmer. However, there are some cases where the programmer must take explicit actions to ensure that the program is relocatable. The executable file contains a relocation list used to identify the locations in the program's binary image which contain absolute addresses. When the program is loaded, each of these locations is modified by adding the starting address of the program to the number contained in that location. Only 32-bit numbers may be so modified. While RISC OS Forthmacs is running, it maintains its own relocation table, identifying those locations in the Forth dictionary which must be relocated during <code><A href="_smal_AF#185">cold-code</A>.</code> Each bit in the map represents the address of one aligned location. This relocation table is completely different from the standard RISC OS relocation tables, it is only used from within RISC OS Forthmacs. In order for this to work properly, the programmer must be careful to use <code><A href="_smal_BX#2FF">token,</A></code> A, <code><A href="_smal_AL#24B">link,</A></code> <code><A href="_smal_BW#2FE">token!</A>,</code> A! or <code><A href="_smal_AK#24A">link!</A></code> to store an address or token in the dictionary, all six set the relocation flags. Addresses may be stored into <code><A href="_smal_BN#325">variable</A>s</code> with ! ( without requiring the use of <code><A href="_smal_BW#2FE">token!</A></code> ) if the <code><A href="_smal_BN#325">variable</A></code> is re-initialized every time that the application is started. <code><A href="_smal_BW#2FE">token!</A></code> is only necessary if the <code><A href="_smal_BN#325">variable</A>s</code> value must be set before <code><A href="_smal_BI#2C0">save-forth</A></code> is executed, and then is used when the saved application is later invoked, without being re-initialized by the application's initialization code. If , or ! is used instead, the address will not be properly relocated if <code><A href="_smal_BI#2C0">save-forth</A></code> has been used to write the dictionary image to an executable file. Note: The lib/checkrel.fth program can help you catch relocation problems in your applications. It should be loaded before you load your application, and will warn you if your application does things that may not be relocatable. After you have fixed the relocation problems, you can load your application without lib/checkrel.fth . See: <code><A href="_smal_AQ#D0">.buffers</A></code> <code><A href="_smal_BE#DC">.pointers</A></code> <code><A href="_smal_BW#2FE">token!</A></code> <code><A href="_smal_BX#2FF">token,</A></code> A! A, <code><A href="_smal_AK#24A">link!</A></code> <code><A href="_smal_AL#24B">link,</A></code> <code><A href="_smal_BT#2CB">set-relocation-bit</A></code> <code><A href="_smal_AI#2A8">relocation-map</A></code> <h2>Program header</h2> The header of the executable binary image looks like this: <pre> h_magic ( 0) \ Magic Number h_tlen ( 4) \ length of text (code) h_dlen ( 8) \ length of initialised data h_blen ( c) \ length of BSS unitialised data h_slen ( 10) \ length of symbol table h_entry ( 14) \ Entry address h_trlen ( 18) \ Text Relocation Table length h_drlen ( 1c) \ Data Relocation Table length </pre> the magic number is the branch+link instruction just behind this header. Note: this header might be changed with future releases according to Acorns executable binary code standard. <h2>Heap memory</h2> RISC OS Forthmacs is loaded to $8000 and will have as much memory available as was defined by WimpSlot . The <code><A href="_smal_BJ#261">main-task</A>s</code> user area immediately follows the first instructions and some permanent data at $8040. $600 byte will be allocated in the module-heap RMA, it will hold the <code><A href="_smal_AA#1E0">env-area</A>,</code> the command-line area plus all handlers used by shelled programs. The implementation of the dynamic memory manager has changed in Version 3.1-2.00. From now on the dictionary and the heap share the same memory area, the dictionary grows from lower addresses and the heap can be as large as the area between the stacks and <code><A href="_smal_AP#21F">here</A>.</code> Note: Of course you may install another memory manager or add more heaps. <h2>Dictionary memory</h2> At the top of the dictionary are both stacks defined by <code><A href="_smal_AX#2B7">rp0</A></code> - <code><A href="_smal_BB#2B9">rs-size</A></code> and <code><A href="_smal_AJ#2D9">sp0</A></code> - <code><A href="_smal_BU#29C">ps-size</A></code> and the <code><A href="_smal_BM#2F4">tib</A>,</code> below this are MBytes of free memory (well, hopefully). <code><A href="_smal_AP#21F">here</A></code> marks the end of the allocated dictionary, classically <code><A href="_smal_BH#28F">pad</A></code> is <code><A href="_smal_AP#21F">here</A></code> plus something. RISC OS Forthmacs knows about two dictionary areas, the <code><A href="_smal_AL#2AB">resident</A></code> (which is the dictionary you know in all implementations) and the <code><A href="_smal_AD#303">transient</A>.</code> The transient dictionary is in the heap memory, definitions defined here won't use dictionary space in the target application. So it might be useful to do: <pre> transient</pre> <pre> fload assembler</pre> <pre> fload debugger</pre> <pre> resident</pre> <pre> fload myapplication</pre> Now the debugger and assembler will be in transient address space. To remove all links, pointers etc. into the transient address space use <code><A href="_smal_AO#1BE">dispose</A>,</code> it will do this for you. <code><A href="_smal_AX#D7">.dispose</A></code> will also give some informations what is removed while executing <code><A href="_smal_AO#1BE">dispose</A>.</code> </body> </html>