[Pixel]<DragonWare0.1>Documentation>DragonTemplates.tioga!1

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]<Atkinson>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} =

regK is destination for 1-word expr, k is number of regK

General case

GenStack{expr};

drSRn[k];

Special case: regK is aliased [S+1]

GenStack{expr};

Special case: expr is in local reg regL

drROR [c: regK, a: const0, b: regL];

Special case: expr is a special constant in regC

drROR [c: regK, a: regC, b: const0];

Special case: expr is the sum of two special constants in regC1 and regC2

drROR [c: regK, a: regC1, b: regC2];

GenStack{regK} =

regK is a 1-word item in a register, k is number of regK

General case

drLRn[k];

GenWordsLoad[offset, width] =

General case

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] =

General case

IF offset+width < 256

THEN

ELSE {GenStack[reg]; GenWordsLoad[offset, width]};

Field

GenStack{R.F} =

R is a record, F is a field of width w at offset k

GenStack{@R};

GenStackLoad[k, w];

GenStack{R.Fw} =

R is a record, Fw is a 1-word field at offset k (Fk < 256)

fd is field desc for field F

General case

GenStack{@R};

drRB[k];

Special case: R is a local variable, k is register for Fw

drLRn[k];

Special case: R is a record contained in the local frame, k is register for Fw

drLRn[k];

GenReg [regT] {R.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

GenStack{R.Fw};

SRt;

Special case: R.Fw is contained in regK in local frame

MOVR [regT, regK];

Special case: R.Fw is at offset K from regV in local frame

RRI [regT, regV, K];

GenStack{R.F} =

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

GenStack{R.Fw};

EF [fd];

Indexing

GenStack{R[I]} =

R is a REF or pointer to an array

GenStack{R^[I]};

GenStack{A[I]} =

A is an array of 1-word items (offset Aoff, index bias Abias)

General case (offset Aoff, index bias Abias)

GenStack{@A[I]};

RFX [c: topDst, a: popSrc, b: popSrc];

Special case (offset 0, index bias 0)

GenStack{@A};

GenStack{I};

RFX [c: topDst, a: popSrc, b: popSrc];

Special case (offset 0, index bias 0, @A in register regA)

GenStack{I};

RFX [c: topDst, a: regA, b: popSrc];

Special case (offset 0, index bias 0, index in register regI)

GenStack{@A};

RFX [c: topDst, a: popSrc, b: regI];

Special case (offset 0, index bias 0, @A in register regA, index in register regI)

RFX [c: topDst, a: regA, b: regI];

GenStack{A[I]} =

A is an array of k-word items (offset Aoff, index bias Abias)

General case

GenStack{@A[I]};

RSB [0]; EXCH;

...

RB [k-1];

Special case: regT avail as temp

GenReg [regT] {@A[I]};

RSB [0]; EXCH;

...

RB [k-1];

GenStack{A[I]} =

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

GenStack{I};

SPA [sz];

GenStack{A};

ADD;

EF [fd];

Address

GenStack{@R^} =

GenStack{R};

GenStack{@R.F} =

R is a record, F is a word-aligned field starting at Foff

General case

GenStack{@R};

GenStack {Foff};

ADD;

Special case (Foff < 256*256)

GenStack{@R};

ADDDB [Foff];

Special case (Foff < 256)

GenStack{@R};

ADDB [Foff];

GenStack{A[I]} =

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

GenStack{I};

SPA [sz];

GenStack{A};

ADD;

EF [fd];

Arithmetic

GenStack{expr1 è expr2} =

è is the operation desired (32-bit signed arithmetic with overflow detection assumed), while © is the corresponding stack opcode, and ® is the corresponding register opcode.

è + -

® RADD RSUB

General case

GenStack[expr1];

GenStack[expr2];

©;

Special case: expr1 is in regK (including special constants)

GenStack[expr2];

® [c: topDst, a: regK, b: topSrc];

Special case: expr2 is in regK (including special constants)

GenStack[expr1];

® [c: topDst, a: topSrc, b: regK];

GenReg [regT] {expr1 è expr2} =

è and ® are as in GenStack[expr1 è expr2]

General case

GenStack[expr1];

GenStack[expr2];

® [c: regT, a: popSrc, b: popSrc];

Special case: expr1 is in regK (including special constants)

GenStack[expr2];

® [c: regT, a: regK, b: popSrc];

Special case: expr2 is in regL (including special constants)

GenStack[expr1];

® [c: regT, a: topSrc, b: regL];

Special case: expr1 is in regK, expr2 is in regL (either may be special constants)

® [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, è denotes the condition desired (32-bit signed comparison unless otherwise specified), © denotes the corresponding opcode for the false jump, and ® is the opcode for the false jump if the operands are reversed.

#è = ` < > d e

#© RJNEB RJEB RJGEB RJLEB RJGB RJLB

#® RJNEB RJEB RJLEB RJGEB RJLB RJGB

GenCond[label]{expr1 è expr2} =

expr1 & expr2 both eval to words (or fields)

the general case

GenStack{expr1}; GenStack{expr2};

©[popLeft: TRUE, right: popSrc, dest: label];

special case, expr2 is in regN (includes register constants)

GenStack{expr1};

©[popLeft: TRUE, right: regN, dest: label1];

special case, expr1 is in regN (includes register constants)

GenStack{expr2};

©[popLeft: TRUE, right: regN, dest: label1];

GenCond[label]{expr1 è expr2} =

è is 32-bit unsigned comparison

GenStack{expr1};

RXOR [c: topDst, a: topSrc, b: constNI];

GenStack{expr2};

RXOR [c: topDst, a: topSrc, b: constNI];

©[popLeft: TRUE, right: popSrc, dest: label];

GenCond[label]{bool} =

expr evaluates to a boolean

the general case

GenStack{bool};

RJEB[popLeft: TRUE, right: popSrc, dest: label];

special case, bool = R.F, F is sign bit, Fw is word offset for F

GenStack{R.Fw};

RJGEB[popLeft: TRUE, right: const0, dest: label];

special case, bool = bool1 AND bool2

GenCond[label]{bool1};

GenCond[label]{bool2};

special case, bool = bool1 OR bool2

tLabel = GenLabel[];

GenCond[tLabel]{NOT bool1};

GenCond[label]{bool2};

DefLabel[tLabel];

GenCond[label]{NOT bool} =

expr evaluates to a boolean

the general case

GenStack{bool};

RJEB[popLeft: TRUE, right: popSrc, dest: label];

special case, bool = R.F, F is sign bit, Fw is word offset for F

GenStack{R.Fw};

RJLB[popLeft: TRUE, right: const0, dest: label];

special case, bool = bool1 AND bool2

GenCond[label]{(NOT bool1) OR (NOT bool2)};

special case, bool = bool1 OR bool2

GenCond[label]{(NOT bool1) AND (NOT bool2)};

special case, bool = NOT bool1

GenCond[label]{bool1};

Statements

Assignment

GenStmt{var ← expr} =

require var is 1 word (includes sole field right-justified in word)

General case

GenStack{expr};

GenStack{@var};

WB [0];

Special case: var is in regV

GenReg [regV] {expr};

Special case: @var is at offset K (K < 256) from regV (index v)

GenStack{expr};

SRIv [K];

Special case: @var is at offset K (K < 256) from regV (index v), expr in in local reg m

WRI [reg1: m, reg2: v, disp: K];

GenStack{A[I] ← X} =

A is array of one-word items, I is an index into that array

General case

GenStack{X};

GenStack{@A[I]};

WB [0];

Special case:

GenStack{X};

GenStack{@A[I]};

WB [0];

GenStack{A[I] ← X} =

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]

GenStack{@A};

GenStack{I};

ADD;

GenStack{X1};

PSB [0];

GenStack{X2};

PSB [1];

...

GenStack{Xn};

WSB [n-1];

GenStack{A[I] ← X} =

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

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

integer is on stack, result is on stack

RXOR [c: topDst, a: topSrc, b: constNSI];

RSUB [c: topDst, a: topSrc, b: constNSI];

INT -> INTEGER

int is on stack, result is on stack; trap if can't fit

RVADD [c: pushDst, a: topSrc, b: constNSI];

RADD [c: pushDst, a: constNSI, b: constNSI];

BNDCK;

DIS;