Dragon Code Templates To DragonCore^.pa Date August 23, 1984 From Russ Atkinson Location PARC Subject Dragon Code Templates Organization CSL XEROX Release as DragonTemplates.tioga Came from [Ivy]Dragon>DragonTemplates.tioga Last edited by Russ Atkinson, August 23, 1984 12:35:56 pm PDT Abstract This document describes the Dragon opcodes that should be generated for a variety of Cedar/Mesa constructs. Familiarity with the Dragon instruction set is assumed. Dragon Code Templates This document is a DRAFT, and most of the information in it is volatile. This document is also INCOMPLETE, and should be viewed with some suspicion. Revisions are currently being sent through Russ Atkinson. Registers and local frames The most easily accessible operands are those in registers, which are used for arguments to procedures, local variables, temporary variables and the special constants {FIRST[INT], -2, -1, 0, 1, 2, 3, 100000B} (possibly more to come). If the total number of words for arguments, local variables, and temporaries exceeds 14 words, then some of them must be allocated in a frame extension, which is a block of memory referenced indirectly through a register. If the amount of space for arguments is greater than 14 words, they must be passed in an auxilliary block of memory. This leaves one word for the global frame pointer, and potentially one word for the static link. Besides the number of local registers permitted, we also limit the stack depth to be at most 32 words above the base of the frame. If the stack depth threatens to become larger than that (due to nested expressions), then some words must be migrated to temporaries, which will then be in a frame extension. Frame extensions are also required for nested procedures and addressable variables. They are also desirable for arrays that are indexed by non-constants, since it is difficult to generate arrays in registers (they are not indexable). In checked Cedar programs, frame extensions might well come from counted storage. This automatically leads to retained frames. In cases where frame extensions must be allocated from uncounted storage, a simple k-slot cache can be used for the each size of extension (under a certain amount). On allocation, we check each of the k slots using CST to atomically allocate frames. This is a simple accelerator for the general case of frame allocation, however. Expressions The code for expressions will differ significantly depending on whether the target is to the stack or to register. General GenReg [regK] {expr} = GenStack{expr}; drSRn[k]; GenStack{expr}; drROR [c: regK, a: const0, b: regL]; drROR [c: regK, a: regC, b: const0]; drROR [c: regK, a: regC1, b: regC2]; GenStack{regK} = drLRn[k]; GenWordsLoad[offset, width] = IF width = 1 AND offset < 256 THEN drRB[offset] ELSE { SELECT TRUE FROM offset < 256 => drADDB[offset]; offset < 256*256 => drADDDB[offset]; ENDCASE => drLIQB[offset]; drADD[]; SELECT width FROM 1 => drRB[0]; 2 => { drRSB[1]; drRFX[c: belowDst, a: belowSrc, b: const0]; }; 3 => { drDUP[]; drRFX[c: belowDst, a: belowSrc, b: const0]; drRSB[2]; drRFX[c: belowDst, a: belowSrc, b: const1]; }; ENDCASE => { FOR i: INT IN [0..width-1) DO drRVADD[pushDst, topSrc, const1]; drRFX[belowDst, a: belowSrc, b: const0]; ENDLOOP; drRB[0]; }; }; GenRegWordsLoad[reg, offset, width] = IF offset+width < 256 THEN ELSE {GenStack[reg]; GenWordsLoad[offset, width]}; Field GenStack{R.F} = GenStack{@R}; GenStackLoad[k, w]; GenStack{R.Fw} = GenStack{@R}; drRB[k]; drLRn[k]; drLRn[k]; GenReg [regT] {R.Fw} = GenStack{R.Fw}; SRt; MOVR [regT, regK]; RRI [regT, regV, K]; GenStack{R.F} = GenStack{R.Fw}; EF [fd]; Indexing GenStack{R[I]} = GenStack{R^[I]}; GenStack{A[I]} = GenStack{@A[I]}; RFX [c: topDst, a: popSrc, b: popSrc]; GenStack{@A}; GenStack{I}; RFX [c: topDst, a: popSrc, b: popSrc]; GenStack{I}; RFX [c: topDst, a: regA, b: popSrc]; GenStack{@A}; RFX [c: topDst, a: popSrc, b: regI]; RFX [c: topDst, a: regA, b: regI]; GenStack{A[I]} = GenStack{@A[I]}; RSB [0]; EXCH; ... RB [k-1]; GenReg [regT] {@A[I]}; RSB [0]; EXCH; ... RB [k-1]; GenStack{A[I]} = GenStack{I}; SPA [sz]; GenStack{A}; ADD; EF [fd]; Address GenStack{@R^} = GenStack{R}; GenStack{@R.F} = GenStack{@R}; GenStack {Foff}; ADD; GenStack{@R}; ADDDB [Foff]; GenStack{@R}; ADDB [Foff]; GenStack{A[I]} = GenStack{I}; SPA [sz]; GenStack{A}; ADD; EF [fd]; Arithmetic GenStack{expr1 a expr2} = a + - c ADD SUB r RADD RSUB GenStack[expr1]; GenStack[expr2]; c; GenStack[expr2]; r [c: topDst, a: regK, b: topSrc]; GenStack[expr1]; r [c: topDst, a: topSrc, b: regK]; GenReg [regT] {expr1 a expr2} = GenStack[expr1]; GenStack[expr2]; r [c: regT, a: popSrc, b: popSrc]; GenStack[expr2]; r [c: regT, a: regK, b: popSrc]; GenStack[expr1]; r [c: regT, a: topSrc, b: regL]; r [c: regT, a: regK, b: regL]; Conditional Tests GenCond[label]{test} generates code to test the condition and branch to the given label if the condition is FALSE. In this section, a denotes the condition desired (32-bit signed comparison unless otherwise specified), c denotes the corresponding opcode for the false jump, and r is the opcode for the false jump if the operands are reversed. a = = < > < > c RJNEB RJEB RJGEB RJLEB RJGB RJLB r RJNEB RJEB RJLEB RJGEB RJLB RJGB GenCond[label]{expr1 a expr2} = GenStack{expr1}; GenStack{expr2}; c[popLeft: TRUE, right: popSrc, dest: label]; GenStack{expr1}; c[popLeft: TRUE, right: regN, dest: label1]; GenStack{expr2}; c[popLeft: TRUE, right: regN, dest: label1]; GenCond[label]{expr1 a expr2} = GenStack{expr1}; RXOR [c: topDst, a: topSrc, b: constNI]; GenStack{expr2}; RXOR [c: topDst, a: topSrc, b: constNI]; c[popLeft: TRUE, right: popSrc, dest: label]; GenCond[label]{bool} = GenStack{bool}; RJEB[popLeft: TRUE, right: popSrc, dest: label]; GenStack{R.Fw}; RJGEB[popLeft: TRUE, right: const0, dest: label]; GenCond[label]{bool1}; GenCond[label]{bool2}; tLabel = GenLabel[]; GenCond[tLabel]{NOT bool1}; GenCond[label]{bool2}; DefLabel[tLabel]; GenCond[label]{NOT bool} = GenStack{bool}; RJEB[popLeft: TRUE, right: popSrc, dest: label]; GenStack{R.Fw}; RJLB[popLeft: TRUE, right: const0, dest: label]; GenCond[label]{(NOT bool1) OR (NOT bool2)}; GenCond[label]{(NOT bool1) AND (NOT bool2)}; GenCond[label]{bool1}; Statements Assignment GenStmt{var _ expr} = GenStack{expr}; GenStack{@var}; WB [0]; GenReg [regV] {expr}; GenStack{expr}; SRIv [K]; WRI [reg1: m, reg2: v, disp: K]; GenStack{A[I] _ X} = GenStack{X}; GenStack{@A[I]}; WB [0]; GenStack{X}; GenStack{@A[I]}; WB [0]; GenStack{A[I] _ X} = GenStack{@A}; GenStack{I}; ADD; GenStack{X1}; PSB [0]; GenStack{X2}; PSB [1]; ... GenStack{Xn}; WSB [n-1]; GenStack{A[I] _ X} = GenStack{@A}; GenStack{I}; SPA [sz]; ADD; GenStack{X}; RFX [c: pushDst, a: belowSrc, b: const0]; IF [fd]; WSB [0]; Conditional GenStmt{IF E1 = E2 THEN S1} = GenStack{E1}; GenStack{E2}; RJNEB[pop, pop, L1]; GenStmt{S1}; DefLabel{L1}; GenStmt{IF E1 = E2 THEN S1 ELSE S2} = GenStack{E1}; GenStack{E2}; RJNEB[pop, pop, L1]; GenStmt{S1}; Jump{L2}; DefLabel{L1}; GenStmt{S2}; DefLabel{L2}; GenStmt{SELECT E FROM E1,E2 => S1; E3 => S2; ENDCASE => S3} = GenStack{E}; GenStack{E1}; RJEB[top, pop, L1]; GenStack{E2}; RJNEB[top, pop, L2]; DefLabel{L1}; GenStmt{S1}; Jump{LX}; DefLabel{L2}; GenStack{E2}; RJNEB[top, pop, Lend]; GenStmt{S2}; Jump{labelx}; DefLabel{Lend}; GenStmt{S3}; DefLabel{LX}; Procedures Simple procedures start with an enter byte, E, which gives the number of arguments to the procedure. When the procedure is called, RL _ SP - E. Simple procedures that need access to the global frame load the global frame with PRL (?). Multi-module procedures start with an enter byte as well. They also load the global frame into a register. Then they transfer to the common part of the routine using a DJ instruction. Conversions INTEGER -> INT RXOR [c: topDst, a: topSrc, b: constNSI]; RSUB [c: topDst, a: topSrc, b: constNSI]; INT -> INTEGER RVADD [c: pushDst, a: topSrc, b: constNSI]; RADD [c: pushDst, a: constNSI, b: constNSI]; BNDCK; DIS; –Copyright c 1984 by Xerox Corporation. All rights reserved. regK is destination for 1-word expr, k is number of regK General case Special case: regK is aliased [S+1] Special case: expr is in local reg regL Special case: expr is a special constant in regC Special case: expr is the sum of two special constants in regC1 and regC2 regK is a 1-word item in a register, k is number of regK General case General case General case R is a record, F is a field of width w at offset k R is a record, Fw is a 1-word field at offset k (Fk < 256) fd is field desc for field F General case Special case: R is a local variable, k is register for Fw Special case: R is a record contained in the local frame, k is register for Fw regT is at index t, R is a record, Fw is a 1-word field at offset Foff (Fk < 256) fd is field desc for field F General case Special case: R.Fw is contained in regK in local frame Special case: R.Fw is at offset K from regV in local frame R is a record, F is a sub-word field in R, Fw is the containing word field (synthetic) fd is field desc for field F Special case: R is a record contained in the local frame, regF is register for F R is a REF or pointer to an array A is an array of 1-word items (offset Aoff, index bias Abias) General case (offset Aoff, index bias Abias) Special case (offset 0, index bias 0) Special case (offset 0, index bias 0, @A in register regA) Special case (offset 0, index bias 0, index in register regI) Special case (offset 0, index bias 0, @A in register regA, index in register regI) A is an array of k-word items (offset Aoff, index bias Abias) General case Special case: regT avail as temp A is a packed array, where the element size is one of {1, 2, 4, 8, 16} bits sz is log of size of packed array element; fd is field desc with shift spec from Q R is a record, F is a word-aligned field starting at Foff General case Special case (Foff < 256*256) Special case (Foff < 256) A is a packed array, where the element size is one of {1, 2, 4, 8, 16} bits sz is log of size of packed array element; fd is field desc with shift spec from Q a is the operation desired (32-bit signed arithmetic with overflow detection assumed), while c is the corresponding stack opcode, and r is the corresponding register opcode. General case Special case: expr1 is in regK (including special constants) Special case: expr2 is in regK (including special constants) a and r are as in GenStack[expr1 a expr2] General case Special case: expr1 is in regK (including special constants) Special case: expr2 is in regL (including special constants) Special case: expr1 is in regK, expr2 is in regL (either may be special constants) expr1 & expr2 both eval to words (or fields) the general case special case, expr2 is in regN (includes register constants) special case, expr1 is in regN (includes register constants) a is 32-bit unsigned comparison expr evaluates to a boolean the general case special case, bool = R.F, F is sign bit, Fw is word offset for F special case, bool = bool1 AND bool2 special case, bool = bool1 OR bool2 expr evaluates to a boolean the general case special case, bool = R.F, F is sign bit, Fw is word offset for F special case, bool = bool1 AND bool2 special case, bool = bool1 OR bool2 special case, bool = NOT bool1 require var is 1 word (includes sole field right-justified in word) General case Special case: var is in regV Special case: @var is at offset K (K < 256) from regV (index v) Special case: @var is at offset K (K < 256) from regV (index v), expr in in local reg m A is array of one-word items, I is an index into that array General case Special case: A is an array of n-word items; I is an index into that array; X can be generated as separate words [X1, X2, ..., Xn] A is a packed array of sub-word items; I is an index into that array sz is log of size of packed array element; fd is field desc with shift spec from Q integer is on stack, result is on stack int is on stack, result is on stack; trap if can't fit Κ ¬˜Icenter•Mark centerHeaderšΟb˜ImemoHeadšΟsœžœžœ˜+Lšžœžœ˜!Lšžœž œ˜5Ilogošœ˜Iabstractš ž Οtœž Ÿœ+ž Ÿœ1˜”NšžŸœ€˜­titlešœ˜Nšœ Οmœ1™