Featherweight DSP
2.3 The Essence of the Custom DSP
2.3.1 Syntax of Featherweight DSP
Number of procedures: 43
Number of procedures with adoloop: 42
Number of procedures with nesteddoloops: 4
Number of procedures with a local jump: 3
Number of procedures with acallor a longjmp: 0 Average size excluding comments (lines of code): 25 Average size including comments (lines of code): 40 Average percentage of the size of comments 37 Total size of all procedures excluding comments (lines of code): 1074 Number of calls to undefined labels (in macros): 4
Number of shared bodies: 5
Number of procedures where the first label is not a call target: 10 Number of procedures which are not a target of acall: 2
Figure 2.5: Statistics for ROM primitives
programs P ≡ (ℓi, ℓ1:mval1 · · · ℓn:mvaln) memory values mval ≡ I|dval
data values dval ≡ X:<c1, . . . ,cn>
| Y:<c1, . . . ,cn>
instruction sequences I ≡ jmp(v)
| ret
| halt
| ins I
instructions ins ≡ call(v)
| sins1;. . .;sinsn
| do(v) {B}
| enddo
| bop r, v do-bodies B ≡ ins1· · ·insn
small instructions sins ≡ rd = xmem[rs]
| xmem[rmd] = rs
| rd = ymem[rs]
| ymem[rmd] = rs
| rd += aexp
| rd = aexp arithmetic expressions aexp ≡ v
| r1 + r2
| r1 * r2
branch operators bop ≡ beq|bneq|bgt|blt|bgte|blte
values v ≡ c|r
constants c ≡ f |i|ℓ
fixed-point constants f integer constants i
labels ℓ
Figure 2.6: Syntax for Featherweight DSP.
self-explanatory as it resembles the syntax of a high-level language like C. To load a value from X memory into the registerrdwe write:
rd = xmem[rs]
where rs is the source register that must contain an address in X memory.
And similar if we want to store the value in the registerrs to Y memory we write:
ymem[rmd] = rs
where rmd is the memory destination register that must contain an address in Y memory.
Arithmetic operations are restricted to addition and multiplication of two registers. This is of course only a small subset of the arithmetic operations
1 vecpmult:
2 do (i7) {
3 x0 = xmem[i0]; i0+=1; y0 = ymem[i4]; i4+=1
4 a0=x0*y0
5 xmem[i1] = a0; i1+=1
6 }
7 ret
Figure 2.7: Pointwise vector multiplication in Featherweight DSP.
the real custom DSP provides. The real custom DSP has a multiply with pre-add:
rd = r1 * (r2 + r3)
and various bit-fiddling operations like shifts, for instance. Curiously enough, the custom DSP does not have any division operation, so we omit it too.
Composite instructions
We form composite instructions out of small instructions simply by putting semicolon between themsins1;. . .;sinsn. However, we need to place certain restrictions on the small instructions in a composite instruction:
1. A register must only occur once in a destination registerrdposition.
2. There must be at most one load or store from X memory.
3. There must be at most one load or store from Y memory.
We define the predicate UniqDef over composite instructions to be true if these restrictions are satisfied and false otherwise. The restrictions for Feath-erweight DSP are a relaxed version of the restrictions for the real custom DSP.
The only property we are interested in for Featherweight DSP, is that no race conditions can occur. That is, the contents of a register or a memory loca-tion must be deterministic. Composite instrucloca-tions are also used to model the auto increment feature of the load and store operations of the real cus-tom DSP.
Loops
I have made a slightly modified syntax for do-loops compared to the real custom DSP. In the real custom DSP assembler language the doinstruction takes a label denoting the last instruction of the loop body as its second ar-gument. In Featherweight DSP the body of a do-loop is simply enclosed in curly braces. Figure 2.7 contains the code for pointwise vector multiplica-tion in Featherweight DSP for comparison with the code in Figure 2.2(a) on page 18.
Contrary to what our first intuition might lead us to believe, the instruc-tionenddoisnotused to terminate ado-loop. The instructionenddois used
if we jump out of the body of a do-loop, because the do-stack is left in an inconsistent state, andenddobrings the stack back into a consistent state by popping the top element of the do-stack. If we jump out of nested loops, then enddomust be called as many times as the nesting is deep. Also notice that, in Featherweight DSP the instructions jmp and ret are not allowed in the body of a loop. Thus, the only way to jump out of a loop is to use a branch instruction. In Featherweight DSP the instructionsdoandenddoare the only instructions for manipulating the do-stack. Whereas in the real custom DSP the do-stack can also be manipulated through peripheral space, but I have not found any real code that does that feature.
Hardware procedures
Featherweight DSP (and the real custom DSP) offers hardware support for implementing procedures using the instructionscallandret. The instruc-tioncalltakes a code locationvas its sole operand;callpushes the address of the instruction following thecallinstruction onto the call-stack and then transfers control to the instruction atv. The instructionretpops the top el-ement, which is a code location, off the call-stack and jumps to this location.
In Featherweight DSP the instructionscallandretare the only instructions for manipulating the call-stack. The call-stack cannot be used for transferring arguments to procedures, these arguments must be transferred via registers or memory. In the real custom DSP the call-stack can also be manipulated through peripheral space, but I have not found any examples of real code that does that.
Branch instructions
In the assembler language for the real custom DSP the branch instruction has the form:
if(e) jmp(v)
whereeis one of a finite set of expressions testing the CCR. An example of such a test is:
a == 0
which tests that the last test instruction on one of the anaccumulators was zero. For example, the following two instructions tests ifa0is zero and if so jumps to the code located atfoo:
a0 & a0
if (a == 0) jmp foo
where a0 & a0is the bitwise AND test instruction the operands of this in-struction are not altered but the CCR is).
In Featherweight DSP there is no CCR, instead there are several branch instructions that take two operands and branch to the second operand if the first operand is appropriately related to zero; otherwise execution continues
with the instruction following the branch instruction. Thus, the following instruction tests whethera0is zero, and if, so jumps tofoo:
beq a0, foo
I have chosen this simplification of the branch instruction, because then the type system presented in the next chapter does not have to keep track of a CCR.
Instruction sequences and control transfer instructions
An instruction sequence, I, is a list of instructions terminated by an uncon-ditional control transfer instruction: jmp,ret, orhalt.