TITLE[Cedar1];*This file is inserted at the end of Cedar0.Mc

%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 FindReclaimableRefs or by an earlier ReclaimRef, only those
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], GoToP[.+1], At[EscD6,0];*Alpha = 140b
%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.
%
OnPage[gcPage];
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 FindReclaimableRefs (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], GoToP[.+1], At[EscD6,1];*Alpha = 141b
*Clear garbage bits in high word
OnPage[gcPage];
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 @ClearOnStack 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.
%
@ClearOnStack:
GoToP[.+1], At[EscD6,2];*Alpha = 142b
*Check for finished. T ← PI + HT offset
OnPage[gcPage];
gcROS1:T ← (Stack) + (HTOffset), GoTo[gcROS3,R>=0];
gcPopTail:
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
LoadPage[opPage0];
gcNop: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 CedarState 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.
%
@CedarState:
T ← LSh[Stack&-1,10], GoToP[.+1], At[EscD6,3];*Alpha = 143b
OnPage[gcPage];
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.
@ReadZeroCount:*Alpha = 144b
PFetch1[GC,Stack,RCeqRCFinalize!], GoToP[gcRet], At[EscD6,4];

%FindReclaimableRefs[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 FindReclaimableRefs, and to reexecute FindReclaimableRefs 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: 14.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 .123 seconds
(HT and OT both full).
%
@FindReclaimableRefs:*Alpha = 145b
gcRAVal ← 76000C, GoToP[.+1], At[EscD6,5];
OnPage[gcPage];
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;

*Args are TOS/ cardinal count of words to 0; 2OS,,3OS/ long pointer to block.
@BLZL:*Alpha = 146b
Stack&-1, LoadPage[opPage1], GoToP[.+1], At[EscD6,6];
OnPage[gcPage];
T ← Stack&-1, CallP[StackLPx];*Setup Long pointer from 2OS,,3OS
Stack&+3, Call[.+1];*Point StkP at count
*Loop here to zero all words in the block in reverse order.
LU ← Stack;
T ← (Stack) - 1, Skip[ALU#0];
:IF[CacheLocals]; *************************************
PFetch4[LOCAL,LocalCache0,0], GoTo[gcPopTail];
:ELSE; ************************************************
LU ← NextInst[IBuf], CallX[gcPopTailx];
:ENDIF; ***********************************************
PStore1[LP,RZero], GoTo[gcLBX];


*Arg on TOS is cardinal count of words in local frame to zero.
@LOCALBLKZ:*Alpha = 150b
GoToP[.+1], At[EscD6,10];
OnPage[gcPage];
LU ← Stack, Call[.+2];*Unnecessary to do Stack&-1 for Esc opcode
*Loop here
*Frame starts at LOCAL+0, so count-1 is displacement of last word
*remaining to be zeroed; do block in reverse order.
LU ← Stack;
T ← (Stack) - 1, Skip[ALU#0];
:IF[CacheLocals]; *************************************
PFetch4[LOCAL,LocalCache0,0], GoTo[gcPopTail];
:ELSE; ************************************************
LU ← NextInst[IBuf], CallX[gcPopTailx];
:ENDIF; ***********************************************
PStore1[LOCAL,RZero];
gcLBX:Nop;*Wait for MC1 fault to abort 4th mi.
Nop;
Skip[IntPending];
Stack ← (Stack) - 1, Return;*MC1 fault aborts this mi.
Stack ← (Stack) - 1, LoadPage[opPage0];
:IF[CacheLocals]; *************************************
PFetch4[LOCAL,LocalCache0,0], GoToP[NopInt];
:ELSE; ************************************************
GoToP[NopInt];
:ENDIF; ***********************************************

%NewRef 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 @NewRef 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.
%
@NewRef:*Alpha = 147b
PFetch2[GC,gcRCEMask,2], GoToP[.+1], At[EscD6,7];
OnPage[gcPage];
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 NewRef 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;
RTemp ← (RTemp) + (Sub[EscTrapOffset!,SDOffset!]C), Skip[ALU#0];
LU ← NextInst[IBuf], CallX[gcPop2Tailx];
LoadPage[opPage0];
gcCollectingTrap:
TrapParm ← TSRunningTP, GoToP[P4Trap];

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 10d) + 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;
RTemp ← (RTemp) + (Sub[EscTrapOffset!,SDOffset!]C), Skip[ALU=0];
LU ← NextInst[IBuf], CallX[gcFWriteTTailx];
LoadPage[opPage0];
TrapParm ← NotCanonicalizedTP, GoToP[P4Trap];

%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:*Alpha = 151b
T ← RefTypeCtr, GoToP[.+1], At[EscD6,11];
OnPage[gcPage];
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[gcPage4];
PFetch4[GC,xBuf,QMap], GoToP[gcGRTBegin];
:ELSE; *********************************************
@RefType:*Alpha = 151b
LoadPage[gcPage4], GoToP[.+1], At[EscD6,11];
OnPage[gcPage];
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:*Alpha = 152b
T ← CRefTypeCtr, GoToP[.+1], At[EscD6,12];
OnPage[gcPage];
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[gcPage4];
PFetch4[GC,xBuf,QMap], GoToP[gcGCRTBegin];
:ELSE; *********************************************
@CRefType:*Alpha = 152b
LoadPage[gcPage4], GoToP[.+1], At[EscD6,12];
OnPage[gcPage];
PFetch4[GC,xBuf,QMap], GoToP[gcGCRTBegin];
:ENDIF; ********************************************

%WCDLB[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 WCDLB 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 WCDLB 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[opPage3];
gcWCSetup:
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.
@WCDLB:T ← LdF[Stack&-1,12,6], Opcode[372];
*Enter here from @WCIDLB
gcWCN1:LPhi ← T, LoadPage[gcPage2], Call[gcWCSetup];
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
gcPS1:LP, Skip[R Odd];*Fetch refOld into gcRef0,,gcResidue
PFetch2[LP,gcRef0,0], GoTo[gcWC0];
PFetch1[LP,gcResidue,1], Call[gcRet];
PFetch1[LP,gcRef0,0];
gcWC0:LU ← gcRCEMask, GoTo[gcWC1,R>=0];
*Reference counting is disabled; trap with TSRunningTP if collecting else
*convert opcode to a Store2.
LU ← gcProcNo;
*Fake an Esc alpha value for gcFind or collection in progress traps
RTemp ← ARFakeAlpha, Skip[ALU#0];
*Simple assignment if no collection in progress
PStore2[LP,Stack,0], GoTo[gcWC4];
*TrapParm .eq. TSRunningTP if collecting.
LoadPage[opPage0], GoTo[gcCollectingTrap];

*Reference counting is enabled.
gcWC1:gcResidue ← T ← LdF[gcResidue,12,6];
LU ← (gcRef0) or T, Call[gcWC3], 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 WCDLB;
(3) Process B completes an WCDLB 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 WCDLB 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[gcWCO];*Odd placement
%Timing to here on @WCDLB: 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[gcWC2];
PStore1[LP,gcRef0,1], Call[gcRet];
PStore1[LP,gcRef0,0], GoTo[gcWC2];

*Timing to here on @WCDLB:
* 4.5+16+20+(7 if LP odd) to here = 40.5 + (7 if LP odd) cycles
gcWC3:RTemp ← ARFakeAlpha, 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 @WCDLB:
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]
%
gcWC2:T ← LdF[Stack&-1,12,6];
LU ← (Stack) or T, Call[gcWCN], At[FindRetTab,21];
gcCAR ← (gcCAR) + (LShift[1,10]C), Call[gcWC6];
:IF[gcStats]; **************************************
T ← ARCtr, Call[gcCount];
:ENDIF; ********************************************
PStore2[LP,Stack,0];
:IF[CacheLocals]; **********************************
gcWC4:T ← RSh[LOCAL,2], GoTo[gcWC4x,QuadOvf’];
Stack&+2, Task;
PStore1[LP,Stack,1];
PStore1[LP,Stack,0];
gcWC4x:LU ← (RSh[LP,2]) xor T;
Skip[ALU#0];
PFetch4[LOCAL,LocalCache0,0];
:ELSE; *********************************************
gcWC4:GoTo[gcTail,QuadOvf’];
Stack&+2, Task;
PStore1[LP,Stack,1];
PStore1[LP,Stack,0];
:ENDIF; ********************************************
gcTail:LU ← NextInst[IBuf], CallX[gcTailx];
gcTailx:
NIRet;

*Skip for no change if RefCnt = 127d; otherwise,
*when new RefCnt = RCFinalize or RCFinalize-1 (2 or 3), preserve OnStack; if
*new RefCnt=RCFinalize+1, clear OnStack so that the RCE disappears; otherwise,
*OnStack is don’t care.
gcWC6: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.
gcWCO: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];

gcWCN: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];


*WCIDLB--now same as WCDLB.
@WCIDLB:
T ← LdF[Stack&-1,12,6], GoTo[gcWCN1], Opcode[373];


*PSCDLB[ptrRef,refNew]--same as WCDLB with args reversed.
@PSCDLB:
Stack&-2, Opcode[374];
gcPS0:T ← LdF[Stack&-1,12,6];
LPhi ← T, LoadPage[gcPage2], Call[gcWCSetup];
T ← NextData[IBuf];
T ← (Stack&+1) + T, LoadPage[gcPage];
Stack&+2, SkipP[Carry’];
OnPage[gcPage];
LPhi ← (LPhi) + (400C) + 1;
LP ← T, GoTo[gcPS1];

*PSCIDLB now same as PSCDLB.
@PSCIDLB:
Stack&-2, GoTo[gcPS0], Opcode[375];

END[Cedar1];

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