--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 by 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 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?