-- RandomCodeTypedProgramGraphs.mesa last edited by Sturgis: October 8, 1984 10:41:44 am PDT DIRECTORY IO USING[STREAM], RandomCodeTypes USING[SeqType, TypeSet, WordType], Rope USING[ROPE]; RandomCodeTypedProgramGraphs: CEDAR DEFINITIONS = BEGIN OPEN RandomCodeTypes; OpTypeClass: TYPE = {TestX, PushX, PushD, DecrX, PushW, PopW, PopWW, PopWPushW, PopWWPushW, PushT, PopT, StoreLocalT, PushFIT, PopSIT}; OpDescriptor: TYPE = REF OpDescriptorBody; OpDescriptorBody: TYPE = RECORD[ kind: OpKind, data: REF ANY]; OpKind: TYPE = REF OpKindBody; OpKindBody: TYPE = RECORD[ name: Rope.ROPE, Copy: PROCEDURE[OpDescriptor] RETURNS[OpDescriptor], NoteInstallation: PROCEDURE[OpDescriptor, PGNode], -- called when a node starts pointing to it Release: PROCEDURE[OpDescriptor, PGNode], -- called when a node stops pointing to it GetDummyOpShape: PROCEDURE[OpDescriptor] RETURNS[nArgs, nResults: CARDINAL], GetSize: PROCEDURE [OpDescriptor] RETURNS[INT], SetRelativeJump: PROCEDURE [OpDescriptor, INT], -- might generate TooFar typeCheck: PROCEDURE[OpDescriptor, PGNode], printDetails: PROCEDURE[op: OpDescriptor, node: PGNode, on: IO.STREAM, nested: CARDINAL], genBytes: PROCEDURE[op: OpDescriptor, oneByte: PROC[[0..255]]] ]; TooFar: SIGNAL; PGNode: TYPE = REF PGNodeBody; PGNodeBody: TYPE; Arc: TYPE = RECORD[ from: PGNode, which: ArcNumber ]; ArcNumber: TYPE = {first, second}; DummyNodesTable: TYPE = REF DummyNodesTableBody; DummyNodesTableBody: TYPE = RECORD[ nNodes: CARDINAL, nodes: REF DummyNodesTableArray]; DummyNodesTableArray: TYPE = RECORD[ SEQUENCE MaxNNodes: CARDINAL OF PGNode]; ProcedureInfo: TYPE = REF ProcedureInfoBody; ProcedureInfoBody: TYPE = RECORD[ procedure: REF ANY, allowedArgs: SeqType, possibleResults: SeqType, dummyNodesTable: DummyNodesTable, sorted: BOOLEAN, typeSet: TypeSet, entryNode: PGNode, linearized: BOOLEAN, relativeAddressesSet: BOOLEAN]; -- inspection for manipulation GetRandomDummyTableEntry: PROCEDURE[table: DummyNodesTable, random: CARDINAL] RETURNS[PGNode]; GetDummyTableSize: PROCEDURE[table: DummyNodesTable] RETURNS[CARDINAL]; GetDummyNodeOpShape: PROCEDURE[node: PGNode] RETURNS[nArgs, nResults: CARDINAL]; GetStack: PROCEDURE[node: PGNode] RETURNS[SeqType]; GetNextStack: PROCEDURE[node: PGNode] RETURNS[SeqType]; GetTopOfStack: PROCEDURE[node: PGNode] RETURNS[WordType]; GetTopOfNextStack: PROCEDURE[node: PGNode] RETURNS[WordType]; GetNextOfStack: PROCEDURE[node: PGNode] RETURNS[WordType]; GetNextOfNextStack: PROCEDURE[node: PGNode] RETURNS[WordType]; GetFrameVarType: PROCEDURE[node: PGNode, varOffset: CARDINAL] RETURNS[WordType]; GetNextFrameVarType: PROCEDURE[node: PGNode, varOffset: CARDINAL] RETURNS[WordType]; GetTypeSet: PROCEDURE[node: PGNode] RETURNS[TypeSet]; TopTwoArgsOfDummyOp: PROCEDURE[dummyOp: OpDescriptor] RETURNS[s0, s1: WordType]; TopResultOfDummyOp: PROCEDURE[dummyOp: OpDescriptor] RETURNS[t0: WordType]; -- manipulation CreateProcedureGraph: PROCEDURE[ allowedArgs, frameExtension, possibleResults: SeqType, typeSet: TypeSet, random: PROCEDURE RETURNS[CARDINAL], getEPOpForEntry: PROCEDURE[nArgs: CARDINAL] RETURNS[OpDescriptor], getDragonOp: PROCEDURE[ class: OpTypeClass, random: PROCEDURE RETURNS[CARDINAL], selectLocalIndex: PROCEDURE RETURNS[CARDINAL], selectRemoteIndex: PROCEDURE RETURNS[CARDINAL], selectLocalRemoteIndices: PROCEDURE RETURNS[l,r: CARDINAL]] RETURNS[OpDescriptor], getRetOpForReturn: PROCEDURE[nRetWords: CARDINAL] RETURNS[OpDescriptor]] RETURNS[ procedureInfo: ProcedureInfo]; SplitADummyArc: PROCEDURE[source: PGNode, copySomeOfOpSource: BOOLEAN, amountOfCopy: CARDINAL, extension: SeqType]; -- assumes that the operation at source is Dummy, and inserts a new node along the first arc leaving source. The frame type of the new node is the same as source, and the stack type is the concatenation of the some types from either source, or source.arcs[first], depending on value of copySomeOfOpSource; concatenated with extension. InsertTestA: PROCEDURE[source: PGNode, op: OpDescriptor, loop: BOOLEAN]; -- assumes that the op at source is Dummy. Replaces it with a op, which is assumed to be a test op code, followed by assorted dummy arcs. If loop = TRUE, then source.arcs[second] eventually returns to source. InsertSourceReduction: PROCEDURE[source: PGNode, selectOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType] RETURNS[OpDescriptor, CARDINAL]]; -- assumes a dummy op at source, calls on selectOp with the given dummy op and local frame type as arguments, expecting a new dummy operation in return. Replaces the dummy arc with the newly supplied operation, followed by a new dummy arc. InsertTargetReduction: PROCEDURE[source: PGNode, selectOp: PROCEDURE[dummyOp: OpDescriptor, locals: SeqType, ordinaryWordType: WordType] RETURNS[OpDescriptor, CARDINAL]]; -- assumes a dummy op at source, calls on selectOp with the given dummy op and local frame type as arguments, expecting an operation in return. Replaces the dummy arc with a new dummy arc, followed by the newly supplied operation. InsertSFCallInDummyArc: PROCEDURE[source: PGNode, op: OpDescriptor, procType: WordType]; RemoveNullDummy: PROCEDURE[source: PGNode]; CreateDummyOpArc: PROCEDURE[source: PGNode, target: PGNode]; -- inserts an arc from source to target, using a dummy arc. Uses frame and stack types as it finds them. -- type checking code BeginTypeCheck: PROCEDURE[node: PGNode]; BasicNodeTypeCheck: PROCEDURE[node: PGNode, nArgs, nResults: CARDINAL, skipResultVar: CARDINAL _ LAST[CARDINAL], twoArcs: BOOLEAN _ FALSE, jump: BOOLEAN _ FALSE]; TypeCheckEPNode: PROCEDURE[node: PGNode, nArgs: CARDINAL]; TypeCheckRETNode: PROCEDURE[node: PGNode, nResults: CARDINAL]; CheckRelativeJump: PROCEDURE[node: PGNode, relativeJumpBytes: INT]; -- Sort and Print procedures PrintSortGraph: PROCEDURE[node: PGNode]; -- This procedure sorts that portion of the program graph which is reachable from the given node. The result is that the "next" field at each node is arranged to point to the next node in the sort order. The resulting order is a "print order". First, all "backward" arcs are identified, thus finding a tree which covers the graph. The print order is determined such that a given node will be "visited" only after all nodes from which it can be reached (by "forward" arcs) have already been visited. Otherwise, nodes which can be visited by "first" arcs will be visited before nodes that require following "second" arcs, etc. Uses an incremented value of the (global) variable sortScanNumb to distinguish visits of this sort call from those of previous calls. PrintGraph: PROCEDURE[title: Rope.ROPE, node: PGNode, on: IO.STREAM]; -- This procedure assumes that PrintSortGraph has previously been called. -- final procedures for linearizing and binary output AssignRelativeGraphNodeAddresses: PROCEDURE[node: PGNode, GetJBOpForJump: PROCEDURE[deltaBytes: INTEGER] RETURNS[OpDescriptor], GetJDBOpForJump: PROCEDURE[deltaBytes: INTEGER] RETURNS[OpDescriptor]] RETURNS[size: INT]; TearDownGraph: PROCEDURE[node: PGNode]; GenGraphBytes: PROCEDURE[node: PGNode, oneByte: PROC[[0..255]]]; -- op codes (used for testing, Dragon Op Codes are used for real generation) LoadStore: TYPE = {load, store}; CreateBinaryOp: PROCEDURE[ordinaryWordType: WordType] RETURNS[OpDescriptor]; CreatePopOp: PROCEDURE[ordinaryWordType: WordType] RETURNS[OpDescriptor]; CreateIndirectOp: PROCEDURE[loadStore: LoadStore, remoteOffset: CARDINAL] RETURNS[OpDescriptor]; CreateLocalOp: PROCEDURE[loadStore: LoadStore, localOffset: CARDINAL] RETURNS[OpDescriptor]; CreateLocalIndirectOp: PROCEDURE[loadStore: LoadStore, localOffset: CARDINAL, remoteOffset: CARDINAL] RETURNS[OpDescriptor]; END. MODULE HISTORY Initial by: Sturgis, October 8, 1984 10:42:30 am PDT, from RandomCodeInternal