<> <> <> <> DIRECTORY Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, Core, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover, Drot; DrotImpl: CEDAR MONITOR IMPORTS Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover EXPORTS Drot ~ BEGIN OPEN DrotBool, DrotCover, Drot; <> CellTypeFromExpressions: PUBLIC PROC [outputs: LIST OF ROPE, fanout: INT _ 4] RETURNS [Core.CellType] ~ { <> tree: Dag _ BoolTreeFromExpressionList[outputs, TRUE]; RETURN[CreateCellTypeFromDag[tree, fanout]] }; CreateCellTypeFromDag: PUBLIC PROC [tree: Dag, fanout: INT _ 4] RETURNS [Core.CellType] ~ { <> ctcoll: Treeset _ MakeNewCTreeSet[]; AssembleCTree[ctcoll]; FOR ctiter: Dag _ ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO RemoveOrs[ctiter]; ENDLOOP; TwoifyAllTrees[ctcoll]; SimplifyDag[tree]; EstablishLevels[tree]; TwoifyTree[tree]; ReduceFanout[tree, fanout]; RemoveOrs[tree]; WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP; BufferNecessaryNodes[tree]; ReduceFanout[tree, fanout]; KillHangingNodes[tree, FALSE]; ProduceTotalCovering[tree, ctcoll]; RETURN[FromDagToCellType[tree]] }; Parse: PUBLIC PROC [tree: Dag, be: ROPE, inpos, len: INT] RETURNS [outv: Node, outpos: INT] ~ { <> onode, anode, temp: Node _ NIL; --the current or and and node andcount, orcount: INT _ 0; --the number of terms encountered so far in the current or and and. notactivep: BOOL _ FALSE; --should we negate the current expression WHILE inpos # len DO SELECT Rope.Fetch[be, inpos] FROM '( => { --Parse a subexpression [outv: temp, outpos: inpos] _ Parse[tree, be, inpos+1, len]; IF notactivep THEN temp _ Negate[tree, temp]; notactivep _ FALSE; IF andcount > 0 THEN MakeLink[anode, temp]; andcount _ andcount + 1}; ' => --Ignore spaces NULL; '~ => --We should negate the next expression notactivep _ NOT notactivep; '* => --The past item was a term in a multiply IF andcount = 1 THEN { [] _ MakeNewNodeA[tree, NIL, and]; anode _ tree^.csucs; MakeLink[anode, temp]}; '+ => { --The past item was a term in an add IF orcount = 0 THEN { [] _ MakeNewNodeA[tree, NIL, or]; onode _ tree^.csucs}; orcount _ orcount + 1; IF andcount = 1 THEN MakeLink[onode, temp] ELSE MakeLink[onode, anode]; andcount _ 0}; ') => { --we've just finished an expression IF orcount # 0 THEN { outv _ onode; IF andcount = 1 THEN MakeLink[onode, temp] ELSE MakeLink[onode, anode]} ELSE IF andcount = 1 THEN outv _ temp ELSE outv _ anode; outpos _ inpos; RETURN} ENDCASE => { --there is an input variable to be processed nomen: ROPE; [name: nomen, outpos: inpos] _ GetName[be, inpos]; temp _ FindNodeByName[tree, nomen]; IF temp = NIL THEN { [] _ MakeNewNodeA[tree, NIL ,prim]; temp _ tree^.csucs; temp^.inname _ nomen}; IF notactivep THEN temp _ Negate[tree, temp]; notactivep _ FALSE; IF andcount > 0 THEN MakeLink[anode, temp]; andcount _ andcount + 1}; inpos _ inpos + 1; outpos _ inpos; ENDLOOP; }; GetName: PROC [be: ROPE, inpos: INT] RETURNS [name: ROPE, outpos: INT] ~ { <> endpos: INT _ Rope.SkipTo[be, inpos, "()+*"] - 1; inpos _ Rope.SkipOver[be, inpos, " "]; outpos _ endpos; WHILE Rope.Fetch[be,endpos] = ' DO endpos _ endpos - 1 ENDLOOP; name _ Rope.Substr[be, inpos, endpos - inpos + 1] }; AugmentBoolTreeBySingleExpression: PUBLIC PROC [tree: Dag, output: ROPE] ~ { <> len: INT _ Rope.Length[output]; be: ROPE; v1: Node; asspos: INT _ Rope.Find[output, "=", 0]; internal: BOOL _ asspos > -1; asspos _ MAX[asspos, Rope.Find[output, "_", 0]]; be _ Rope.Substr[output, asspos + 1, len - asspos - 1]; IF InputOKp[be] THEN { [outv: v1] _ Parse[tree, Rope.Cat["(", be, ")"], 1, Rope.Length[be]+2]; IF asspos > -1 THEN IF internal THEN v1^.varname _ Rope.Substr[output,0,asspos -1] ELSE v1^.outname _ CONS[Rope.Substr[output,0,asspos -1], v1^.outname]; IF NOT internal THEN v1^.output _ TRUE} ELSE ERROR }; AddInputToCover: PUBLIC PROC [be1: ROPE, ctcoll: Treeset] ~ { <> iter: Node; len: INT _ Rope.Length[be1]; asspos: INT _ Rope.Find[be1, "_", 0]; be : ROPE _ Rope.Substr[be1, asspos + 1, len - asspos - 1]; MakeNewCTree[ctcoll, NIL]; IF InputOKp[be] THEN { [outv: iter] _ Parse[ctcoll^.top, Rope.Cat["(",be,")"], 1, Rope.Length[be] + 2]; IF asspos > -1 THEN iter^.outname _ CONS[Rope.Substr[be1,0,asspos - 1], iter^.outname]; iter^.output _ TRUE} ELSE ERROR }; AssembleCTree: PROC [ctcoll: Treeset] ~ { <> <<>> <<1 input>> AddInputToCover["X _ ~I", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "inv"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; <<2 inputs>> AddInputToCover["X _ ~(I-A * I-B)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand2"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ I-A * I-B", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and2"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ ~(I-A + I-B)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor2"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ I-A + I-B", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or2"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; <<3 inputs (some missing)>> AddInputToCover["X _ ~(I-A * I-B * I-C)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand3"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ (I-A * I-B * I-C)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and3"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ ~(I-A + I-B + I-C)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor3"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ (I-A + I-B + I-C)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or3"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; <<4 inputs (many missing)>> AddInputToCover["X _ ~(I-A * I-B * I-C * I-D)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand4"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; AddInputToCover["X _ ~(I-A + I-B + I-C + I-D)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor4"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; <> AddInputToCover["X _ (I-A * I-B + ~I-A * ~I-B)", ctcoll]; ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "xor2"].val]; ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^; }; InputOKp: PROC [be1: ROPE, out: IO.STREAM] RETURNS [test: BOOL] ~ { <> len: INT _ Rope.Length[be1]; asspos: INT _ Rope.Find[be1, "_", 0]; be : ROPE _ Rope.Substr[be1, asspos + 1, len - asspos - 1]; IF NOT ParensMatch[be] THEN {IO.PutF[out, "Parens not OK\n"]; RETURN[FALSE]} ELSE {IO.PutF[out, "Parens OK\n"]; IF AndOrOK[be] THEN {IO.PutF[out, "Chars OK"]; RETURN[TRUE]} ELSE {IO.PutF[out, "Chars not OK"]; RETURN[FALSE]}} }; ParensMatch: PROC [be: ROPE] RETURNS [test: BOOL] ~ { <> count: INT _ 0; len: INT _ Rope.Length[be]; FOR pos: INT _ Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be,pos+1,"()"] DO IF pos = len THEN RETURN[count = 0] ELSE IF Rope.Fetch[be,pos] = '( THEN count _ count + 1 ELSE { count _ count - 1; IF count = -1 THEN RETURN[FALSE]}; ENDLOOP; }; AndOrOK: PROC [be: ROPE] RETURNS [test: BOOL] ~ { <> len: INT _ Rope.Length[be]; FOR pos: INT _ Rope.SkipTo[be, 0, "*+~"], Rope.SkipTo[be, pos+1, "*+~"] DO <> IF pos = len THEN EXIT ELSE IF Rope.Fetch[be,pos] # '~ THEN { jobbg : INT _ Rope.SkipOver[be, pos+1, "*+ )"]; IF jobbg = len THEN RETURN[FALSE] ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE]; FOR iter: INT _ pos - 1, iter - 1 DO IF iter = -1 THEN RETURN[FALSE] ELSE SELECT Rope.Fetch[be,iter] FROM '*,'+,'(,'~ => RETURN[FALSE]; ' => NULL; ENDCASE => EXIT; ENDLOOP} ELSE { jobbg : INT _ Rope.SkipOver[be, pos+1, "*+ )"]; IF jobbg = len THEN RETURN[FALSE] ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE]} ENDLOOP; FOR pos: INT _ Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be, pos+1, "()"] DO <> IF pos = len THEN RETURN[TRUE] ELSE IF Rope.Fetch[be,pos] = '( THEN { jobbg: INT _ Rope.SkipTo[be, pos+1, ")"]; IF Rope.SkipOver[be,pos+1,") "] > jobbg THEN RETURN[FALSE]; FOR iter: INT _ pos - 1, iter - 1 DO IF iter = -1 THEN EXIT ELSE SELECT Rope.Fetch[be,iter] FROM '*,'+,'~,'( => EXIT; ' => NULL; ENDCASE => RETURN[FALSE]; ENDLOOP} ELSE { jobbb: INT _ Rope.SkipOver[be, pos+1, "+* )"]; jobbg : INT _ Rope.SkipTo[be, pos+1, "*+)"]; IF jobbb < jobbg THEN RETURN[FALSE]}; ENDLOOP; }; Commander.Register[key: "Gen", proc: MakeGenerator, doc: "Standard cells from logic equations"]; <> MakeGenerator: Commander.CommandProc = TRUSTED {Process.Detach[FORK Gen]}; Gen: PUBLIC PROC ~ { tree: Dag _ MakeNewBoolTree[]; ctcoll: Treeset _ MakeNewCTreeSet[]; gettinginput : BOOL _ TRUE; in, out: IO.STREAM; be: ROPE; dummy : INT _ 0; [] _ MakeNewNodeB[tree, NIL, prim, "Gnd"]; [] _ MakeNewNodeB[tree, NIL, prim,"Vdd"]; [in: in, out: out] _ ViewerIO.CreateViewerStreams["Logic Generator"]; AssembleCTree[ctcoll]; IO.PutF[out, "Enter Boolean expressions, to terminate sequence\n"]; WHILE gettinginput DO IO.PutF[out, "> "]; ViewerTools.SetSelection[ViewerIO.GetViewerFromStream[in]]; be _ IO.GetLineRope[in]; IF Rope.IsEmpty[be] THEN EXIT ELSE IF Rope.Fetch[be,0] = ': THEN { be _ Rope.Substr[be,1,Rope.Length[be] - 1]; IF InputOKp[be, out] THEN AddInputToCover[be,ctcoll] ELSE IO.PutF[out, " Problem with cover expression. Please enter anew.\n"]} ELSE IF InputOKp[be,out] THEN AugmentBoolTreeBySingleExpression[tree, be] ELSE IO.PutF[out, " Problem with input expression. Please enter anew.\n"]; dummy _ dummy + 1; ENDLOOP; FromLogicToCell[tree, ctcoll, out]; dummy _ dummy + 1; }; FromLogicToCell: PROC [tree: Dag, ctcoll: Treeset, out: IO.STREAM] ~ { foo: Core.CellType; FOR ctiter: Dag _ ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO RemoveOrs[ctiter]; ENDLOOP; IO.PutF[out, "Done with first pass\n"]; TwoifyAllTrees[ctcoll]; IO.PutF[out, "Done with second pass\n"]; SimplifyDag[tree]; IO.PutF[out, "Done with third pass\n"]; EstablishLevels[tree]; IO.PutF[out, "Done with fourth pass\n"]; TwoifyTree[tree]; IO.PutF[out, "Done with fifth pass\n"]; ReduceFanout[tree, 4]; IO.PutF[out, "Done with sixth pass\n"]; RemoveOrs[tree]; IO.PutF[out, "Done with seventh pass\n"]; WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP; IO.PutF[out, "Done with pass seven and a half\n"]; BufferNecessaryNodes[tree]; ReduceFanout[tree, 4]; KillHangingNodes[tree, FALSE]; IO.PutF[out, "Done with pass seven and three quarters\n"]; ProduceTotalCovering[tree, ctcoll]; IO.PutF[out, "Done with eighth pass\n"]; foo _ FromDagToCellType[tree]; IO.PutF[out, "Done\n"]; }; Disp: PUBLIC PROC [tree: Dag, out: IO.STREAM] ~ { <> iter: Node _ tree^.csucs; WHILE iter # NIL DO kiter: Kidptr _ iter^.kidlist; piter: Kidptr _ iter^.parlist; IO.PutF[out, "\n%3g: ", IO.int[iter^.number]]; SELECT iter^.type FROM and => IO.PutF[out," and"]; nand => IO.PutF[out,"nand"]; or => IO.PutF[out," or"]; nor => IO.PutF[out," nor"]; not => IO.PutF[out," not"]; buf => IO.PutF[out," buf"]; ENDCASE => IO.PutF[out,"prim"]; IO.PutF[out, Rope.Concat[" ",Rope.Concat[iter^.inname, Rope.Concat[" ", iter^.varname]]]]; IF iter^.output THEN IO.PutF[out, Rope.Concat["*^*",iter^.outname.first]]; IF iter^.sim THEN IO.PutF[out," Sim "]; IO.PutF[out, " %3g\n", IO.int[iter^.level]]; IO.PutF[out, " Kids: "]; WHILE kiter # NIL DO IO.PutF[out, "%3g", IO.int[kiter^.child^.number]]; IF kiter^.next # NIL THEN IO.PutF[out, ","] ELSE IO.PutF[out, "\n"]; kiter _ kiter^.next; ENDLOOP; IO.PutF[out, " Pars: "]; WHILE piter # NIL DO IO.PutF[out, "%3g", IO.int[piter^.child^.number]]; IF piter^.next # NIL THEN IO.PutF[out, ","]; piter _ piter^.next; ENDLOOP; iter _ iter^.next; ENDLOOP; IO.PutF[out,"\n"] }; <> SimplifyDag: PROC [tree: Dag] ~ { iter : Node; firstPass : BOOL _ TRUE; WHILE firstPass OR AbsorbIdenticalNodes[tree] DO WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] OR ProcessGndAndVdd[tree] OR ReduceExpressions[tree] DO ENDLOOP; firstPass _ FALSE; ENDLOOP; <> OrderNodesByPrims[tree]; iter _ tree^.csucs^.prev; WHILE iter # tree^.csucs DO temp : Node _ iter^.next; RAdjustVertex[tree, iter]; IF temp = NIL THEN IF iter = tree^.csucs^.prev THEN iter _ iter^.prev ELSE iter _ tree^.csucs^.prev ELSE IF temp^.prev = iter THEN iter _ iter^.prev ELSE iter _ temp^.prev; ENDLOOP; RAdjustVertex[tree, iter]; }; AbsorbIdenticalNodes: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ { <> OrderNodesByOrphans[tree]; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO subtype : Vtype; IF iter^.type = and OR iter^.type = nand THEN subtype _ and ELSE IF iter^.type = or OR iter^.type = nor THEN subtype _ or ELSE subtype _ iter^.type; <> FOR kiditer: Kidptr _ iter^.kidlist, kiditer^.next UNTIL kiditer = NIL DO IF (kiditer^.child^.type = subtype OR iter^.type = not OR iter^.type = buf) AND kiditer^.child^.parnum = 1 AND NOT kiditer^.child^.output THEN { FOR grandchilditer: Kidptr _ kiditer^.child^.kidlist, grandchilditer^.next UNTIL grandchilditer = NIL DO MakeLinkE[iter, grandchilditer^.child]; ENDLOOP; IF iter^.type = not THEN iter^.type _ NegNodeType[kiditer^.child^.type] ELSE IF iter^.type = buf THEN iter^.type _ kiditer^.child^.type; RemoveNode[tree, kiditer^.child]; modified _ TRUE}; ENDLOOP; ENDLOOP; }; RemoveDuplicateNodes: PUBLIC PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ { <> <> PrimitivesToEnd[tree]; IF tree^.csucs^.type # prim THEN { front: Node _ tree^.csucs^.prev; rear : Node _ front; ClearScratch[tree]; WHILE front^.type = prim DO front _ front^.prev; ENDLOOP; WHILE front # NIL DO szuloiter : Kidptr _ rear^.parlist; middle: Node _ front^.next; WHILE szuloiter # NIL DO KidptrToEnd[szuloiter^.parlink, szuloiter^.child]; IF szuloiter^.child^.scratch = szuloiter^.child^.kidnum - 1 THEN { nodeiter: Node _ middle^.prev; WHILE nodeiter # front DO IF nodeiter^.type = szuloiter^.child^.type AND ForwardSimilar[nodeiter, szuloiter^.child] THEN { MergeNodes[nodeiter, szuloiter^.child, tree]; modified _ TRUE; EXIT} ELSE nodeiter _ nodeiter^.prev; ENDLOOP; front _ PlaceAfter[tree, front, szuloiter^.child]} ELSE szuloiter^.child^.scratch _ szuloiter^.child^.scratch + 1; szuloiter _ szuloiter^.next; ENDLOOP; rear _ rear^.prev; ENDLOOP} }; MergeNodes: PROC [bol, be: Node, tree: Dag] ~ { <> be^.output _ be^.output OR bol^.output; be^.outname _ MergeListOfRopes[bol^.outname, be^.outname]; be^.inname _ Rope.Concat[be^.inname, bol^.inname]; be^.varname _ Rope.Concat[be^.varname, bol^.varname]; FOR iter: Kidptr _ bol^.parlist, iter^.next UNTIL iter = NIL DO MakeLink[iter^.child, be]; ENDLOOP; RemoveNode[tree, bol] }; RemoveAllIdenticalLinks: PROC [tree: Dag] RETURNS [modified: BOOL _ FALSE] ~ { FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO modified _ modified OR RemoveIdenticalLinks[iter] ENDLOOP; }; RemoveIdenticalLinks: PROC [vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ { FOR kiditer: Kidptr _ vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO kiditer^.child^.scratch _ 0; ENDLOOP; FOR kiditer: Kidptr _ vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO IF kiditer^.child^.scratch = 1 THEN { [] _ KillCLink[kiditer]; modified _ TRUE} ELSE kiditer^.child^.scratch _ 1; ENDLOOP; FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO pariter^.child^.scratch _ 0; ENDLOOP; FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO IF pariter^.child^.scratch = 1 THEN { [] _ KillPLink[pariter]; modified _ TRUE} ELSE pariter^.child^.scratch _ 1; ENDLOOP; }; ProcessGndAndVdd: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ { <> gnd: Node _ FindInputByName[tree, "Gnd"]; vdd: Node _ FindInputByName[tree, "Vdd"]; IF gnd # NIL OR vdd # NIL THEN { IF gnd = NIL THEN [] _ MakeNewNodeB[tree, NIL, prim, "Gnd"] ELSE IF vdd = NIL THEN [] _ MakeNewNodeB[tree, NIL, prim, "Vdd"]; IF gnd^.parlist # NIL OR vdd^.parlist # NIL THEN mdoified _ TRUE; WHILE gnd^.parlist # NIL OR vdd^.parlist # NIL DO IF gnd^.parlist # NIL THEN ProcessGnd[gnd, vdd, tree]; IF vdd^.parlist # NIL THEN ProcessVdd[gnd, vdd, tree]; ENDLOOP} }; ProcessGnd: PROC [gnd, vdd: Node, tree: Dag] ~ { <> par : Node _ gnd^.parlist^.child; SELECT par^.type FROM or, nor => { [] _ KillPLink[gnd^.parlist]; RAdjustVertex[tree, par]}; and, buf => { FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLinkE[pariter^.child, gnd]; ENDLOOP; gnd^.output _ gnd^.output OR par^.output; gnd^.outname _ MergeListOfRopes[gnd^.outname, par^.outname]; RemoveNode[tree, par]}; nand, not => { FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLinkE[pariter^.child, vdd]; ENDLOOP; vdd^.output _ vdd^.output OR par^.output; vdd^.outname _ MergeListOfRopes[vdd^.outname, par^.outname]; RemoveNode[tree, par]}; ENDCASE => tree^.csucs^.prev^.next^.prev _ NIL; --This will cause an error. Shouldn't be reached. }; ProcessVdd: PROC [gnd, vdd: Node, tree: Dag] ~ { par: Node _ vdd^.parlist^.child; SELECT par^.type FROM and, nand => { [] _ KillPLink[gnd^.parlist]; RAdjustVertex[tree, par]}; nor, not => { FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLinkE[pariter^.child, gnd]; ENDLOOP; gnd^.output _ gnd^.output OR par^.output; gnd^.outname _ MergeListOfRopes[gnd^.outname, par^.outname]; RemoveNode[tree, par]}; or, buf => { FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLinkE[pariter^.child, vdd]; ENDLOOP; vdd^.output _ vdd^.output OR par^.output; vdd^.outname _ MergeListOfRopes[vdd^.outname, par^.outname]; RemoveNode[tree, par]}; ENDCASE => tree^.csucs^.prev^.next^.prev _ NIL; --This will cause an error. Shouldn't be reached. }; ReduceExpressions: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ { <> OrderNodesByPrims[tree]; FOR iter: Node _ tree^.csucs^.prev, iter^.prev UNTIL iter = tree^.csucs DO modified _ modified OR ReduceExpression1[tree, iter]; modified _ modified OR ReduceExpression2[tree, iter]; ENDLOOP; modified _ modified OR ReduceExpression1[tree, tree^.csucs]; modified _ modified OR ReduceExpression2[tree, tree^.csucs]; }; ReduceExpression1: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ { <> subtype: Vtype _ and; IF vertex^.kidnum > 1 THEN { iter1: Kidptr _ vertex^.kidlist; IF vertex^.type = and OR vertex^.type = nand THEN subtype _ or; WHILE iter1 # NIL DO pair : Node _ NegativeOf[iter1^.child]; IF pair = NIL THEN iter1 _ iter1^.next ELSE { iter2: Kidptr _ vertex^.kidlist; IF ConnectionBetween[vertex, pair] # NIL THEN { This is the a*~a clause IF subtype = or THEN [] _ MakeLink[vertex, FindInputByName[tree, "Gnd"]] ELSE [] _ MakeLink[vertex, FindInputByName[tree, "Vdd"]]; <> [] _ ProcessGndAndVdd[tree]; RETURN[TRUE]}; WHILE iter2 # NIL DO IF iter2^.child^.type # subtype OR iter2 = iter1 OR ConnectionBetween[iter2^.child, pair] = NIL <> THEN iter2 _ iter2^.next ELSE IF iter2^.child^.kidnum = 2 THEN { IF iter2^.child^.kidlist^.child = pair THEN [] _ MakeLinkE[vertex, iter2^.child^.kidlist^.next^.child] ELSE [] _ MakeLinkE[vertex, iter2^.child^.kidlist^.child]; iter2 _ iter2^.next; modified _ TRUE; IF iter2^.prev^.child^.parnum = 1 THEN RemoveNode[tree, iter2^.prev^.child] ELSE [] _ KillCLink[iter2^.prev]} ELSE IF iter2^.child^.parnum = 1 THEN { temp: Kidptr _ iter2^.next; [] _ KillCLink[ConnectionBetween[iter2^.child, pair]]; [] _ PlaceKidptrAfter[iter1, iter2, vertex]; modified _ TRUE; iter2 _ temp} ELSE iter2 _ iter2^.next; <> ENDLOOP; iter1 _ iter1^.next}; ENDLOOP} }; ReduceExpression2: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ { <> subtype : Vtype _ and; IF vertex^.kidnum > 1 THEN { front: Kidptr; OrderKidptrsBySize[vertex]; front _ vertex^.kidlist; IF vertex^.type = and OR vertex^.type = nand THEN subtype _ or; WHILE front # NIL DO nextfront: Kidptr _ front^.next; IF front^.child^.type = subtype THEN { rear: Kidptr _ front^.next; WHILE rear # NIL DO IF rear^.child^.type # subtype THEN rear _ rear^.next ELSE { conFromFrontToRear: Kidptr _ ConnectionBetween[front^.child, rear^.child]; conFromRearToFront: Kidptr _ ConnectionBetween[rear^.child, front^.child]; <> IF conFromRearToFront # NIL THEN IF rear^.child^.parnum = 1 THEN {rear _ rear^.next; modified _ TRUE; IF rear = NIL THEN RemoveNode[tree, vertex^.kidlist^.prev^.child] ELSE RemoveNode[tree, rear^.prev^.child]} ELSE rear _ KillCLink[rear] ELSE IF conFromFrontToRear # NIL THEN { nextfront _ front^.next; IF front^.child^.parnum = 1 THEN RemoveNode[tree, front^.child] ELSE [] _ KillCLink[front]; modified _ TRUE; rear _ NIL} ELSE IF rear^.child^.kidnum # front^.child^.kidnum THEN IF IntersectionSize[front^.child, rear^.child] = rear^.child^.kidnum <> THEN { --second case nextfront _ front^.next; IF front^.child^.parnum = 1 THEN RemoveNode[tree, front^.child] ELSE [] _ KillCLink[front]; modified _ TRUE; rear _ NIL} ELSE rear _ rear^.next ELSE { --third case temp: Kidptr; exp, negexp: Kidptr; [son1 : exp, son2: negexp] _ CheckTheseTwo[front^.child, rear^.child]; IF exp = NIL THEN rear _ rear^.next ELSE { IF rear^.child^.parnum = 1 THEN { temp _ rear; [] _ KillCLink[negexp]; Percolate[temp, vertex]; nextfront _ KillCLink[front]; modified _ TRUE; IF exp^.parlink^.child^.parnum = 0 AND NOT exp^.parlink^.child^.output THEN RemoveNode[tree, exp^.parlink^.child]} ELSE IF front^.child^.parnum = 1 THEN { temp _ front; [] _ KillCLink[exp]; [] _ KillCLink[rear]; modified _ TRUE; nextfront _ front^.next; Percolate[temp, vertex]} ELSE { MakeLink[vertex, MakeNewNodeA[tree, vertex, subtype]]; <> <> temp _ vertex^.next^.parlist^.parlink; FOR iter: Kidptr _ front^.child^.kidlist, iter^.next UNTIL iter = NIL DO IF iter # exp THEN MakeLink[temp^.child, iter^.child]; ENDLOOP; Percolate[temp, vertex]; [] _ KillCLink[rear]; nextfront _ KillCLink[front]}; rear _ NIL}}} ENDLOOP}; front _ nextfront; ENDLOOP}; }; CheckTheseTwo: PROC [sib1, sib2: Node] RETURNS [son1: Kidptr _ NIL, son2: Kidptr _ NIL] ~ { <> FOR iter: Kidptr _ sib1^.kidlist, iter^.next UNTIL iter = NIL DO pair: Node _ NegativeOf[iter^.child]; IF pair # NIL THEN { dummy: BOOL _ TRUE; sonlink: Kidptr _ ConnectionBetween[sib2, pair]; IF sonlink # NIL THEN { <> FOR iter1: Kidptr _ sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO iter1^.child^.scratch _ 0; ENDLOOP; FOR iter2: Kidptr _ sib2^.kidlist, iter2^.next UNTIL iter2 = NIL DO iter2^.child^.scratch _ 1; ENDLOOP; FOR iter1: Kidptr _ sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO IF iter1^.child^.scratch # 1 AND iter1^.child # iter^.child THEN dummy _ FALSE; ENDLOOP; IF dummy THEN { son1 _ iter; son2 _ sonlink; RETURN}}} ENDLOOP; }; OrderKidptrsBySize: PROC [vertex: Node] ~ { iter: Kidptr _ vertex^.kidlist; temp: Kidptr; IF iter # NIL THEN iter _ iter^.prev ELSE RETURN; WHILE iter # vertex^.kidlist DO temp _ iter^.prev; Percolate[iter, vertex]; iter _ temp; ENDLOOP; Percolate[iter, vertex] }; Percolate: PROC [kid: Kidptr, vertex: Node] ~ { IF kid^.next # NIL AND kid^.next^.child^.kidnum > kid^.child^.kidnum THEN { FOR iter: Kidptr _ kid^.next, iter^.next UNTIL iter = NIL DO IF kid^.child^.kidnum > iter^.child^.kidnum THEN { [] _ PlaceKidptrAfter[iter^.prev, kid, vertex]; RETURN} ENDLOOP; [] _ PlaceKidptrAfter[vertex^.kidlist^.prev, kid, vertex]} }; PlaceKidptrAfter: PROC [before, after: Kidptr, tree: Node] RETURNS[Kidptr] ~ { <> IF before = NIL THEN PlaceKidptrAtBeg[after, tree] ELSE IF before # after AND (before^.next # after) THEN IF before^.next = NIL THEN { before^.next _ after; IF after = tree^.kidlist THEN { tree^.kidlist _ after^.next; after^.next _ NIL} ELSE { after^.prev^.next _ after^.next; after^.next^.prev _ after^.prev; tree^.kidlist^.prev _ after; after^.next _ NIL; after^.prev _ before}} ELSE { IF after^.next = NIL THEN tree^.kidlist^.prev _ after^.prev ELSE after^.next^.prev _ after^.prev; IF after = tree^.kidlist THEN tree^.kidlist _ after^.next ELSE after^.prev^.next _ after^.next; after^.prev _ before; after^.next _ before^.next; before^.next^.prev _ after; before^.next _ after}; IF after = tree^.kidlist THEN RETURN[NIL] ELSE RETURN[after^.prev]; }; PlaceKidptrAtBeg: PROC [vertex: Kidptr, tree: Node] ~ { <> IF vertex # tree^.kidlist THEN { IF vertex^.next = NIL THEN { vertex^.prev^.next _ NIL } ELSE { vertex^.prev^.next _ vertex^.next; vertex^.next^.prev _ vertex^.prev; vertex^.prev _ tree^.kidlist^.prev; tree^.kidlist^.prev _ vertex }; vertex^.next _ tree^.kidlist; tree^.kidlist _ vertex} }; RAdjustVertex: PROC [tree: Dag, vertex: Node] ~ { <> IF vertex^.type # prim THEN IF vertex^.kidnum = 0 THEN { IF vertex^.output THEN vertex^.kidlist^.next _ NIL;--Error. There is a floating output FOR iter: Kidptr _ vertex^.parlist, iter^.next UNTIL iter = NIL DO par : Node _ iter^.child; [] _ KillPLink[iter]; RAdjustVertex[tree, par]; ENDLOOP} ELSE IF vertex^.kidnum = 1 THEN SELECT vertex^.type FROM nand, nor => vertex^.type _ not; and, or => { son: Node _ vertex^.kidlist^.child; son^.output _ son^.output OR vertex^.output; son^.outname _ MergeListOfRopes[son^.outname, vertex^.outname]; FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLink[pariter^.child, son]; ENDLOOP; RemoveNode[tree, vertex]}; ENDCASE => NULL; }; ReduceFanout: PUBLIC PROC [tree: Dag, fout: INT] ~ { <> OrderNodesByOrphans[tree]; ClearScratch[tree]; FOR front: Node _ tree^.csucs, front^.next UNTIL front = NIL DO IF front^.type # prim THEN WHILE front^.parnum > fout DO [] _ MakeNewNodeB[tree, front, front^.type]; FOR kiditer: Kidptr _ front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO MakeLink[front^.prev, kiditer^.child]; ENDLOOP; IF fout < 2*front^.parnum THEN FOR i: INT IN [1..front^.parnum/2] DO MakeLink[front^.parlist^.child,front^.prev]; [] _ KillPLink[front^.parlist]; ENDLOOP ELSE FOR i: INT IN [1..fout] DO MakeLink[front^.parlist^.child,front^.prev]; [] _ KillPLink[front^.parlist]; ENDLOOP; ENDLOOP; ENDLOOP }; BufferNecessaryNodes: PROC [tree: Dag] ~ { <> OrderNodesByOrphans[tree]; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO IF iter^.type = prim THEN IF iter^.output THEN { IF Member[iter^.inname, iter^.outname] THEN iter^.outname _ RemoveNameFromList[iter^.inname, iter^.outname] ELSE iter^.output _ FALSE; SELECT iter^.inname FROM "Gnd" => IF iter^.outname # NIL THEN { vdd: Node _ FindInputByName[tree, "Vdd"]; WHILE iter^.outname # NIL DO MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], vdd]; iter^.outname _ iter^.outname.rest; ENDLOOP; "Vdd" => IF iter^.outname # NIL THEN { gnd: Node _ FindInputByName[tree, "Gnd"]; WHILE iter^.outname # NIL DO MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], gnd]; iter^.outname _ iter^.outname.rest; ENDLOOP; ENDCASE => IF iter^.outname # NIL THEN { notAbove: Node _ NotAbove[iter^.parlist]; IF notAbove = NIL THEN { notAbove _ MakeNewNodeB[tree, iter, not]; MakeLink[notAbove, iter]}; WHILE iter^.outname # NIL DO MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove]; notAbove^.prev^.output _ TRUE; notAbove^.prev^.outname _ LIST[iter^.outname.first]; iter^.outname _ iter^.outname.rest; ENDLOOP}; IF iter^.output THEN iter^.outname _ LIST[iter^.inname];} <> ELSE NULL ELSE IF iter^.output THEN IF iter^.outname # NIL AND iter^.outname.rest # NIL THEN { notAbove: Node _ NotAbove[iter^.parlist]; IF notAbove = NIL THEN { notAbove _ MakeNewNodeB[tree, iter, not]; MakeLink[notAbove, iter]}; WHILE iter^.outname.rest # NIL DO MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove]; notAbove^.prev^.output _ TRUE; notAbove^.prev^.outname _ LIST[iter^.outname.first]; iter^.outname _ iter^.outname.rest; ENDLOOP}; ENDLOOP; }; RemoveNameFromList: PROC [name: ROPE, list: LIST OF ROPE] RETURNS [LIST OF ROPE] ~ { <> IF list = NIL THEN RETURN[NIL] ELSE IF Rope.Equal[list.first,name] THEN RETURN[RemoveNameFromList[name, list.rest]] ELSE RETURN[CONS[list.first, RemoveNameFromList[name, list.rest]]] }; Member: PROC [element: ROPE, list: LIST OF ROPE] RETURNS [BOOL] ~ { <> IF list = NIL THEN RETURN[FALSE] ELSE IF Rope.Equal[element,list.first] THEN RETURN[TRUE] ELSE RETURN[Member[element, list.rest]] }; RemoveOrs: PROC [tree: Dag] ~ { <> OrderNodesByOrphans[tree]; FOR front: Node _ tree^.csucs, front^.next UNTIL front = NIL DO notAbove : Node; IF front^.type = or OR front^.type = nor THEN { FOR kiditer: Kidptr _ front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO NegateConnection[tree, kiditer]; ENDLOOP; IF front^.type = or THEN front^.type _ nand ELSE front^.type _ and}; IF front^.type = and THEN { notAbove _ NotAbove[front^.parlist]; IF notAbove = NIL THEN { Splitnode[tree, front]; front^.type _ nand; front^.prev^.type _ not} ELSE IF front^.parnum =1 AND NOT front^.output THEN { FOR iter: Kidptr _ notAbove^.parlist, iter^.next UNTIL iter = NIL DO MakeLink[iter^.child, front]; ENDLOOP; front^.output _ notAbove^.output; front^.varname _ notAbove^.varname; front^.inname _ notAbove^.inname; front^.outname _ notAbove^.outname; RemoveNode[tree, notAbove]; front^.type _ nand} ELSE SwitchWithNot[notAbove]}; IF front^.type = not THEN { notAbove _ NotAbove[front^.parlist]; IF notAbove # NIL THEN { FOR pariter: Kidptr _ notAbove^.parlist, pariter^.next UNTIL pariter = NIL DO MakeLink[pariter^.child, front^.kidlist^.child]; ENDLOOP; front^.kidlist^.child^.output _ front^.kidlist^.child^.output OR notAbove^.output; front^.kidlist^.child^.inname _ Rope.Concat[front^.kidlist^.child^.inname, notAbove^.inname]; front^.kidlist^.child^.outname _ MergeListOfRopes[notAbove^.outname, front^.kidlist^.child^.outname]; RemoveNode[tree, notAbove]}}; ENDLOOP; }; Splitnode: PROC [tree: Dag, vertex: Node, type: Vtype _ not] ~ { <> temp: Node _ NEW[Noderec _ [next: vertex, prev: vertex^.prev, kidlist: NEW[Kidrec _ [child: vertex]], kidnum: 1, parnum: vertex^.parnum, parlist: vertex^.parlist, type: type, output: vertex^.output, inname: vertex^.inname, outname: vertex^.outname, number: tree^.size + 1]]; pariter: Kidptr; vertex^.parlist _ NEW[Kidrec _ [child: temp, parlink: temp^.kidlist]]; vertex^.parnum _ 1; vertex^.output _ FALSE; vertex^.outname _ NIL; vertex^.inname _ NIL; vertex^.varname _ NIL; vertex^.parlist^.prev _ vertex^.parlist; temp^.kidlist^.prev _ temp^.kidlist; temp^.kidlist^.parlink _ vertex^.parlist; IF vertex = tree^.csucs THEN tree^.csucs _ temp ELSE vertex^.prev^.next _ temp; vertex^.prev _ temp; pariter _ temp^.parlist; WHILE pariter # NIL DO pariter^.parlink^.parlink _ pariter; pariter^.parlink^.child _ temp; pariter _ pariter^.next ENDLOOP; tree^.size _ tree^.size + 1 }; SwitchWithNot: PROC [vertex: Node] ~ { <> fmarker : Kidptr _ vertex^.parlist; rmarker : Kidptr _ NIL; tempname: ROPE; tempoutname: LIST OF ROPE; IF fmarker # NIL THEN rmarker _ fmarker^.prev; FOR piter: Kidptr _ vertex^.kidlist^.child^.parlist, piter^.next UNTIL piter = NIL DO IF piter^.child # vertex THEN { MakeLink[piter^.child, vertex]; [] _ KillPLink[piter]}; ENDLOOP; IF fmarker # NIL THEN { FOR piter: Kidptr _ fmarker, piter^.next UNTIL piter = rmarker DO MakeLink[piter^.child, vertex^.kidlist^.child]; [] _ KillPLink[piter]; ENDLOOP; MakeLink[rmarker^.child, vertex^.kidlist^.child]; [] _ KillPLink[rmarker]}; IF ((NOT vertex^.kidlist^.child^.output) AND vertex^.output) OR (vertex^.kidlist^.child^.output AND NOT vertex^.output) THEN { vertex^.kidlist^.child^.output _ vertex^.output; vertex^.output _ NOT vertex^.output}; tempname _ vertex^.inname; vertex^.inname _ vertex^.kidlist^.child^.inname; vertex^.kidlist^.child^.inname _ tempname; tempname _ vertex^.varname; vertex^.varname _ vertex^.kidlist^.child^.varname; vertex^.kidlist^.child^.varname _ tempname; tempoutname _ vertex^.outname; vertex^.outname _ vertex^.kidlist^.child^.outname; vertex^.kidlist^.child^.outname _ tempoutname; vertex^.kidlist^.child^.type _ NegNodeType[vertex^.kidlist^.child^.type]; }; TwoifyTree: PUBLIC PROC [tree: Dag] ~ { <> OrderNodesByOrphans[tree]; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO TwoifyGate[iter, tree]; ENDLOOP; }; TwoifyGate: PROC [vertex: Node, tree: Dag] ~ { < 2 children, this will remake that node so that there are at most two inputs per gate at that node.-->> IF vertex^.kidnum > 2 THEN { level: INT _ 1; inleft: INT; singlep: BOOL _ FALSE; remaining: INT _ vertex^.kidnum; nexttype: Vtype _ and; iter: Kidptr; right, left: Node; links: Links _ CreateLinkSet[vertex^.kidlist]; llinks: Links _ CreateLinkSet[NIL]; rlinks: Links _ CreateLinkSet[NIL]; OrderLinksByReq[links]; iter _ links^.top; WHILE iter # NIL DO IF iter^.req > 0 THEN { temp: Kidptr _ iter^.next; TransferLink[links, iter, llinks]; iter _ temp; remaining _ remaining - 1; IF Fullp[llinks] THEN IF Fullp[rlinks] THEN ERROR --Cannot satisfy requirements in TwoifyGate at vertex^.number ELSE { templs: Links _ llinks; llinks _ rlinks; rlinks _ templs}}; iter _ iter^.next; ENDLOOP; WHILE SpaceA[llinks, level] + SpaceA[rlinks, level] < remaining DO level _ level + 1; ENDLOOP; inleft _ (remaining * SpaceA[llinks, level])/(SpaceA[llinks, level] + SpaceA[rlinks, level]); FOR counter: INT IN [1..inleft] DO TransferLink[links, links^.top, llinks]; ENDLOOP; WHILE links^.top # NIL DO TransferLink[links, links^.top, rlinks]; ENDLOOP; IF inleft # 1 AND rlinks^.top^.next = NIL THEN { templs: Links _ llinks; llinks _ rlinks; rlinks _ templs; inleft _ 1}; singlep _ (inleft = 1); IF vertex^.type = nor OR vertex^.type = or THEN nexttype _ or; right _ MakeNewNodeA[tree, vertex, nexttype, NIL]; vertex^.kidlist _ rlinks^.top; WHILE vertex^.kidlist # NIL DO MakeLink[right, vertex^.kidlist^.child]; [] _ KillCLink[vertex^.kidlist]; ENDLOOP; vertex^.kidlist _ llinks^.top; IF NOT singlep THEN { left _ MakeNewNodeA[tree, vertex, nexttype, NIL]; WHILE vertex^.kidlist # NIL DO MakeLink[left, vertex^.kidlist^.child]; [] _ KillCLink[vertex^.kidlist]; ENDLOOP; MakeLink[vertex, left]}; MakeLink[vertex, right]; IF NOT singlep THEN TwoifyGate[left, tree]; TwoifyGate[right, tree]} }; CreateLinkSet: PROC [link: Kidptr] RETURNS [newLinks: Links] ~ { <> newLinks _ NEW[Linksrec _ [top: link]]; IF link # NIL THEN newLinks^.size _ link^.parlink^.child^.kidnum }; OrderLinksByReq: PROC [links: Links] ~ { <> front : Kidptr _ links^.top; WHILE front # NIL DO iter: Kidptr _ front^.next; WHILE iter # NIL DO IF iter^.req > iter^.prev^.req THEN { SwitchLinksB[iter, links]; IF front^.prev = iter THEN front _ iter; iter _ iter^.next}; iter _ iter^.next ENDLOOP; front _ front^.next; ENDLOOP }; SwitchLinksB: PROC [link: Kidptr, links: Links] ~ { <> IF link # links^.top THEN { prev: Kidptr _ link^.prev; IF link^.next = NIL THEN links^.top^.prev _ prev ELSE link^.next^.prev _ prev; link^.next _ prev; IF prev # links^.top THEN prev^.prev^.next _ link ELSE links^.top _ link; prev^.prev _ link} }; TransferLink: PROC [ebbol: Links, link: Kidptr, ebbe: Links] ~ { <> IF link^.next = NIL THEN ebbol^.top^.prev _ link^.prev ELSE link^.next^.prev _ link^.prev; IF link = ebbol^.top THEN ebbol^.top _ link^.next ELSE link^.prev^.next _ link^.next; link^.next _ NIL; IF ebbe^.top = NIL THEN ebbe^.top _ link ELSE { link^.prev _ ebbe^.top^.prev; ebbe^.top^.prev^.next _ link}; ebbe^.top^.prev _ link; ebbol^.size _ ebbol^.size - 1; ebbe^.size _ ebbe^.size + 1; IF link^.req > 0 THEN link^.req _ link^.req - 1 }; Fullp: PROC [links: Links] RETURNS [valasz: BOOL _ FALSE] ~ { <> IF links^.top # NIL THEN RETURN[0 # SpaceA[links, links^.top^.prev^.req]] }; SpaceA: PROC [links: Links, level: INT] RETURNS [free: INT _ 1] ~ { < 0 this yields the number of free nodes still left assuming a tree of maximum depth level-->> iter: Kidptr _ links^.top; atlevel: INT _ 0; -- Sort of kludgey, but TransferLink has subtracted one from the req field -- WHILE iter # NIL DO IF iter^.req > atlevel THEN IF atlevel = level THEN RETURN ELSE { atlevel _ atlevel + 1; free _ 2 * free} ELSE { free _ free - 1; IF free = 0 THEN RETURN; iter _ iter^.next} ENDLOOP; WHILE atlevel + 1 # level DO free _ 2 * free; atlevel _ atlevel + 1; ENDLOOP; RETURN }; <> CollectWires: PROC [iter: Node] RETURNS [pas: LIST OF CoreCreate.PA _ NIL] ~ { <> IF iter # NIL THEN { IF iter^.type = prim THEN pas _ CONS[[iter^.inname, iter^.mate^.wire], CollectWires[iter^.next]] ELSE IF iter^.output THEN pas _ CONS[[iter^.outname.first, iter^.mate^.wire], CollectWires[iter^.next]] ELSE pas _ CollectWires[iter^.next]} }; WireNameFromNode: PROC [vertex: Node] RETURNS [name: ROPE] ~ { <> IF vertex^.output OR vertex^.type = prim THEN IF vertex^.type = prim THEN name _ vertex^.inname ELSE name _ vertex^.outname.first ELSE IF NOT Rope.IsEmpty[vertex^.inname] THEN name _ Rope.Concat["intrnal", vertex^.inname] ELSE IF NOT Rope.IsEmpty[vertex^.varname] THEN name _ Rope.Concat["intrnal", vertex^.varname] ELSE name _ Rope.Concat["intrnal",Convert.RopeFromInt[vertex^.number,10,FALSE]]; }; MarkCoveredSubtree: PROC [vertex: Node, cover: Node] ~ { <> IF cover^.type = prim THEN IF vertex^.scratch # 1 THEN { vertex^.scratch _ 1; IF vertex^.type # prim THEN MarkCoveredSubtree[vertex, vertex^.cover^.csucs]} ELSE NULL ELSE IF cover^.type = not THEN MarkCoveredSubtree[vertex^.kidlist^.child, cover^.kidlist^.child] ELSE { MarkCoveredSubtree[cover^.kidlist^.child^.mate, cover^.kidlist^.child]; MarkCoveredSubtree[cover^.kidlist^.next^.child^.mate, cover^.kidlist^.next^.child]} }; FromDagToCellType: PROC [tree: Dag] RETURNS [cellType: Core.CellType] ~ { <> publics: LIST OF CoreCreate.WR _ NIL; intOnlys: LIST OF CoreCreate.WR _ NIL; instances: CoreCreate.CellInstances _ NIL; ClearScratch[tree]; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO <> IF iter^.output AND iter^.scratch = 0 THEN { iter^.scratch _ 1; IF iter^.type # prim THEN MarkCoveredSubtree[iter, iter^.cover^.csucs]}; IF iter^.type = prim THEN iter^.scratch _ 1; <> ENDLOOP; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO <> IF iter^.scratch = 1 THEN { iter^.wire _ CoreOps.CreateWires[0, WireNameFromNode[iter]]; IF iter^.output OR iter^.type = prim THEN publics _ CONS[iter^.wire, publics] ELSE intOnlys _ CONS[iter^.wire, intOnlys]} ENDLOOP; FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO <> IF iter^.scratch = 1 AND iter^.type # prim THEN instances _ CONS[CoreCreate.InstanceList[iter^.cover^.cell, CollectWires[iter^.cover^.csucs]], instances]; ENDLOOP; RETURN [CoreCreate.Cell[ public: CoreCreate.WireList[publics], onlyInternal: CoreCreate.WireList[intOnlys], instances: instances ]] }; <> BoolTreeFromExpressionList: PUBLIC PROC [outputs: LIST OF ROPE, includeGlobalVariablesp: BOOL _ FALSE] RETURNS [tree: Dag] ~ { <> tree _ MakeNewBoolTree[]; IF includeGlobalVariablesp THEN { [] _ MakeNewNodeB[tree, NIL, prim, "Gnd"]; [] _ MakeNewNodeB[tree, NIL, prim, "Vdd"]}; RBoolTreeFromExpressionList[tree, outputs] }; RBoolTreeFromExpressionList: PROC [tree: Dag, outputs: LIST OF ROPE] ~ { <> IF outputs # NIL THEN { AugmentBoolTreeBySingleExpression[tree, outputs.first]; RBoolTreeFromExpressionList[tree, outputs.rest]} }; MakeNewBoolTree: PUBLIC PROC [] RETURNS [tree: Dag] ~ { <> tree _ NEW[Degree] }; MakeNewVariableNode: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [newNode: Node] ~ { <> newNode _ MakeNewNodeB[tree, NIL, prim, name] }; MakeNewNotNode: PUBLIC PROC [tree: Dag, node: Node] RETURNS [newNode: Node] ~ { <> newNode _ MakeNewNodeA[tree, node, not, NIL]; MakeLink[newNode, node] }; <<>> RMakeNewLinks: PROC [vertex: Node, nodes: LIST OF Node] ~ { IF nodes # NIL THEN { MakeLink[vertex, nodes.first]; RMakeNewLinks[vertex, nodes.rest]} }; <<>> MakeNewOrNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ { <> newNode _ MakeNewNodeA[tree, NIL, or, NIL]; RMakeNewLinks[newNode, nodes] }; MakeNewAndNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ { <> newNode _ MakeNewNodeA[tree, NIL, and, NIL]; RMakeNewLinks[newNode, nodes] }; NameNode: PUBLIC PROC [node: Node, name: ROPE] ~ { <> node^.varname _ name }; MakeNamedOutputNode: PUBLIC PROC [tree: Dag, node: Node, name: ROPE] ~ { <> node^.output _ TRUE; node^.outname _ LIST[name] }; END.