EXPORTS Flow = {
OPEN Flow, Globals;
FlowTable: PUBLIC Hash.Table ← Hash.NewTable[];
Random variables to keep track of statistics.
searchCount: INT ← 0;
totalFlows: INT ← 0;
Value passed between high-level command procedure and search action procedure.
index: INT;
Mark:
PUBLIC CmdProc = {
Hash.Enumerate[table: NodeTable, pattern: "*", proc: markProc];
};
markProc: Hash.EnumProc = {
This routine is called once for each node in the node table. If the node has a gate attached or is an output, then invoke checkFlowTo to see if the node can be driven and set flow bits along the way. Note: don't do any checks from input nodes (includeing Vdd and Ground) unless the nodes are also output nodes. Also, ignore gates that are attached to their source or drain.
n: Node ← NARROW[entry.clientData];
p: Pointer;
f: Fet;
IF n.output
THEN {
[] ← checkFlowTo[n];
RETURN;
};
IF n.input THEN RETURN;
FOR p ← n.firstPointer, p.next
UNTIL p =
NIL
DO
f ← p.fet;
IF (f.gate = n)
AND (f.source # n)
AND (f.drain # n)
THEN {
[] ← checkFlowTo[n];
RETURN;
};
ENDLOOP;
};
checkFlowTo:
PROC[node: Node]
RETURNS [result:
BOOLEAN] = {
This recursive local procedure does most of the work of flow marking. It returns TRUE if the given node can possibly be an information source. If information sources can be reached from node, then transistors along the way get their flow flags set to show what is possible.
p: Pointer;
f: Fet;
next: Node;
fromDrain: BOOLEAN;
searchCount ← searchCount + 1;
Use the inPath flag to avoid infinite recursion.
node.inPath ← TRUE;
result ← FALSE;
FOR p ← node.firstPointer, p.next
UNTIL p =
NIL
DO
f ← p.fet;
Make sure that our node hooks to the source or drain of this transistor, and that we haven't already marked flow in this direction. If there's an attribute conflicting with the flow in this transistor, just skip the transistor.
IF f.source = node
THEN {
next ← f.drain;
fromDrain ← TRUE;
IF f.flowFromDrain
THEN {
result ← TRUE;
LOOP;
};
IF f.noDrainInfo THEN LOOP;
}
ELSE
IF f.drain = node
THEN {
next ← f.source;
fromDrain ← FALSE;
IF f.flowFromSource
THEN {
result ← TRUE;
LOOP;
};
IF f.noSourceInfo THEN LOOP;
}
ELSE LOOP;
Watch out for circular paths.
IF next.inPath THEN LOOP;
If the node on the other side of the fet is an input, then we can set the flow in the fet right away. Otherwise, we have to call ourselves recursively to find out if that node connects to anything.
IF
NOT next.input
THEN
IF NOT checkFlowTo[next] THEN LOOP;
IF fromDrain THEN f.flowFromDrain ← TRUE
ELSE f.flowFromSource ← TRUE;
result ← TRUE;
ENDLOOP;
node.inPath ← FALSE;
RETURN [result];
};
Build:
PUBLIC
PROC[fet: Fet, name: Rope.
ROPE, source:
BOOLEAN] = {
flow: FlowCtl;
h: Hash.Entry;
fp: FlowPtr;
See if there's already an entry for the given flow. If not, allocate and initialize a new one.
h ← Hash.Find[table: FlowTable, name: name];
IF h.clientData =
NIL
THEN {
flow ← NEW[FlowRec ← [name, NIL, NIL, FALSE, FALSE, FALSE, FALSE]];
h.clientData ← flow;
totalFlows ← totalFlows + 1;
}
ELSE flow ← NARROW[h.clientData];
Link the flow into the list for the transistor.
fp ← NEW[FlowPtrRec ← [flow, fet.firstFlow, source, NOT source]];
fet.firstFlow ← fp;
};
Lock:
PUBLIC
PROC[fet: Fet, input: Node]
RETURNS [
BOOLEAN] = {
fp: FlowPtr;
flow: FlowCtl;
IF (input # fet.source) AND (input # fet.drain) THEN RETURN [TRUE];
First make a pass through all of the flows attached to this fet to be sure that there aren't any conflicting locks already set.
FOR fp ← fet.firstFlow, fp.next
UNTIL fp =
NIL
DO
flow ← fp.flow;
IF flow.ignore THEN LOOP;
IF flow.off THEN RETURN [FALSE];
IF ((input = fet.source)
AND fp.source)
OR ((input = fet.drain)
AND fp.drain)
THEN {
IF flow.outOnly THEN RETURN [FALSE];
IF flow.left # NIL THEN RETURN [FALSE];
}
ELSE {
IF flow.inOnly THEN RETURN [FALSE];
IF flow.entered # NIL THEN RETURN [FALSE];
};
ENDLOOP;
Now make a second pass through all the flows to set locks.
FOR fp ← fet.firstFlow, fp.next
UNTIL fp =
NIL
DO
flow ← fp.flow;
IF ((input = fet.source)
AND fp.source)
OR ((input = fet.drain)
AND fp.drain)
THEN {
IF flow.entered = NIL THEN flow.entered ← input;
}
ELSE {
IF flow.left = NIL THEN flow.left ← input;
};
ENDLOOP;
RETURN [TRUE];
};
Unlock:
PUBLIC
PROC[fet: Fet, input: Node] = {
fp: FlowPtr;
flow: FlowCtl;
FOR fp ← fet.firstFlow, fp.next
UNTIL fp =
NIL
DO
flow ← fp.flow;
IF flow.entered = input THEN flow.entered ← NIL;
IF flow.left = input THEN flow.left ← NIL;
ENDLOOP;
};
FlowCmd:
PUBLIC CmdProc = {
names:
ARRAY[0..5)
OF Rope.
ROPE ← [
"ignore",
"in",
"normal",
"off",
"out"
];
IF args =
NIL
THEN {
IO.PutRope[StdOut, "No keyword given: try ignore, off, in, out, or normal.\n"];
RETURN;
};
TRUSTED {index ← Parse.Lookup[args.rope, DESCRIPTOR[names]]};
IF index < 0
THEN {
IO.PutRope[StdOut, "Bad keyword, try ignore, off, in, out, or normal.\n"];
RETURN;
};
args ← args.next;
Go through the attributes one at a time and mark their flags.
WHILE args #
NIL
DO
Hash.Enumerate[table: FlowTable, pattern: args.rope, proc: flowProc, errorStream: StdOut];
args ← args.next;
ENDLOOP;
};
flowProc: Hash.EnumProc = {
flow: FlowCtl ← NARROW[entry.clientData];
flow.inOnly ← FALSE;
flow.outOnly ← FALSE;
flow.off ← FALSE;
flow.ignore ← FALSE;
SELECT index
FROM
0 => flow.ignore ← TRUE;
1 => flow.inOnly ← TRUE;
3 => flow.off ← TRUE;
4 => flow.outOnly ← TRUE;
ENDCASE;
};
Stats:
PUBLIC
PROC[] = {
IO.PutF[StdOut, "Total number of flows: %d.\n", IO.int[totalFlows]];
IO.PutF[StdOut, "Total number of calls during flow marking: %d.\n", IO.int[searchCount]];
};
}.