FILE: MarkImpl.mesa
Last edited by Ousterhout, August 30, 1983 11:48 am
Christian LeCocq December 19, 1986 11:54:58 am PST
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;
The following variables are used to pass information from high-level command procedures to low-level search action routines.
flag: {input, output, bus, precharged, watched};
value: REAL;
ivalue: INT;
The following variables are used to record statistics.
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.
The following flags determine whether or not we print out node names whenever they get set to particular values or marked dynamic.
SeeSettings: PUBLIC BOOLEAN ← FALSE;
SeeAllSettings: PUBLIC BOOLEAN ← FALSE;
SeeDynamic: PUBLIC BOOLEAN ← FALSE;
The following stuff is used to cause a graceful abort in findStrength when it's spending too long searching.
FSLimit: PUBLIC INT ← 1000;
fSCount: INT;
InputCmd: PUBLIC Globals.CmdProc =
BEGIN
node: Globals.Node;
flag ← input;
WHILE args # NIL DO
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut];
node ← Build.NodeFromRope[args.rope, globalVars];
node.input ← TRUE;
args ← args.next;
ENDLOOP;
END;
OutputCmd: PUBLIC Globals.CmdProc =
BEGIN
node: Globals.Node;
flag ← output;
WHILE args # NIL DO
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut];
node ← Build.NodeFromRope[args.rope, globalVars];
node.output ← TRUE;
args ← args.next;
ENDLOOP;
END;
BusCmd: PUBLIC Globals.CmdProc =
BEGIN
node: Globals.Node;
flag ← bus;
WHILE args # NIL DO
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut];
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
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut];
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
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: flagProc, errorStream: Globals.StdOut];
node ← Build.NodeFromRope[args.rope, globalVars];
node.watched ← TRUE;
args ← args.next;
ENDLOOP;
END;
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;
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
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: resProc, errorStream: Globals.StdOut];
node ← Build.NodeFromRope[args.rope, globalVars];
node.res ← value;
args ← args.next;
ENDLOOP;
END;
resProc: Hash.EnumProc =
BEGIN
node: Globals.Node ← NARROW[entry.clientData];
node.res ← value;
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
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: capProc, errorStream: Globals.StdOut];
node ← Build.NodeFromRope[args.rope, globalVars];
node.cap ← value;
args ← args.next;
ENDLOOP;
END;
capProc: Hash.EnumProc =
BEGIN
node: Globals.Node ← NARROW[entry.clientData];
node.cap ← value;
END;
SetNodeValue: PUBLIC PROC[node: Globals.Node, value: INT, propAnyway: BOOLEAN ← FALSE, globalVars: Globals.GlobalVars] =
BEGIN
p: Globals.Pointer;
f: Globals.Fet;
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 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 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]];
IF SeeAllSettings OR SeeSettings THEN
IO.PutF[Globals.StdOut, "Node %s forced to %d.\n", IO.rope[Printout.NodeRope[node, globalVars]], IO.int[value]];
Find all of the transistors connecting to this node, and take action (if necessary) to propagate the level setting.
FOR p ← node.firstPointer, p.next UNTIL p = NIL DO
f ← p.fet;
Where this node connects to sources or drains, check to see if level information will propagate to the next node over.
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 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.
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] =
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).
BEGIN
p: Globals.Pointer;
f: Globals.Fet;
other: Globals.Node;
strength, strength2, value: INT;
simCount ← simCount+1;
Find strongest certain source of a 0 or 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;
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.
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
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.
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] =
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.
BEGIN
p: Globals.Pointer;
f: Globals.Fet;
other: Globals.Node;
strength, strength2: INT;
simCount ← simCount+1;
Abort gracefully if we can't finish the search with a reasonable effort.
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;
Use the inPath flag to avoid infinite recursion.
node.inPath ← TRUE;
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.
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 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.
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
Hash.Enumerate[table: globalVars.nodeTable, pattern: args.rope, proc: setProc, errorStream: Globals.StdOut];
SetNodeValue[Build.NodeFromRope[args.rope, globalVars], ivalue, TRUE, globalVars];
args ← args.next;
ENDLOOP;
END;
setProc: Hash.EnumProc =
BEGIN
node: Globals.Node ← NARROW[entry.clientData];
SetNodeValue[node, ivalue, TRUE];
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;
Hash.Enumerate[table: globalVars.nodeTable, pattern: "*", proc: markDynamicProc, errorStream: Globals.StdOut];
[] ← HashTable.Pairs[globalVars.nodeTable, MarkDynamicProc]
};
END.