Arnold Sch"onhage, July 2001, Oct 2001, Jan 2005 TPICO - 1 TPICOdoc-01 - TP Intermediate Code Specification ================================================== 1. TP32 modules .m32 -------------------------- In .m32 format, a TP32 module is a sequence of (little endian) 32-bit unsigned integers containing several subsections. After a `header' of just a few length words, the initial part is the program `body' which is an intermediate code (tpico) listing of the TP instructions of the module with additional pseudo instructions for directives and further structure information, ending with the directive `END.' Optionally, there may then follow a section with the local or global `Tables' introduced with this module, starting at word number `tab00' (=0 iff empty) and, if tab00 > 0, a table of these tables containing their lengths #xx and words pointing to their bottom elements. Next there is always a list of the P-names (the public labels defined in this module), starting at word number pxx00. The body contains `P- label directives' pointing to the entries of this list. Moreover this list is also containing all external capnames xx used in this module as goal of a JP.xx without being named by a P-label directive. Any `JS' in the body pointing to this part is thus understood as a `JP'. A minimum of tracing information (potentially to be used for keyboard interrupts) is always appended as a `line directory' LINES containing line numbers and word address pointers to (some of the) instructions in the body. For parts of the module subject to tracing (enclosed by TR1/TR0 pairs) and for explicit trace stops TS n, LINES shall also contain verbatim citations of source code lines as additional infor- mation for source code debugging. When invoked with option `-g', tpa provides this more extensive mode for all of the module. Accordingly, the header in words 0-3 of the .m32 module contains the words [0] `length'= total number of 32-bit words, [1] `tab00' = address of table of tables, [2] `pxx00' = address of list of P-names; [3] `lines' = bottom address of LINES; body: beginning with its initial P-label directive. 2. TPico instructions and pseudo instructions --------------------------------------------- Instruction formats are varying for different instruction groups; the bottom byte always contains the basic opcode (bits op0,...,op7), with the first major distinction by op7: op7=1 for all jump instructions and for some pseudo instructions, for jumps followed by (absolute) 20-bit word address [w8-w27] and 4-bit max tape count `mtc' for this segment in [w28-w31], while pseudo instructions may employ other patterns; op7=0 for loading, storing, boolean and arithmetic operations, bit operations and counting, shifts, and tape control. First we describe the instructions of the second group beginning with an outline of their general instruction format. TPICO - 2 The format for opcodes op < 128 is | op 0| r' i'm| n |ttr|mtc| in four 8-bit bytes, where ------------------------------- `mtc' gives tape count at the end of segments, the `ttr' field holds monitoring information about tracing and timing extras, etc., the n-field provides constants, offsets, counts n < 256; all further specifications about tape addresses, register use etc. are in the source field r'i'm of 3+3+2 bits, |···'···'··| in byte [w8-w15], `r' for regs, tape number `i' (i=7 for constants), `m' for modify. Possible TP sources are s = t |.r|=c|#xx|= r+xx with tape addresses t = i|i+|i-|-K|-n; next we give a listing of their r'i'm encodings, sometimes leaving optional slots for future TP code extensions. t= i ooo' i 'oo with n=0, i+ ooo' i '1o with n=0, i- ooo' i 'o1 with n=0, -n ooo'ooo'oo with n>0, (extension pi-n for i>0 ?) -K ooo'ooo'11 with n=0, (extension pi-K-n for i>0 ?) with op=64 for storing, these are the encodings for ZT t, other rT t analogously with r= 1,2,3,4,5,6 for M,A,C,B,K,E; ____________________ s= .r r>0'ooo'oo /these 7 lines so far ooo' i '1o with n>0 for Pi+n,\ / valid only for op=6; ooo' i 'o1 with n>0 for Pi-n, > dynamic n, 111' i '1o with n>0 for Pi+n,\ 111' i 'o1 with n>0 for Pi-n, > static n, under mtc, 0 r=6 encodes q= MA; 00'111'oo with n specifying xx at tab00 + 2n; =c 111'111'1o for constant c= n ( 0 <= c <= 255) 111'111'o1 for constant c= n - 256 (-256<= c < 0 ) 111'111'11 for 32-bit c = n + h·256, with 0 < h < 2^24 from the previous word 0'h (with opcode= 0) having prepared that h; only the instructions with this =c source are requiring a 2nd word. -------------------------------------------------------------------- op6=1: op= 64 for storing, ZT t, rT t; op= 64+rr for loading, L rr s with rr > 0 in [op0-op5] for any nonempty subset of (M,A,C,B,K,E). op6=0: op= 32 for AND, = 36 for OR, = 40 for EOR, NOT = EOR= -1, 111'111'o1 with n=255; = 44 for AD, \ = 48 for AC, \ with these preliminary adhoc encodings: = 52 for SB, > op+1 for prefix E1, (IAD,IAC,ISB,...), = 56 for ADE, / op+2 for prefix E0, (OAD,OAC,OSB,...), = 60 for ACE, / (op+3 for mod & result-> A, unchanged) --------------- op5=0: op = 0 for long constant high part in [w8-w31] (see above), = 1 with .r = M,A,C,B, E for HM1, HA1, HC1, HB1, E1, = 2 with .r = M,A,C,B, E for HM0, HA0, HC0, HB0, E0, = 3 with .r = M,A,C,B, E for HM+, HA+, HC+, HB+, E+; (r = 1,2,3,4, 6) TPICO - 3 Opcodes .....000 continued: --------------------------- op = 4 as NOP (void), provided rim=0 and n=0; op = 4 for shifts Sr H \ with r= 1,..,6 for M,A,MA, B,MAE,AE, = 5 for shifts Sr L / i= ooo, and m= 11 for S...K, m= oo for S..n; op = 6 r=ooo for Pi+n (m=1o), Pi-n (m=o1), n `dynamic', r=111 same with static n, covered by mtc; 0 specifying second operand in .B 10 for DIV, / thus leaving possibilities for extensions e.g. with operands from other sources op =12 for NMA, with r'i'm = 3'ooo'11 (similar to op=4) or MSK, with rim=0, and operand n --------------- =16 for TUP t (preliminary) these are pseudo operations =17 for TUS t (settled) for time accounting, see below; =18 for CP with n=1, possible extension with any n =19 for CM with n=1, =20 for KP with n=1, numbering as for JCM, JKP,... =21 for KM with n=1, op =22 for T-directives, always i=0, with m = oo, 1o, o1, 11, comments: and r=0 for TI0, TI1, TR0, TR1, (n=0) r=1 for TS n, -- -- -- tracestop r=2 for TMA, -- -- -- (n=0) r=3 for TK, -- -- -- (n=0) r=4 for -- TU+n, TU-n, -- (if ti>0) r=5 for -- TU+n, TU-n, -- see below r=6 for TA n, TA+n, TA K, TA+K, r=7 for TCA n, TCA+n, TCAK, TCA+K; the TU±n code with r=5 implies TUS±n, used while timing off. --------------------------------------------------------------------- In emulations, special cases like AC.A == 48'2, ACE.A == 60'2, ACE.E == 60'6, and also NOT == EOR= -1 deserve special handling. _______________________________ TUP t, TUS t have the format | op | t (signed) |ttr|mtc| with a signed 16-bit field for t, possibly also tape count mtc > 0. With the `preliminary' form TUP, adding t to some intermediate sum like `ticnt' (32-bit, cf. emudoc01) will suffice, while TUS includes clean-up of such pending quantities. --------------------------------------------------------------------- TPICO - 4 Jump instructions have the format | op sz1| jump address |mtc| with op < 24, `zero bit' z, and ------------------------------- the extra bit `s' specifying JS (s=1) versus J (s=0). Also in case of JS possibly mtc=0, not including stack tape control! JP[..].xx have address cxx pointing to the link field of P-name xx. Coding by (op mod 8)= r is similar to the former coding of regs, the higher bits of `op' label the three rows of the following table: \ r= 0 1 2 3 4 5 6 7 | op3,op4 \ ---------------------------------------------------------· = oo | J/JS M A C B K E P.xx | | END. | = 1o | RTS HM HA HC HB AB | | `LS' `EQ' `GR' | = o1 | void void CP CM KP KM (CPH) (CMH) | -------------------------------------------------------------------· Cobined with flags z and s, we have examples like JSHB.xx encoded by op=12, s=1, z=0 (opcode = 12+32+128 = 172), or JCPZ.xx encoded by op=18, s=0, z=1 (opcode = 18+64+128 = 210), or JNLS.xx encoded by op=13, s=0, z=0 (for the `N') resulting in opcode = 13+128 = 141. Note: the entries `LS', `EQ', `GR' in this table are meant for z=1, ----- motivated by the equivalence A=B <==> A-B is zero. Possible extensions: `JCPH' and `JCMH' (op=22,23) as shortcuts for CP,JHC... / CM,JHC... Entry `P.xx' in column r=7 stands for encoding of a P-label directive by the word 135'cxx, where cxx denotes the word address of the link word c of entry xx in the list of P-names (see section 4). Encoding of the END-directive `END.' is by the word 135'0 . In column r=0, 128 for J, 160 for JS (or JP), 136 for RTS, are (so far) the only valid opcodes, here all other sz combinations are (still) undefined. --------------------------------------------------------------------- 3. Table section ---------------- Word address tab00 is pointing to the beginning of `table of tables' which contains two words for each table (possibly empty) and a final delimiting zero word; the first word u of the n-th word pair (stored at tab00 + 2n) is the word address of the bottom element xx_n[0] of the n-th table, or of the first word after the name of the n-th table, if that table is still undefined; the second word v of that pair (at tab00 + 2n+1) specifies the length or the name of the table, or both: * if the table is defined locally (by `TAB xx', without `P.') then v has a zero bottom byte v8=0 and shows the length (in words) in its upper 24-bit portion v24; - the (local) name has been eliminated; * if the table is defined under a public name (by `TAB P.xx'), then v24 is the length, and u-v8 (with v8>0) is pointing to the initial word of that capname xx (stored below xx_n[0], in big endian byte order, see next section, and terminating in word u-1); * if the table (named xx) has been used (by source =r+xx or #xx), without being defined in this module, then v24=0, and again u-v8 is pointing to the first word of xx. -- Note: empty strings as in `TABVOID =\\' are stored as a zero word, thus have length one.-- TPICO - 5 4. Structure of the list of P-names ----------------------------------- Each entry of this list contains two linking words c, d, and its cap- name xx of variable length stored wordwise in the format specified in section 1 of `dict01' (big endian byte order, with a final zero byte). In relative addressing, such entry has the following structure: word 0: c = link to (link m32[c] of) next entry, c=0 for last entry; word 1: d = destination; d=0 for used (but undefined) external cap- names, else d is the module relative address of the code word addressed by this P-label, with its P-label direc- tive word 135'cxx one or a few words earlier, where cxx denotes the word address of the preceding link word c; word 2: first word of name xx, ending in a word with bottom byte =0; - the names xx of the list are linked in alphabetical order. 5. Data structures in LINES --------------------------- The syntactical elements of a TPAL source line (before any comments) are counted by 1,2,3,..., including labels (also empty ones `:') and any directives (also TCA2, TAB= ..., TR1, etc.). An element is called `tracy' iff (later, in final machine code) its implementation will be initiated with a tracer call or if it is an explicit trace stop TS n, whereas other directives are never tracy. An instruction is tracy iff it is preceded by a `TR1' (and no closer `TR0'). In the example line TR1, LAB2: CT3, TK, LA5, AD=6, TR0, SAL 8, with 8 elements, --- --- ---- the tracy elements are underlined. When running a program under trac- ing, interactive commands for setting breakpoints rely on these con- ventions: setting a breakpoint at element 2 of this line results in a breakpoint at the next tracy element `CT3', to set a breakpoint at element 7 will be refused as impossible (no search in further lines). Elements are called `halty' iff they may possibly lead to a halt then showing a tracing display, thus any tracy element is also halty, but there are many other instructions being halty in this sense. To begin with, any instruction possibly leading to some alarm is of this kind: besides the particular instructions `JP[..].ALARM', this includes all prewinds and rewinds Pi+q, Pi-q, DPi-q, and also Pi±n with dynamic n (unless done by inline coding), which may cause `wind bound violation' or `storage overflow'. The latter could also happen with any instruc- tion that is preceded by a tape count control calling `mm01' (usually with jumps ending a segment), or with the subroutine calls JS/JP... preceded by calling the stack manager `stmm'. Moreover these service routines `mm01' and `stmm' are also implicit trace points because of their periodical checking for potential keyboard interrupt. TPICO - 6 In order to provide suitable cross referencing to the source code for all its halty elements, the module file contains corresponding infor- mation in LINES organized in the following way. For each line of the TPAL source containing a halty element, LINES contains a so-called line word, containing a 16-bit line number `lnr', an 8-bit field `cit' as citation link, plus a link byte c for chain- ing such lines, |......lnr......|..cit..|...c...| that is followed by so-called halty points, one word per halty element of the line numbered in the preceding line word, with a word address `addr' as lower 20-bit part pointing to the corresponding instruction in the body (to the 2nd word, if op=0, or a NOP precedes a jump) plus 12-bit part `dt' as a signed timer difference, -2048 <= dt < 2048, |........addr.......|....dt.....| The initial line word of LINES has address `lines', its link byte c0 specifies lina(1)= lines +c0 as word address of the next line word, with its link c1 then lina(2) = lines +c0 +c1 is the address of the third line word, and so forth until a final line word at some address lina(N), with link byte c satisfying lina(N) + c = length of module. The lnr's in this chain of line words are in increasing order, and so are the halty points. For a line word with citation link cit= 0 and link byte c, there are exactly c-1 halty points for this line (thus always c > 1), while any line of the source code containing a tracy element is represented in LINES by a line word (at address lina(k), say) with cit > 0 and full citation of that line plus additional information stored under module relative word addresses lina(k) + cit, ..., lina(k) + c-1. The same verbosity shall always apply for lines with a `JP[..].ALARM'. If tpa is invoked with option `-g', also the other lines of LINES are treat- ed in the same way (then also including all baby tape count controls as halty points). Otherwise, without option -g, purely `halty' lines without any tracy element are only listed with their halty points and cit = 0, indicating that there is no citation. Then the source code reference for such halts by keyboard interrupt or any potential alarm can merely specify the corresponding module name plus line number. For cit >0, such citation is stored bytewise, little endian packed in those words starting at address lina(k)+cit. It contains the verbatim text of the line as a string (without final zero byte), beginning at relative byte address 1, and in that initial word preceded by the bot- tom byte `elt' which specifies a relative byte offset pointing to the beginning of an `element table', immediately after the final byte of the line in byte position elt-1. That element table contains one byte for each syntactical (non comment) element of the line, plus an extra byte 128 to indicate termination. TPICO - 7 The encoding of these bytes is perhaps best explained by an example, here (assuming a previous TR1) shown for the line "U: LA1,TR0, P1-A," containing four elements, and elt= 18, where all of this citation is listed in byte positions 00-22 (6 words): 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16|17 18 19 20 21 22 | | | | | | | | | | | | | | | | | | | | | | | |18 U : L A 1 , T R 0 , P 1 - A ,|00 04 00 141 |128 This registers nonhalty elements (like "U:" and "TR0") by zero bytes. For a tracy element, value b tells the byte offset b of its beginning (here b=4 for the second element "LA1,"), and b+128 is used for other halty elements (here with b=13 for "P1-A,"), with their top bit being set, which exploits that no line has more than 127 bytes). These con- ventions leave 128 to serve as termination byte. - For this example, LINES contains two halty point words, with dt values dt1= 0, dt2 = 2 (if with timing, else dt2=0). Those dt values specify the number of `pending' static time units not yet accounted for. A more instructive example (assuming previous TR1, TI1) is the line ": ZT2+, JCM, P0-2, RTS," with 4 tracy elements, where dt1=0, dt2= -3, dt3= -1, dt4= -3, because when tracy point JCM has been reached, the timer call for that loop has already happened, each time accounting 5 tu, but the 3 tu for that JCM are not yet due, and after exit from that loop, there is dt3= -1 pending, and at the `RTS' its timing of 3 tu has already been "prepaid". -- Here the only purpose of these timer offsets is to provide interactive tracing with correct timer information at any possible halty point. The foregoing conventions imply, in particular, that subroutine calls JS or JP being preceded by calling `mm01' or `stmm' are always halty and thus are pointed to by a halty point word in LINES. Under tracing or under tpa option -g, full citation of all these calls is available in LINES. - Return addresses related to JS or JP are not specified in this text, but with most types of any emulating machine code, usually they will be just a few bytes higher than their related halty points, so the tracer can reconstruct the halty points belonging to the re- turn addresses found on the stack, e.g. using binary search in LINES. In this way (at any intermediate stop) the contents of the stack (the current nesting of subroutine calls) can at least be told in terms of line numbers, or (under -g) by line and element numbers. TPICO - 8 6. The ti/tr-field ------------------ Except for the jumps and the special opcode 00 for long constant high part setting, all other instructions offer their `ti/tr' nibble for all kinds of monitoring purposes. In this implementation we adhere to the following conventions concerning these four bits: w24=1 iff tracy, jumps are tracy anyway if tracing is `on'; w25=1 iff halty even with mtc=0 (for halty instructions like Pi±q); w26=1 iff this instruction has an actual label -- with opcode zero that mark w26=1 is then set in the next word; if the need to set such a label indicator coincides with a jump instruction at the beginning of a segment, tpa may insert a NOP (opcode 4, rim=n=0) with that mark w26=1; w27=1 iff this word contains a special compound instruction needing special textual expansion. These are: opcode 40, 111'111'o1, n= 255 for EOR= -1, turned into `NOT,' opcode 45 for IAD, expanded as `E1,AD...,' opcode 46 for OAD, expanded as `E0,AD...,' opcode 49 for IAC, expanded as `E1,AC...,' opcode 50 for OAC, expanded as `E0,AC...,' opcode 53 for ISB, expanded as `E1,SB...,' opcode 54 for OSB, expanded as `E0,SB...,' opcode 57 for ADI, expanded as `E1,ADE...,' opcode 58 for ADO, expanded as `E0,AD...,' same as for OAD, opcode 61 for ACI, expanded as `E1,SB...,' same as for ISB, opcode 62 for ACO, expanded as `E0,AC...,' same as for OAC. opcode 150 for JCPH, expanded as `CP,JHC. .., opcode 151 for JCMH, expanded as `CM,JHC. .., opcode 182 for JsCPH, expanded as `CP,JsHC..., with s= S|P opcode 183 for JsCMH, expanded as `CM,JsHC..., with s= S|P opcode 214 for JCPHZ, expanded as `CP,JHCZ..., opcode 215 for JCMHZ, expanded as `CM,JHCZ..., opcode 246 for JsCPHZ, expanded as `CP,JsHCZ..., with s= S|P opcode 247 for JsCMHZ, expanded as `CM,JsHCZ..., with s= S|P 7. Experimenting with tpa ------------------------- Translation of module `intari.t' (with option -r) yields a module file `intari.m32' of 6476 words (25904 bytes), namely 4 header words, 4311 words for the body, +1 (no tables so far), 278 words for the P-names, 1882 words in LINES. With option -rt (including timing) one gets 7985 words (31940 bytes), now with 5820 words for the body, which thus is longer by 35 percent, the very same percentage has been found for `recari.t'. With option -rg (including citations) one gets 16162 words (64648 bytes), now with 11568 words for LINES, and option -rgt yields 17671 words. All these translations take at most 0.11 sec (on a 400 MHz Pentium II). TPICO - 9 8. TP16 modules .m16 -------------------------- The first pass translation of any TPAL source file .t for TP16 (by calling our assembler `tpa16') produces an intermediate code file .m16 subject to almost the very same conventions as described in the preceding sections for .m32 modules, up to the following minor differences, in section 2: source =c with 16-bit value c > 255 (r'i'm= 11111111) uses 2nd byte h < 256 from the previous word 0'h'0'0, preparing this h by opcode = 0. in section 3: in the table of tables (with word pairs u,v= v8'v24), u and v8 are still counting 32-bit words, whereas v24 (if nonzero) specifying the `length' of that table is then counting `16-bit' words, occupying [(v24 + 1)/2] words of the .m16 module, in case of odd v24 with an additional zero half-word at the upper end.