-- RTRefAccounting.Mesa

--  last edited  2-Sep-81 16:28:12 by Willie-Sue Haugeland
--  last edited 8-Feb-82 11:47:23 by Paul Rovner

DIRECTORY
  Inline USING[LongNumber, BITXOR, BITSHIFT, LowHalf, HighHalf],
  RTRefCounts,
  Runtime USING[GlobalFrame],
  SpecialSpace USING[MakeCodeResident, MakeGlobalFrameResident];

RTRefAccounting: PROGRAM
  IMPORTS RTRefCounts, Inline, SpecialSpace, Runtime
= BEGIN
  OPEN RTRefCounts;
  
  RCEntriesSummary: TYPE =
     RECORD [empty: CARDINAL_ 0, normal: CARDINAL_ 0, overflow: CARDINAL_ 0];

  distributionSummary: TYPE = RECORD
                  [ LTrcFinalize: CARDINAL_ 0,
                    EQrcFinalize: CARDINAL_ 0,
		    rcFinalizePlus1: CARDINAL_ 0,
                    rcFinalizePlus2: CARDINAL_ 0,
                    rcFinalizePlus3: CARDINAL_ 0,
		    rcFinalizePlus4: CARDINAL_ 0,
		    rcFinalizePlus5: CARDINAL_ 0,
		    rcFinalizePlus5Plus: CARDINAL_ 0,
		    rcCountPegged: CARDINAL_ 0
		  ];

  oiLengthsSummary: TYPE = RECORD
                [ two: CARDINAL_ 0,
                  threeTo5: CARDINAL_ 0,
		  sixTo9: CARDINAL_ 0,
                  tenTo29: CARDINAL_ 0,
		  GEThirty: CARDINAL_ 0
	        ];

  chainHead: TYPE = RECORD [ pi: ProbeIndex_ 0, length: INTEGER_ 0];

  longOiChainsSummary: TYPE = ARRAY (0..5] OF chainHead;
   		  
  RefCountsSummary: TYPE = RECORD
   [ nRCEntries: RCEntriesSummary,
     distribution: distributionSummary,
     oiLengths: oiLengthsSummary,
     firstNormalEntry: ProbeIndex_ 0,
     firstOiEntry: ProbeIndex_ 0,
     numOiInUse: INTEGER_ 0,
     longOiChains: longOiChainsSummary
   ];

  chainEntries: TYPE = ARRAY (0..10] OF LONG POINTER;

  OverflowChain: TYPE = RECORD [num: INTEGER_ 0, cEntries: chainEntries];
  mappirce: LONG POINTER TO AMapPiRce_ RTRefCounts.GetMapPiRce[];
  mapoioe: LONG POINTER TO AMapOiOe_ RTRefCounts.GetMapOiOe[];  

  SummarizeCounts: PROC RETURNS[SummaryOfRefCounts: RefCountsSummary] =
   BEGIN
   firstNormalSeen: BOOLEAN_ FALSE;
   firstOiSeen: BOOLEAN_ FALSE;
   longOiIndex: INTEGER_ 0;
   lowestOi: INTEGER_ LAST[INTEGER];
   SummaryOfRefCounts_ [,,,,,,];
   
   FOR pi: ProbeIndex IN [0..LAST[ProbeIndex]] DO
    { rce: RCEntry _ mappirce[pi];
      IF rce = rceEmpty THEN
       SummaryOfRefCounts.nRCEntries.empty_ SummaryOfRefCounts.nRCEntries.empty+1
      ELSE
       WITH rce: rce SELECT FROM
        normal =>
        { SummaryOfRefCounts.nRCEntries.normal_ SummaryOfRefCounts.nRCEntries.normal+1;
          DoRCaccounting[@SummaryOfRefCounts, rce];
	  IF ~firstNormalSeen THEN {SummaryOfRefCounts.firstNormalEntry_ pi; firstNormalSeen_ TRUE};
	 };
        overflow =>
	{ len: INTEGER_ 0;
	  oiFirst: MapOiOeIndex _ rce.oi;
          pOe: LONG POINTER TO OverflowEntry;
          oi: MapOiOeIndex _ oiFirst;

          SummaryOfRefCounts.nRCEntries.overflow_ SummaryOfRefCounts.nRCEntries.overflow+1;
	 IF ~firstOiSeen THEN {SummaryOfRefCounts.firstOiEntry_ pi; firstOiSeen_ TRUE};
	 DO
	  BEGIN
	   pOe_ @mapoioe[oi];
	   len_ len + 1;
	   DoRCaccounting[@SummaryOfRefCounts, pOe.rce];
	   WITH rce: pOe.oe1 SELECT FROM
	    normal => {len_ len + 1; DoRCaccounting[@SummaryOfRefCounts, rce]; EXIT};
	    overflow => oi _ rce.oi;
	   ENDCASE;
	  END;
	  ENDLOOP;
	  SummaryOfRefCounts.numOiInUse_ SummaryOfRefCounts.numOiInUse + len;

	  DoOiLengthAccounting[@SummaryOfRefCounts, len];
	  IF longOiIndex < 5 THEN
	  { longOiIndex_ longOiIndex+ 1;
	    SummaryOfRefCounts.longOiChains[longOiIndex]_ [pi: pi, length: len];
	    IF len < lowestOi THEN lowestOi_ len;
	  }
	  ELSE
	  { IF len > lowestOi THEN
	     FOR i: INTEGER IN (0..5] DO
	      IF SummaryOfRefCounts.longOiChains[i].length = lowestOi THEN
	       { SummaryOfRefCounts.longOiChains[i]_ [pi: pi, length: len];
	         FOR j: INTEGER IN (i..5] DO
		  IF SummaryOfRefCounts.longOiChains[j].length = lowestOi THEN GO TO done; ENDLOOP;
		 lowestOi_ len; EXIT;
	        };
	     REPEAT
	       done => NULL;
	     ENDLOOP;
           };
	};
       ENDCASE;
     };
   ENDLOOP;
  END;

  FollowOiChain: PROC[pi: ProbeIndex] RETURNS[OiChain: OverflowChain] =
   {  len: INTEGER_ 0;
       nrce: RCEntry_ mappirce[pi];
       pOe: LONG POINTER TO OverflowEntry;
       oi: MapOiOeIndex;
       OiChain_ [,];
       
       FOR i: INTEGER IN (0..10] DO OiChain.cEntries[i]_ NIL; ENDLOOP;

       WITH nrce: nrce SELECT FROM
        overflow =>
        { oi_ nrce.oi;
          DO
          { pOe_ @mapoioe[oi];
            len_ len + 1;
	    OiChain.cEntries[len]_ LOOPHOLE[RcePiToRef[pOe.rce, pi], LONG POINTER];
	    IF len > 10 THEN EXIT;
	    WITH nrce: pOe.oe1 SELECT FROM
	     normal =>		-- end of chain
	      { OiChain.cEntries[len]_ LOOPHOLE[RcePiToRef[pOe.oe1, pi], LONG POINTER];
	       EXIT;
	      };
	     overflow => oi _ nrce.oi;
	     ENDCASE;
           };
	  ENDLOOP;
	};
       ENDCASE;
       OiChain.num_ len;
   };
    
  DoRCaccounting: PROC[SummaryOfRefCounts: LONG POINTER TO RefCountsSummary, rce: RCEntry] =
   { nrce: nRCEntry_ LOOPHOLE[rce, nRCEntry];
     SELECT nrce.rc FROM
	0,1,2 => SummaryOfRefCounts.distribution.LTrcFinalize_
	          SummaryOfRefCounts.distribution.LTrcFinalize+1;
	rcFinalize => SummaryOfRefCounts.distribution.EQrcFinalize_
	               SummaryOfRefCounts.distribution.EQrcFinalize+1;
	rcFinalize+1 => SummaryOfRefCounts.distribution.rcFinalizePlus1_
	               SummaryOfRefCounts.distribution.rcFinalizePlus1+1;
	rcFinalize+2 => SummaryOfRefCounts.distribution.rcFinalizePlus2_
	                 SummaryOfRefCounts.distribution.rcFinalizePlus2+1;
	rcFinalize+3 => SummaryOfRefCounts.distribution.rcFinalizePlus3_
	                 SummaryOfRefCounts.distribution.rcFinalizePlus3+1;
	rcFinalize+4 => SummaryOfRefCounts.distribution.rcFinalizePlus4_
	                 SummaryOfRefCounts.distribution.rcFinalizePlus4+1;
	rcFinalize+5 => SummaryOfRefCounts.distribution.rcFinalizePlus5_
	                 SummaryOfRefCounts.distribution.rcFinalizePlus5+1;
	LAST[RefCt] => SummaryOfRefCounts.distribution.rcCountPegged_
	                SummaryOfRefCounts.distribution.rcCountPegged+1;
	ENDCASE => SummaryOfRefCounts.distribution.rcFinalizePlus5Plus_
	            SummaryOfRefCounts.distribution.rcFinalizePlus5Plus+1;
   };
 
  DoOiLengthAccounting: PROC[SummaryOfRefCounts: LONG POINTER TO RefCountsSummary, len: INTEGER] =
   { SELECT len FROM
	0,1,2 => SummaryOfRefCounts.oiLengths.two_
	          SummaryOfRefCounts.oiLengths.two+1;
	IN [3..5] => SummaryOfRefCounts.oiLengths.threeTo5_
	              SummaryOfRefCounts.oiLengths.threeTo5+1;
	IN [6..9] => SummaryOfRefCounts.oiLengths.sixTo9_
	                SummaryOfRefCounts.oiLengths.sixTo9+1;
	IN [10..29] => SummaryOfRefCounts.oiLengths.tenTo29_
	                SummaryOfRefCounts.oiLengths.tenTo29+1;
	ENDCASE => SummaryOfRefCounts.oiLengths.GEThirty_
	            SummaryOfRefCounts.oiLengths.GEThirty+1;
   };

  RefToPiRes: PROC[ref: LONG CARDINAL] RETURNS [pi: ProbeIndex, res: Residue] =
    { OPEN Inline;
      res_ RefToRes[ref];
      pi_ LOOPHOLE[BITXOR[BITSHIFT[LowHalf[ref],-1], res], ProbeIndex]};
   
  RefToRes: PROC[ref: LONG CARDINAL] RETURNS [Residue] =
   { RETURN[Inline.HighHalf[ref]]};

  RcePiToRef: PROC[rce: RCEntry, pi: ProbeIndex] RETURNS[REF] =
    { OPEN Inline;
      nrce: nRCEntry_ LOOPHOLE[rce, nRCEntry];
      res: Residue = nrce.res;
      RETURN[LOOPHOLE[LongNumber[num[highbits: res,
                                     lowbits: BITSHIFT[BITXOR[pi, res], 1]]]]]};

  PiToRef: PROC[pi: ProbeIndex] RETURNS[REF] =
    { rce: RCEntry _ mappirce[pi];
      WITH rce SELECT FROM
       normal => RETURN[RcePiToRef[rce, pi]];
       ENDCASE => RETURN[NIL];
     };
      
-- *****************************

SpecialSpace.MakeCodeResident[Runtime.GlobalFrame[SummarizeCounts]];
SpecialSpace.MakeGlobalFrameResident[RTRefAccounting];

END.