<> <> <> <> DIRECTORY Convert, Core, CoreCreate, CoreDirectory, CoreOps, CoreProperties, Drot, DrotBool, DrotCover, Rope, SymTab, TerminalIO; DrotImpl: CEDAR PROGRAM IMPORTS Convert, CoreCreate, CoreDirectory, CoreOps, CoreProperties, DrotBool, DrotCover, Rope, SymTab, TerminalIO 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]; InputOK[be]; [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; }; 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]; InputOK[be]; [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; }; AddCell: PROC [ctcoll: Treeset, name, expression: ROPE] = { AddInputToCover[expression, ctcoll]; ctcoll.top.cell _ NARROW [SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], name].val]; ctcoll.top.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll.top.cell, $CellArea], REF INT]^; }; AssembleCTree: PROC [ctcoll: Treeset] ~ { <> <<1 input>> AddCell[ctcoll, "inv", "X _ ~I"]; <<2 inputs>> AddCell[ctcoll, "nand2", "X _ ~(I-A * I-B)"]; AddCell[ctcoll, "and2", "X _ I-A * I-B"]; AddCell[ctcoll, "nor2", "X _ ~(I-A + I-B)"]; AddCell[ctcoll, "or2", "X _ I-A + I-B"]; AddCell[ctcoll, "xor2", "X _ I-A * I-B + ~I-A * ~I-B"]; AddCell[ctcoll, "xnor2", "X _ I-A * ~I-B + ~I-A * I-B"]; AddCell[ctcoll, "xnor2", "X _ ~( I-A * ~I-B + ~I-A * I-B)"]; -- might produce other mappings than the previous one! <<3 inputs (some missing)>> AddCell[ctcoll, "nand3", "X _ ~(I-A * I-B * I-C)"]; AddCell[ctcoll, "and3", "X _ I-A * I-B * I-C"]; AddCell[ctcoll, "nor3", "X _ ~(I-A + I-B + I-C)"]; AddCell[ctcoll, "or3", "X _ I-A + I-B + I-C"]; AddCell[ctcoll, "a21o2i", "X _ ~(A*B+C)"]; <<4 inputs (many missing)>> AddCell[ctcoll, "nand4", "X _ ~(I-A * I-B * I-C * I-D)"]; AddCell[ctcoll, "nor4", "X _ ~(I-A + I-B + I-C + I-D)"]; AddCell[ctcoll, "and4", "X _ I-A * I-B * I-C * I-D"]; AddCell[ctcoll, "or4", "X _ I-A + I-B + I-C + I-D"]; AddCell[ctcoll, "a22o2i", "X _ ~(A*B+C*D)"]; AddCell[ctcoll, "o22a2i", "X _ ~((A+B)*(C+D))"]; }; InputOK: PUBLIC PROC [output: ROPE] ~ { <> len: INT _ Rope.Length[output]; asspos: INT _ Rope.Find[output, "_", 0]; be : ROPE _ Rope.Substr[output, asspos + 1, len - asspos - 1]; IF NOT ParensMatch[be] THEN {TerminalIO.PutF["Parens not OK\n"]; ERROR}; IF NOT AndOrOK[be] THEN {TerminalIO.PutF["Chars not OK"]; ERROR} }; 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; }; <> 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 AND kiditer^.child^.type # prim 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 modified _ 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 { <> 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 TRUE FROM Rope.Equal[iter.inname, "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; }; Rope.Equal[iter.inname, "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] ~ { <> WHILE iter # NIL DO SELECT TRUE FROM iter.type = prim => pas _ CONS [[iter.inname, iter.mate.wire], pas]; iter.output => pas _ CONS [[iter.outname.first, iter.mate.wire], pas]; ENDCASE => {}; iter _ iter.next; ENDLOOP; }; WireNameFromNode: PROC [vertex: Node] RETURNS [name: ROPE] ~ { <> name _ SELECT TRUE FROM vertex.type = prim AND vertex.inname=NIL => ERROR, vertex.type = prim => vertex.inname, vertex.output AND vertex.outname.first=NIL => ERROR, vertex.output => vertex.outname.first, NOT Rope.IsEmpty[vertex.inname] => vertex.inname, <> NOT Rope.IsEmpty[vertex.varname] => Rope.Concat["intrnal", vertex.varname], ENDCASE => 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 { name: ROPE _ WireNameFromNode[iter]; IF Rope.IsEmpty[name] THEN ERROR; iter.wire _ CoreOps.CreateWire[name: name]; 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] }; Find: PROC [number: INT, tree: Dag] RETURNS [vertex: Node] ~ { FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO IF iter^.number = number THEN RETURN[iter]; ENDLOOP; }; END.