<> <> <top>static.df>> DIRECTORY Ascii, Atom, Commander, CommandTool, FS, IO, Real, RefTab, RefText, Rope; StaticImpl: CEDAR MONITOR IMPORTS Ascii, Atom, Commander, CommandTool, FS, IO, Real, RefTab, RefText, Rope = BEGIN <> <> <> <> <> <> MAXPDL: NAT = 7; pdlIndex: TYPE = [1..MAXPDL]; NodeRef: TYPE = REF Node; NETransRef: TYPE = REF NETrans; NDTransRef: TYPE = REF NDTrans; ThreshCt: TYPE = [0..15]; -- a number of enhancement thresholds negative from vdd Node: TYPE = RECORD [ IPD: BOOL _ FALSE, -- there is a path of enhancement transistors from this node to ground GATE: BOOL _ FALSE, -- this node contains one or more gates INPUT: BOOL _ FALSE, -- this node is an off-chip input (has a lightning arrestor) MANY: BOOL _ FALSE, -- appeared more than once in the input file threshCt: ThreshCt _ LAST[ThreshCt], <> equiv: NodeRef _ NIL, -- Link for equivalence class of nodes connected together by enhancement-mode transistors. Canonical node has equiv=NIL, others connect to him by a chain of equiv links. igates: NETransRef _ NIL, -- List of transistors whose gates control this node highAssertions: INTEGER _ 0, <<0 means no assumptions, <0 means asserted low, >0 means asserted high. Absolute values are used for accounting.>> name: ATOM ]; NETrans: TYPE = RECORD [ gate, source, drain: NodeRef, igate: NETransRef _ NIL, <> elength, ewidth, x, y: INT, next: NETransRef ]; NDTrans: TYPE = RECORD [ gate, source: NodeRef, -- drain is vdd dlength, dwidth, x, y: INT, next: NDTransRef ]; eBase: NETransRef; dBase: NDTransRef; out: IO.STREAM; lowLimit,highLimit: REAL; -- limits on L/W (set by user) degradationPerThresh: REAL; <> inputThreshCt: ThreshCt; -- number of thresholds down from vdd that an input high is nodes: RefTab.Ref; -- table pu: NDTransRef; pd: ARRAY pdlIndex OF NETransRef; nNodes, ndtrans: INT; vdd,gnd: NodeRef; WriteCoords: PROC [x, y: INT] = {out.PutF["%d %d ", IO.int[x], IO.int[y]]}; blank: Rope.ROPE = "blank"; -- doesn't print Remark: PROC [remark: Rope.ROPE, t, n1, n2, n3: REF _ NIL] = BEGIN IF t#NIL THEN WITH t SELECT FROM e: NETransRef => BEGIN WriteCoords[e.x, e.y]; IF n1=NIL THEN BEGIN n1 _ e.gate.name; n2 _ e.source.name; n3 _ e.drain.name; END; END; d: NDTransRef => BEGIN WriteCoords[d.x, d.y]; IF n1=NIL THEN BEGIN n1 _ d.gate.name; n2 _ d.source.name; n3 _ "Vdd"; END; END; n: NodeRef => IF n1=NIL THEN n1 _ n.name; ENDCASE => NULL; out.PutRope[remark]; IF n1#NIL AND n1#blank THEN out.PutF[" %g", IO.rope[ToRope[n1]]]; IF n2#NIL THEN out.PutF[" %g", IO.rope[ToRope[n2]]]; IF n3#NIL THEN out.PutF[" %g", IO.rope[ToRope[n3]]]; out.Put[IO.char['\n]]; END; IsSD: PROC [e: NETransRef, a: NodeRef, b: NodeRef _ NIL] RETURNS [BOOL] = { RETURN[( SELECT a FROM e.source => b=NIL OR b=e.drain, e.drain => b=NIL OR b=e.source, ENDCASE => FALSE)]}; OtherSD: PROC [e: NETransRef, a: NodeRef] RETURNS [b: NodeRef] = {b _ SELECT a FROM e.source => e.drain, e.drain => e.source, ENDCASE => NIL}; caps: REF TEXT = RefText.New[200]; Lookup: PROC [s: REF TEXT] RETURNS [n: NodeRef] = BEGIN atom: ATOM; found: BOOL; ref: REF; caps.length _ s.length; FOR i: NAT IN [0..s.length) DO caps[i] _ Ascii.Upper[s[i]] ENDLOOP; atom _ Atom.MakeAtomFromRefText[caps]; [found: found, val: ref] _ nodes.Fetch[atom]; IF found THEN {n _ NARROW[ref]; n.MANY _ TRUE} ELSE BEGIN n _ NEW[Node _ [name: atom]]; [] _ nodes.Store[key: atom, val: n]; nNodes _ nNodes+1; END; END; FindCanon: PROC [n: NodeRef] RETURNS [m: NodeRef] = BEGIN <> FOR m _ n, m.equiv UNTIL m.equiv = NIL DO ENDLOOP; FOR k: NodeRef _ n, k.equiv UNTIL k=m DO k.equiv _ m ENDLOOP; END; IsEquiv: PROC [m,n: NodeRef] RETURNS [BOOL] = {RETURN[FindCanon[n] = FindCanon[m]]}; MakeEquiv: PROC [m,n: NodeRef] = BEGIN <> k: NodeRef = FindCanon[m]; l: NodeRef = FindCanon[n]; IF k # l THEN BEGIN k.equiv _ l; IF k.IPD THEN l.IPD _ TRUE; END; END; Pulldown: PROC [n: NodeRef] = {FindCanon[n].IPD _ TRUE}; DoPullups: PROC [] = BEGIN -- called once in main a, b, c: NodeRef; w, x: NDTransRef; y, z: NETransRef; <> <> pullups: INT _ 0; -- number of pullups <> <> <> <> nisbuffers: INT _ 0; -- number of inverting superbuffers <> <> <> <> <> nsbuffers: INT _ 0; -- number of non-inverting superbuffers unknowns: INT; -- number on unrecognizable depletion mode transistors FOR w _ dBase, w.next UNTIL w = NIL DO a _ w.source; b _ w.gate; IF a.threshCt = 0 THEN Remark[remark: "Node pulled up more than once:", n1: a.name]; a.threshCt _ 0; IF a = b THEN {pullups _ pullups+1; LOOP -- ordinary pullup -- }; FOR y _ b.igates, y.igate UNTIL y = NIL DO IF IsSD[y , b, gnd] THEN BEGIN c _ y.gate; FOR z _ a.igates, z.igate UNTIL z = NIL DO IF z.gate = c AND IsSD[z, a, gnd] THEN FOR x _ dBase, x.next UNTIL x = NIL DO IF x.source = b AND x.gate = b THEN {nisbuffers _ nisbuffers+1; GOTO quit1 -- inverting superbuffer -- }; ENDLOOP; ENDLOOP; END; REPEAT quit1 => LOOP; ENDLOOP; FOR z _ a.igates, z.igate UNTIL z = NIL DO IF IsSD[z, a, gnd] THEN BEGIN c _ z.gate; FOR y _ c.igates, y.igate UNTIL y = NIL DO IF y.gate = b AND IsSD[y, c, gnd] THEN FOR x _ dBase, x.next UNTIL x = NIL DO IF x.gate = c AND x.source = c THEN {nsbuffers _ nsbuffers+1; GOTO quit2 -- non-inverting superbuffer -- }; ENDLOOP; ENDLOOP; END; REPEAT quit2 => LOOP; ENDLOOP; Remark["depletion transitor not a pullup or a superbuffer: d", w]; ENDLOOP; out.PutF["pullups and non-inverting superbuffers: %7d %7d\n", IO.int[pullups], IO.int[ nsbuffers]]; unknowns _ ndtrans - pullups - nsbuffers - nisbuffers; out.PutF["inverting superbuffers and unknowns: %7d %7d\n", IO.int[nisbuffers], IO.int[unknowns]]; END; tChanged: BOOL; ComputeThresholds: PROC = BEGIN tChanged _ TRUE; WHILE tChanged DO tChanged _ FALSE; ForEachETran[PropagateEThresh]; ENDLOOP; END; PropagateEThresh: PROC [e: NETransRef] = BEGIN IF e.source#gnd AND MAX[e.drain.threshCt, e.gate.threshCt+1] < e.source.threshCt THEN {e.source.threshCt _MAX[e.drain.threshCt, e.gate.threshCt+1]; tChanged _ TRUE}; IF e.drain#gnd AND MAX[e.source.threshCt, e.gate.threshCt+1] < e.drain.threshCt THEN {e.drain.threshCt _ MAX[e.source.threshCt, e.gate.threshCt+1]; tChanged _ TRUE}; END; FindInput: PROC [e: NETransRef] = BEGIN <> IF e.gate = gnd THEN BEGIN o: NodeRef = OtherSD[e, gnd]; IF o#NIL AND NOT o.INPUT THEN BEGIN Remark["Assuming lightning arrested node is an Input:", e, o.name]; o.IPD _ o.INPUT _ TRUE; o.threshCt _ MIN[inputThreshCt, o.threshCt]; END; END; END; CheckThreshold: PROC [e: NETransRef] = BEGIN <> <> <> <> <> <> <> <> <> IF e.gate.threshCt IN [2..LAST[ThreshCt]) THEN Remark[IO.PutFR["Gate is at least %d thresholds negative from Vdd:", IO.int[e.gate.threshCt]], e]; IF e.gate.threshCt>0 AND NOT IsSD[e, gnd] AND ((e.source.threshCt>0 AND e.drain.GATE) OR (e.drain.threshCt>0 AND e.source.GATE)) THEN Remark["Pass transistor driven by pass transistor or input:", e]; END; CheckRatio: PROC [d: NDTransRef] = BEGIN n: NodeRef _ d.source; IF n # vdd AND n.threshCt=0 AND NOT n.INPUT THEN {pu _ d; DoPulldowns[n,1]}; END; DoPulldowns: PROC [n: NodeRef, depth: pdlIndex] = BEGIN <> IF AssertLow[n] THEN BEGIN IF n = gnd THEN BEGIN <> Bottom[depth]; <> END ELSE FOR e: NETransRef _ n.igates, e.igate UNTIL e = NIL DO <> o: NodeRef = OtherSD[e, n]; IF o#NIL AND (o=gnd OR (o.highAssertions=0 AND o.threshCt#0 AND NOT o.GATE)) AND depth < MAXPDL AND AssertHigh[e.gate] THEN <<>> <> <<1. it is ground, or else>> <<1a. it is not already part of the path under consideration,>> <<1b. it is not directly pulled up, and>> <<1c. it does not drive a gate. The reason for excluding nodes that drive gates is to keep from chasing down a path that consists of a Pullup driving a passgate multiplexer. If the examination is not stopped at the node that drives the passgate, the ratio will almost always be too high, and will produce spurious error messages (since the gates of the pass transistors almost always have mutally exclusive control signals). This will miss some valid paths, but life is hard.>> <<2. the path is not already too long, and>> <<3. the transistor can be turned on.>> <<>> IF AssertHigh[e.gate] THEN BEGIN pd[depth] _ e; DoPulldowns[o,depth+1]; RelaxHighAssertion[e.gate]; END; ENDLOOP; RelaxLowAssertion[n]; END; END; AssertHigh: PROC [ n: NodeRef ] RETURNS [ BOOL ] = BEGIN SELECT n.highAssertions FROM >0 => {n.highAssertions _ n.highAssertions+1; RETURN[TRUE]}; <0 => RETURN[FALSE]; -- this node is already asserted low ENDCASE => BEGIN FOR e: NETransRef _ n.igates, e.igate UNTIL e=NIL DO o: NodeRef _ OtherSD[e, n]; IF o=NIL OR (o.highAssertions<0 AND NOT AssertLow[e.gate]) THEN BEGIN <> RelaxLowGates[n: n, stop: e]; RETURN[FALSE]; END; ENDLOOP; n.highAssertions _ 1; RETURN[TRUE]; END; END; RelaxHighAssertion: PROC [ n: NodeRef ] = BEGIN SELECT n.highAssertions FROM <=0 => ERROR; -- this node is not asserted high >1 => n.highAssertions _ n.highAssertions-1; ENDCASE => BEGIN RelaxLowGates[n]; n.highAssertions _ 0; END; END; AssertLow: PROC [ n: NodeRef ] RETURNS [ BOOL ] = BEGIN SELECT n.highAssertions FROM <0 => {n.highAssertions _ n.highAssertions-1; RETURN[TRUE]}; >0 => RETURN[FALSE]; -- this node is already asserted high ENDCASE => BEGIN n.highAssertions _ -1; RETURN[TRUE]; END; END; RelaxLowAssertion: PROC [ n: NodeRef ] = BEGIN SELECT n.highAssertions FROM >=0 => ERROR; -- this node is not asserted low <-1 => n.highAssertions _ n.highAssertions+1; ENDCASE => BEGIN n.highAssertions _ 0; END; END; RelaxLowGates: PROC [ n: NodeRef, stop: NETransRef _ NIL ] = BEGIN FOR e: NETransRef _ n.igates, e.igate UNTIL e=stop DO o: NodeRef _ OtherSD[e, n]; IF o#NIL AND o.highAssertions<0 THEN RelaxLowAssertion[e.gate]; ENDLOOP; END; Bottom: PROC [depth: pdlIndex] = BEGIN Degradation: PROC [e: NETransRef] RETURNS [REAL] = {RETURN[1.0+e.gate.threshCt*degradationPerThresh]}; i: pdlIndex; pdZ: REAL _ 0.0; ratio: REAL; FOR i_ 1, i+1 UNTIL i=depth DO pdZ _ pdZ+ (IF pd[i].ewidth = 0 THEN 1.0e10 -- avoids divide by 0 ELSE REAL[pd[i].elength] / pd[i].ewidth*Degradation[pd[i]]); ENDLOOP; ratio _ IF pu.dwidth*pdZ = 0 THEN 1.0e10 ELSE pu.dlength/(pu.dwidth*pdZ); IF ratio < lowLimit OR ratio > highLimit THEN BEGIN n: NodeRef _ pu.source; WriteCoords[pu.x,pu.y]; out.PutF["Up/Down Z ratio = %5.2f: Node %g is pulled up by a %dx%d (l x w), and\n",IO.real[ratio], IO.rope[ToRope[pu.source.name]], IO.int[pu.dlength], IO.int[pu.dwidth]]; FOR i_1, i+1 UNTIL i=depth DO degradation: REAL = Degradation[pd[i]]; n_OtherSD[pd[i],n]; WriteCoords[pd[i].x,pd[i].y]; out.PutF["pulled down (by %g) thru a %dx%d (l x w)", IO.rope[ToRope[pd[i].gate.name]], IO.int[pd[i].elength], IO.int[pd[i].ewidth]]; IF degradation#1.0 THEN out.PutF[" (w/ %5.2f degradation)", IO.real[degradation]]; out.PutF[" to %g%g\n", IO.rope[ToRope[n.name]], IO.rope[IF i> FOR e: NETransRef _ d.source.igates, e.igate UNTIL e=NIL DO IF e.source.GATE OR e.drain.GATE THEN EXIT; REPEAT FINISHED => {Remark["Value not used:", d, d.source.name]}; ENDLOOP; END; ReadSimFile: PROC [in: IO.STREAM] = BEGIN line: REF TEXT _ NEW[TEXT[300]]; token: REF TEXT _ NEW[TEXT[300]]; lineStream: IO.STREAM; t0, t1, t2: NodeRef; l, w, x, y: INT; d: NDTransRef; netrans, ndfunny: INT _ 0; nNodes _ ndtrans _ 0; DO ScanTransistor: PROC = BEGIN [] _ lineStream.SkipWhitespace[]; token _ lineStream.GetToken[buffer: token].token; t0 _ Lookup[token]; [] _ lineStream.SkipWhitespace[]; token _ lineStream.GetToken[buffer: token].token; t1 _ Lookup[token]; [] _ lineStream.SkipWhitespace[]; token _ lineStream.GetToken[buffer: token].token; t2 _ Lookup[token]; l _ lineStream.GetInt[]; w _ lineStream.GetInt[]; x _ lineStream.GetInt[]; y _ lineStream.GetInt[]; END; MakeETrans: PROC [t0, t1, t2: NodeRef] = BEGIN e: NETransRef = NEW[NETrans _ [gate: t0, source: t1, drain: t2, elength: l, ewidth: w, x: x, y: y, next: eBase]]; eBase _ e; IF t0 # vdd AND t0 # gnd THEN e.gate.GATE _ TRUE; e.igate _ NIL; IF NOT IsSD[e, vdd] AND NOT IsSD[e, gnd] AND e.gate # gnd THEN <> MakeEquiv[e.source, e.drain]; IF OtherSD[e, gnd]#NIL THEN Pulldown[OtherSD[e, gnd]]; IF e.gate = gnd AND e.source # gnd AND e.drain # gnd THEN <> Remark["Gate is GND: e", e]; IF e.gate = vdd THEN Remark["Gate is VDD: e", e]; IF e.gate # gnd AND (e.gate = e.source OR e.gate = e.drain) THEN Remark[ "gate and source or drain equality: e", e]; END; line _ in.GetLine[ line ! IO.EndOfStream => EXIT ]; lineStream _ IO.TIS[line, lineStream]; [] _ lineStream.SkipWhitespace[]; SELECT lineStream.GetChar[ ! IO.EndOfStream => LOOP ] FROM 'e, 'E => BEGIN -- enhancement transistor ScanTransistor[]; MakeETrans[t0, t1, t2]; netrans _ netrans+1; END; 'd, 'D => BEGIN -- depletion transistor ScanTransistor[]; IF t1 # vdd AND t2 # vdd THEN BEGIN -- nonstandard use of NDTrans ndfunny _ ndfunny+1; IF t1 = t2 AND t1 # t0 THEN BEGIN -- capacitor WriteCoords[x,y]; out.PutF["depletion capacitor - ignored: d %g %g %g\n", IO.rope[ToRope[t0.name]], IO.rope[ToRope[t1.name]], IO.rope[ToRope[t2.name]]]; LOOP; END; IF (t0 = t1) OR (t0 = t2) THEN BEGIN --resistor WriteCoords[x,y]; out.PutF["depletion resistor: d %g %g %g\n", IO.rope[ToRope[t0.name]], IO.rope[ToRope[t1.name]], IO.rope[ToRope[t2.name]]]; MakeETrans[vdd, t1,t2]; LOOP; END; WriteCoords[x,y]; out.PutF["yellow transistor: d %g %g %g\n", IO.rope[ToRope[t0.name]], IO.rope[ToRope[t1.name]], IO.rope[ToRope[t2.name]]]; MakeETrans[vdd, t1, t2]; LOOP; END; d _ NEW[NDTrans]; d.next _ dBase; dBase _ d; d.gate _ t0; IF (t1 = vdd) = (t2 = vdd) THEN { WriteCoords[x,y]; out.PutF["depletion error: d %g %g %g\n", IO.rope[ToRope[t0.name]], IO.rope[ToRope[t1.name]], IO.rope[ToRope[t2.name]]]}; d.source _ (IF t1= vdd THEN t2 ELSE t1); d.dlength _ l; d.dwidth _ w; d.x _ x; d.y _ y; ndtrans _ ndtrans+1; IF t0 # d.source THEN t0.GATE _ TRUE; END; 'n, 'N => NULL; -- node characteristics '| => NULL; -- comment character '= => NULL; <> ENDCASE => out.PutF["syntax error: %s\n", IO.text[line]]; ENDLOOP; -- .sim file reading out.PutF["Nodes, Etrans, Dtrans, FunnyDtrans: %7d %7d %7d %7d\n", IO.int[nNodes], IO.int[netrans], IO.int[ndtrans], IO.int[ndfunny]]; END; LinkToEquiv: PROC [e: NETransRef] = BEGIN n: NodeRef = FindCanon[(SELECT e.source FROM vdd, gnd => e.drain, ENDCASE => e.source)]; <> IF n = gnd THEN {Remark["funny NETrans: e", e]}; <> e.igate _ n.igates; n.igates _ e; END; CopyCanonIGates: PROC [n: NodeRef] = {n.igates _ FindCanon[n].igates}; ToRope: PROC [ r: REF ] RETURNS [ s: Rope.ROPE ] = BEGIN WITH r SELECT FROM atom: ATOM => s _ Atom.GetPName[atom]; refText: REF TEXT => s _ Rope.FromRefText[refText]; rope: Rope.ROPE => s _ rope; ENDCASE => s _ "?"; END; ReallyDoStatic: ENTRY PROC [cmd: Commander.Handle] = BEGIN Release: PROC = BEGIN nodes _ NIL; eBase _ NIL; dBase _ NIL; IF in#NIL THEN {in.Close[]; in _ NIL}; IF out#NIL THEN {out.Close[]; out _ NIL}; END; in: IO.STREAM _ NIL; out _ NIL; BEGIN ENABLE UNWIND => Release[]; args: CommandTool.ArgumentVector = CommandTool.Parse[cmd]; RealArg: PROC [n: NAT, default: REAL] RETURNS [REAL] = BEGIN RETURN[IF args.argc>n THEN IO.RIS[args[n]].GetReal[ ! IO.Error, IO.EndOfStream => GOTO BadArg] ELSE default]; EXITS BadArg => ERROR CommandTool.Failed[Rope.Cat["""", args[n], """ isn't a number"]]; END; IF args.argc<2 THEN ERROR CommandTool.Failed["Too few arguments"]; in _ FS.StreamOpen[args[1]]; out _ FS.StreamOpen[args[2], $create]; lowLimit _ RealArg[3, 4.0]; highLimit _ RealArg[4, 10.0]; degradationPerThresh _ RealArg[5, 1.0]; inputThreshCt _ Real.Fix[RealArg[6, 1]]; out.PutF["\n%g -> %g %g\n", IO.rope[args[1]], IO.rope[args[2]], IO.time[]]; nodes _ RefTab.Create[517]; eBase _ NIL; dBase _ NIL; vdd_ Lookup["vdd"]; gnd _ Lookup["gnd"]; gnd.IPD _ TRUE; vdd.threshCt _ 0; vdd.highAssertions _ 1; gnd.highAssertions _ -1; ReadSimFile[in]; ForEachETran[LinkToEquiv]; ForEachNode[CopyCanonIGates]; DoPullups[]; ComputeThresholds[]; ForEachETran[FindInput]; ForEachNode[CheckNode]; ForEachDTran[CheckSourceNodeUsed]; ForEachETran[CheckThreshold]; ForEachDTran[CheckRatio]; END; Release[]; END; DoStatic: Commander.CommandProc = BEGIN BEGIN -- for EXITS ReallyDoStatic[cmd ! CommandTool.Failed => {cmd.err.PutF["\nStatic failed on command line because %g\n", IO.rope[errorMsg]]; GOTO Explain}; IO.Error => {cmd.err.PutF["\nStatic failed trying to get real number in command line\n"]; GOTO Explain}; FS.Error => IF error.group=user THEN {cmd.err.PutF["\nStatic failed trying to open a file because %g\n", IO.rope[error.explanation]]; GOTO Explain} ELSE REJECT]; EXITS Explain => cmd.err.PutF["%g\n", IO.rope[cmd.procData.doc]]; END; END; Commander.Register[key: "Static", proc: DoStatic, doc: "Static analyzes whether a .sim file represents a reasonable NMOS design. Format:\n static inputfile outputfile lowUp/DownZRatio_4.0 highUp/DownZRatio_10.0 degradationPerThresh_1.0 inputThreshFromVdd_1"]; END.