FILE: FlowImpl.mesa
Last edited by Ousterhout, April 16, 1985 10:59:32 am PST
DIRECTORY
Flow,
Globals,
Hash,
IO,
Parse,
Rope;
FlowImpl: CEDAR PROGRAM
IMPORTS
Globals,
Hash,
IO,
Parse
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]];
};
}.