--FILE: RandomCodeRandomProceduresImpl.mesa
--Last Edited by: Sturgis, October 10, 1984 3:34:28 pm PDT

DIRECTORY
 IO USING[STREAM],
 RandomCodeRandom USING[Random, RandomState],
 RandomCodeTypes USING[CreateSeqType, FillSeqType, GetLocalOffset, GetRemoteOffset, GetSeqTypeOfPointerType, GetSizeOfTypeSet, GetWordTypeFromIndex, SeqType, TypeSet, WordType],
 RandomCodeTypedProgramGraphs USING[AssignRelativeGraphNodeAddresses, BeginTypeCheck, CreateProcedureGraph, DummyNodesTable, GenGraphBytes, GetDummyTableSize, GetRandomDummyTableEntry, InsertSFCallInDummyArc, InsertSourceReduction, InsertTargetReduction, InsertTestA, GetDummyNodeOpShape, OpDescriptor, OpTypeClass, PGNode, PrintGraph, PrintSortGraph, ProcedureInfo, RemoveNullDummy, SplitADummyArc, TearDownGraph, TopResultOfDummyOp, TopTwoArgsOfDummyOp],
 RandomCodeDragonOps USING[GetEPOpForEntry, GetDragonOp, GetJBOpForJump, GetJDBOpForJump, GetRetOpForReturn, GetSFCOpForSFCall],
 RandomCodeRandomProcedures USING[],
 Rope USING[ROPE];

RandomCodeRandomProceduresImpl: CEDAR MONITOR IMPORTS RandomCodeRandom, RandomCodeTypes, RandomCodeTypedProgramGraphs, RandomCodeDragonOps EXPORTS RandomCodeRandomProcedures =

BEGIN
OPEN RandomCodeRandom, RandomCodeTypes, RandomCodeTypedProgramGraphs, RandomCodeDragonOps;

ProcedureBody: TYPE = REF ProcedureBodyData;
ProcedureBodyData: PUBLIC TYPE = RECORD[
 procedureInfo: ProcedureInfo];

ProcTypeTable: TYPE = RECORD[SEQUENCE nProcTypes: CARDINAL OF WordType];
 
GenerateRandomProcedure: PUBLIC PROCEDURE[allowedArgs, possibleResults: SeqType, typeSet: TypeSet, randomState: RandomState] RETURNS[ProcedureBody, INT] =
 BEGIN
 procedure: ProcedureBody;
 byteSize: INT;
 table: DummyNodesTable;
 tableSize: CARDINAL;
 frameExtension: SeqType ← MakeRandomSeqType[typeSet, randomState];
 procTypes: REF ProcTypeTable;
 nProcTypes: CARDINAL;
 
 RandomForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[Random[randomState]]};
 
 LocalSelectSourceReductionOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType] RETURNS[OpDescriptor, --nPop-- CARDINAL] =
  BEGIN
  op: OpDescriptor; nPop: CARDINAL;
  [op, nPop] ← GeneralSelectSourceReductionOp[dummyOp, locals, ordinaryWordType, randomState];
  RETURN[op, nPop];
  END;
  
 LocalSelectTargetReductionOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType] RETURNS[OpDescriptor, --nPush-- CARDINAL] =
  BEGIN
  op: OpDescriptor; nPop: CARDINAL;
  [op, nPop] ← GeneralSelectTargetReductionOp[dummyOp, locals, ordinaryWordType, randomState];
  IF op = NIL THEN ERROR;
  RETURN[op, nPop];
  END;
 
 SelectRandomProcType: PROCEDURE RETURNS[WordType] =
  {RETURN[procTypes[Random[randomState] MOD procTypes.nProcTypes]]};
 
 nProcTypes ← 0;
 FOR I: CARDINAL IN [0..GetSizeOfTypeSet[typeSet]) DO
  t: WordType ← GetWordTypeFromIndex[typeSet, I];
  IF t.type = procedure THEN nProcTypes ← nProcTypes + 1;
  ENDLOOP;
 procTypes ← NEW[ProcTypeTable[nProcTypes]];
 nProcTypes ← 0;
 FOR I: CARDINAL IN [0..GetSizeOfTypeSet[typeSet]) DO
  t: WordType ← GetWordTypeFromIndex[typeSet, I];
  IF t.type = procedure THEN
   BEGIN
   procTypes[nProcTypes] ← t;
   nProcTypes ← nProcTypes + 1;
   END;
  ENDLOOP;
 
 [procedure, table] ← CreateNewProcedureBody[allowedArgs, frameExtension, possibleResults, typeSet, RandomForDragon];
 TypeCheckProcedure[procedure];
 
 WHILE (tableSize ← GetDummyTableSize[table]) < 50 DO -- this depends on initialized size of table
  dummyNode: PGNode;
  r: CARDINAL ← Random[randomState] MOD 1000;
  IF tableSize = 0 THEN ERROR;
  dummyNode ← GetRandomDummyTableEntry[table, Random[randomState]];
  SELECT TRUE FROM
   r < 100 =>
    InsertSFCallInDummyArc[dummyNode, GetSFCOpForSFCall[], SelectRandomProcType[]];
   r < 383 => InsertTestA[dummyNode, GetDragonOp[TestX, RandomForDragon, NIL, NIL, NIL], TRUE];
   r < 716 => InsertTestA[dummyNode, GetDragonOp[TestX, RandomForDragon, NIL, NIL, NIL], FALSE];
   ENDCASE =>
    BEGIN
    new: SeqType ← MakeRandomSeqType[typeSet, randomState];
    SplitADummyArc[dummyNode, TRUE, 1, new];
    END;
  ENDLOOP;
  
 WHILE GetDummyTableSize[table] # 0 DO
  dummyNode: PGNode ← GetRandomDummyTableEntry[table, Random[randomState]];
  nArgs, nResults: CARDINAL;
  [nArgs, nResults] ← GetDummyNodeOpShape[dummyNode];
  IF nArgs > 0 AND nResults > 0 THEN
   BEGIN
   IF Random[randomState] MOD 1000 > 499 THEN
     InsertSourceReduction[dummyNode, LocalSelectSourceReductionOp]
    ELSE InsertTargetReduction[dummyNode, LocalSelectTargetReductionOp]
   END
   ELSE IF nArgs > 0 THEN
    InsertSourceReduction[dummyNode, LocalSelectSourceReductionOp]
   ELSE IF nResults > 0 THEN
    InsertTargetReduction[dummyNode, LocalSelectTargetReductionOp]
   ELSE
    RemoveNullDummy[dummyNode];
  ENDLOOP;
 
 byteSize ← AssignRelativeProcedureNodeAddresses[procedure];
 RETURN[procedure, byteSize]
 END;
 
CreateNewProcedureBody: PUBLIC PROCEDURE[allowedArgs, frameExtension, possibleResults: SeqType, typeSet: TypeSet, random: PROCEDURE RETURNS[CARDINAL]] RETURNS[ProcedureBody, DummyNodesTable] =
 BEGIN
 -- following procedures are to support the subsequent call to CreateProcedureGraph
 
 getEPOpForEntry: PROCEDURE[nArgs: CARDINAL] RETURNS[OpDescriptor] =
   {RETURN[GetEPOpForEntry[nArgs]]};

 getDragonOp: PROCEDURE[
  class: OpTypeClass,
  random: PROCEDURE RETURNS[CARDINAL],
  selectLocalIndex: PROCEDURE RETURNS[CARDINAL],
  selectRemoteIndex: PROCEDURE RETURNS[CARDINAL],
  selectLocalRemoteIndices: PROCEDURE RETURNS[l,r: CARDINAL]]
  RETURNS[OpDescriptor] =
   {RETURN[GetDragonOp[class, random, selectLocalIndex, selectRemoteIndex, selectLocalRemoteIndices]]};
  
 getRetOpForReturn: PROCEDURE[nRetWords: CARDINAL] RETURNS[OpDescriptor] =
   {RETURN[GetRetOpForReturn[nRetWords]]};
 
 procedureInfo: ProcedureInfo ← CreateProcedureGraph[allowedArgs, frameExtension, possibleResults, typeSet, random, getEPOpForEntry, getDragonOp, getRetOpForReturn];
 
 procedure: ProcedureBody ← NEW[ProcedureBodyData ← [procedureInfo]];
 
 RETURN[procedure, procedureInfo.dummyNodesTable];
 END;

PrintProcedureGraph: PUBLIC PROCEDURE[title: Rope.ROPE, procedure: ProcedureBody, on: IO.STREAM] =
 BEGIN
 IF NOT procedure.sorted THEN PrintSortGraph[procedure.entryNode];
 PrintGraph[title, procedure.entryNode, on]
 END;

GenProcedureBytes: PUBLIC PROCEDURE[procedure: ProcedureBody, oneByte: PROCEDURE[[0..255]]] =
 BEGIN
 IF NOT procedure.sorted THEN PrintSortGraph[procedure.entryNode];
 GenGraphBytes[procedure.entryNode, oneByte]
 END;

TypeCheckProcedure: PUBLIC PROCEDURE[procedure: ProcedureBody] =
 {BeginTypeCheck[procedure.entryNode]};

AssignRelativeProcedureNodeAddresses: PUBLIC PROCEDURE[procedure: ProcedureBody] RETURNS[size: INT] =
-- may have to install some extra jumps, or modify some conditional jumps
 BEGIN
 IF NOT procedure.sorted THEN PrintSortGraph[procedure.entryNode];
 RETURN[AssignRelativeGraphNodeAddresses[procedure.entryNode, GetJBOpForJump, GetJDBOpForJump]];
 END;

TearDownProcedure: PUBLIC PROCEDURE[procedure: ProcedureBody] =
 BEGIN
 IF NOT procedure.sorted THEN PrintSortGraph[procedure.entryNode];
 TearDownGraph[procedure.entryNode];
 END;

MakeRandomSeqType: PROCEDURE[typeSet: TypeSet, randomState: RandomState] RETURNS[SeqType] =
 BEGIN
 seqSize: CARDINAL ← Random[randomState] MOD 5;
 seq: SeqType ← CreateSeqType[typeSet, NIL, seqSize];
 typeSetSize: CARDINAL ← GetSizeOfTypeSet[typeSet];
 genWType: PROCEDURE[i: CARDINAL] RETURNS[WordType] =
  BEGIN
  x: CARDINAL ← Random[randomState] MOD typeSetSize;
  t: WordType ← GetWordTypeFromIndex[typeSet, x];
  WHILE t.type = uninitialized DO
   x ← Random[randomState] MOD typeSetSize;
   t ← GetWordTypeFromIndex[typeSet, x];
   ENDLOOP;
  RETURN[t];
  END;
 FillSeqType[seq, genWType];
 RETURN[seq];
 END;

GeneralSelectSourceReductionOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType, randomState: RandomState] RETURNS[OpDescriptor, --nPop-- CARDINAL] =
 BEGIN
 RandomForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[Random[randomState]]};
  
 SelectLocalWIndexForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[GetLocalOffset[locals, ordinaryWordType, Random[randomState]]]};
  
 SelectNilLocalIndexForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[LAST[CARDINAL]]};
 
 SelectLocalS0IndexForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[GetLocalOffset[locals, s0, Random[randomState]]]};
 
 s0, s1: WordType;
 
 [s0, s1] ← TopTwoArgsOfDummyOp[dummyOp];
 IF s0 = NIL THEN RETURN[NIL, 0];
 
 -- possible allowed ops affect the stack by popping off the s0, or by replacing <s0,s1> by <s1> or nothing. s0 is never NIL, but s1 may be NIL.
 IF s1 # NIL THEN -- see if we can insert an op which replaces top two of stack by one or zero. We treat exactly two cases: arithmetic operations on ordinary words, or storing through a pointer.
  BEGIN
  SELECT s1.type FROM
  ordinary =>
   BEGIN
   SELECT s0.type FROM
    ordinary =>
     BEGIN -- we do some arithmetic
     op: OpDescriptor ← GetDragonOp[PopWW, RandomForDragon, SelectLocalWIndexForDragon, NIL, NIL];
     IF op # NIL THEN RETURN[op, 2];
     END;
    ENDCASE => NULL;
   END;
  pointer =>
   BEGIN -- find a suitable field within s1 at which to store s0
   remoteSeq: SeqType ← GetSeqTypeOfPointerType[s1];
   offset: CARDINAL ← GetLocalOffset[remoteSeq, s0, Random[randomState]];
   op: OpDescriptor ← NIL;
   
   SelectRemoteTIndexForDragon: PROCEDURE RETURNS[CARDINAL] =
    {RETURN[offset]};
    
   IF offset # LAST[CARDINAL] THEN
    op ← GetDragonOp[PopSIT, RandomForDragon, NIL, SelectRemoteTIndexForDragon, NIL];
   IF op # NIL THEN RETURN[op, 2];
   END;
  ENDCASE => NULL;
  END;
 
 -- at this point we know that there is at least one item on top of stack 
 SELECT s0.type FROM
  ordinary =>
   BEGIN -- we do some arithmetic
   op: OpDescriptor ← GetDragonOp[PopW, RandomForDragon, SelectLocalWIndexForDragon, NIL, NIL];
   IF op # NIL THEN RETURN[op, 1];
   END;
  ENDCASE => NULL;
 
 -- finally, we try removing the top of stack by storing it locally
  BEGIN
  op: OpDescriptor ← GetDragonOp[PopT, RandomForDragon, SelectLocalS0IndexForDragon, NIL, NIL];
  IF op # NIL THEN RETURN[op, 1];
  END;
  
 -- if all else fails, we just remove the top of stack by popping it.
  BEGIN
  op: OpDescriptor ← GetDragonOp[PopW, RandomForDragon, SelectNilLocalIndexForDragon, NIL, NIL];
  IF op # NIL THEN RETURN[op, 1];
  END;
 ERROR;
 END;
 
GeneralSelectTargetReductionOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType, randomState: RandomState] RETURNS[OpDescriptor, --nPush-- CARDINAL] =
 BEGIN
 RandomForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[Random[randomState]]};
  
 SelectLocalWIndexForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[GetLocalOffset[locals, ordinaryWordType, Random[randomState]]]};
  
 SelectLocalTIndexForDragon: PROCEDURE RETURNS[CARDINAL] =
  {RETURN[GetLocalOffset[locals, t0, Random[randomState]]]};
 

 t0: WordType;
 
 t0 ← TopResultOfDummyOp[dummyOp];
 IF t0 = NIL THEN RETURN[NIL, 0];
 

 -- all allowed ops load <t0> onto the stack.
 
 -- first see if t0 is ordinary
 IF t0.type = ordinary THEN
  BEGIN
  op: OpDescriptor ← GetDragonOp[PushW, RandomForDragon, SelectLocalWIndexForDragon, NIL, NIL];
  IF op # NIL THEN RETURN[op, 1];
  END;
 
 -- next see if we can find a local t0
  BEGIN
  op: OpDescriptor ← GetDragonOp[PushT, RandomForDragon, SelectLocalTIndexForDragon, NIL, NIL];
  IF op # NIL THEN RETURN[op, 1];
  END;
 
 -- now see if we can find a remote t0, one indirection remote
  BEGIN
  localOffset: CARDINAL;
  remoteOffset: CARDINAL;
  
 SelectLocalRemoteIndexForDragon: PROCEDURE RETURNS[l,r: CARDINAL] =
  {RETURN[localOffset, remoteOffset]};
  
  [localOffset, remoteOffset] ← GetRemoteOffset[locals, t0, Random[randomState]];
  IF localOffset # LAST[CARDINAL] THEN
   BEGIN
   op: OpDescriptor ← GetDragonOp[PushFIT, RandomForDragon, NIL, NIL, SelectLocalRemoteIndexForDragon];
   IF op # NIL THEN RETURN[op, 1];
   END;
  END;
  
 -- can't see how to do it for now 
 ERROR;
 END;


  

END.

MODULE HISTORY

Initial by: Sturgis, October 8, 1984 11:41:09 am PDT, from RandomGraphs?