DIRECTORY Build, Flow, Globals, HashTable, IO, Mark, Model, Parse, Printout, Rope; MarkImpl: CEDAR PROGRAM IMPORTS Build, Flow, Globals, IO, HashTable, Model, Parse, Printout EXPORTS Mark = BEGIN OPEN Mark; flag: {input, output, bus, precharged, watched}; value: REAL; ivalue: INT; nodes0: INT _ 0; -- number of nodes forced to zero. nodes1: INT _ 0; -- number of nodes forced to one. dynamic: INT _ 0; -- number of nodes marked dynamic. simCount: INT _ 0; -- counts calls to checkNode and findStrength. SeeSettings: PUBLIC BOOLEAN _ FALSE; SeeAllSettings: PUBLIC BOOLEAN _ FALSE; SeeDynamic: PUBLIC BOOLEAN _ FALSE; FSLimit: PUBLIC INT _ 1000; fSCount: INT; InputCmd: PUBLIC Globals.CmdProc = BEGIN node: Globals.Node; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.input _ TRUE; args _ args.next; ENDLOOP; END; OutputCmd: PUBLIC Globals.CmdProc = BEGIN node: Globals.Node; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.output _ TRUE; args _ args.next; ENDLOOP; END; BusCmd: PUBLIC Globals.CmdProc = BEGIN node: Globals.Node; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.bus _ TRUE; args _ args.next; ENDLOOP; END; PrechargedCmd: PUBLIC Globals.CmdProc = BEGIN node: Globals.Node; flag _ precharged; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.precharged _ TRUE; node.bus _ TRUE; args _ args.next; ENDLOOP; END; WatchCmd: PUBLIC Globals.CmdProc = BEGIN node: Globals.Node; flag _ watched; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.watched _ TRUE; args _ args.next; ENDLOOP; END; ResCmd: PUBLIC Globals.CmdProc = BEGIN ok: BOOLEAN; node: Globals.Node; IF args = NIL THEN BEGIN IO.PutRope[Globals.StdOut, "No resistance value given.\n"]; RETURN; END; [ok, value] _ Parse.Real[args]; IF (NOT ok) OR (value < 0) THEN BEGIN IO.PutRope[Globals.StdOut, "Bad resistance value.\n"]; RETURN; END; args _ args.next; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.res _ value; args _ args.next; ENDLOOP; END; CapCmd: PUBLIC Globals.CmdProc = BEGIN ok: BOOLEAN; node: Globals.Node; IF args = NIL THEN BEGIN IO.PutRope[Globals.StdOut, "No capacitance value given.\n"]; RETURN; END; [ok, value] _ Parse.Real[args]; IF (NOT ok) OR (value < 0) THEN BEGIN IO.PutRope[Globals.StdOut, "Bad capacitance value.\n"]; RETURN; END; args _ args.next; WHILE args # NIL DO node _ Build.NodeFromRope[args.rope, globalVars]; node.cap _ value; args _ args.next; ENDLOOP; END; SetNodeValue: PUBLIC PROC[node: Globals.Node, value: INT, propAnyway: BOOLEAN _ FALSE, globalVars: Globals.GlobalVars] = BEGIN p: Globals.Pointer; f: Globals.Fet; IF value = 0 THEN BEGIN IF node.always1 THEN IO.PutF[Globals.StdOut, "Node forced to 1, then to 0 (0 wins): %s.\n", IO.rope[Printout.NodeRope[node, globalVars]]]; node.always1 _ FALSE; IF node.always0 AND NOT propAnyway THEN RETURN; node.always0 _ TRUE; nodes0 _ nodes0 + 1; END ELSE BEGIN IF node.always0 THEN IO.PutF[Globals.StdOut, "Node forced to 0, then to 1 (1 wins): %s.\n", IO.rope[Printout.NodeRope[node, globalVars]]]; node.always0 _ FALSE; IF node.always1 AND NOT propAnyway THEN RETURN; node.always1 _ TRUE; nodes1 _ nodes1 + 1; END; IF SeeAllSettings OR SeeSettings THEN IO.PutF[Globals.StdOut, "Node %s forced to %d.\n", IO.rope[Printout.NodeRope[node, globalVars]], IO.int[value]]; FOR p _ node.firstPointer, p.next UNTIL p = NIL DO f _ p.fet; IF (f.source = node) AND f.flowFromSource AND (f.onAlways OR f.forcedOn) THEN CheckNode[f.drain, globalVars]; IF (f.drain = node) AND f.flowFromDrain AND (f.onAlways OR f.forcedOn) THEN CheckNode[f.source, globalVars]; IF f.gate = node THEN BEGIN IF ((value=1) AND f.on1) OR ((value=0) AND f.on0) THEN f.forcedOn _ TRUE ELSE IF f.on1 OR f.on0 THEN f.forcedOff _ TRUE ELSE LOOP; IF f.flowFromDrain THEN CheckNode[f.source, globalVars]; IF f.flowFromSource THEN CheckNode[f.drain, globalVars]; END; ENDLOOP; END; CheckNode: PROC[node: Globals.Node, globalVars: Globals.GlobalVars] = BEGIN p: Globals.Pointer; f: Globals.Fet; other: Globals.Node; strength, strength2, value: INT; simCount _ simCount+1; strength _ 0; FOR p _ node.firstPointer, p.next UNTIL p = NIL DO f _ p.fet; IF NOT (f.onAlways OR f.forcedOn) THEN LOOP; IF f.source = node THEN BEGIN other _ f.drain; IF NOT f.flowFromDrain THEN LOOP; END ELSE IF f.drain = node THEN BEGIN other _ f.source; IF NOT f.flowFromSource THEN LOOP; END ELSE LOOP; IF other.always0 THEN BEGIN IF Model.TypeTable[f.type].strengthLo > strength THEN BEGIN value _ 0; strength _ Model.TypeTable[f.type].strengthLo; END; END ELSE BEGIN IF Model.TypeTable[f.type].strengthHi > strength THEN BEGIN value _ 1; strength _ Model.TypeTable[f.type].strengthHi; END; END; ENDLOOP; fSCount _ 0; IF strength > 0 THEN BEGIN strength2 _ FindStrength[node: node, value: 1-value, beatThis: strength-1, globalVars: globalVars]; IF strength > strength2 THEN SetNodeValue[node, value, FALSE, globalVars]; END ELSE IF (FindStrength[node: node, value: 1, beatThis: 0, globalVars: globalVars] = 0) AND (FindStrength[node: node, value: 0, beatThis: 0, globalVars: globalVars] = 0) THEN BEGIN FOR p _ node.firstPointer, p.next UNTIL p=NIL DO f _ p.fet; IF f.source = node THEN BEGIN IF NOT f.flowFromSource THEN LOOP; f.flowFromSource _ FALSE; CheckNode[f.drain, globalVars]; END ELSE IF f.drain = node THEN BEGIN IF NOT f.flowFromDrain THEN LOOP; f.flowFromDrain _ FALSE; CheckNode[f.source, globalVars]; END ; ENDLOOP; END; END; FindStrength: PROC[node: Globals.Node, value: INT, beatThis: INT, globalVars: Globals.GlobalVars] RETURNS [INT] = BEGIN p: Globals.Pointer; f: Globals.Fet; other: Globals.Node; strength, strength2: INT; simCount _ simCount+1; fSCount _ fSCount + 1; IF fSCount >= FSLimit THEN BEGIN IO.PutF[Globals.StdOut, "Aborting simulation at %s:\n", IO.rope[Printout.NodeRope[node, globalVars]]]; IO.PutRope[Globals.StdOut, " It's taking too long to find all the potential signal sources.\n"]; IO.PutRope[Globals.StdOut, " You probably need to add more flow control info. \n"]; IO.PutRope[Globals.StdOut, " A list of nodes in the area follows:\n"]; RETURN [-1]; END; node.inPath _ TRUE; FOR p _ node.firstPointer, p.next UNTIL p=NIL DO f _ p.fet; IF f.forcedOff THEN LOOP; IF value = 0 THEN strength _ Model.TypeTable[f.type].strengthLo ELSE strength _ Model.TypeTable[f.type].strengthHi; IF strength <= beatThis THEN LOOP; IF f.source = node THEN BEGIN other _ f.drain; IF NOT f.flowFromDrain THEN LOOP; END ELSE IF f.drain = node THEN BEGIN other _ f.source; IF NOT f.flowFromSource THEN LOOP; END ELSE LOOP; IF f.firstFlow # NIL THEN IF NOT Flow.Lock[fet: f, input: other] THEN LOOP; IF other.always1 OR other.always0 OR other.input THEN BEGIN IF value = 0 THEN BEGIN IF other.always1 THEN BEGIN IF f.firstFlow # NIL THEN Flow.Unlock[fet: f, input: other]; LOOP; END; END ELSE IF other.always0 THEN BEGIN IF f.firstFlow # NIL THEN Flow.Unlock[fet: f, input: other]; LOOP; END; END ELSE BEGIN IF other.inPath THEN BEGIN IF f.firstFlow # NIL THEN Flow.Unlock[fet: f, input: other]; LOOP; END; strength2 _ FindStrength[node: other, value: value, beatThis: beatThis, globalVars: globalVars]; IF strength2 < 0 THEN BEGIN IO.PutF[Globals.StdOut, " %s\n", IO.rope[Printout.NodeRope[node, globalVars]]]; node.inPath _ FALSE; IF f.firstFlow # NIL THEN Flow.Unlock[fet: f, input: other]; RETURN [-1]; END; IF strength2 < strength THEN strength _ strength2; IF f.firstFlow # NIL THEN Flow.Unlock[fet: f, input: other]; END; IF strength > beatThis THEN beatThis _ strength; ENDLOOP; node.inPath _ FALSE; RETURN [beatThis]; END; SetCmd: PUBLIC Globals.CmdProc = BEGIN ok: BOOLEAN; IF args = NIL THEN BEGIN IO.PutRope[Globals.StdOut, "\"Set\" needs a 0/1 value and node names.\n"]; RETURN; END; [ok, ivalue] _ Parse.Int[args]; IF (NOT ok) OR (ivalue < 0) OR (ivalue > 1) THEN BEGIN IO.PutRope[Globals.StdOut, "Value must be 0 or 1.\n"]; RETURN; END; args _ args.next; WHILE args # NIL DO SetNodeValue[Build.NodeFromRope[args.rope, globalVars], ivalue, TRUE, globalVars]; args _ args.next; ENDLOOP; END; Stats: PUBLIC PROC[] = BEGIN IO.PutF[Globals.StdOut, "Total nodes set to 0: %d.\n", IO.int[nodes0]]; IO.PutF[Globals.StdOut, "Total nodes set to 1: %d.\n", IO.int[nodes1]]; IO.PutF[Globals.StdOut, "Total nodes marked dynamic: %d.\n", IO.int[dynamic]]; IO.PutF[Globals.StdOut, "Total number of recursive simulation calls: %d.\n", IO.int[simCount]]; END; MarkDynamic: PUBLIC PROC[globalVars: Globals.GlobalVars] = { MarkDynamicProc: HashTable.EachPairAction = BEGIN p: Globals.Pointer; f: Globals.Fet; node: Globals.Node _ NARROW[value]; node.dynamic _ FALSE; IF node.input OR node.always0 OR node.always1 THEN RETURN; FOR p _ node.firstPointer, p.next UNTIL p = NIL DO f _ p.fet; IF f.source = node THEN BEGIN IF NOT f.flowFromDrain THEN LOOP; END ELSE IF f.drain = node THEN BEGIN IF NOT f.flowFromSource THEN LOOP; END ELSE LOOP; IF NOT f.forcedOff THEN RETURN; ENDLOOP; node.dynamic _ TRUE; dynamic _ dynamic + 1; IF SeeDynamic THEN IO.PutF[Globals.StdOut, "%s is dynamic.\n", IO.rope[Printout.NodeRope[node, globalVars]]]; END; [] _ HashTable.Pairs[globalVars.nodeTable, MarkDynamicProc] }; END. ήFILE: MarkImpl.mesa Last edited by Ousterhout, August 30, 1983 11:48 am Christian LeCocq December 19, 1986 11:54:58 am PST The following variables are used to pass information from high-level command procedures to low-level search action routines. The following variables are used to record statistics. The following flags determine whether or not we print out node names whenever they get set to particular values or marked dynamic. The following stuff is used to cause a graceful abort in findStrength when it's spending too long searching. flag _ input; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut]; flag _ output; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut]; flag _ bus; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut]; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut]; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut]; flagProc: Hash.EnumProc = BEGIN node: Globals.Node _ NARROW[entry.clientData]; SELECT flag FROM input => node.input _ TRUE; output => node.output _ TRUE; bus => node.bus _ TRUE; watched => node.watched _ TRUE; precharged => BEGIN node.precharged _ TRUE; node.bus _ TRUE; END; ENDCASE; END; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: resProc, errorStream: Globals.StdOut]; resProc: Hash.EnumProc = BEGIN node: Globals.Node _ NARROW[entry.clientData]; node.res _ value; END; Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: capProc, errorStream: Globals.StdOut]; capProc: Hash.EnumProc = BEGIN node: Globals.Node _ NARROW[entry.clientData]; node.cap _ value; END; Make sure that there is no conflict in setting the node's value, then set the flags on the node. If the level was already forced, then we can return immediately (this check prevents circular loops). IF SeeAllSettings OR (SeeSettings AND ((Rope.Fetch[node.name, 0] < '0) OR (Rope.Fetch[node.name, 0] > '9))) THEN IO.PutF[Globals.StdOut, "Node %s forced to %d.\n", IO.rope[Printout.NodeRope[node]], IO.int[value]]; Find all of the transistors connecting to this node, and take action (if necessary) to propagate the level setting. Where this node connects to sources or drains, check to see if level information will propagate to the next node over. If the node connects to a transistor's gate and turns the transistor on, this may cause one of the nodes on either side to become fixed in value. If the transistor is now turned off, then the source or drain may become fixed because of the reduced "competition" for that node. This procedure checks to see if a node is forced to a value, and sets it if necessary. It operates in two stages. First, it finds the strongest certain source of 0 or 1 for the node (certain sources are those connected to the node by transistors that are definitely turned on). Then it finds the strongest possible source of the opposite value (a possible source is one connected to the node by transistors that aren't definitely turned off). If the certain source is stronger than any possible opposition, then the node value is set. If in the process of all this we discover that there are no transistors that can source information to the node, then the procedure is called recursively on all nodes that this node can source (this handles the case where the bottom transistor of a NAND gate turns off). Find strongest certain source of a 0 or 1. See if there is a potential source of the opposite signal that is at least as strong as the certain source. If not, then it's OK to set the node's value. There's no certain source. Now see if there is any possible source. If not, mark all the transistors that flow away from this node as disconnected and call ourselves recursively to handle the nodes on the other side. This is a recursive local procedure that looks for the strongest possible source of a zero or one signal in a (potentially) connected piece of circuit. Only sources stronger than beatThis are considered. If a stronger source is found, it's strength is returned. Otherwise beatThis is returned. If a negative value is returned, it means that we looked and looked and eventually gave up without finishing all the possibilities. Abort gracefully if we can't finish the search with a reasonable effort. Use the inPath flag to avoid infinite recursion. Check all transistors whose sources or drains connect to this node to see if they could potnetially provide a strong enough source of the right value. This may involve recursive calls. If an adjacent node is fixed in value, we know the strength right away: it's the strength of the connecting transistor. Otherwise we have to find the weakest transistor in the path to a driven node. Be sure to consider only nodes driven to the right value. Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: setProc, errorStream: Globals.StdOut]; setProc: Hash.EnumProc = BEGIN node: Globals.Node _ NARROW[entry.clientData]; SetNodeValue[node, ivalue, TRUE]; END; Hash.Enumerate[table: globalVars.nodeTable, pattern: "*", proc: markDynamicProc, errorStream: Globals.StdOut]; ΚU˜Jšœ™šœ3™3Icode™2—J˜šΟk ˜ J˜J˜J˜J˜ Jšœ˜J˜J˜J˜J˜ J˜—J˜JšΟnœœ˜š˜J˜J˜J˜Jšœ˜J˜ J˜J˜Jšœ˜—Jšœ˜Jš˜Jšœ˜ J˜Jšœ|™|J˜J˜0Jšœœ˜ Jšœœ˜ J˜Jšœ6™6J˜Jšœœ Οc"˜6Jšœœ Ÿ!˜5Jšœ œŸ"˜6Jšœ œŸ.˜CJ˜Jšœ‚™‚J˜Jšž œœœœ˜$Jšžœœœœ˜'Jšž œœœœ˜#J˜Jšœl™lJ˜Jšœ œœ˜Jšœ œ˜ J˜J˜šžœœ˜#Jš˜Jšœ˜J™ šœœ˜Jšœm™mJšœ1˜1Jšœ œ˜J˜Jšœ˜—Jšœ˜J˜—šž œœ˜$Jšœ˜Jšœ˜J™šœœ˜Jšœm™mJšœ1˜1Jšœœ˜J˜Jšœ˜—Jšœ˜J˜—šžœœ˜!Jšœ˜Jšœ˜J™ šœœ˜Jšœm™mJšœ1˜1Jšœ œ˜J˜Jšœ˜—Jšœ˜J˜—šž œœ˜(Jšœ˜Jšœ˜J˜šœœ˜Jšœm™mJšœ1˜1Jšœœ˜Jšœ œ˜J˜Jšœ˜—Jšœ˜—J˜šžœœ˜"Jš˜Jšœ˜J˜šœœ˜Jšœm™mJšœ1˜1Jšœœ˜J˜Jšœ˜—Jšœ˜—J˜šΟbœ™Jš™Jšœœ™.šœ™Jšœœ™Jšœœ™Jšœœ™Jšœœ™™Jš™Jšœœ™Jšœ œ™Jšœ™—Jšœ™—Jšœ™—J˜šžœœ˜ Jš˜Jšœœ˜ Jšœ˜J˜šœœ˜Jš˜Jšœ9˜;Jšœ˜Jšœ˜—J˜šœœœ ˜Jš˜Jšœ4˜6Jšœ˜Jšœ˜—J˜J˜šœœ˜Jšœl™lJšœ1˜1J˜J˜Jšœ˜—Jšœ˜J˜—š œ™Jš™Jšœœ™.J™Jšœ™—J˜šžœœ˜ Jš˜Jšœœ˜ Jšœ˜J˜šœœ˜Jš˜Jšœ:˜