% Section 2.2.3, Exo.27: Subroutine Allocation % Author Chan Vinh VONG % Draft Version 2012 March 27th % % This MMIX program is an answer to the exercise 27 page 272 of TAoCP % Volume 1. % % Data Structure Implementation: (Tape) Directory ===================== % % In the MIX version of the program, the following structure was used: % % +--+--+--+--+--+--+ % | B |SPACE| LINK| 1x MIX Word % +--+--+--+--+--+--+ % | B | SUB1| SUBn| % +--+--+--+--+--+--+ % % In this proposal, we make use of a slightly different structure: % % 63rd % |62nd % || 61st 0 bit position % +--+----------...-----------+ % |B | SPACE or LINK or SUBi | 1x OCTA % +--+----------...-----------+ % % B is on 2 bits, which allows values within {-2,-1,0,1} using two's % complement (reverted flag order compared to MIX version); % SPACE/LINK/SUBi are on 62-bits, which allows max #3F-FF, which covers % the Text Segment and Data Segment using absolute addressing, or any % 2^62-1 range of memory using relative addressing => we use relative % addressing, this gives enough room for the subroutine allocation % (assuming you have as most 2^62-1 subroutines to allocate that is...) % % We will work on blocks of 2 OCTAs, thus B in the 2nd OCTA is not used % at all and will always be defaulted to 0 (that's the slight diff % compared to the MIX version). The directory thereafter can contain % three kinds of nodes, each of which has 2 D-block holding B and a % Data. % % +--+-------...--------+ % |B | SPACE | 1x OCTA % +--+-------...--------+ % |x | LINK | B is not used and defaulted to 0 % +--+-------...--------+ % or % +--+-------...--------+ % |B | SUB1 | % +--+-------...--------+ % |x | SUB2 | % +--+-------...--------+ % or % +--+-------...--------+ % |B | SUB1 | % +--+-------...--------+ % |x | 0 | % +--+-------...--------+ % % In order to use value 0 as the NULL pointer, all relative addressing % is made relative to a base pointer plus one unit of block => 0 is % reserved for NULL, just add an unused block as the Base Pointer +0 % block of the directory. That first block will contain the FIRST link % variable in the 1st block. Example: % % | OCTA | OCTA | % |0|FIRST|0| 0 | Entry 0 of the directory (not used), base pointer % |B|SPACE|x|LINK | Entry 1 % |B|SUB1 |x|SUB2 | % % /!\ ACHTUNG /!\ ATTENTION /!\ CAUTION /!\ % LINK/SUBi are no more absolute addresses but now relative addresses % to the base pointer of the directory. In MIX, addresses on 1.5 bytes % could cover the 4000 words of memory, it is no more the case in MMIX. % Here, having the relative addresses on 62-bits gives more than enough % room to cover any two consecutive Segments in memory. % % In the MIX version, indexing starts from 0, while in this proposal, % it starts from 1. This comes from the use of relative addressing. % Would we have used 0 to point to the first entry, then the NULL value % could not be distinguished from that 0. % % Data Structure Implementation: X Table ============================== % % The choice for the directory constraints this one. So let's use the % following layout: % % +----------------+ % | - | 1x OCTA % +----------------+ % | SUB | % +----------------+ % % Each X[k] is made of 2 OCTAs, the algorithm will fill in the first % one and update the second: % % +----------------+ % | BASE | 1x OCTA % +----------------+ % | SUB | % +----------------+ % % Note that in any case, the first two bits of each block is not used. % Thus, we do not make use of 1.56% of the bits for the directory and % 3.13% of the bits for the X Table. We won't lose any bit if we put B, % SPACE and LINK or SUBi and SUBj in the same OCTA. But that would % lower considerably the number of possible entries in the directory. % (note: make another proposal for that technical choice) % % ===================================================================== LOC Data_Segment+0 % Directory (could be loaded from file) D GREG @ % example from the book, w/ rel. addr. % note that we revert the flag logic % it's now +1 and not -1 % B SPACE LINK NODE OCTA 3,0 % [FIRST] 0 0 (not used) OCTA 20 % 0 20 6 1 Subroutine OCTA 6 OCTA #4000000000000003 % +1 3 0 2 OCTA 0 OCTA #400000000000001E % +1 30 11 3 Subroutine OCTA 11 OCTA 200 % 0 200 8 4 Subroutine OCTA 8 OCTA #4000000000000001 % +1 1 7 OCTA 7 OCTA #4000000000000064 % +1 100 4 6 Subroutine OCTA 4 OCTA #400000000000003C % +1 60 1 7 Subroutine OCTA 1 OCTA 200 % 0 200 0 8 Subroutine OCTA 0 OCTA 6 % 0 6 3 9 OCTA 3 OCTA #4000000000000007 % +1 7 0 10 OCTA 0 OCTA #4000000000000014 % +1 20 7 11 Subroutine OCTA 7 LOC Data_Segment+4096 % X Table (could be loaded from file) X GREG @ OCTA 0,0 % not used, X starts at X[1], avoid k-1.. % BASE LINK OCTA 0,4 % 0 4 OCTA 0,11 % 0 11 BLOCK1 IS 0 BLOCK2 IS 8 NULL GREG 0 N GREG 0 nn GREG 0 MLOC GREG 0 dd GREG 0 % cursor of Directory w/ absolute address xx GREG 0 % cursor of X Table w/ absolute address temp GREG 0 temp2 GREG 0 flag GREG 0 subrt GREG 0 LOC #100 GREG @ % A set of subroutines which mux/demux B from the D-Block ============= % % ReadB(ptr):b % % Calling Sequence: % SET $X1, % PUSHJ $X0,ReadB % Entry Conditions: % $X1 is the absolute address of the node % Exit Conditions: % $X0 holds value of node.B ReadB LDO $1,$0,BLOCK1 MUX $0,$1,NULL SR $0,$0,62 POP 1,0 % % WriteB(ptr,b):void % % Calling Sequence: % SET $X2, % SET $X1, % PUSHJ $X0,WriteB % Entry Conditions: % $X1 is the absolute address of the node % $X2 is the value of B to be written in the node % Exit Conditions: % none WriteB LDO $2,$0,BLOCK1 SL $1,$1,62 MUX $2,$1,$2 STO $2,$0,BLOCK1 POP 0,0 % A set of subroutines which read/write Data from/to the D-Block ====== % % ReadSPACE(ptr):SPACE % ReadSUB1(ptr):SUB1 % ReadSUB2(ptr):SUB2 % ReadSUB(ptr):SUB % ReadLINK(ptr):LINK % % Calling Sequence: % SET $X1, % PUSHJ $X0,Read{SPACE|SUB1|SUB2|SUB|LINK} % Entry Conditions: % $X1 is the absolute address of the node % Exit Conditions % $X0 is the value of SPACE or SUBi or LINK ReadFIRST SWYM ReadSPACE SWYM ReadSUB1 SET $1,BLOCK1 JMP 1F ReadSUB2 SWYM ReadSUB SWYM ReadLINK SET $1,BLOCK2 1H LDO $2,$0,$1 MUX $0,NULL,$2 POP 1,0 % % WriteBASE(ptr,base):void % WriteSUB(ptr,sub):void % % Calling Sequence: % SET $X2, % SET $X1, % PUSHJ $X0,Write{BASE|SUB} % Entry Conditions: % $X1 is the absolute address of the node % $X2 is the value to write in the node % Exit Conditions % none WriteBASE SET $2,BLOCK1 JMP 1F WriteSUB SET $2,BLOCK2 1H LDO $3,$0,$2 MUX $3,$3,$1 STO $3,$0,$2 POP 0,0 % A set of subroutines which computes the cursors ===================== % % N => X[N].SUB => pointer to D[X[N].SUB] % N2dd(N):dd % xx2dd(xx):dd % % Calling Sequence: % SET $X1, % PUSHJ $X0,2dd % Entry Conditions: % $X1 is the N index or a cursor of the X Table % Exit Conditions : % $X0 is a cursor of the Directory xx2dd JMP 1F N2dd 16ADDU $2,$0,X 1H GET $0,rJ PUSHJ $1,ReadSUB % N => ( xx => SUB ) PUT rJ,$0 16ADDU $0,$1,D POP 1,0 % % N2xx(N):xx % % Calling Sequence: % SET $X1, % PUSHJ $X0,N2xx % Entry Conditions: % $X1 is the N index % Exit Conditions : % $X0 is a cursor of the X Table N2xx 16ADDU $0,$0,X POP 1,0 % % SUBi2dd(SUB):dd % % Calling Sequence: % SET $X1, % PUSHJ $X0,SUBi2dd % Entry Conditions: % $X1 is a relative address of a Directory entry % Exit Conditions : % $X0 is a cursor of the Directory SUBi2dd 16ADDU $0,$0,D POP 1,0 % Main Routine ======================================================== Main SET NULL,0 SET N,2 SET MLOC,2400 SETH temp,#C000 PUT rM,temp % mask for MUXing B from other fields SET nn,N A0 SET $4,nn PUSHJ $3,N2dd SET dd,$3 PUSHJ $2,ReadB BN $2,1F % is B >= 0 ? SUB $2,$2,2 SET $1,dd PUSHJ $0,WriteB 1H SUB nn,nn,1 BP nn,A0 % For 1<=J<=N, B(X[J])-=2 SWYM % BP: Depth-1 subroutines of X are now flagged B<0 in D SET nn,N A1 BZ nn,B1 SET $2,nn PUSHJ $1,N2dd SET dd,$1 SUB nn,nn,1 A2 SET $1,dd PUSHJ $0,ReadB NEGU $2,$0 CSNN $2,$0,$0 SUB $2,$2,1 BZ $2,A1 ADD dd,dd,16 % P <- P + 1 A3 SET flag,1 SET $3,dd PUSHJ $2,ReadSUB1 SET temp,$2 3H PUSHJ $1,SUBi2dd SET temp2,$1 PUSHJ $0,ReadB BN $0,3F % if B(SUB1(P) >= 0 ADD nn,nn,1 % then mark SUB1 as needed by the routine SUB $0,$0,2 SET $2,$0 SET $1,temp2 PUSHJ $0,WriteB SET $2,nn PUSHJ $1,N2xx SET $2,temp PUSHJ $0,WriteSUB % X[N] <- SUB1(P) BZ flag,3F % processed SUB1 AND SUB2? SET $1,dd PUSHJ $0,ReadSUB2 BZ $0,3F % also mark SUB2 if applicable SET $2,$0 SET flag,0 JMP 3B 3H JMP A2 B1 SWYM % BP: Depth-all subroutines of X are now flagged B<0 in D SET $2,D PUSHJ $1,ReadFIRST SET subrt,$1 PUSHJ $0,SUBi2dd SET dd,$0 B2 CMP temp,dd,D % process the last subroutine BNZ temp,B3 ADD nn,nn,1 SET $2,nn PUSHJ $1,N2xx SET xx,$1 SET $2,MLOC PUSHJ $0,WriteBASE SET $1,xx SET $2,NULL PUSHJ $0,WriteSUB JMP Exit B3 SET $1,dd % process subroutine, filling X as needed PUSHJ $0,ReadB BNN $0,B4 ADD nn,nn,1 SET $2,nn PUSHJ $1,N2xx SET xx,$1 SET $2,MLOC PUSHJ $0,WriteBASE SET $2,subrt SET $1,xx PUSHJ $0,WriteSUB SET $1,dd PUSHJ $0,ReadSPACE SET temp,$0 ADD MLOC,MLOC,temp B4 SET $2,dd % follow the LINK in the pre-ordered PUSHJ $1,ReadLINK % chain of subroutines SET subrt,$1 PUSHJ $0,SUBi2dd SET dd,$0 JMP B2 Exit TRAP 0,Halt,0 % Expected result should be as expected in V1e3 p.272 (w/ a small incr) % % X Table % BASE SUB % [1] #960 3 % [2] #97E 11 % [3] #992 7 % [4] #9CE 1 % [5] #9E2 4 % [6] #AAA 0 ! we've got a AAA rating ! %