:IF[WithGarbCollect]; ******************************
TITLE[CedarGC];
%
Ed Fiala 11 May 1982: Make change to GetRefType trying to avoid bug.
Ed Fiala 22 April 1982: Add GetRefType and GetCRefType opcodes; fix
bug in CreateRef change; fix bug in AssignRef not preserving OnStack when
RefCnt .le. RCFinalize; while doing this, speed up AssignRef and CreateRef
slightly; make AssignRefNew same as AssignRef; speed up ReclaimRef by
6 cycles; bum many mi.
Ed Fiala 24 February 1982: Change error check in CreateRef to crash
only if RefCnt in existing entry .ne. value CreateRef would have put
there. If RefCounting disabled in gcRCEMask and if gcProcNo .ne. 0,
then trap on AssignRef, AssignRefNew, and CreateRef with TrapParm .eq. 2.
If ref counting disabled and gcProcNo .eq. 0 then CreateRef = Noop and
AssignRef and AssignRefNew = store 2 words. Fix page fault problem in
AssignRef by doing NIL store after refOld update and by writing the new
value after refNew update. Add RCeqRCFinalize counter. Fix tasking after
gcFind calls in ReclaimRef and AssignRef. Change UVersion to 13b.
Ed Fiala 8 October 1981: Create from Dorado implementation.
1) Modify ReclaimAll to use 128d-entry table so one call exhausts a PI.
2) Add ReclaimRef opcode replacing unusual AlterCount used previously.
Change AlterCount to never return a value and to manipulate OnStack and
RefCnt fields in a consistent way for all calls.
3) Eliminate RCEReclaim (An appropriate AlterCount is equivalent).
4) Rearrange data structure so that a single base register suffices;
change word allignment for the Dolphin.
5) Use odd word of last OT cell in a chain for RCE.
6) Reverse args for CreateRef.
7) Thread free list through even words of OT cells (Must terminate with 0).
8) Change in the Collector process wakeup algorithm.
9) Require Ref’s to be even; change hashing algorithm and RCE format.
10) Restrict NPR < RCFinalize and RCFinalize=(2↑n)-1.

The collector stores RCEs for Refs; an RCE newly-created by CreateRef is
entered with RefCnt .eq. RCFinalize-NPR (NPR = no. package references, an
argument .le. 2); as each new pointer to the Ref is created by AssignRef,
RefCnt is increased by 1, up to 127d. An RCE attaining RefCnt=127d freezes
at that value, becoming uncollectable. As Refs are dereferenced (by
AssignRef, ReclaimRef, and AlterCount), RefCnt is reduced by 1. The
Collector will examine RCEs with RefCnt .le. RCFinalize.

To reduce table size, RCEs with RefCnt=RCFinalize+1 (the most common case)
are not kept in the table (unless the OnStack bit is also 1); this is
accomplished by the following algorithm:

Add 1Sub 1
127dRemains 127d.127dRemains 127d.
RCFinalizeIf OnStack=0, destroy0Crash--bug.
RCE; elseRCFinalize+2If OnStack=0, destroy
RefCnt ← RefCnt+1.RCE; else
otherRefCnt ← RefCnt+1.RefCnt ← RefCnt-1.
no entryCreate with RefCntotherRefCnt ← RefCnt-1.
.eq. RCFinalize+2no entryCreate with RefCnt=
and OnStack=0RCFinalize, OnStack=
(rcMask & OnStack).

The collector uses a contiguous 64k-aligned block of storage. The GC base
register points at its origin and all pointers in the hash table (HT) and
overflow table (OT) are relative to GC. Words of interest are as follows:

0gcFLdisplacement to 1st cell on free list
1gcFLCount
biased count of OT free list cells; trap when an OT cell is
needed and gcFLCount .le. 0 unless collector is running.
2gcRCEMask
00 if ref-counting allowed; 1 if ref-counting disabled
1:7RCEMask (always 177b)
8dOnStack (0 normally, 1 during a collection)
9:15dzeroes
3gcProcNo
Collector process id (.eq. 0 when collector not running)
4- 5LP to table indexed by Ref rsh 10d containing zone (.ge 0)
or zone index (.ls. 0).??
6- 7LP to table describing zones by subzones
10- 11LP to table indexed by zone index containing LP to zone
12- 13LP to table indexed by type containing LP to canonical type
14- 15Count of HT or OT entries with RefCnt .eq. RCFinalize.
16- 131unused
132- 177Optional counters (defined for Mesa debugger prettyprint--
these counts don’t necessarily occur) defined later.
200- 377table for entries with RefCnt<=RCFinalize on ReclaimAll
400-100377HT (hash table--1 word/cell)
100400-177777OT (overflow table--2 words/cell, length determined by
software)

gcFL and gcFLCount are initialized by the GCSetup opcode and are then handled
only by opcodes in this module--this allows both words to be cached in
registers. gcRCEMask, gcProcNo, and optional counters may also be cached in
registers--software must execute another GCSetup opcode after one of these
registers changes before and after a collection. The switch argument to
GCSetup determines whether or not gcFL, gcFLCount, and optional counters are
being loaded from storage on initialization or being stored back into storage
prior to examination by software.

An RCE is accessed by hashing a 22-bit Ref into a 15-bit probe index (PI) and
6-bit residue (R). PI is bits 10:15d xor bits 16:30d; R = bits 10:15d; PI
indexes HT, formatted as follows: A one-long chain is contained within the
HT cell; otherwise, HT points to an OT cell containing a RCE in the 1st word
and either a RCE or a pointer to another OT cell in the 2nd word. Every word
in HT or OT has the following form:
If bit 0 is 0, the word is a RCE:
1:7RefCnt
8OnStack
9:15Residue (allows one extra bit)
else if bit 0 is 1, the word is a pointer or empty:
0:15dindex of next OT cell in chain (always even);
-1 denotes an empty entry (HT only--illegal in OT)

The 1st word of an OT cell is NEVER a pointer and the 2nd word is NEVER empty.
In other words, a NIL pointer or empty word is disallowed since the chain can
be collapsed in this case.

The free list pointed to by gcFL threads through even words of OT cells and
is terminated by a 0 (odd word values are ’don’t care’). gcFLCount is
initialized to the number of cells on the free list minus a parameter. Any
process which tries to create a new cell and finds gcFLCount .le. 0 will trap
unless the process is the Collector. Software then wakes the Collector and
blocks. The Collector process can acquire OT cells until the free list is
entirely exhausted (denoted by a 0 pointer in gcFL).

Initially the Collector is quiescent and OnStack bits in RCE’s are all 0;
clients set OnStack=0 on every operation. When a collection starts, the
Collector sets OnStack=1 in gcRCEMask and executes another GCSetup to transmit
the gcRCEMask change to microcode. The only operations affected by OnStack
in gcRCEMask are CreateRef and AssignRef, which sets OnStack=1 when
decrementing RefCnt as described earlier.

The Collector uses AlterCount to mark RCEs with OnStack=1 for all double
words on process stacks; a pointer with no HT/OT entry is entered with
RefCnt=RCFinalize+1 and OnStack=1. If the conservative algorithm creates some
RCEs for non-Ref doublewords, no great harm is done because those RCEs will
be discarded after collection, and CreateRef can cope with such an extraneous
RCE that happens to match a Ref being created.

RCEs with RefCnt<=RCFinalize and OnStack=0 are enumerated by ReclaimAll. For
each of these, software determines whether reclaim is possible; if so,
ReclaimRef is used on Refs inside the object, and any of these having its
RefCnt decremented to RCFinalize is handled in the same way as those
enumerated by ReclaimAll (If RefCnt for one of these was already .le.
RCFinalize, then ReclaimAll already enumerated or will enumerate it, so no
futher action is necessary).

When done, the collector sets OnStack mode for client processes to normal
again and uses ResetOnStack to sweep HT/OT clearing OnStack bits and
release RCEs with RefCnt=RCFinalize+1.

NOTES:
1) Opcodes that call gcFind and the *RefType opcodes may trap with TrapParm=1;
CreateRef, and AssignRef map trap with TrapParm=2. The first is for a
collector wakeup; the second is because the trace and sweep is running and
wants the world to be stable.
2) Page 0 of GC must be locked down for statistics counters and GCSetup.
3) Software should check for RefCnt=0 in the RCEs returned by ReclaimAll
and flag a bug if this ever happens (Microcode checks for RefCnt going below
0, but exactly 0 check is too expensive).

Possible Changes or problems:
1) Change some opcode from Esc to regular after AssignRefNew eliminated.
2) Use 8 unused bits in GChi and/or the wasted bit in gcFL to indicate
"collector off" and "collection in progress" eliminating gcRCEMask; then
need only one more permanent register for gcProcNo.
3) Permanent register for RCeqRCFinalize.
4) Gather precisely those stats needed to decide when to collect.
5) Disallowing RCE’s for Ref’s .ls. 64k saves 2 cycles per gcFind call.
6) Consider RCE-to-Ref opcode.
7) Consider swapping the collector microcode (ReclaimRef, AlterCount,
ReclaimAll, ResetOnStack).
%

RV2[GC,GChi,64];*Permanent base register
RV2[gcFL,gcFLCount,24];*permanent free list pointer and count

*General temporaries
*RTemp (RM 52) holds alpha and must be preserved until trap is impossible.
RV2[gcRCEMask,gcProcNo,44];
RV2[gcStat0,gcStat1,46];
RV2[gcCAR,gcCDR,70];*gcCDR is used for HT cells and odd words in OT
*cells, gcCAR for even words in OT cells.

*LP and LPhi (RM 66 & 67) are used by @AssignRef.
*RM 53 and 56-57 are for sure available here (maybe others).
RV2[gcRef0,gcResidue,72];*For @AssignRef; gcResidue for gcFind
RV[gcReturnPC,72];*For gcFind
RV2[gcCADR,gcCDDR,72];*For @ResetOnStack
RV[gcRecIndex,72];*For @ReclaimAll
RV[gcRAVal,73];*For @ReclaimAll
RV[gcPred,50];*For gcFind, @ResetOnStack
RV[gcNewCell,51];*For gcFind

MC[OnStack,200];
Set[RCFinalize,3];
MC[RCFinalizePlus1,4];
MC[RCFinalizePlus1LSh1,10];

*Displacements in GC structure
Set[QMap,4];*Long pointer to quantum map; word 0 is nentries
*(always 4096d); one-word entry contains 14d-bit
*type if bit 0 is 0 else 15d-bit zone).
Set[SubZMap,6];*Long pointer to subzone map; word 0 is nentries;
*entries are long pointers to zones.
*Word 0 of a zone is its type.
Set[CMap,12];*Long pointer to ? table indexed by type. Word 0
*is nentries; words 1-2, 3-4, etc. are long pointers
*to the word containing the canonical type.
MC[ReclaimOffset,200];*0th word of 200b-word Reclaim table
MC[HTOffset,400];
MC[HTLength,100000];**Branch conditions "know" this value.
MC[OTOffset,100400];

MC[sCatastrophe,171];
MC[OTCarNotEntry,0];*Even word of OT cell not a RCE (.ls. 0)
MC[BadOTPointer,1];*Pointer in HT or OT .ls. OTOffset
MC[RefNotEven,2];*Ref arg not even
MC[BadCreate,3];*CreateRef on already-existing RCE with OnStack=0
MC[RCBelowZero,4];*Attempt to make RefCnt<0
*Codes 6 reported by Dorado microcode.
MC[BadMapIndex,7];*Table index .gr. word 0 of the table
MC[ReferentOnFL,10];
MC[BadFLPointer1,11];*Pointer from free list odd
MC[BadFLPointer2,12];*Pointer from free list .ls. 100400b.
MC[DelBadPtr,13];*Pointer added to FL not even or .ls. 100400b
MC[BadPackRefCnt,14];*Package reference count not in range 0 to 2.
* MC[BadHTE,15];*HT entry .ls. 0, odd, and .ne. -1

MC[UVersion,13];*Must agree with declaration in AllocRC.Mesa

*Also have 10b mi on opPage0 and 2b mi on xfPage1
Set[gcPage,2];*341b mi (+26b mi if gcStats=1)
Loca[MiscDisp4,gcPage,40];
*1-5, 10-15, 21-23, 25-30, and 32-34 are used in FindRetTab
Loca[FindRetTab,gcPage,0];
Set[gcPage2,2];*1b mi
Set[gcPage3,2];*1b mi
Set[gcPage4,10];*154b mi (+10b mi if gcStats=1) must have refill


%To look at the GC structure with the Mesa debugger:
Set Root Configuration RT
Set Module Context RTRefCountsImpl
GCState↑looks at first 400b words of GC
MapPiRce[n]looks at HT entry n
MapOiOe[m]looks at OT entry m

The constants below are offsets from GC to double-precision event counters
that are implemented if gcStats=1.

Number of existing Refs is CRCtr-RRDelCtr+ACSubCtr-ACAddCtr.
Number of Refs freed is ACAddCtr+RRDelCtr (i.e., ACAddCtr counts Refs
delivered by ReclaimAll that are freed and RRDelCtr counts the number
threading from those which are freed).

One proposed algorithm for deciding when to do a collection needs the best
guess possible for the amount of storage reclaimable by a collection.
An estimate for this quantity can be made by estimating:
(1) No. Refs enumerated by ReclaimAll that will be freed;
(2) The expected number of Refs reclaimed for each of the ones enumerated;
(3) The expected size of each item reclaimed.
(1) can be approximated by the number of Refs with RefCnt=RCFinalize; the
error in this approximation is ones that are OnStack plus (?) ones that have
experienced finalization. ACAddCtr+RRDelCtr/ACAddCtr approximates (2) by its
historical average. (3) can be estimated either by tracking block size and
number of frees in previous collections or by tracking storage allocated
since the last collection.

RCeqRCFinalize is used algorithmically (therefor not optional).

ACZeroCtr, ACSubCtr, ACAddCtr, OTDelCtr, OTCreCtr, HTDelCtr, HTCreCtr are
displayed by software as of 18 February 1982, but not used algorithmically
(therefor can change or deimplement). Dorado has the AC*Ctrs used for
all gcFind calls not just AlterCount calls.
%
MC[RCeqRCFinalize,14];*HT/OT entries with RefCnt .eq. RCFinalize.

Set[gcStats,1];*Enables optional event counters enumerated below


*Numbers in () are for an early run of a Poplar test program.
MC[FreeQCtr,114];*() FreeQuantized completions
MC[FreeHCtr,116];*() FreeHeap completions
MC[FreeObjCtr,120];*() FreeObject completions
MC[AllocQCtr,122];*() Allocate Quantized completions
MC[AllocHCtr,124];*() Allocate Heap completions
MC[RefTypeCtr,126];*() RefType completions
MC[CRefTypeCtr,130];*() CRefType completions
MC[ACIllCtr,132];*( 9394) AlterCount calls with NIL or odd Ref arg.
MC[ACZeroCtr,134];*( 37957) AlterCount completions not changing RefCnt
*(must be setting OnStack=1).
MC[ACSubCtr,136];*( 0) AlterCount completions subtracting from
*RefCnt (must be fixing RefCnt for a ReclaimRef which
*found no RCE but had finalization).
MC[ACAddCtr,140];**( 81656) AlterCount completions adding to RefCnt (must be
*flushing RCE delivered by ReclaimAll).
MC[OTDelCtr,142];*( 25107) OT cell deletions
MC[OTCreCtr,144];*( 25223) OT cell creations
MC[HTDelCtr,146];**(404897) HT deletions
MC[HTCreCtr,150];**(420811) HT creations
MC[RRNilCtr,152];*( 0) ReclaimRef completions with NIL arg
MC[RRNoDelCtr,154];*( 192353) ReclaimRef completions (not deleted)
MC[RRDelCtr,156];**(259909) ReclaimRef completions (already deleted)
MC[RACtr,162];*( 123) ReclaimAll completions
MC[CRCtr,164];*( 351059) CreateRef completions
MC[ARCtr,166];*(1047322) AssignRef completions refNew non-NIL
* (not including those with the collector disabled).
*MC[ARNCtr,170];*Deimplemented
MC[RONilCtr,172];*( 737678) RefOld=NIL in AssignRef (+ page fault restarts
*and collector disabled AssignRefs as an error term)
MC[RNNilCtr,174];*( 272916) AssignRef completions with RefNew=NIL
*MC[ROeqRNCtr,176];*RefOld=RefNew in AssignRef

gcRefill:
PFetch4[PCB,IBuf,4], GoToP[MesaRefill], At[LShift[gcPage,10],377];

gcCount:
PFetch2[GC,gcStat0];
gcCount1:
gcStat0 ← (gcStat0) + 1;
gcStat1 ← (gcStat1) + 1, UseCOutAsCIn;
PStore2[GC,gcStat0], GoTo[gcRet];

gcUnimp:
TrapParm ← 0C, GoToP[UndefTrap];

*Jump here when data structure is found to be inconsistent.
gcBug:StkP ← RZero;*For Midas breakpoint
LoadPage[opPage3];
T ← sCatastrophe, GoToP[kfcr];

*Jump here from @ReclaimRef, @ReclaimAll
gcPushTTail:
LU ← NextInst[IBuf];*Odd placement; paired with gcRAInt-1
gcPushTTailx:
Stack&+1 ← T, NIRet;

%Misc dispatch. Timing = 18.5 cycles (including buffer refill) to the 1st
working mi for the opcode.
T ← CNextData[IBuf], Call[.+2], Opcode[364];
LU ← NextInst[IBuf], Call[P7Tailx];
RTemp ← T, LoadPage[xfPage1], Skip[H2Bit8’];
TrapParm ← 0C, GoToP[MiscUnimp];
Dispatch[RTemp,11,3], GoToP[.+1];
Dispatch[RTemp,14,4], Disp[.+1];
...
%
T ← (R400) + T, LoadPage[gcPage], At[MiscDisp0,3];
Dispatch[RTemp,14,4], RTemp ← T, NoRegILockOK;
OnPage[gcPage];
Disp[@ReclaimRef];

@Esc66:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,6];
@Esc70:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,10];

:IF[gcStats]; **************************************
gcUnimpCount:
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[opPage0], GoTo[gcUnimp];

@Esc73:T ← AllocQCtr, GoTo[gcUnimpCount], At[MiscDisp4,13];*AllocQuantized
@Esc74:T ← AllocHCtr, GoTo[gcUnimpCount], At[MiscDisp4,14];*AllocHeap
@Esc75:T ← FreeObjCtr, GoTo[gcUnimpCount], At[MiscDisp4,15];*FreeObject
@Esc76:T ← FreeQCtr, GoTo[gcUnimpCount], At[MiscDisp4,16];*FreeQuantized
@Esc77:T ← FreeHCtr, GoTo[gcUnimpCount], At[MiscDisp4,17];*FreePrefixed
:ELSE; *********************************************
@Esc73:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,13];*AllocQuantized
@Esc74:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,14];*AllocHeap
@Esc75:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,15];*FreeObject
@Esc76:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,16];*FreeQuantized
@Esc77:LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,17];*FreePrefixed
:ENDIF; ********************************************

%gcDelChk is called with the results of gcFind to store the RCE or flush
it if RefCnt=RCFinalize+1 and OnStack=0. Have pointer to predecessor in
gcPred, pointer to word holding RCE in MNBR, and other word from OT cell
(if from OT) in gcCDR. No references here can be illegal or fault.
gcDelChk is the entry for AlterCount; gcDelChk0 for ReclaimRef, AlterCount,
and AssignRef; gcPreserve for CreateRef and AssignRef; gcDelete for
AssignRef. T contains (RCFinalize+1) lshift 1 at gcDelChk.

Timing: 22 (5 free) if not deleting RCE and RefCnt .ne. RCFinalize,
50 (13 free) if RefCnt .eq. RCFinalize,
25 (14 free) if deleting HT entry, or
43 (14 free) if deleting CDR[OT] or CAR[OT].
"5 free" etc. indicates the dead time of the final PStore reference.
Although these times are long, the references can’t page fault, so the
tasking behavior may be marginally acceptable.
%
gcDelChk:*Check OnStack=0 & RefCnt=RCFinalize+1
LU ← (LdF[gcCAR,0,11]) - T;
gcDelChk0:
T ← MNBR, GoTo[gcDelete,ALU=0];
gcPreserve:
PStore1[GC,gcCAR];*Fixup RCE
T ← (gcCAR) xor (LShift[RCFinalize,10]C), Skip[R>=0];
TrapParm ← RCBelowZero, CallX[gcBug];
LU ← (R400) - T - 1;
Skip[ALU<0];
T ← RCeqRCFinalize, GoTo[gcCount];
gcRet:Return;

gcDelete:
LU ← (gcPred) xor T;*Flush the entry
T ← gcPred, GoTo[gcDelOT,ALU#0];
:IF[gcStats]; **************************************
PStore1[GC,AllOnes];*Delete from HT
T ← HTDelCtr, GoTo[gcCount];
:ELSE; *********************************************
PStore1[GC,AllOnes], Return;*Delete from HT
:ENDIF; ********************************************
gcDelOT:
PStore1[GC,gcCDR];*Delete from OT: copy gcCDR into predecessor.
gcCollectMNBR:*Only 1 entry here (from @ResetOnStack)
T ← gcFL;
gcCollectCAR:*Only 1 entry here (from @ResetOnStack)
gcNewCell ← T;
T ← 1C;
T ← (MNBR) and not T, Skip[R<0];
TrapParm ← DelBadPtr, CallX[gcBug];
gcCollectAny:
gcFLCount ← (gcFLCount) + 1;
gcFL ← T;
:IF[gcStats]; **************************************
PStore1[GC,gcNewCell];
T ← OTDelCtr, GoTo[gcCount];
:ELSE; *********************************************
PStore1[GC,gcNewCell], Return;
:ENDIF; ********************************************

*gcCDR even, .ls. 0 checks here would be redundant
gcCollectCDR:*Only 1 entry here (from @ResetOnStack)
T ← gcCDR, GoTo[gcCollectAny];

%gcResidue holds R and T holds the PI for an entry to be looked up; an
absent entry (RefCnt .eq. RCFinalize+1) is recreated with OnStack=0 except
when the calling mi is at an even location (only ReclaimRef has its call on
an even location); for ReclaimRef, exit with StkP advanced by 1.
Return pointer to the predecessor in gcPred, pointer to the RCE in MNBR,
and the RCE in gcCAR; gcCDR contains the other word if the RCE came from
an OT cell. The three cases are:
1) gcPred .eq. MNBR (entry is in HT);
2) gcPred .ne. MNBR and MNBR odd (entry is in odd word of OT cell);
3) gcPred .ne. MNBR and MNBR even (entry is in even word of OT cell).

Caller must have fetched gcProcNo before the call (except on ReclaimRef) and
must store gcCAR into the word pointed at by MNBR after the return. gcCDR
holds the other word of the OT cell so that gcDelChk can flush the RCE
faster later.

Caller will modify gcCAR and then call gcDelChk to store back the results.
The caller must task before calling gcDelChk because at exit from gcFind
the time since last task may be over 20 cycles.

Timing:28 cycles (31 for @ReclaimRef) not found in empty chain
66 (10 free) cycles (28 for @ReclaimRef) not found in one-long chain
92 (10 free) (54 for @ReclaimRef) + 24*N cycles not found in OT chain
*Longer times when found occur for RefCnt .eq. RCFinalize
(31 or 61 (10 free)) cycles found in one-long chain
(48 or 78 (10 free)) + 24*N cycles found in CAR of OT chain
(63 or 93 (10 free)) + 24*N cycles found in CDR of OT chain
where N is the number of OT cells preceding the one in which match occurs
or preceding the last cell in the chain if no match. "14 free" means that
the next 14 cycles are during the dead time of a memory reference.
+ 9 cycles if not found during a collection when gcFLCount .ls. 0
%
gcRefUneven:
TrapParm ← RefNotEven, CallX[gcBug];*Odd placement
gcFind:T ← (R400) + T, LoadPage[gcPage4];*Know HTOffset=400b
PFetch1[GC,gcCDR];*Fetch HT entry
OnPage[gcPage4];
gcPred ← T, UseCTask;*Bypass kludge ok since GC=0
T ← APCTask&APC, Task;
gcReturnPC ← T;
MNBR ← gcPred, Task;
T ← gcResidue;
LU ← (LdF[gcCDR,11,7]) xor T, GoTo[gcFindIndEmpty,R<0];
*A single entry is in gcCDR and its residue in T--check for match.
T ← gcCDR, GoTo[gcFindNM,ALU#0];
*Match.
gcCAR ← T;
%Reduce the count of RCE’s with RefCnt .eq. RCFinalize, whenever gcFind
returns such an entry. Caller must call gcDelChk, which increments
the count if the value stored back has REfCnt .eq. RCFinalize.
%
gcRCFinalizeCount:
T ← (gcCAR) xor (LShift[RCFinalize,10]C);
LU ← (R400) - T - 1, Call[gcRCF1];
gcStat0 ← (gcStat0) - 1;*Single precision since GC 64k words
PStore1[GC,gcStat0,RCeqRCFinalize!], GoTo[gcFExit];

gcRCF1:APCTask&APC ← gcReturnPC, GoTo[gcFRet,ALU<0];
PFetch1[GC,gcStat0,RCeqRCFinalize!], GoTo[gcFRet];

:IF[gcStats]; **************************************
gcFindLogHT:
gcReturnPC, LoadPage[gcPage], Skip[R Odd];
T ← HTCreCtr, GoToP[gcCount];
gcFindRRLog:
T ← RRDelCtr, GoToP[gcCount];
:ENDIF; *******************************************

%Entry not found and one or more other RCE’s at the HT chain where it would
be. Recreate it using a cell from the free list; however, trap if
gcFLCount .le. 0 so that software can wake up the collector process.
The previous final list element is put in the odd word of the new cell and
the new entry in the even word; the predecessor is replaced by a pointer to
the new cell.
Timing from gcFind to here: 21 from HT, 47 + 24*N from OT.
%
gcFindNM:
gcReturnPC, GoTo[gcFindNotRR,R Even];
*gcFind called by @ReclaimRef; finish up and exit.
:IF[gcStats]; **************************************
LoadPage[gcPage], Call[gcFindRRLog];
:ENDIF; ********************************************
LU ← NextInst[IBuf];
gcFindPushTailx:
Stack&+1, NIRet;
gcFindNotRR:
T ← MNBR ← gcFL, Skip[R Even];
TrapParm ← BadFLPointer1, CallX[gcFBug];
*The PFetch1 to advance the free list unfortunately has to be before all
*three references below because of a possible page fault.
*Extra ref at end of free list must not (and won’t) fault because the free
*list is terminated with 0.
PFetch1[GC,gcFL], FreezeResult, GoTo[gcFindNM1,ALU<0];
LU ← gcFL, GoTo[gcOTEmpty,ALU=0];*Totally out of free OT cells
TrapParm ← BadFLPointer2, CallX[gcFBug];
gcFindNM1:
gcNewCell ← T;*Bypass kludge ok since GC=0
*Store 2nd word of new cell (gcCDR). Storing gcCAR is unnecessary because
*the caller always changes it and stores it. PStore1 below will page fault
*whenever the PFetch1 above faults.
T ← (MNBR) + 1;
PStore1[GC,gcCDR];
T ← (gcResidue) + (LShift[RCFinalizePlus1!,10]C), Call[gcTtoCAR];
*Trap to software if no freelist entries are left during a collection
*(indicated by a 0 in gcFL) or if gcFLCount .ls. 0 otherwise--gcFLCount is
*biased.
gcFLCount ← (gcFLCount) - 1, Skip[R<0];
T ← gcPred, GoTo[gcFindNMGo];
*Allow GC process to go ahead when count runs out; trap others.
T ← prCurrentPsb, Call[gcFRet];
LU ← (gcProcNo) xor T;
T ← gcPred, GoTo[gcFindNMGo,ALU=0];
*Fix gcFL, gcFLCount, and StkP prior to trap
gcFLCount ← (gcFLCount) + 1;
T ← MNBR;
gcOTEmpty:*Jump here from above when FL totally exhausted.
gcFL ← T;
gcWakeCollectorTrap:
T ← SStkP;*Restore StkP before trap
gcResidue ← T, LoadPage[opPage0];
StkP ← gcResidue;
OnPage[opPage0];
TrapParm ← 1C, GoTo[UndefTrap];
OnPage[gcPage4];
*Store pointer to OT cell in predecessor
*Returns to caller 21 (10 free) cycles from last task.
gcFindNMGo:
PStore1[GC,gcNewCell];
:IF[gcStats]; **************************************
LoadPage[gcPage];
T ← OTCreCtr, Call[gcCount];
:ENDIF; ********************************************
gcFExit:
APCTask&APC ← gcReturnPC, GoTo[gcFRet];

*19 cycles from gcFind to here.
gcFindIndEmpty:
T ← gcCDR, GoTo[gcFindI1,R Even];
*HT cell was empty.
:IF[gcStats]; **************************************
Call[gcFindLogHT];
:ENDIF; ********************************************
T ← (gcResidue) + (LShift[RCFinalizePlus1!,10]C);
*Return to caller 12 cycles from last task.
APCTask&APC ← gcReturnPC, Skip[R Even];
*gcFind called by @ReclaimRef--adjust StkP and exit
LU ← NextInst[IBuf], CallX[gcFindPushTailx];
*Other gcFind calls return result in gcCAR--do not have to store gcCAR
*because caller will do it.
gcTtoCAR:
gcCAR ← T, Return;

gcFindInd:
T ← gcCDR, Skip[R Even];*Even placement
TrapParm ← BadOTPointer, CallX[gcFBug];
*Fetch OT cell into gcCAR/gcCDR
PFetch2[GC,gcCAR];*Bypass kludge OK since GC=0
*Next 3 mi do gcPred←MNBR+1, MNBR←T.
gcPred ← T, Task;
T ← (MNBR) + 1;
MNBR ← gcPred, gcPred ← T, NoRegILockOK, GoTo[gcFindI2];

*Jump here with the HT word in T known to point at an OT cell.
gcFindI1:
PFetch2[GC,gcCAR];*HT cell was indirect
gcNewCell ← T, Task;
MNBR ← gcNewCell;
gcFindI2:
T ← gcResidue, Call[gcFindI3];
MNBR ← gcCDR, gcCDR ← T, NoRegILockOK, Call[gcMNBRToT];
*APCTask&APC ← gcReturnPC; MNBR ← gcCAR, gcCAR ← T, NoRegILockOK, Return;
*Done. Match in gcCDR.
MNBR ← gcCAR, gcCAR ← T, NoRegILockOK, GoTo[gcRCFinalizeCount];

gcFindI3:
LU ← (LdF[gcCAR,11,7]) xor T, Skip[R>=0];
TrapParm ← OTCarNotEntry, CallX[gcFBug];
*APCTask&APC ← gcReturnPC, GoTo[gcFRet,ALU=0];
GoTo[gcRCFinalizeCount,ALU=0];*Done if match in gcCAR.
*Even word of OT cell doesn’t match, check odd word.
LU ← (LdF[gcCDR,11,7]) xor T, GoTo[gcFindInd,R<0];
T ← (MNBR) + 1, Skip[ALU=0];
*No match in OT cell. Put new entry in even word of cell from free list.
gcPred ← T, GoTo[gcFindNM];
*Match in odd word of OT cell.
*Next six mi do: MNBR←MNBR+1, Exchange(gcCDR,gcCAR)
MNBR ← gcCAR, gcCAR ← T, NoRegILockOK;
gcMNBRToT:
T ← MNBR, Return;

gcFBug:LoadPage[gcPage];
GoToP[gcBug];

gcFRet:*Even; paired with gcFindI3+3
Return;

%ReclaimRef is called with a Ref at TOS,,2OS. If an RCE for the Ref is in
HT/OT, it subtracts 1 from RefCnt and returns NIL; if no RCE exists
(indicating RefCnt=RCFinalize+1 & OnStack=0), it returns the Ref unchanged.
ReclaimRef is used by the Collector for each Ref within a reclaimed object.
Since RCEs which already had RefCnt .le. RCFinalize & OnStack=0 were (or will
be) enumerated by ReclaimAll or by an earlier ReclaimRef, only those being
decremented from RCFinalize+1 to RCFinalize need be reported. NOTE: a new
RCE is NOT created--the collector must subsequently do an AlterCount -1 to
fixup RefCnt if it doesn’t collect the item.

Timing from @ReclaimRef to exit: 33+gcFind if gcFind returns (i.e., if the
Ref cannot be reclaimed) or 7+gcFind if gcFind exits (i.e., if RefCnt=1
and OnStack=0 so that the Ref can be reclaimed).
%
@ReclaimRef:*NOTE: gcFL quadword not needed here.
T ← LdF[Stack&-1,12,6], At[MiscDisp4,0];*Alpha = 60b
%This call to gcFind does not want a new RCE made if one doesn’t exist.
Allow this distinction to be made easily in gcFind by even placement of this
call, odd placement of others. gcFind returns iff RCE exists; otherwise,
it advances StkP by 1 and exits.
%
LU ← (Stack) or T, Call[gcRR1], At[FindRetTab,32];
*A match--no change if RefCnt=127d, else update RCE; note that RCE will
*never be deleted here.
LU ← (gcCAR) + (LShift[1,10]C);
gcCAR ← (gcCAR) - (LShift[1,10]C), Skip[ALU<0];
T ← MNBR, Call[gcPreserve];
*Returns NIL whenever gcFind returns
:IF[gcStats]; **************************************
T ← RRNoDelCtr;
gcRRNilLog:
PFetch2[GC,gcStat0], Call[gcCount1];
:ENDIF; ********************************************
T ← Stack ← 0C, GoTo[gcPushTTail];

gcRR1:gcResidue ← T, Skip[ALU=0];*NIL check
T ← (RSh[Stack,1]) xor T, DblGoTo[gcFind,gcRefUneven,R Even];
:IF[gcStats]; **************************************
*Returns NIL if Ref = nil
T ← RRNilCtr, GoTo[gcRRNilLog];
:ELSE; *********************************************
*Returns NIL if Ref = nil
LU ← NextInst[IBuf], CallX[gcPushTTailx];
:ENDIF; ********************************************

%AlterCount accepts a Ref at TOS,,2OS and an RCE modifier at 3OS. The RefCnt
field in 3OS is treated as a twos-complement value added to the RCE for the
Ref; the OnStack field in 3OS is OR’ed into the RCE. In other words, OnStack
is conditionally set to 1. Returns nothing.

We anticipate AlterCount will be used only by the Collector process and only
in the following situations:
(1) At onset of a collection to set OnStack=1 for pointers in local frames
and process evaluation stacks. Conservative algorithm may use bogus Refs
during this phase.
(2) To reenter a RCE found absent by ReclaimRef that cannot be reclaimed
because it has finalization (Subtract 1 from RefCnt).
(3) To destroy a Ref whose RCE was returned by ReclaimAll (Add n to RefCnt).
(4) By the trace and sweep collector to rebuild HT/OT??

Timing from @AlterCount to exit: gcFind + gcDelChk + (28 or 36) cycles.
%
@AlterCount:
PFetch1[GC,gcProcNo,3], At[MiscDisp4,1];*Alpha = 61b
*Clear garbage bits in high word
T ← LdF[Stack&-1,12,6];
*Convert operation to NOP if the Ref is NIL or if the Ref is illegally ODD.
*This allows conservative stack-scanning to pass arguments unchecked.
LU ← (Stack) or T, GoTo[gcAC3,R Even];
:IF[gcStats]; **************************************
gcAC4: T ← ACIllCtr, Call[gcCount];
LU ← NextInst[IBuf], CallX[gcPop2Tailx];
gcAC3:gcResidue ← T, Skip[ALU#0];
GoTo[gcAC4];
:ELSE; *********************************************
LU ← NextInst[IBuf], CallX[gcPop2Tailx];
gcAC3:gcResidue ← T, Skip[ALU#0];
LU ← NextInst[IBuf], CallX[gcPop2Tailx];
:ENDIF; ********************************************
*FindRetTab+10 to FindRetTab+15 are used here.
T ← (RSh[Stack&-1,1]) xor T, Call[gcFind], At[FindRetTab,11];
T ← (Stack) and (OnStack), Task;
gcCAR ← (gcCAR) or T;*OnStack can be set to 1, but not to 0
:IF[gcStats]; **************************************
LU ← (Stack) and (LShift[177,10]C), Call[gcACCnt];
:ENDIF; ********************************************
*Time to task may be 14+gcDelChk time here
LU ← LSh[Stack,1], Call[gcAC0];
LU ← NextInst[IBuf], CallX[gcTailx];

gcPop2Tailx:
Stack&-2, NIRet;

gcAC0:T ← (Stack&-1) and (LShift[177,10]C), GoTo[gcAC1,ALU<0];
gcCAR ← (gcCAR) + T;*Increment RefCnt
gcAC2:T ← RCFinalizePlus1LSh1, GoTo[gcDelChk,ALU>=0];
*Incrementing RefCnt above 127d.
T ← LShift[177,10]C;
gcCAR ← (LdF[gcCAR,10,10]) or T, GoTo[gcDelChk0];

*Subtracting from RefCnt--NOP if RefCnt=127d, crash if going below 0
gcAC1:LU ← (gcCAR) + (LShift[1,10]C);
gcCAR ← (gcCAR) + T, Skip[ALU>=0];
LU ← NextInst[IBuf], CallX[gcTailx];*RefCnt = 127d
gcCAR ← LdF[gcCAR,1,17], GoTo[gcAC2,ALU<0];
TrapParm ← RCBelowZero, CallX[gcBug];

:IF[gcStats]; **************************************
gcACCnt:
LU ← LSh[Stack,1], Skip[ALU#0];
T ← ACZeroCtr, GoTo[gcCount];*Must be OnStack marking
T ← ACSubCtr, GoTo[gcCount,ALU<0];
T ← ACAddCtr, GoTo[gcCount];
:ENDIF; ********************************************

%Loop through all PIs clearing all OnStack bits and removing RCEs with RefCnt
.eq. RCFinalize+1. TOS (initially zero) is used as a state variable.
Interrupts are allowed after each chain is processed. This opcode is executed
at the end of a collection to clean up the data structure.

Timing from @ResetOnStack to exit: 7 +
24 cycles/PI that is empty
35 cycles/PI that goes from 1 RCE to empty,
38 cycles/PI that has one RCE that remains,
60 to 74/cycles/PI that has two RCE’s
etc.
Total time is .077 to .14 seconds.
%
@ResetOnStack:
Nop, At[MiscDisp4,2];*Alpha = 62b
*Check for finished. T ← PI + HT offset
gcROS1:T ← (Stack) + (HTOffset), GoTo[gcROS3,R>=0];
LU ← NextInst[IBuf];
gcPopTailx:
Stack&-1, NIRet;
gcROS3:PFetch1[GC,gcCDR];*Fetch HT cell
gcPred ← T, Call[gcRet];*Bypass kludge ok since GC=0
LU ← (gcCDR) and (LShift[173,10]C), GoTo[gcResetChain,R<0];
*A single entry is in HT cell or the cell will become empty.
gcROS2:T ← gcPred, Skip[ALU#0];*Go if RefCnt .ne. (RCFinalize+1)
*Store 177777b in the cell indicating empty.
PStore1[GC,AllOnes], GoTo[gcROS0];*35 cycle loop
*Clear the OnStack bit.
gcCDR ← (gcCDR) and not (OnStack);
PStore1[GC,gcCDR], GoTo[gcROS0];*38 cycle loop

%Get here with gcPred pointing at an HT cell containing a pointer and gcCDR
containing the contents of the HT cell.
gcPredpointer to predecessor
gcCDRoriginally, contents of predecessor (empty or a pointer)
MNBRcontents of predecessor
gcCAR,,gcCDRused to hold OT cell pointed at by MNBR (CAR,,CDR)
gcCADR,,gcCDDRused to hold OT cell pointed at by gcCDR (CDAR,,CDDR)
%
gcResetChain:
T ← MNBR ← gcCDR, GoTo[gcROS0,R Odd];*Go if HT cell empty
PFetch2[GC,gcCAR];
T ← gcPred, Call[gcRet];
LU ← (gcCAR) and (LShift[173,10]C), Skip[R>=0];
TrapParm ← OTCarNotEntry, CallX[gcBug];
*Conditionally remove CAR[OT cell] by storing CDR into predecessor and
*collecting the cell.
gcCAR ← (gcCAR) and not (OnStack), GoTo[gcROSRemain,ALU#0];
***Next 2 mi duplicate ones in gcDelChk.
PStore1[GC,gcCDR];
T ← gcFL, Call[gcCollectCAR];
LU ← (gcCDR) and (LShift[173,10]C), DblGoTo[gcResetChain,gcROS2,R<0];

*CAR will remain; check CDR
gcROSRemain:
LU ← (gcCDR) and (LShift[173,10]C), GoTo[gcROSMore,R<0];
*CDR is a RCE (hence the last RCE). If it is flushed, copy CAR into the
*predecessor and collect the cell, else advance to next PI.
gcCDR ← (gcCDR) and not (OnStack), GoTo[.+3,ALU=0];
T ← MNBR;
PStore2[GC,gcCAR], GoTo[gcROS0];
*CAR remains, CDR is a RCE (the last) and gets flushed.
*Copy CAR into predecessor, collect the cell, and done with chain.
T ← gcPred;
PStore1[GC,gcCAR], Call[gcCollectMNBR];
Nop;
gcROS0:Stack ← (Stack) + 1, GoTo[gcROS1,IntPending’];*Odd placement
***This LoadPage prevents LogSE from being used.
LoadPage[opPage0];
gcNop:T ← 2C, GoToP[NOPint];*T gets no. bytes by which to backup PC

gcROSMore:*CAR remains, CDR is a pointer
T ← gcCDR, Skip[R Even];
TrapParm ← BadOTPointer, CallX[gcBug];
PFetch2[GC,gcCADR];
T ← MNBR, Call[gcRet];
LU ← (gcCADR) and (LShift[173,10]C), Skip[R>=0];
TrapParm ← OTCarNotEntry, CallX[gcBug];
GoTo[gcROSMoreRemain,ALU#0];
*CADR can be removed--store CDDR into predecessor and collect the cell.
*This store is redundant if CDDR is a RCE, because it is stored again at
*gcROSRemain, but if it is a pointer, then the PFetch2 at gcROSMore might
*fault leaving the chain smashed, so we have to store CDDR here.
T ← (MNBR) + 1;
PStore1[GC,gcCDDR];
T ← gcFL;
gcNewCell ← T, Call[gcCollectCDR];
gcROSMore1:
T ← gcCDDR;
gcCDR ← T, GoTo[gcROSRemain];*CDR←CDDR.

*CAR remains, CDR is a pointer, CADR remains. Since two or more RCEs
*remain below the cell pointed at by gcPred, gcPred↑ will not change, so
*advance gcPred (etc.) and loop.
gcROSMoreRemain:
PStore2[GC,gcCAR];*Clear OnStack in CAR and store CDR
MNBR ← gcCDR;
gcPred ← (Zero) + T + 1, Task;*gcPred ← (old MNBR)+1
T ← (gcCADR) and not (OnStack);
gcCAR ← T, GoTo[gcROSMore1];

%TOS is the 64k bank number of the Collector data structure, copied into GChi
only during initialization. Software must issue a GCSetup not only during
initialization but also before looking at the free list pointer or count or
after it changes the collector process number or mask word so that cacheing
in registers will work.
2OS is .ls. 0 to refetch everything (initialization), .ge. 0 to update the
free list pointer and count in storage (if these are cached in registers) and
the collector process number and mask in registers (if these are cached).
Returns microcode version on TOS.

**Page fault mustn’t happen on PFetch2 or PStore2 here.
’Return’ from here goes to the NextInst at @MISC+1 in MesaX.

Timing for opcode: 18.5+19 cycles.
%
@GCSetup:
T ← LSh[Stack&-1,10], At[MiscDisp4,3];*Alpha = 63b
Stack ← UVersion, Skip[R<0];
PStore2[GC,gcFL,0], Return;*Update gcFL & gcFLCount for software
GChi ← T, LoadPage[gcPage3];*Only left-half needs to be correct
GC ← 0C;
OnPage[gcPage3];
PFetch2[GC,gcFL,0], Return;


*Return count of RCE’s with RefCnt .eq. RCFinalize.
@CollectCount:
PFetch1[GC,Stack,RCeqRCFinalize!], Return, At[MiscDisp4,4];

%ReclaimAll[PI] searches HT starting at PI=TOS for entries with
(RefCnt <= RCFinalize) & OnStack=0; if none are found, then TOS ← TOS+1,
check for interrupts, and loop. If an entry is found, all such at that PI
are stored into the 200b-word reclaim table in the GC structure, and the count
of these is pushed onto TOS, leaving PI at 2OS. When the last PI
has been scanned, TOS=0 is returned indicating completion.

Software is expected to initialize PI to 0, to service all the entries
returned by ReclaimAll, and to reexecute ReclaimAll at PI+1
until a 0 count is returned.

Algorithm makes use of the fact that RCFinalize is 3 (i.e., 2↑n-1), so
Anding by 76200 will be 0 iff the RCE should be enumerated.

Timing: 18.5 + 9
+ 24 cycles/PI with no RCEs else 27 cycles/PI with one or more RCEs
+ 26 cycles/OT cell
+ 25.5 or 32.5 cycles/PI at which RCEs are reported
Total time for nothing reported is 0.08 seconds (HT empty) to 1.23 seconds
(HT and OT both full).
%
@ReclaimAll:*Alpha = 65b
gcRAVal ← 76000C, At[MiscDisp4,5];
gcRAPILoop:
T ← (Stack) + (HTOffset), GoTo[gcRA0,R>=0];
:IF[gcStats]; **************************************
T ← RACtr, Call[gcCount];
:ENDIF; ********************************************
Stack ← (Stack) - 1;*Software requires PI=Last here
Stack&+1 ← 0C, GoTo[gcTail];*Exit with TOS=0 when PI .gr. last
gcRA0:PFetch1[GC,gcCDR];
gcRecIndex ← ReclaimOffset, Call[gcRAValToT];
*gcRAInd "returns" here to handle odd word of OT cell and task
LU ← (gcCDR) and T, GoTo[gcRAInd,R<0];
*Single entry (the last one); don’t indicate if RefCnt .gr. RCFinalize or if
*OnStack=1
T ← gcRecIndex, GoTo[.+3,ALU#0];
PStore1[GC,gcCDR];*Store RCE in ReclaimTable
T ← (gcRecIndex) - (Sub[ReclaimOffset!,1]C), GoTo[gcPushTTail];
T ← (gcRecIndex) - (ReclaimOffset);
GoTo[gcPushTTail,ALU#0];
Stack ← (Stack) + 1, GoTo[gcRAPILoop,IntPending’];*Advance PI
gcRAInt:
LoadPage[opPage0], GoTo[gcNop];

*"Return" loops to handle odd word of OT cell while simultaneously tasking.
gcRAInd:
T ← gcCDR, Skip[R Even];
*Legitimately get here only when the HT cell is empty, denoted by 177777b.
Stack ← (Stack) + 1, DblGoTo[gcRAPILoop,gcRAInt,IntPending’];
PFetch2[GC,gcCAR];
T ← (gcRAVal) or (OnStack);
LU ← (gcCAR) and T, Skip[R>=0];
TrapParm ← OTCarNotEntry, CallX[gcBug];
T ← gcRecIndex, GoTo[gcRAValToT,ALU#0];
*Report CAR in ReclaimTable.
PStore1[GC,gcCAR];
gcRecIndex ← (gcRecIndex) + 1;
gcRAValToT:
T ← (gcRAVal) or (OnStack), Return;

%CreateRef accepts a Ref at TOS,,2OS and no. of package references (NPR) at
3OS positioned in the RefCnt field with zeroes in the rest of the word. It
creates a new RCE with RefCnt = RCFinalize-NPR, popping 3 items off the stack.

Timing @CreateRef to exit for the normal case in which a new HT or OT
entry is created: 26 + (28, 66, or 92+24*N for gcFind) + (50 if NPR#0 else
22 for gcDelChk) cycles = 104, 142 or 168+24*N if no package references
or 76, 114, or 140+24*N with package references. Average opcode time should
be about 13.5 microseconds.
%
@CreateRef:
PFetch2[GC,gcRCEMask,2], At[MiscDisp4,7];*Alpha = 67b
T ← LdF[Stack&-2,12,6];
LU ← (Stack&+1) - (LShift[3,10]C), Call[gcCreate1], At[FindRetTab,1];
%Have entry in gcCAR, pointer to it in MNBR. There are three legal cases:
either the entry already existed with RefCnt=RCFinalize+1 and OnStack=1
(Representing a false entry due to the collector’s conservative OnStack
marking algorithm), or no entry existed but gcFind has created one with
RefCnt=RCFinalize+1. In either case we subtract (NPR+1) from RefCnt to
get the desired RefCnt and set OnStack to the value in gcRCEMask.
The third case is that the trace and sweep has just run and created an
entry with RefCnt exactly equal to the value CreateRef would store into the
entry. In that case, we fixup OnStack and accept it.
%
:IF[gcStats]; **************************************
T ← CRCtr, Call[gcCount];
:ENDIF; ********************************************
*ORing 100000b into 3OS is equivalent to ORing 100000b into gcRCEMask.
*This is done so that the sign bit won’t be erroneously 1 at the end.
T ← (Stack&-1) or (100000C), Task;
gcCAR ← (gcCAR) and not (OnStack);
LU ← (gcCAR) and (LShift[173,10]C), Call[gcCreate2];
LU ← NextInst[IBuf], CallX[gcTailx];

gcCreate2:
T ← (gcRCEMask) - T, GoTo[gcAlreadyCreated,ALU#0];
*Set OnStack if collecting; subtract npr+1 from RefCnt
gcCAR ← (gcCAR) + T;
gcCreate3:
T ← MNBR, GoTo[gcPreserve];

*Crash unless gcCAR contains the value we would have stored in the cell
*[gcResidue + LShift[RCFinalizePlus1!,10] + T], ignoring OnStack.
gcAlreadyCreated:
T ← (LdF[gcCAR,11,7]) + T;
T ← (LSh[R400,2]) + T;*Add LShift[RCFinalizePlus1!,10]C
*T now has the value we would have stored in the cell.
gcCAR ← (gcCAR) xor T;
LU ← (gcCAR) and not (OnStack);
gcCAR ← T, GoTo[gcCreate3,ALU=0];
TrapParm ← BadCreate, CallX[gcBug];*Already existed

gcCreate1:
gcResidue ← T, Skip[ALU<0];
TrapParm ← BadPackRefCnt, CallX[gcBug];*Package RefCnt .gr. 2
LU ← gcRCEMask, Skip[R<0];
T ← (RSh[Stack&-1,1]) xor T, DblGoTo[gcFind,gcRefUneven,R Even];
*Collector disabled; trap with TrapParm .eq. 2 if collector running, else
*opcode is a noop.
LU ← gcProcNo;
Skip[ALU#0];
LU ← NextInst[IBuf], CallX[gcPop2Tailx];
gcCollectingTrap:
Stack&+1, LoadPage[opPage0];
TrapParm ← 2C, GoToP[UndefTrap];

OnPage[gcPage4];

gcFWriteTTailx:
Stack ← T, NIRet;

%Have long pointer to QMap in xBuf/xBuf1 and to SubZMap in xBuf2/3; have high
part of a Ref in left half of T, low part on TOS.
If the Ref is Nil, return 0 (NilType); otherwise, read the QMap word for the
Ref at QMap[(Ref rsh 12d) + 1] into zBuf2 and build a base register in
LP/LPhi pointing at Ref-1; only the left-half of LPhi need be valid because
only 0 displacement is used.
%
gcGRT0:LU ← (Stack) or T;
*LP/LPhi ← ref-1 for access to type word of prefixed objects.
*Ref-1 is not guaranteed to be in the same 64k region as Ref.
LPhi ← T, Skip[ALU#0];*Nil ref => nil type = 0
LU ← NextInst[IBuf], CallX[gcFWriteTTailx];*NIL Ref => NilType
*Convert xBuf/xBuf1 pointing at quantum map into base register format.
xBuf1 ← T ← LdF[xBuf1,12,6];
xBuf1 ← (LSh[xBuf1,10]) + T + 1;
T ← RSh[Stack,12];
T ← (RSh[LPhi,2]) + T + 1;*(Ref rsh 10d) + 1
PFetch1[xBuf,zBuf2];*zBuf2 ← QMap entry
T ← (Stack) - 1;
LP ← T, Skip[Carry];
LPhi ← (LPhi) - (400C);*Backup to previous 64k region
*Start converting xBuf2/3 into base register format to access SubZMap if
*this is a quantized zone.
T ← xBuf3 ← LdF[xBuf3,12,6], Return;

%If QMap entry .ge. 0, Ref points at a prefixed object with type in
the right 14d bits at Ref[-1]. Otherwise,
LSh[(QMap entry) & 77777b,1]+1 is a displacement into the table of
long pointers pointed at by GC[SubZMap] xBuf2/3; table length is in
word 0 and the long pointers at words 1-2, 3-4, etc. The long
pointer in this table points at the word containing the type.
%
*Non-skip to return Ref[-1] as the type
gcGRT1:zBuf2 ← T ← (LdF[zBuf2,1,17]) + 1, Skip[R<0];
gcGRT3: PFetch1[LP,zBuf2,0], GoTo[gcFRet];
PFetch1[xBuf2,zBuf3,0];*Fetch subzmap length
**11 cycles wasted here
Nop;*Avoid bypass kludge
gcGRT4:LU ← (zBuf3) - T;
T ← LSh[zBuf2,1], Skip[ALU>=0];
TrapParm ← BadMapIndex, CallX[gcFBug];
***Want the table to begin at an odd word, so a PFetch2 can be used here.
PFetch1[xBuf2,LPhi];*Fetch 2nd word of L.P.
T ← (LSh[zBuf2,1]) - 1;
PFetch1[xBuf2,LP];*Fetch 1st word of L.P.
LPhi ← LSh[LPhi,10];
**Interlocking LP here may be unnecessary.
LU ← LP, GoTo[gcGRT3];

*Have type in zBuf2 and length of CMap table in zBuf3.
gcGRT2:T ← zBuf2 ← (LdF[zBuf2,2,16]) + 1, GoTo[gcGRT4,R>=0];
TrapParm ← ReferentOnFL, CallX[gcFBug];

gcGRTBegin:
T ← LSh[Stack&-1,10], Call[gcGRT0];
xBuf3 ← (LSh[xBuf3,10]) + T + 1, Call[gcGRT1];
*Return here with fetch of word containing type to zBuf2 pending.
T ← LdF[zBuf2,2,16], Skip[R>=0];*14d bits
TrapParm ← ReferentOnFL, CallX[gcFBug];
gcFWriteTTail:
LU ← NextInst[IBuf], CallX[gcFWriteTTailx];

gcGCRTBegin:
T ← LSh[Stack&-1,10], Call[gcGRT0];
xBuf3 ← (LSh[xBuf3,10]) + T + 1, Call[gcGRT1];
%Return here after fetch of type to zBuf2; exit if Null type, else convert
CMap long pointer from GC to base register. If the type is less than the
table length from CMap[0], then return the word pointed at by the long
pointer in CMap.
%
PFetch2[GC,xBuf2,CMap], Call[gcFRet];
***Is it possible to have a NIL type when the Ref is non-NIL???
**10 cycles wasted here
T ← xBuf3 ← LdF[xBuf3,12,6];
xBuf3 ← (LSh[xBuf3,10]) + T + 1, Call[gcFRet];
PFetch1[xBuf2,zBuf3,0], Call[gcGRT2];*Fetch table length
T ← zBuf2;
GoTo[gcWakeCollectorTrap,ALU=0];
LU ← NextInst[IBuf], CallX[gcFWriteTTailx];

%Replace the Ref at TOS,,2OS by its type. Ref rsh 12d is the
index into the quantum map, a table in which word 0 is number of entries N,
and words 1 to N are the entries.
The first PFetch4 gets the long pointers to both the quantum
and subzone maps.

***Bounds check base registers here.

Timing from @RefType to exit: 16 cycles if Ref is nil else
58 if prefixed, 97 if quantized.
%
:IF[gcStats]; **************************************
@RefType:
*LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,11];
T ← RefTypeCtr, At[MiscDisp4,11];
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[gcPage4];
PFetch4[GC,xBuf,QMap], GoToP[gcGRTBegin];
:ELSE; *********************************************
@RefType:
LoadPage[gcPage4], At[MiscDisp4,11];
PFetch4[GC,xBuf,QMap], GoToP[gcGRTBegin];
:ENDIF; ********************************************


%Replace the Ref at TOS,,2OS by its canonical type; trap with TrapParm=1
if not canonicalized yet.
Timing from @CRefType to exit: 16 cycles if Ref is nil else
81 if prefixed, 120 if quantized.
%
:IF[gcStats]; **************************************
@CRefType:
*LoadPage[opPage0], CallX[gcUnimp], At[MiscDisp4,12];
T ← CRefTypeCtr, At[MiscDisp4,12];
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[gcPage4];
PFetch4[GC,xBuf,QMap], GoToP[gcGCRTBegin];
:ELSE; *********************************************
@CRefType:
LoadPage[gcPage4], At[MiscDisp4,12];
PFetch4[GC,xBuf,QMap], GoToP[gcGCRTBegin];
:ENDIF; ********************************************

%AssignRef[refNew,ptrRef] returns nothing;
implements ((TOS,,2OS)+alpha)↑ ← (3OS,,4OS); RefCnt for the previous Ref in
that location (refOld) is decremented and that for the new Ref (refNew) is
incremented (but nil does not have an HT/OT cell, so no update when a ref is
nil). When decrementing RefCnt for refOld, OnStack will be set to 1 if a
collection is in progress.

It is possible to page fault or run out of OT cells on either RefCnt operation
or to page fault or trap on the read of alpha+ptrRef↑. A write protect fault
is also possible on the write of either word (because the 2nd word might lie
on a different page from the 1st) of alpha+ptrRef↑, but this is assumed a
crash condition and not handled here.

The safe order of execution used is as follows:
a. Compute base register for TOS,,2OS (ptrRef↑).
b. If the incremental collector is disabled and the collector process is
running (indicating trace and sweep collection), trap with TrapParm .eq. 2;
c. If the incremental collector is disabled and the collector process is
not running, then store 3OS,,4OS (refNew) into alpha+ptrRef↑ and exit
(simple assignment).
d. Fetch refOld at alpha+ptrRef↑.
e. Unless refOld is NIL:
(1)Find its RCE, creating if necessary.*
(2)Subtract 1 from RefCnt for refOld and store RCE (or flush RCE
if RefCnt=RCFinalize+1 and OnStack=0 now).
(3)Store NIL at alpha+ptrRef↑.
f. Unless refNew is NIL:
(1) Find its HT/OT cell, creating if necessary.*
(2) Add 1 to RefCnt for refNew (preserving OnStack when RefCnt winds up
.le. RCFinalize, clearing OnStack when RefCnt winds up .gr.
RCFinalize); store cell (or flush if RefCnt=RCFinalize+1 now).
(3) Store 3OS,,4OS (refNew) into alpha+ptrRef↑.

* Indicates that the step might experience a page fault from which the opcode
would eventually be restarted.

There is no way to avoid the extraneous double-write of NIL. If this is not
done, then a page fault on the refNew RCE update will produce an inconsistency
between a pointer in storage and its associated refCnt as follows:
1) Suppose refNew’s RefCnt is one too small because a page fault aborts
refNew’s RCE update AFTER writing refNew. Another process could intervene
with an AssignRef to the same alpha+ptrRef↑ and refNew’s RefCnt would wind up
one too small--disaster.
2) Alternatively, suppose refNew’s RCE update occurs BEFORE writing refNew.
Then if another process intervenes and does an AssignRef to the same
alpha+ptrRef↑, then refOld’s RefCnt will wind up one too small--disaster.

Since the store of refNew and its RCE update cannot be done in a safe order,
only by delaying the update of refOld’s RCE until certain that refNew’s RCE
won’t fault is it possible to proceed safely, but this isn’t feasible for
the current arrangement of this module.

If it was necessary to worry about safe execution in the presence of write
protect faults, then a WP fault could happen when storing either word of
NIL at alpha+ptrRef↑. This would be disastrous. Only by rewriting refOld
after reading it, then writing NIL as an intermediate value after updating
refOld could the code be safe against this event also.

The most significant word of a Ref or long pointer appears at alpha+1 in
storage and on TOS, the least significant at alpha and on 2OS.

Average timing (includes buffer refill): 52.5 + (7 if ptrRef+alpha is odd)
+(26+(18 if odd)+gcFind+gcDelChk if refOld non-NIL)
+(18+(23 if quadovf)+gcFind+gcDelChk if refNew non-NIL)
gcFind+gcDelChk will use 78 to 127 cycles, averaging ~90, for normal cases.
Average time ~277 cycles for both refOld and refNew non-NIL assuming that
pointers are normally placed at even locations.
If half of executions have ptrRef+alpha odd, timing averages 18 cycles slower.
%

OnPage[opPage0];
gcARSetup:
LPhi ← (LSh[LPhi,10]) + T + 1, GoToP[.+1];
OnPage[gcPage2];
PFetch2[GC,gcRCEMask,2], Return;*Can’t fault

*Cannot do PFetch2 in 1st mi because of bypass kludge with previous opcode.
@AssignRef:
T ← LdF[Stack&-1,12,6], Opcode[76];
*Enter here from @AssignRefNew
gcARN1:LPhi ← T, LoadPage[gcPage2], Call[gcARSetup];
T ← NextData[IBuf];
T ← (Stack&-1) + T, LoadPage[gcPage];
LP ← T, SkipP[Carry’];
OnPage[gcPage];
LPhi ← (LPhi) + (400C) + 1;
*Have ptrRef+alpha in base register format in LP/LPhi.
*Timing = 4.5+16 cycles to here
LP, Skip[R Odd];*Fetch refOld into gcRef0,,gcResidue
PFetch2[LP,gcRef0,0], GoTo[gcAR0];
PFetch1[LP,gcResidue,1], Call[gcRet];
PFetch1[LP,gcRef0,0];
gcAR0:LU ← gcRCEMask, GoTo[gcAR1,R>=0];
*Reference counting is disabled; trap with TrapParm .eq. 2 if collecting else
*convert opcode to a Store2.
LU ← gcProcNo;
RTemp ← 76C, Skip[ALU#0];*76b for gcFind trap
*Simple assignment if no collection in progress
PStore2[LP,Stack,0], GoTo[gcAR4];
*Trap with TrapParm .eq. 2 if collecting.
Stack&+1, GoTo[gcCollectingTrap];

*Reference counting is enabled.
gcAR1:gcResidue ← T ← LdF[gcResidue,12,6];
LU ← (gcRef0) or T, Call[gcAR3], At[FindRetTab,25];
%Set OnStack=1 if collecting, required even though we are not putting any
pointers to refOld on the stack because of the following sequence:
(1) Collector completes its OnStack marking phase;
(2) Process A does a push of RefX on its stack preparatory to an AssignRef;
(3) Process B completes an AssignRef deleting the last pointer to RefX;
(4) The Collector finishes;
(5) Process A continues but RefX has been collected.
The DeleteRef part of Process B’s AssignRef must set OnStack=1 to protect
Process A. An enumeration algorithm might legitimately touch objects in this
way, so ruling out this case with a programming restriction is undesirable.
%
T ← gcRef0 ← 0C, Task;*Must task here
gcResidue ← T;
gcCAR ← (gcCAR) + (LShift[1,10]C), Call[gcARO];*Odd placement
%Timing to here on @AssignRef: 40.5+(7 if odd)+5+(gcFind+6+6)+(gcDelChk-2)
where there are 14 non-mem-ref cycles after gcFind returns. If RefCnt is
RCFinalize+1 and the chain is now 2 or more long, then all 14 of these
cycles are free; if RefCnt is RCFinalize, 10 of these are free. Store NIL.
%
LP, Skip[R Odd];
PStore2[LP,gcRef0,0], GoTo[gcAR2];
PStore1[LP,gcRef0,1], Call[gcRet];
PStore1[LP,gcRef0,0], GoTo[gcAR2];

*Timing to here on @AssignRef:
* 4.5+16+20+(7 if LP odd) to here = 40.5 + (7 if LP odd) cycles
gcAR3:RTemp ← 76C, Skip[ALU=0];*NIL test
T ← (RSh[gcRef0,1]) xor T, DblGoTo[gcFind,gcRefUneven,R Even];
:IF[gcStats]; **************************************
Nop;
T ← RONilCtr, Call[gcCount];
:ENDIF; ********************************************
%Total timing for @AssignRef:
52.5 + (7 if LP odd) +
[26+gcFind+gcDelChk+(18 if LP odd) if refOld non-NIL] +
[19+gcFind+gcDelChk+(23 if LP quadovf) if refNew non-NIL]
%
gcAR2:T ← LdF[Stack&-1,12,6];
LU ← (Stack) or T, Call[gcARN], At[FindRetTab,21];
gcCAR ← (gcCAR) + (LShift[1,10]C), Call[gcAR6];
:IF[gcStats]; **************************************
T ← ARCtr, Call[gcCount];
:ENDIF; ********************************************
PStore2[LP,Stack,0];
gcAR4:GoTo[gcTail,QuadOvf’];
Stack&+2, Task;
PStore1[LP,Stack,1];
PStore1[LP,Stack,0];
gcTail:LU ← NextInst[IBuf], CallX[gcTailx];
gcTailx:
NIRet;

*Skip for no change if RefCnt = 127d; otherwise,
*when RefCnt = RCFinalize or RCFinalize-1 (2 or 3), preserve OnStack; if
*RefCnt=RCFinalize+1, clear OnStack so that the RCE disappears; otherwise,
*OnStack is don’t care.
gcAR6:LU ← (gcCAR) and (LShift[173,10]C), Skip[R<0];
T ← MNBR, DblGoTo[gcPreserve,gcDelete,ALU#0];
Return;

*No change to entry if RefCnt=127d (since OnStack is a don’t care), else set
*OnStack=1 and decrement RefCnt.
gcARO:gcCAR ← (gcCAR) - (LShift[2,10]C), Skip[R>=0];
Return;
LU ← (gcRCEMask) and (OnStack);
*"And" works here because RefCnt=0 is illegal and because OnStack is 0.
LU ← (gcCAR) and (LShift[373,10]C), GoTo[gcDelChk0,ALU=0];
gcCAR ← (gcCAR) or (OnStack), GoTo[gcDelChk0];

gcARN:gcResidue ← T, Skip[ALU=0];
T ← (RSh[Stack&+1,1]) xor T, DblGoTo[gcFind,gcRefUneven,R Even];
*New value is NIL.
:IF[gcStats]; **************************************
Nop;
T ← RNNilCtr, Call[gcCount];
:ENDIF; ********************************************
LU ← NextInst[IBuf], CallX[gcPopTailx];


%AssignRefNew obsolete--now same as AssignRef--will be deimplemented.
%
@AssignRefNew:
T ← LdF[Stack&-1,12,6], GoTo[gcARN1], Opcode[77];

END[CedarGC];

:ELSE; *********************************************
TITLE[No.Cedar.garbage.collector.microcode];
:ENDIF; ********************************************