% Section 2.5, Exo 34 : Garbage Collection and Compacting
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 12th
%
% Data Structure:
%
%                   >|<-----OCTA----->|<
%                    +----------------+
%                    |  S/32    T/32  | x1
%                    +----------------+
%                    |     GCDATA     | x1, Garbage Collector Data
%                    +----------------+
%                    | LINK or CONTENT| x(S-1)
%                    +----------------+
%
% In this proposal, the INFO field has been ignored for simplicity. If
% it is considered as data related to LINK, then a link would be on 2
% OCTAs (LINK,INFO).
%
% S and T are 32-bit values representing numbers of OCTAs.
%
% Compared to the MIX version, step G1 is also omitted here. However,
% LINK(0) cannot be set to a non null value, or with another phrasing:
% because LINK(0) is in the Text_Segment, we have no guarantee that it
% will be non null, and we won't hit that part of the segment which is
% reserved for interrupt vectors! Hence, step G4 does not ignore the
% case Q=0.
%
% Moreover, the MIX opcode MOVE was an easy way to order moves of words
% but such command is not available in MMIX (TODO double-check that).
% The command is used in step G9.
%


% Calling Sequence:
%     PUSHJ $0,GCC
%
% Global Variables:
%     :AVAIL the top of the allocated nodes in the stack
%     :USE   the starting node in use
%     :BASE  the base of the stack
%
        PREFIX GCC:
        
dSIZE   IS 8*0+0
dT      IS 8*0+4
dGCDATA IS 8*1
        
P       IS $0
Q       IS $1
TOP     IS $2
t       IS $3
marked  IS $4 % marked when GCLINK != NULL
size    IS $5
pLINK   IS $6 % pointer to a LINK in the node
k       IS $7

:GCC    CMP   t,:AVAIL,:BASE
        BZ    t,EXIT         % stack is already clean

G2      SET   TOP,:USE       % G2. Initialize marking phase, TOP <- USE
        [[SET   P,:AVAIL]]
        STOU  P,TOP,dGCDATA  % LINK(TOP) <- AVAIL
        STCO  0,P,dGCDATA    % LINK(AVAIL) <- NULL
G3      SET   P,TOP          % G3. Pop up stack, P <- TOP
        LDOU  TOP,P,dGCDATA  % TOP <- LINK(TOP)
        BZ    TOP,G5           % all marked, go to next phase
G4      LDTU  k,P,dT         % G4. Put new links on stack. k <- T(P)
        ADD   pLINK,P,8*1    % start pointing just before LINKs
1H      BZ    k,G3           % k=0? ie all LINKs of P processed? next P
        INCL  pLINK,8*1
        SUB   k,k,1
        LDOU  Q,pLINK
        BZ    Q,1B           % Q=0, no process
        LDOU  marked,Q,dGCDATA
        BNZ   marked,1B      % LINK points to already stacked node
        STOU  TOP,Q,dGCDATA  % GCLINK(Q) <- TOP
        SET   TOP,Q          % TOP <- Q
        JMP   1B
        
        % Visitor Coroutine for Test
        % At this point, reachable nodes are marked
G5      GO :a,:b,0
        % End of Visitor Coroutine
        
        % At the end of the previous phase, P = AVAIL
        
        SET   Q,:BASE
        STCO  0,P            % SIZE(AVAIL) <- 0, sentinel
        STOU  Q,P,dGCDATA    % LINK(AVAIL) <- STACK BASE
        SET   P,:BASE
        JMP   G6
1H      STOU  Q,P,dGCDATA    % P is marked for collection
        8ADDU Q,size,Q       % update simulated compaction marker
        8ADDU P,size,P       % move to next node
G6      LDOU  marked,P,dGCDATA
G6A     LDTU  size,P,dSIZE
        BZ    marked,G7      % P is not marked for collection
        BNZ   size,1B        % sentinel not reached
        
        % Visitor Coroutine for Test
        % At this point, marked nodes have new compaction addresses
        % Unmarked nodes have been compacted
        GO :a,:b,0
        % End of Visitor Coroutine
        
                                % G8. Translate all links
G8      LDOU  :USE,:USE,dGCDATA % update USE to its new address
        SET   :AVAIL,Q          % AVAIL <- Q
        SET   P,:BASE           % P <- BASE
        JMP   G8P
        
1H      LDTU  t,t,dSIZE
        ADD   size,size,t
G7      SET   t,P            % G7. Collapse available areas
        8ADDU t,size,t       % next node
        LDOU  marked,t,dGCDATA
        BZ    marked,1B      % the node is not marked, collapse it
        STTU  size,P,dSIZE   % finalize the collapsed node
        8ADDU P,size,P       % to the next node
        JMP   G6A
  
2H      SUB   k,k,1          % k--
        INCL  pLINK,8        % point to next LINK
        LDOU  Q,pLINK
        LDOU  Q,Q,dGCDATA
        STOU  Q,pLINK        % LINK(Q) <- LINK(LINK(Q))
1H      BNZ   k,2B           % Jump if k != 0
3H      8ADDU P,size,P       % next node
G8P     LDOU  marked,P,dGCDATA
        LDTU  size,P,dSIZE
        BZ    marked,3B      % only translate links of marked nodes
        LDTU  k,P,dT
        ADDU  pLINK,P,8      % prepare to point to the LINKs
        BNZ   size,1B        % sentinel reached
        
        % Visitor Coroutine for Test
        % At this point, all marked nodes have their LINKs updated
        GO :a,:b,0
        % End of Visitor Coroutine
        
                             % G9. Move nodes
G9      SET   P,:BASE        % P will point to node to move
        SET   TOP,:BASE      % TOP will point to location to copy P
        JMP   G9P
1H      STCO  0,P,dGCDATA    % GCDATA(P) restored to NULL
2H      SUB   size,size,1    % copy octas of P
        LDOU  t,P
        STOU  t,TOP
        INCL  TOP,8
        INCL  P,8
        BNZ   size,2B
        JMP   G9P
3H      8ADDU P,size,P       % move to next node
G9P     LDOU  marked,P,dGCDATA
        LDTU  size,P,dSIZE
        BZ    marked,3B      % ignore unmarked nodes
        BNZ   size,1B        % sentinel reached
        
EXIT    POP 0,0
        
        PREFIX :