DIRECTORY Flow, Globals, Hash, HashTable, IO, Parse, Rope; FlowImpl: CEDAR PROGRAM IMPORTS Globals, Hash, HashTable, IO, Parse EXPORTS Flow = { OPEN Flow; FlowTable: PUBLIC Hash.Table _ Hash.NewTable[]; searchCount: INT _ 0; totalFlows: INT _ 0; index: INT; Mark: PUBLIC Globals.CmdProc = { [] _ HashTable.Pairs[globalVars.nodeTable, MarkProc]; }; MarkProc: HashTable.EachPairAction = { n: Globals.Node _ NARROW[value]; p: Globals.Pointer; f: Globals.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: Globals.Node] RETURNS [result: BOOLEAN] = { p: Globals.Pointer; f: Globals.Fet; next: Globals.Node; fromDrain: BOOLEAN; searchCount _ searchCount + 1; node.inPath _ TRUE; result _ FALSE; FOR p _ node.firstPointer, p.next UNTIL p = NIL DO f _ p.fet; 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; IF next.inPath THEN LOOP; 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: Globals.Fet, name: Rope.ROPE, source: BOOLEAN] = { flow: Globals.FlowCtl; h: Hash.Entry; fp: Globals.FlowPtr; h _ Hash.Find[table: FlowTable, name: name]; IF h.clientData = NIL THEN { flow _ NEW[Globals.FlowRec _ [name, NIL, NIL, FALSE, FALSE, FALSE, FALSE]]; h.clientData _ flow; totalFlows _ totalFlows + 1; } ELSE flow _ NARROW[h.clientData]; fp _ NEW[Globals.FlowPtrRec _ [flow, fet.firstFlow, source, NOT source]]; fet.firstFlow _ fp; }; Lock: PUBLIC PROC[fet: Globals.Fet, input: Globals.Node] RETURNS [BOOLEAN] = { fp: Globals.FlowPtr; flow: Globals.FlowCtl; IF (input # fet.source) AND (input # fet.drain) THEN RETURN [TRUE]; 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; 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: Globals.Fet, input: Globals.Node] = { fp: Globals.FlowPtr; flow: Globals.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 Globals.CmdProc = { names: ARRAY[0..5) OF Rope.ROPE _ [ "ignore", "in", "normal", "off", "out" ]; IF args = NIL THEN { IO.PutRope[Globals.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[Globals.StdOut, "Bad keyword, try ignore, off, in, out, or normal.\n"]; RETURN; }; args _ args.next; WHILE args # NIL DO Hash.Enumerate[table: FlowTable, pattern: args.rope, proc: flowProc, errorStream: Globals.StdOut]; args _ args.next; ENDLOOP; }; flowProc: Hash.EnumProc = { flow: Globals.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[Globals.StdOut, "Total number of flows: %d.\n", IO.int[totalFlows]]; IO.PutF[Globals.StdOut, "Total number of calls during flow marking: %d.\n", IO.int[searchCount]]; }; }. `FILE: FlowImpl.mesa Last edited by Ousterhout, April 16, 1985 10:59:32 am PST Christian LeCocq December 19, 1986 11:36:18 am PST Random variables to keep track of statistics. Value passed between high-level command procedure and search action procedure. Hash.Enumerate[table: globalVars.nodeTable, pattern: "*", proc: markProc]; 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. 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. Use the inPath flag to avoid infinite recursion. 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. Watch out for circular paths. 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. See if there's already an entry for the given flow. If not, allocate and initialize a new one. Link the flow into the list for the transistor. 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. Now make a second pass through all the flows to set locks. Go through the attributes one at a time and mark their flags. ÊÒ˜Jšœ™šœ9™9Icode™2—J˜šÏk ˜ J˜J˜J˜J˜ Jšœ˜J˜J˜—J˜Jšœ œ˜š˜J˜J˜J˜ Jšœ˜J˜—šœ ˜J˜Jšœ˜ J˜Jšœ œ˜/J˜Jšœ-™-J˜Jšœ œ˜Jšœ œ˜J˜JšœN™NJ˜Jšœœ˜ J˜J˜šÏbœœ˜ JšœJ™JJšœ5˜5J˜—J˜šžœ˜&J™øJ˜Jšœœ˜ Jšœ˜Jšœ˜J˜šœ œ˜J˜Jšœ˜J˜—Jšœ œœ˜šœœœ˜/J˜ šœœœœ˜;J˜Jšœ˜J˜—Jšœ˜—J˜—J˜J˜šž œœœ œ˜CJ™“J˜Jšœ˜Jšœ˜Jšœ˜Jšœ œ˜J˜J˜J˜J™0J˜Jšœœ˜J˜Jšœ œ˜šœœœ˜2J˜ J˜J™äJ˜šœœ˜J˜Jšœ œ˜šœœ˜Jšœ œ˜Jšœ˜J˜—Jšœœœ˜J˜—šœœœ˜J˜Jšœ œ˜šœœ˜Jšœ œ˜Jšœ˜J˜—Jšœœœ˜J˜—Jšœœ˜ J˜J™J˜Jšœ œœ˜J˜J™ÆJ˜šœœ ˜Jšœœœœ˜#—Jšœ œ˜(Jšœœ˜Jšœ œ˜Jšœ˜—J˜Jšœœ˜Jšœ ˜J˜—J˜J˜š Ïnœœœœ œ˜JJšœ˜J˜Jšœ˜J˜J™_J˜J˜,šœœœ˜Jšœœœœœœœœ˜KJ˜J˜J˜—Jšœœ˜!J˜J™/J˜Jšœœ4œ ˜IJ˜J˜—J˜J˜š Ÿœœœ(œœ˜NJšœ˜Jšœ˜J˜Jš œœœœœ˜CJ˜J™J˜šœœœ˜1J˜Jšœ œœ˜Jšœ œœœ˜ š œœ œœ œ˜TJšœœœœ˜$Jš œ œœœœ˜'J˜—šœ˜Jšœ œœœ˜#Jš œœœœœ˜*J˜—Jšœ˜—J˜J™:J˜šœœœ˜1J˜š œœ œœ œ˜TJšœœœ˜0J˜—šœ˜Jšœ œœ˜*J˜—Jšœ˜—J˜Jšœœ˜Jšœ˜—J˜šŸœœœ+˜>Jšœ˜Jšœ˜J˜šœœœ˜1J˜Jšœœœ˜0Jšœœ œ˜*Jšœ˜—J˜—J˜J˜šžœœ˜#šœœœœ˜#J˜ J˜J˜ J˜J˜J˜—J˜šœœœ˜JšœV˜XJšœ˜J˜—J˜Jšœ" œ ˜=šœ œ˜JšœP˜RJšœ˜J˜—J˜J˜J™=J˜šœœ˜Jšœb˜bJ˜Jšœ˜—J˜—J˜šžœ˜Jšœœ˜1Jšœœ˜Jšœœ˜Jšœ œ˜Jšœœ˜šœ˜Jšœœ˜Jšœœ˜Jšœœ˜Jšœœ˜Jšœ˜—J˜—J˜J˜šŸœœœ˜Jšœ6œ˜LJšœJœ˜aJ˜—J˜J˜——…—€²