*-----------------------------------------------------------
Title[CedarOps.mc...November 29, 1983  5:01 PM...Taft];
* Cedar Allocator and Reference-Counting opcodes (version 5.0)
*-----------------------------------------------------------

* General notes:
* 1. These opcodes as presently implemented are NOT restartable in the
*    face of write-protect faults.
* 2. zct.wp is cached and is not stored in memory except when the microcode
*    is disabled.
* 3. ASSIGNREF takes over the WCLB opcode from the old RC microcode whenever
*    ENABLEMICROCODE is executed, and gives it back whenever the old
*    RTSETUP opcode is executed.


*-----------------------------------------------------------
* Data structures -- from Allocator.mesa, ZCT.mesa, and Collector.mesa
*-----------------------------------------------------------

* -- Header preceding allocated normal Cedar reference-counted objects.
* -- 2 words long, and always even-word aligned.
* NHeaderP: TYPE = LONG POINTER TO NormalHeader;
* NormalHeader: TYPE = MACHINE DEPENDENT RECORD [
MSC[NH.rcWord, 0];
  MC[NHR.inZCT, 100000];	* inZCT (0: 0..0): BOOLEAN, -- must be bit 0
  MC[NHR.maybeOnStack, 40000];	* maybeOnStack (0: 1..1): BOOLEAN, -- must be bit 1
  MC[NHR.blockSizeIndex, 37400]; * blockSizeIndex (0: 2..7): BlockSizeIndex,
  MC[NHR.finalizable, 200];	* finalizable (0: 8..8): BOOLEAN,
  MC[NHR.refCount, 176];	* refCount (0: 9..14): RefCount,
  MC[NHR.rcOverflowed, 1];	* rcOverflowed (0: 15..15): BOOLEAN, -- must be bit 15
MSC[NH.type, 1];		* -- type: SafeStorage.Type];
	* Note: for compatibility with Cedar 4, the actual definition is:
				* typePad: (1: 0..1): [0..3] ← 0,
  MC[NHT.type, 37777];		* type (1: 2..15): SafeStorage.Type];

MC[sizeNH, 2];			* must be 2

* RefCount: TYPE = [0..77B];	* Microcode requires max value less than 200B

MC[nullType, 0];		* nullType: SafeStorage.Type = [0]; -- must be zero

* -- Header for free normal Cedar objects (the only kind this allocator deals with).
* -- Following is a simplification of the variant record declaration in Allocator.mesa.
* FNHeaderP: TYPE = LONG POINTER TO NormalFreeHeader;
* NormalFreeHeader: TYPE = MACHINE DEPENDENT RECORD [
*				* fnh (0): NormalHeader,
MC[NFH.nextFree, 2];		* nextFree (2): FNHeaderP];

* Data structures (cont'd)

* ZeroCountTable: TYPE = LONG POINTER TO ZCTObject;
* ZCTObject: TYPE = MACHINE DEPENDENT RECORD [
MSC[ZCT.wp, 0];			* wp (0): LONG POINTER TO Allocator.NHeaderP,
				* rp (2): LONG POINTER TO Allocator.NHeaderP,
				* lastNP (4): LONG POINTER TO LONG POINTER,
				* pad (6: 0..14): [0..77777B],
MSC[ZCT.markingDecrements, 6];	* markingDecrements (6: 15..15): BOOLEAN,
				* unused1 (7): ARRAY [7..wordsPerPage) OF WORD,
MC[ZCT.bsiToFreeList, 400];	* bsiToFreeList (wpp): BSIToFreeListObj,
				* unused2 (wpp+SIZE[BSIToFreeListObj]): ARRAY
				*   [wpp+SIZE[BSIToFreeListObj]..2*wpp) OF WORD,
MC[ZCT.bsiToSize, 1000];	* bsiToSize (2*wpp): BSIToSizeObj,
				* unused3 (2*wpp+SIZE[BSIToSizeObj]): ARRAY
				*   [2*wpp+SIZE[BSIToSizeObj]..3*wpp) OF WORD,
MC[ZCT.sizeToBSI, 1400];	* sizeToBSI (3*wpp): SizeToBSIObj,
				* unused4 (3*wpp+SIZE[SizeToBSIObj]): ARRAY
				*   [3*wpp+SIZE[SizeToBSIObj]..5*wpp) OF WORD,
MC[ZCT.fosTable, 2400];		* fosTable (5*wpp): FOSTableObject];

				* wpp: CARDINAL = PrincOps.wordsPerPage;
MC[zctBlockWords, 4000];	* zctBlockWords: INT = 8 * PrincOps.wordsPerPage;


* SizeToBSIObj: TYPE = PACKED ARRAY [0..maxSmallBlockSize] OF BlockSizeIndex;
* BSIToSizeObj: TYPE = ARRAY BlockSizeIndex OF CARDINAL;
* BSIToFreeListObj: TYPE = ARRAY BlockSizeIndex OF FNHeaderP;
MC[maxSmallBlockSize, 1076];	* maxSmallBlockSize: CARDINAL = 1076B;
MC[maxBSI, 77];			* BlockSizeIndex: TYPE = [0..77B];
MC[bsiEscape, maxBSI];		* bsiEscape: BlockSizeIndex = LAST[BlockSizeIndex];
* -- Note: sizes do not include NormalHeader overhead (2 words)

* FOSTableObject: TYPE = ARRAY FOSTableIndex OF FOSTableResidue;
* FOSTableIndex: TYPE = [0..FOSTableLength);
* FOSTableResidue: TYPE = CARDINAL;
* -- except for fosWildCard and fosEmpty, FOSTableResidues will be in [0..3777B]
* -- with a 24-bit virtual address and in [0..77777B] with a 28-bit VA.
MC[fosWildCard, 177777];	* fosWildCard: FOSTableResidue = 177777B; -- must be -1
MC[fosEmpty, 100000];		* fosEmpty: FOSTableResidue = 100000B;
MC[FOSTableLength, 10000];	* FOSTableLength: CARDINAL = 10000B;

*-----------------------------------------------------------
* Trap parameter values -- from RCMicrocodeImpl.mesa
*-----------------------------------------------------------

MC[tpRCOverflowOccurred, 1];
MC[tpUCDisabled, 2];
MC[tpRCUnderflowOccurred, 3];
MC[tpZCTFull, 4];
MC[tpRCBug, 5];
MC[tpLookFurtherAtReclaimedRef, 6];
MC[tpNormalFreeListEmpty, 6];


*-----------------------------------------------------------
* R registers
*-----------------------------------------------------------

Set[!RCRegs, !Region15];	* RMRegion[RCRegs] -- move to RegisterDefs someday
SetRMRegion[RCRegs];

RVN[RCFlags];	* B0=1 => microcode enabled, 0 disabled
		* B15 = copy of zct.markingDecrements
		* If RCFlags is entirely zero then ASSIGNREF gives control to the
		* corresponding opcode (WCLB) in the old RC microcode.
RVN[WPOffset];	* Write pointer, relative to WPBR
RVN[RCWord];	* Contents of RC word at nhp↑
RV[ZCTBlockLink, Sub[zctBlockWords!, 2]];  * Offset of link cell in ZCTBlock
RVN[RCTemp0];
RVN[RCTemp1];
RVN[RCTemp2];
RVN[RCTemp3];


*-----------------------------------------------------------
* Base registers -- move these to ADefs someday
*-----------------------------------------------------------

* Following 2 registers are an even/odd pair
BR[ZCTBR, 6];	* pointer to ZCT
BR[WPBR, 7];	* cached version of ZCT.wp

* Following 2 registers are an even/odd pair and are IFU-addressable
* BR[LPtr, 34];	* Defined in DMesaDefs
BR[BR35, 35];

TopLevel;

*-----------------------------------------------------------
AllocateM: MiscTable[145],
* Timing: 40 cycles normal, 46 max (+ MISC dispatch)
*-----------------------------------------------------------

* type: SafeStorage.Type = Pop[];
* size: CARDINAL = Pop[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase← RBase[RCRegs], StkP-2;
	MemBase← ZCTBR, RCFlags, Branch[RCDisabledTrap3, R>=0];

* IF size>maxSmallBlockSize THEN {PushLong[NIL]; RETURN};
	T← HighByte[maxSmallBlockSize];
	T← T OR (LowByte[maxSmallBlockSize]);
	PD← (Stack)-T-1;
	T← (Stack) RSH 1,		* T← size/2
		Branch[.+2, Carry'];
	 T← Stack&+1← A0, Branch[PushT];

* bsi: BlockSizeIndex = zct.sizeToBSI[size];
* fnhp: FNHeaderP = zct.bsiToFreeList[bsi];
* nhp: NHeaderP = @fnhp.fnh;  -- no-op (just a type conversion)
* IF fnhp=NIL THEN OpcodeTrap[tpNormalFreeListEmpty];
	T← T+(ZCT.sizeToBSI);		* Fetch[@zct.sizeToBSI[size]]↑
	Fetch← T, RCTemp2← RShift[ZCT.bsiToFreeList!, 1]C;
	T← MD, Stack&+1, Branch[.+2, R odd];
	 T← RSH[T, 10], Branch[.+2];	* Extract left (even) byte
	 T← T AND (377C);		* Extract right (odd) byte
	RCTemp2← ((RCTemp2)+T) LSH 1;	* Index into double-word array
	T← (Fetch← RCTemp2)+1;		* Fetch[@zct.bsiToFreeList[bsi]]↑
	T← MD, Fetch← T;
	RCTemp0← T, MemBase← LPtr;
	RCTemp1← MD, PD← (BRLo← T) OR (MD);
	T← A0, BRHi← RCTemp1, Branch[NormalFreeListEmptyTrap, ALU=0];

* -- touch fnhp.nextFree to ensure it won't fault later
* OnZ[nhp];
* nhp.maybeOnStack ← zct.markingDecrements;
* nhp.type ← type;
* Note that nhp is in RCTemp1,,RCTemp0 at this point.
	Fetch← T, T← NFH.nextFree;	* Fetch RCword at nhp↑		
	RCWord← RCFlags;		* nhp.maybeOnStack ← zct.markingDecrements
	RCWord← DPF[RCWord, 1, MaskPos[NHR.maybeOnStack!], MD];
	Fetch← T,			* Touch fnhp.nextFree before calling OnZCT
		T← RCTemp0, Call[OnZCT]; * Put on ZCT; update RCWord and return T=0

* No page faults are possible after here.
	T← (Store← T)+1, DBuf← RCWord;	* Store updated RCWord at nhp↑
	T← (Store← T)+1, DBuf← Stack&-1, * Store type at nhp.type
		Call[FetchGetsT];	* Fetch fnhp.nextFree

* zct.bsiToFreeList[bsi] ← fnhp.nextFree;
* fnhp.nextFree ← NIL;
	T← (Store← T)+1, DBuf← 0C, RCTemp3← MD, Call[FetchGetsT];
	Store← T, DBuf← 0C;
	T← RCTemp3, MemBase← ZCTBR;
	RCTemp2← (Store← RCTemp2)+1, DBuf← T, T← MD; * Store[@zct.bsiToFreeList[bsi]]
	Store← RCTemp2, DBuf← T;

* PushLong[NHPToRef[nhp]];
	T← (RCTemp0)+(sizeNH);
	Stack&+1← T;
	T← A← RCTemp1, XorSavedCarry, Branch[PushT];

*-----------------------------------------------------------
FreeM: MiscTable[146],
* Timing: 23 + 1.25 * object size in words (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase← RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase← LPtr and loads BRHi
	T← A0, BRLo← Stack;

* bsi: BlockSizeIndex = nhp.blockSizeIndex;
* IF bsi=bsiEscape THEN {Push[FALSE]; RETURN};
* fnhp: FNHeaderP = LOOPHOLE[nhp]; -- no-op (just a type conversion)
	Fetch← T;			* Fetch[@nhp.rcWord]↑
	T← MD, MemBase← ZCTBR;
	RCTemp0← LDF[T, MaskSize[NHR.blockSizeIndex!], MaskPos[NHR.blockSizeIndex!]];
	PD← (RCTemp0)#(bsiEscape);
	T← (RCTemp0)+(ZCT.bsiToSize), Branch[.+2, ALU#0];
	 Stack← A0, IFUNext0;		* Just return FALSE

* Zero[nhp+SIZE[NormalHeader], zct.bsiToSize[bsi]-SIZE[NormalHeader]];
	Fetch← T,			* Fetch[@zct.bsiToSize[bsi]]↑
		RCTemp3← Add[sizeNH!, 40]C;
	RCTemp2← ID, T← MD, MemBase← LPtr; * RCTemp2← sizeNH
	RCTemp1← T-(sizeNH)-1;

* On first iteration, do ((count-1) mod 20B)+1 words;
* on subsequent iterations, do 20B words.
* RCTemp1 = (remaining count)-1; RCTemp2 = current displacement;
* RCTemp3 = current displacement + 40B (for PreFetches);
* Carry=0 iff count is exhausted.
FreeZMunch:
	T← (RCTemp1) AND (17C),		* T ← (# words to do this iteration)-1
		Branch[FreeZDone, Carry'];
	RCTemp3← PreFetch← RCTemp3, Carry20, * PreFetch 40B words ahead
		Branch[.+2, Reschedule'];
	 StkP+1, Branch[MesaReschedTrap];
	Cnt← T;
	RCTemp2← (Store← RCTemp2)+1, DBuf← 0C, Branch[., Cnt#0&-1];
	RCTemp1← (RCTemp1)-T-1, Branch[FreeZMunch]; * Update count

* No page faults are possible after here.
* fnhp.fnh.type ← nullType;
* fnhp.nextFree ← zct.bsiToFreeList[bsi];
* zct.bsiToFreeList[bsi] ← fnhp;
* Push[TRUE];
FreeZDone:
	T← (RCTemp0)+(RCTemp0), MemBase← ZCTBR; * Indexing into double-word array
	T← T+(ZCT.bsiToFreeList),
		Call[FetchGetsT];	* Fetch[@zct.bsiToFreeList[bsi]]↑ -- low half
	RCTemp0← MD,
		T← (Store← T)+1, DBuf← Stack&+1, * Store[@zct.bsiToFreeList[bsi]]↑ ← fnhp
		Call[FetchGetsT];	* Same for high half
	RCTemp1← MD, Store← T, DBuf← Stack&-1, T← A0;
	Stack← T+1, MemBase← LPtr;	* Stack← 1 (= TRUE)
	T← (Store← NH.type)+1, DBuf← T;	* nhp.type ← nullType
	T← (Store← T)+1, DBuf← RCTemp0;	* fnhp.nextFree ← ptr fetched from bsiToFreeList
	Store← T, DBuf← RCTemp1, IFUNext0;

*-----------------------------------------------------------
IFUR[ASSIGNREF, 2, L];
IFUR[ASSIGNREFNEW, 2, L];
* Timings:	lhs↑	rhs	min	max (assuming no trap)
*		=NIL	=NIL	11	11
*		#NIL	=NIL	27	43
*		=NIL	#NIL	25	25
*		#NIL	#NIL	31	47  (except 11 if lhs↑=rhs)
*-----------------------------------------------------------

* RCTemp0, RCTemp1: lnhp (= lhs-SIZE[NormalHeader]), arg to OnZCT
* RCTemp2: (updated) header word at rnhp↑
* RCTemp3: alpha byte of opcode
* RCWord: (updated) header word at lnhp↑
* ScratchBR: lhs
* LPtr: lnhp
* BR35: rnhp
* Cnt is used as a flag: Cnt=0 means rhs=NIL.

* lhs: LONG POINTER TO REF = PopLong[]+GetCodeByte[];
* rhs: REF = PopLong[];
* rrc: RefCount;
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase← RBase[RCRegs];
	PD← RCFlags, MemBase← ScratchBR, Branch[RCDisabledTrap1, R>=0];

* IF lhs↑=rhs THEN RETURN;
* Overlapped with this test, load lhs into BR35 and save away lhs↑ in
* RCTemp1,,RCTemp0.  Also save the alpha byte in RCTemp3.
	BRHi← Stack&-1;	
	BRLo← Stack&-2;
	T← (Fetch← ID)+1;		* Fetch[lhs+alpha]↑
	RCTemp3← (Fetch← T)-1, T← MD;
	PD← (Stack&+1)#T, Cnt← 1S;
	RCTemp0← T, MemBase← BR35, Branch[.+2, ALU#0];
	 PD← (BRHi← Stack&-1)#MD, Branch[.+2]; * Low halves equal, compare high

* IF rhs#NIL THEN {
*   rnhp: NHeaderP = LOOPHOLE[rhs - SIZE[NormalHeader]];
*   rrc ← rnhp.refCount;
*   IF rrc = LAST[RefCount] THEN OpcodeTrap[tpRCOverflowOccurred]};
	 PD← (BRHi← Stack&-1)-(Stack&-1)-1;
	T← (Stack&+1)-(sizeNH),		* Convert REF to NHeaderP
		Branch[.+2, ALU#0];	* Complete ref equal test
	 StkP-2, IFUNext0;		* Equal, nothing to do
	T← Stack&-1, BRLo← T, Branch[.+3, Carry];
	 RCTemp1← MD, T← T-1, Branch[RHSNIL, ALU=0];
	 BRHi← T;
	RCTemp1← MD, Fetch← 0S;		* Fetch[rnhp]↑
	RCTemp2← LShift[1, MaskPos[NHR.refCount!]]C;
	RCTemp2← (RCTemp2)+MD, MemBase← LPtr; * Add 1 to ref count and see if it wraps
	PD← (RCTemp2) AND (NHR.refCount);
	RCTemp2← (RCTemp2) AND NOT (NHR.maybeOnStack), * Prepare for later update to rnhp↑
		DblBranch[RCOverflowTrap, CheckLHS, ALU=0];

* ASSIGNREF (cont'd)

* IF lhs↑#NIL THEN {
*   lnhp: NHeaderP = LOOPHOLE[lhs - SIZE[NormalHeader]];
*   lrc: RefCount ← lnhp.refCount;
*   CheckForRCUnderflow[lnhp];
*   IF lrc=1 AND ~nhp.rcOverflowed THEN OnZ[lnhp];
*   lnhp.maybeOnStack ← zct.markingDecrements;
*   lnhp.refCount ← lrc-1};
RHSNIL:
	MemBase← LPtr;
* This branch always goes to .+2 and is executed solely for its side-effect
* of setting Cnt← 0.
	BRHi← RCTemp1, DblBranch[.+2, .+3, Cnt#0&-1];

* RCTemp2 remembers new value for RCWord at rnhp↑ if non-NIL (Cnt=0 if rhs=NIL);
* Current MemBase = LPtr.  lhs↑ was already fetched and saved in RCTemp1,,RCTemp0.
CheckLHS:
	 BRHi← RCTemp1;
	RCTemp0← T← (RCTemp0)-(sizeNH);	* Convert REF to NHeaderP in RCTemp1,,RCTemp0
	PD← RCTemp1, BRLo← T, Branch[.+3, Carry];
	 RCTemp1← (RCTemp1)-1, Branch[LHSNIL, ALU=0];
	 BRHi← RCTemp1;
	Fetch← 0S, T← RCFlags;		* Fetch[lnhp]↑
	RCWord← DPF[T, 1, MaskPos[NHR.maybeOnStack!], MD],
					* nhp.maybeOnStack ← zct.markingDecrements
		Call[CheckForRCUnderflow]; * Returns with ALU = decremented refCount
	T← A0, Branch[.+3, ALU#0];	* Branch if refCount not zero
	 T← RCTemp0, Call[OnZCT];	* Put lnhp in ZCT and update flags in RCWord
	 T← A0;
	Store← T, DBuf← RCWord,		* Store[lnhp]↑
		FlipMemBase,		* MemBase← BR35
		DblBranch[DoRCAssign, UpdateRHS, Cnt=0&-1];

* IF rhs#NIL THEN {
*   rnhp.refCount ← rrc+1;
*   rnhp.maybeOnStack ← FALSE};
* RCTemp2 contains rnhp↑ with refCount and maybeOnStack already updated.
LHSNIL:
	MemBase← BR35, Branch[.+2, Cnt=0&-1]; * Skip if rhs=NIL
UpdateRHS:
	 Store← 0S, DBuf← RCTemp2;

* lhs↑ ← rhs;
DoRCAssign:
	T← RCTemp3, MemBase← ScratchBR;	* Get back alpha
	T← (Store← T)+1, DBuf← Stack&+1; * Store low part of rhs
	Store← T, DBuf← Stack&-2, IFUNext0; * Store high part of rhs

*-----------------------------------------------------------
CreateRefM: MiscTable[143],
* Timing: 15 cycles normal, 22 max (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* nhp.maybeOnStack ← zct.markingDecrements;
* OnZ[nhp];
	RBase← RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase← LPtr and loads BRHi
	T← BRLo← Stack&-1;
	Fetch← 0S, RCTemp0← T;		* Fetch RCword
	T← RCFlags;
	RCWord← DPF[T, 1, MaskPos[NHR.maybeOnStack!], MD];
					* nhp.maybeOnStack ← zct.markingDecrements
	T← RCTemp0, Call[OnZCT];
	Store← 0S, DBuf← RCWord, IFUNext0;


*-----------------------------------------------------------
GetReferentTypeM: MiscTable[71],
* I believe this is obsolete in Cedar 5, but is still used by Cedar 4.
*-----------------------------------------------------------

	Branch[GetCanonicalReferentTypeM];


*-----------------------------------------------------------
GetCanonicalReferentTypeM: MiscTable[72],
* This implementation is compatible with both Cedar 4 and Cedar 5.
* Timing: 5 cycles (+ MISC dispatch)
*-----------------------------------------------------------

* ref: REF = PopLong[];
* IF ref=NIL THEN {Push[nullType]; RETURN};
* nhp: NHeaderP = LOOPHOLE[ref - SIZE[NormalHeader]];
* Push[nhp.type];
	StkP-2, MemBase← LPtr;
	PD← (BRLo← Stack) OR T;
	T← (BRHi← T)-T-1, Branch[.+2, ALU#0];
	 Stack← A0, IFUNext0;
	LongFetch← T, B← T, T← A0;	* Fetch[@nhp.type]↑ -- know @nhp.type = ref-1
* For Cedar 4 compatibility, must mask off some high-order bits.
	Stack← DPF[T, Sub[20, MaskSize[NHT.type!]], MaskSize[NHT.type!], MD],
		IFUNext0;

*-----------------------------------------------------------
ReclaimableRefM: MiscTable[144],
* Timing: 10 cycles min, 36 max (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* Push[CheckReclaimable[nhp, FALSE]];
	RBase← RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase← LPtr and loads BRHi
	T← BRLo← Stack;
	Nop;				* Placement
	Fetch← 0S, RCTemp0← T;		* Fetch RCword
	RCWord← MD,			* This may be updated by CheckReclaimable
		SCall[CheckReclaimable]; * Returns disposition in T
	 Store← 0S, DBuf← RCWord;	* +1: need to store RCWord back into nhp↑
	Stack← T, IFUNext0;		* +2: don't need to store; just return disposition


*-----------------------------------------------------------
ReclaimedRefM: MiscTable[140],
* Timing: 16 cycles min, 43 max (+ MISC dispatch)
*-----------------------------------------------------------

* ref: REF = PopLong[];
* ans: REF;
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* nhp: NHeaderP = LOOPHOLE[ref - SIZE[NormalHeader]];
* CheckForRCUnderflow[nhp];
	RBase← RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase← LPtr and loads BRHi
	T← (Stack)-(sizeNH);		* Convert REF to NHeaderP
	RCTemp0← A0, BRLo← T, Branch[.+3, Carry];
	RCTemp1← (RCTemp1)-1;		* Had to borrow from high part
	BRHi← RCTemp1;
	Fetch← RCTemp0, RCTemp0← T;	* Fetch rcWord
	RCWord← MD, Call[CheckForRCUnderflow]; * Decrements refCount

* SELECT CheckReclaimable[nhp, TRUE] FROM
*   continue => ans ← NIL;
*   reclaimIt => ans ← ref;
*   finalizeIt => OpcodeTrap[tpLookFurtherAtReclaimedRef];
*   ENDCASE;
* nhp.refCount ← nhp.refCount-1;
* PushLong[ans];
	Call[CheckReclaimable];		* Returns T = ALU = disposition
	BDispatch← T,			* Dispatch on disposition
		DispTable[1, 1, 1];	* Force CheckReclaimable always to return here
	T← RCWord;			* Prepare to RCWord back into nhp↑

* Note that CheckReclaimable may have called OnZCT only if disposition = continue.
* In particular, this means that if disposition = finalizeIt, no changes have
* been made anywhere in memory, so it's OK to trap at that point.  For the other
* cases, we are now committed to finish the opcode.
DispTable[3];
	T← Stack&+1← Store← 0S, DBuf← T, * disposition = continue: Push[NIL] and exit
		Branch[PushT];
	Store← 0S, DBuf← T,		* disposition = reclaimIt: leave ref on stack
		StkP+1, IFUNext0;
	T← tpLookFurtherAtReclaimedRef,	* disposition = finalizeIt: trap
		Branch[OpcodeTrap];

*-----------------------------------------------------------
EnableMicrocodeM: MiscTable[141],
*-----------------------------------------------------------

* zct ← PopLong[];
* -- Load microcode registers (currently zct, zct.wp, and zct.markingDecrements)
* ucDisabled ← FALSE;
* Push[CedarMicrocode.microcodeVersion --currently 3--];
* Note: since the header page of the ZCT is guaranteed to be resident, no precautions
* need be taken to ensure restartability after page faults.
	RBase← RBase[RCRegs], StkP-1;
	T← (ID)+1, MemBase← ZCTBR;	* T← microcodeVersion (know ID=2)
	BRHi← Stack&-1;			* ZCTBR ← zct
	Stack← T, BRLo← Stack;		* Stack ← microcodeVersion
	T← NOT (Fetch← ZCT.markingDecrements); * T← small negative number
	RCFlags← DPF[T, 17, 1, MD];	* RCFlags[0] ← 1,
					* RCFlags[15] ← zct.markingDecrements
	T← (Fetch← ZCT.wp)+1;		* Load zct.wp
	Fetch← T, WPOffset← MD,
		FlipMemBase;		* Flip to WPBR
	T← (WPOffset) AND NOT (Sub[zctBlockWords!, 1]C); * Mask out WP offset bits
	WPOffset← (BRLo← T) XOR (WPOffset), T← MD; * BR← base, WPOffset← offset
	BRHi← T, IFUNext0;


*-----------------------------------------------------------
DisableMicrocodeM: MiscTable[142],
*-----------------------------------------------------------

* [] ← PopLong[]; -- DISCARD zct arg; assume it's the same as the one we already have
* -- Dump any cached variable state (currently just zct.wp)
* ucDisabled ← TRUE;
* Note: since the ZCT is guaranteed to be resident, no precautions need be taken
* to ensure restartability after page faults.
	T← A0, RBase← RBase[RCRegs], StkP-3;
	RCFlags← T+1, MemBase← WPBR;	* RCFlags[0] ← 0, RCFlags word # 0
	DummyRef← WPOffset, T← MD,	* Compute WPBR+WPOffset
		FlipMemBase;		* Flip to ZCTBR
	RCTemp0← 7777C;
	RCTemp0← (RCTemp0) AND (VAHi);	* Damn hardware returns ones in VAHi[0:3]
	T← VALo;
	T← (Store← ZCT.wp)+1, DBuf← T;	* Store in ZCT.wp
	Store← T, DBuf← RCTemp0, IFUNext0; * Can't fault since ZCT is resident

* Subroutines

*-----------------------------------------------------------
CheckReclaimable:
* Enter: RCTemp1,,RCTemp0 = LONG POINTER TO NormalHeader (nhp)
*	RCWord = contents of word at nhp↑, with refCount field decremented
*		if there is a decrement pending
* Call:	SCall[CheckReclaimable];
* Exit: Traps if need to put in ZCT and the ZCT is full; otherwise:
*	T = ALU = disposition (0=continue, 1=reclaim, 2=finalize)
*	MemBase either unchanged or set to LPtr (i.e., unchanged if it
*		was equal to LPtr at the time of the call)
* Returns +1 if RCWord has been updated by this subroutine and needs to be stored
* back into memory, +2 otherwise.
* Clobbers T, RCTemp2
* Timing: continue, 2 or 3 cycles normally; 11 to 27 if need to put on ZCT;
*	14 if reclaim or finalize
*-----------------------------------------------------------
Subroutine;

* rc: RefCount ← nhp.refCount;
* IF decrPending THEN rc ← rc-1;  -- done by caller
* IF rc#0 OR nhp.rcOverflowed OR nhp.inZCT THEN RETURN [continue];
	PD← (RCWord) AND (OR[NHR.refCount!, NHR.rcOverflowed!]C),
		Branch[.+2, R>=0];
	 T← A0, RCFlags, Return[R<0];	* Return +2 always
	PD← (RCWord)+(RCWord), Branch[.+2, ALU=0];
	 T← A0, RCFlags, Return[R<0];	* Return +2 always

* IF nhp.maybeOnStack OR FoundInFHSnapshot[nhp] THEN OnZ[nhp]
* ELSE RETURN [IF nhp.finalizable THEN finalizeIt ELSE reclaimIt];
	T← RCTemp0, Branch[.+2, ALU>=0]; * OnZCT if maybeOnStack (bit 1)
	 Branch[OnZCTTail];		* Call OnZCT and return +1

* -- Expanded in-line:
* FOSTableHash: PROC [nhp: NHeaderP] RETURNS [x: FosTableIndex, r: FOSTableResidue] = {
*   r ← BITOR[BITSHIFT[HighHalf[nhp], 3], BITSHIFT[LowHalf[nhp], -13]];
*   x ← BITAND[BITXOR[BITSHIFT[LowHalf[nhp], -1], r], FOSTableLength-1]};
* For a 28-bit address space, residue is 15 bits derived from high[4..15],,low[0..2];
* index is 12 bits derived from low[3..14] and hashed with the residue.
* low[15] is ignored since REFs are always even.
	RCTemp2← LDF[T, 14, 1];		* log[FOSTableLength] bits of nhp
	T← RCY[RCTemp1, T, 15];		* residue
	RCTemp2← (RCTemp2) XOR T, MemBase← ZCTBR; * hash the index bits with residue
	RCTemp2← (RCTemp2) AND (Sub[FOSTableLength!, 1]C); * mod FOSTableLength

* -- Expanded in-line:
* FoundInFHSnapshot: PROC [nhp: NHeaderP] RETURNS [found: BOOLEAN ← FALSE] = {
*   index: FOSTableIndex;
*   residue, entry: FOSTableResidue;
*   [index, residue] ← FOSTableHash[nhp];
*   entry ← zct.fosTable[index];
*   RETURN [entry=residue OR entry=fosWildCard]};
	RCTemp2← (RCTemp2)+(ZCT.fosTable);
	Fetch← RCTemp2;			* Fetch[@zct.fosTable[index]]↑;
	PD← T XOR MD, MemBase← LPtr;	* Compare residue with entry
	PD← NOT MD, Branch[.+2, ALU#0];
	 T← RCTemp0, Branch[OnZCTTail];	* residue = entry
	T← LDF[RCWord, 1, MaskPos[NHR.finalizable!]], Branch[.+2, ALU#0];
	 T← RCTemp0, Branch[OnZCTTail];	* entry = fosWildCard
	T← T+1, RCFlags, Return[R<0];	* reclaimIt=1, finalizeIt=2; return +2 always

*-----------------------------------------------------------
OnZCT:			* Puts reference in Zero Count Table
* Enter: RCTemp1,,T = LONG POINTER TO NormalHeader (nhp)
*	RCWord = contents of word at nhp↑
* Exit: Traps if the ZCT is full; otherwise:
*	RCWord updated but not stored back into memory
*	T = ALU = 0 (for the convenience of CheckReclaimable)
*	MemBase = LPtr
* Timing: 7 cycles usually, 13 if need to chain to a new ZCT block.
*-----------------------------------------------------------
Subroutine;

* wp: LONG POINTER TO NHeaderP;
* IF nhp.inZCT THEN RETURN;
* wp ← zct.wp;
* wp↑ ← nhp;
* wp ← wp+SIZE[LONG POINTER];
	MemBase← WPBR, RCWord,
		DblBranch[AlreadyInZCT, PutInZCT, R<0]; * Test nhp.inZCT

* Duplicate entry point: tail of CheckReclaimable
OnZCTTail:
	MemBase← WPBR, RCWord, DblBranch[AlreadyInZCT, PutInZCT, R<0];

AlreadyInZCT:
	T← A0, MemBase← LPtr, Return;

PutInZCT:
	T← (Store← WPOffset)+1, DBuf← T; * Store low half -- this can fault
	WPOffset← T← (Store← T)+1, DBuf← RCTemp1; * Store high half -- this cannot fault

* IF BITAND[LowHalf[wp], zctBlockWords-1] = zctBlockWords-SIZE[LONG POINTER] THEN
*   IF (wp ← LOOPHOLE[wp↑]) = NIL THEN OpcodeTrap[tpZCTFull];
* nhp.inZCT ← TRUE;
* zct.wp ← wp;
	PD← T XOR (ZCTBlockLink);
	RCWord← (RCWord) OR (NHR.inZCT),
		Branch[ZCTNotFull, ALU#0];

* This block is now full; attempt to follow link to next.  If a trap occurs, the
* cell into which we just stored will appear not to have been used.
	T← (Fetch← T)+1;
	WPOffset← (Fetch← T)-(3C),	* Restore wp to original value in case we trap
		T← MD;
	PD← T OR MD;
	Branch[RCZCTFullTrap, ALU=0];	* Branch if it is NIL
	BRLo← T, T← MD;			* Set new ZCT block base and reset offset
	BRHi← T, WPOffset← A0;
ZCTNotFull:
	T← A0, MemBase← LPtr, Return;

*-----------------------------------------------------------
CheckForRCUnderflow:
* Enter: RCWord = word containing RefCount to be checked
* Exit: Traps if the RefCount has underflowed; otherwise:
*	RCWord = entire word with refCount decremented
*	ALU = value of refCount and rcOverflowed fields
* Clobbers T
* Timing: 3 cycles normally
*-----------------------------------------------------------
Subroutine;

* IF nhp.refCount=0 THEN
*   IF nhp.rcOverflowed THEN OpcodeTrap[tpRCUnderflowed] ELSE OpcodeTrap[tpRCBug];
	PD← (RCWord) AND (NHR.refCount);
	RCWord← (RCWord)-(LShift[1, MaskPos[NHR.refCount!]]C), * Decrement refCount
		Branch[RefCountZero, ALU=0];
	PD← (RCWord) AND (OR[NHR.refCount!, NHR.rcOverflowed!]C), Return;

RefCountZero:				* Underflow if rcOverflowed, bug otherwise
	RCWord, DblBranch[RCUnderflowTrap, RCBugTrap, R odd];


*-----------------------------------------------------------
DisableNewRCMicrocode:
* Called from RTSETUP opcode in DMesaReclaim to disable the new RC microcode
* and take over the ASSIGNREF opcode.
*-----------------------------------------------------------
Subroutine;
DontKnowRBase;

	RCFlags← A0, Return;


*-----------------------------------------------------------
FetchGetsT:
*-----------------------------------------------------------
Subroutine;

	PD← Fetch← T, Return, Global;

*-----------------------------------------------------------
TrapIfRCDisabled:
* Enter: RBase = RCRegs
*	T = word to be loaded into high part of LPtr
* Exit: Traps if RC microcode is disabled; otherwise:
*	MemBase = LPtr
*	BRHi = RCTemp1 = T at call
* Timing: 2 cycles
*-----------------------------------------------------------
Subroutine;
KnowRBase[RCRegs];

	MemBase← LPtr, RCFlags, Branch[RCDisabledTrap2, R>=0];
	RCTemp1← BRHi← T, Return;


*-----------------------------------------------------------
* Traps
*-----------------------------------------------------------
TopLevel;

RCOverflowTrap:
	T← tpRCOverflowOccurred, Branch[OpcodeTrap];
RCDisabledTrap1:
* This is the trap from ASSIGNREF.  If RCFlags is entirely zero then
* invoke the WCLB opcode in the old RC microcode.  ALU = RCFlags here.
	MemBase← LPtr, Branch[.+2, ALU=0];
	 T← tpUCDisabled, Branch[OpcodeTrap];
	Branch[OldWCLB];
RCDisabledTrap2:
	T← tpUCDisabled, Branch[OpcodeTrap];
RCDisabledTrap3:
	T← tpUCDisabled, Branch[OpcodeTrap];
RCUnderflowTrap:
	T← tpRCUnderflowOccurred, Branch[OpcodeTrap];
RCZCTFullTrap:
	T← tpZCTFull, Branch[OpcodeTrap];
RCBugTrap:
	T← tpRCBug, Branch[OpcodeTrap];
NormalFreeListEmptyTrap:
	T← tpNormalFreeListEmpty, Branch[OpcodeTrap];


*-----------------------------------------------------------
* Unused MISC opcodes
*-----------------------------------------------------------

	MiscOpcodeUnimplemented[147];
	MiscOpcodeUnimplemented[150];
	MiscOpcodeUnimplemented[151];
	MiscOpcodeUnimplemented[152];
	MiscOpcodeUnimplemented[153];
	MiscOpcodeUnimplemented[154];
	MiscOpcodeUnimplemented[155];
	MiscOpcodeUnimplemented[156];
	MiscOpcodeUnimplemented[157];