DIRECTORY Atom, Core, CoreClasses, CoreOps, CoreFiddling, CoreProperties, CoreTracing, FS, IO, PartialOrders, RefTab, Rope, ViewerIO; CoreFiddlingImpl: CEDAR PROGRAM IMPORTS CoreClasses, CoreOps, CoreProperties, CoreTracing, IO, PartialOrders, RefTab, Rope EXPORTS CoreFiddling = BEGIN OPEN CC: CoreClasses, CO: CoreOps, CP: CoreProperties, CT: CoreTracing, PO: PartialOrders, CoreFiddling; LORA: TYPE = LIST OF REF ANY; InstanceList: TYPE = LIST OF CC.CellInstance; WireList: TYPE ~ LIST OF Core.Wire; Perm: TYPE = REF PermPrivate; PermPrivate: TYPE = RECORD [ indices: SEQUENCE length: NAT OF NAT]; log: PUBLIC IO.STREAM _ NIL; oneOutsideUse: ATOM = CP.RegisterProperty[ $CoreFiddlingOneOutsideUse, CP.Props[[CP.propPrint, CP.PropDontPrint]] ]; oneInsideUse: ATOM = CP.RegisterProperty[ $CoreFiddlingOneInsideUse, CP.Props[[CP.propPrint, CP.PropDontPrint]] ]; killit: ATOM = CP.RegisterProperty[ $CoreFiddlingKillWire, CP.Props[[CP.propPrint, CP.PropDontPrint]] ]; PrintCellTypes: PUBLIC PROC [to: IO.STREAM, order: PartialOrder] = { PerCellType: PROC [rank: INT, elt: REF ANY, v: PO.Vertex] --PO.Consumer-- = { cellType: Core.CellType = NARROW[elt]; CO.PrintCellType[cellType, to]; }; order.Enumerate[decreasing, NIL, PerCellType]; }; PrintCellTypeGraph: PUBLIC PROC [to: IO.STREAM, order: PartialOrder] = { row: INT _ 0; depth: INT _ 1; PerCellType: PROC [rank: INT, elt: REF ANY, v: PO.Vertex] --PO.Consumer-- = { cellType: Core.CellType = NARROW[elt]; cellTypeName: ROPE = CO.GetCellTypeName[cellType]; to.PutF["%03g%l ", [integer[row]], [rope[SELECT row MOD 3 FROM 0 => "", 1 => "z", 2 => "y", ENDCASE => ERROR]] ]; FOR i: INT IN [1 .. depth) DO to.PutChar['\t]; ENDLOOP; to.PutF[ "%l%g; %g public, ", [rope[" "]], [rope[cellTypeName]], [integer[cellType.public.size]] ]; WITH cellType.data SELECT FROM recordCellType: CC.RecordCellType => { to.PutF[ "%g internal, %g components", [integer[recordCellType.internal.size]], [integer[recordCellType.size]] ]; }; ENDCASE => { to.PutRope["atomic"]; }; to.PutF[ ", %g uses\n", [integer[CT.Count[CT.EnumeratorForInstances[cellType]]]] ]; row _ row + 1; depth _ depth + 1; order.EnumerateDirectDominees[v, PerCellType]; depth _ depth - 1; }; order.ComputeDirectDominance[]; order.EnumerateDirectDominees[NIL, PerCellType]; }; PrintCellInstanceGraph: PUBLIC PROC [to: IO.STREAM, order: PartialOrder, instanceNames: BOOL _ TRUE] = { PrintCell: PROC [cellType: Core.CellType, depth: INT, instanceName: ROPE] = { cellTypeName: ROPE = CO.GetCellTypeName[cellType]; FOR i: INT IN [0 .. depth) DO to.PutChar['\t]; ENDLOOP; IF instanceNames THEN to.PutF["%g: ", [rope[instanceName]]]; to.PutF["%g\n", [rope[cellTypeName]]]; WITH cellType.data SELECT FROM recordCellType: CC.RecordCellType => { FOR i: INT IN [0 .. recordCellType.size) DO ci: CC.CellInstance = recordCellType[i]; PrintCell[ci.type, depth+1, CC.GetCellInstanceName[ci]]; ENDLOOP; }; ENDCASE => NULL; to _ to; }; PerCellType: PROC [rank: INT, elt: REF ANY, v: PO.Vertex] --PO.Consumer-- = { cellType: Core.CellType = NARROW[elt]; PrintCell[cellType, 0, "root"]; }; order.ComputeDirectDominance[]; order.EnumerateDirectDominees[NIL, PerCellType]; }; SortPublics: PUBLIC PROC [cellTypes: Table] = { PerCellType: PROC [key, val: REF ANY] RETURNS [quit: BOOLEAN _ FALSE] --RefTab.EachPairAction-- = { cellType: Core.CellType = NARROW[val]; SortCellTypePublics[cellType]; }; CT.Prepare[CT.EnumeratorForHashTable[cellTypes, FALSE, TRUE]]; [] _ cellTypes.Pairs[PerCellType]; }; SortCellTypePublics: PROC [cellType: Core.CellType] = { cellTypeName: ROPE = CO.GetCellTypeName[cellType]; perm: Perm = NEW [PermPrivate[cellType.public.size]]; inv: Perm ~ NEW [PermPrivate[cellType.public.size]]; PerInstance: PROC [ra: REF ANY] = { ci: CC.CellInstance = NARROW[ra]; IF ci.type # cellType THEN ERROR; PermuteWire[ci.actual, perm]; }; PerSequence: PROC [ra: REF ANY] = { seqCellType: Core.CellType ~ NARROW[ra]; seq: CC.SequenceCellType ~ NARROW[seqCellType.data]; IF seq.sequence # NIL THEN FOR i: NAT IN [0 .. seq.sequence.length) DO seq.sequence[i] _ inv[seq.sequence[i]]; ENDLOOP; IF seq.flatSequence # NIL THEN FOR i: NAT IN [0 .. seq.flatSequence.length) DO seq.flatSequence[i] _ inv[seq.flatSequence[i]]; ENDLOOP; IF seq.stitch # NIL THEN FOR i: NAT IN [0 .. seq.stitch.length) DO seq.stitch[i].this _ inv[seq.stitch[i].this]; seq.stitch[i].that _ inv[seq.stitch[i].that]; ENDLOOP; }; FOR i: NAT IN [0 .. perm.length) DO perm[i] _ i ENDLOOP; FOR i: NAT DECREASING IN (0 .. perm.length) DO FOR j: NAT IN [0 .. i) DO jName: ROPE = CO.GetShortWireName[cellType.public[perm[j]]]; iName: ROPE = CO.GetShortWireName[cellType.public[perm[i]]]; SELECT jName.Compare[iName, FALSE] FROM less => NULL; equal => ERROR; greater => {k: NAT _ perm[j]; perm[j] _ perm[i]; perm[i] _ k}; ENDCASE => ERROR; ENDLOOP; ENDLOOP; FOR i: NAT IN [0 .. perm.length) DO inv[perm[i]] _ i ENDLOOP; PermuteWire[cellType.public, perm]; CT.EnumerateInstances[cellType, PerInstance]; CT.EnumerateSequences[cellType, PerSequence]; cellType _ cellType; }; PermuteWire: PROC [wire: Core.Wire, perm: Perm] = { temp: Core.Wire = NEW [Core.WireRec[wire.size]]; IF wire.size # perm.length THEN ERROR; FOR i: NAT IN [0 .. wire.size) DO temp[i] _ wire[i] ENDLOOP; FOR i: NAT IN [0 .. wire.size) DO wire[i] _ temp[perm[i]]; ENDLOOP; perm _ perm; }; PrintAny: PROC [ra: REF ANY] = { WITH ra SELECT FROM cellType: Core.CellType => { log.PutF[ "%g: %g CellType\n", [rope[CO.GetCellTypeName[cellType]]], [rope[cellType.class.name]] ]; }; wire: --internal-- Core.Wire => { log.PutF[ "%g.%g: %gWire\n", [rope[CO.GetCellTypeName[CT.WireContainer[wire]]]], [rope[CO.GetShortWireName[wire]]], [rope[IF CT.WirePublicity[wire].public THEN "PUBLIC " ELSE ""]] ]; }; ci: CC.CellInstance => { log.PutF[ "%g.%g: %g\n", [rope[CO.GetCellTypeName[CT.InstanceContainer[ci]]]], [rope[CC.GetCellInstanceName[ci]]], [rope[CO.GetCellTypeName[ci.type]]] ]; }; lc: CT.LocalConnection => { log.PutF[ "%g.%g: %g[%g: %g]\n", [rope[CO.GetCellTypeName[CT.InstanceContainer[lc.ci]]]], [rope[CC.GetCellInstanceName[lc.ci]]], [rope[CO.GetCellTypeName[lc.ci.type]]], [rope[CO.GetFullWireName[lc.ci.type.public, CT.SubWire[lc.ci.type.public, lc.publicPath]]]], [rope[CO.GetFullWireName[lc.ci.actual, CT.SubWire[lc.ci.actual, lc.publicPath]]]] ] }; ENDCASE => log.PutF["%g\n", [refAny[ra]]]; }; SqueezeDown: PROC [order: PartialOrder] = --privatize public wires whose actuals never connect with anything else-- { SqueezeCellType: PROC [rank: INT, elt: PO.Element, v: PO.Vertex] --PO.Consumer-- = { ct: Core.CellType = NARROW[elt]; cellTypeName: ROPE = CO.GetCellTypeName[ct]; SELECT ct.class FROM CC.recordCellClass => { quaRecord: CC.RecordCellType = NARROW[ct.data]; NoteInstance: PROC [ra: REF ANY] = { ci: CC.CellInstance = NARROW[ra]; FOR pi: INT IN [0 .. oldSize) DO pw: Core.Wire = ct.public[pi]; connections: INT ~ CT.EnumeratorForLocalConnections[ci.actual[pi]].Count[2]; SELECT connections FROM =0 => ERROR; =1 => NULL; >1 => CP.PutWireProp[pw, oneOutsideUse, NIL]; ENDCASE => ERROR; ENDLOOP; }; ie: CT.Enumerator = CT.EnumeratorForInstances[ct]; oldSize, newSize: INT _ ct.public.size; losses: INT _ 0; InitPW: PROC [wire: Core.Wire] RETURNS [subWires: BOOL _ TRUE, quit: BOOL _ FALSE] --CO.EachWireProc-- ~ { CP.PutWireProp[wire, oneOutsideUse, $T]; subWires _ FALSE; }; IF CO.VisitWireSeq[ct.public, InitPW] THEN ERROR; ie.Enumerate[ie.data, NoteInstance]; FOR pi: INT IN [0 .. oldSize) DO pw: Core.Wire = ct.public[pi]; SELECT CP.GetWireProp[pw, oneOutsideUse] FROM $T => {losses _ losses + 1; newSize _ newSize - 1}; NIL => NULL; ENDCASE => ERROR; ENDLOOP; IF losses > 0 THEN { Pass: PROC [index: NAT] RETURNS [keep: BOOL] = { keep _ CP.GetWireProp[ct.public[index], oneOutsideUse] = NIL; }; FixInstance: PROC [ra: REF ANY] = { ci: CC.CellInstance = NARROW[ra]; parent: Core.CellType = CT.InstanceContainer[ci]; parentRecord: CC.RecordCellType = NARROW[parent.data]; PassInternal: PROC [index: NAT] RETURNS [keep: BOOL] = { keep _ CP.GetWireProp[parentRecord.internal[index], killit] = NIL; }; ci.actual _ FilterWire[ci.actual, Pass, losses, killit, $T].new; parentRecord.internal _ FilterWire[parentRecord.internal, PassInternal, losses].new; CT.Repair[parent]; }; lostPublics: WireList; log.PutF["Removing %g from cell type %g:\n", [integer[losses]], [rope[cellTypeName]]]; FOR pi: INT IN [0 .. oldSize) DO pw: Core.Wire = ct.public[pi]; SELECT CP.GetWireProp[pw, oneOutsideUse] FROM $T => log.PutF["\t%g\n", [rope[CO.GetShortWireName[pw]]]]; NIL => NULL; ENDCASE => ERROR; ENDLOOP; ie.Enumerate[ie.data, FixInstance]; [ct.public, lostPublics] _ FilterWire[ct.public, Pass, losses]; CT.Repair[ct]; FOR lostPublics _ lostPublics, lostPublics.rest WHILE lostPublics # NIL DO lp: Core.Wire ~ lostPublics.first; connections: INT ~ CT.EnumeratorForLocalConnections[lp].Count[1]; IF connections = 0 THEN log.PutF[ "%g.%g has no connections after SqueezeDown\n", [rope[CO.GetCellTypeName[ct]]], [rope[CO.GetShortWireName[lp]]] ]; ENDLOOP; }; }; ENDCASE => NULL; }; order.Enumerate[decreasing, NIL, SqueezeCellType]; }; Enuf: ERROR = CODE; debugSqueeze: BOOL _ FALSE; SqueezeUp: PROC [order: PartialOrder] = --remove public wires not connected to anything-- { SqueezeCellType: PROC [rank: INT, elt: PO.Element, v: PO.Vertex] --PO.Consumer-- = { ct: Core.CellType = NARROW[elt]; cellTypeName: ROPE = CO.GetCellTypeName[ct]; SELECT ct.class FROM CC.recordCellClass => { quaRecord: CC.RecordCellType = NARROW[ct.data]; losses: NAT _ 0; FOR i: INT IN [0 .. quaRecord.internal.size) DO iw: Core.Wire = quaRecord.internal[i]; e: CT.Enumerator = CT.EnumeratorForLocalConnections[iw]; count: NAT _ 0; lc1: CT.LocalConnection _ NIL; PerLC: PROC [ra: REF ANY] = { lc: CT.LocalConnection = NARROW[ra]; IF (count _ count + 1) > 2 THEN Enuf; IF count = 1 THEN lc1 _ lc; IF debugSqueeze THEN log.PutF[ "%g.%g <-> %g.%g\n", [rope[CO.GetCellTypeName[ct]]], [rope[CO.GetFullWireName[quaRecord.internal, CT.SubWire[iw, lc.subscript]]]], [rope[IF lc.ci = NIL THEN "" ELSE CC.GetCellInstanceName[lc.ci]]], [rope[CO.GetShortWireName[CT.SubWire[IF lc.ci = NIL THEN ct.public ELSE lc.ci.type.public, lc.publicPath]]]] ]; }; e.Enumerate[e.data, PerLC !Enuf => CONTINUE]; IF count = 0 THEN log.PutF[ "%g.%g has no connections\n", [rope[CO.GetCellTypeName[ct]]], [rope[CO.GetShortWireName[iw]]] ] ELSE IF count > 1 THEN NULL ELSE IF lc1.ci # NIL THEN NULL ELSE { log.PutF[ "Squeezing up %g.%g\n", [rope[CO.GetCellTypeName[ct]]], [rope[CO.GetShortWireName[iw]]] ]; CP.PutWireProp[iw, oneInsideUse, $T]; losses _ losses + 1; }; ENDLOOP; IF losses > 0 THEN { PassExternal: PROC [index: NAT] RETURNS [keep: BOOL] = { keep _ CP.GetWireProp[ct.public[index], oneInsideUse] = NIL; }; PassInternal: PROC [index: NAT] RETURNS [keep: BOOL] = { keep _ CP.GetWireProp[quaRecord.internal[index], oneInsideUse] = NIL; }; FixInstance: PROC [ra: REF ANY] = { ci: CC.CellInstance = NARROW[ra]; parent: Core.CellType = CT.InstanceContainer[ci]; losts: WireList; [ci.actual, losts] _ FilterWire[ci.actual, PassExternal, losses]; CT.Repair[parent]; FOR losts _ losts, losts.rest WHILE losts # NIL DO lw: Core.Wire ~ losts.first; connections: INT ~ CT.EnumeratorForLocalConnections[lw].Count[1]; IF connections = 0 THEN log.PutF[ "%g.%g has no connections after SqueezeUp\n", [rope[CO.GetCellTypeName[parent]]], [rope[CO.GetShortWireName[lw]]] ]; ENDLOOP; }; ie: CT.Enumerator = CT.EnumeratorForInstances[ct]; ie.Enumerate[ie.data, FixInstance]; quaRecord.internal _ FilterWire[quaRecord.internal, PassInternal, losses].new; ct.public _ FilterWire[ct.public, PassExternal, losses].new; CT.Repair[ct]; }; }; ENDCASE; }; order.Enumerate[increasing, NIL, SqueezeCellType]; }; FilterWire: PROC [old: Core.Wire, Pass: PROC [NAT] RETURNS [BOOL], losses: INT, markProp: ATOM _ NIL, markValue: REF ANY _ NIL] RETURNS [new: Core.Wire, gone: WireList] = { ni: INT _ 0; new _ NEW [Core.WireRec[old.size - losses]]; new.properties _ old.properties; gone _ NIL; FOR oi: INT IN [0 .. old.size) DO copy: BOOL = Pass[oi]; IF copy THEN { new[ni] _ old[oi]; ni _ ni + 1; } ELSE { gone _ CONS[old[oi], gone]; IF markProp # NIL THEN CP.PutWireProp[old[oi], markProp, markValue]; }; ENDLOOP; IF ni # new.size THEN ERROR; }; END. ΈCoreFiddlingImpl.Mesa Spreitzer, January 11, 1986 6:06:13 pm PST Mike Spreitzer March 7, 1987 12:57:26 pm PST Last tweaked by Mike Spreitzer on November 29, 1988 7:12:24 pm PST ΚΈ– "cedar" style˜code™K™*K™,K™B—K˜KšΟk œNœœ(˜…K˜šΡbnxœœ˜Kšœ4œ˜ZKšœ ˜—K˜Kšœœœœœ œœœ˜pK˜Kš œœœœœœ˜Kšœœœœ˜-Kšœ œœœ ˜#K˜Kšœœœ ˜šœ œœ˜Kš œ œ œœœ˜&—K˜Kš œœœœœ˜K˜šœœœ˜*K˜Kšœœ œ˜*K˜—K˜šœœœ˜)K˜Kšœœ œ˜*K˜—K˜šœœœ˜#K˜Kšœœ œ˜*K˜—K˜š Οnœœœœœ˜DšŸ œœœœœœ Οcœ˜MKšœœ˜&Kšœ˜K˜—Kšœœ˜.K˜—K˜š Ÿœœœœœ˜HKšœœ˜ Kšœœ˜šŸ œœœœœœ  œ˜MKšœœ˜&Kšœœœ˜2˜K˜šœœœ˜K˜K˜ K˜ Kšœœ˜—K˜—šœœœ˜K˜Kšœ˜—˜K˜K˜ K˜K˜K˜—šœœ˜šœ&˜&˜K˜K˜(K˜K˜—K˜—šœ˜ K˜K˜——˜K˜Kšœ œœ$˜8K˜—K˜Kšœ˜Kšœ.˜.Kšœ˜K˜—Kšœ˜Kšœœ˜0K˜—K˜šŸœœœœœ&œœ˜hšŸ œœ"œœ˜MKšœœœ˜2šœœœ˜K˜Kšœ˜—Kšœœ'˜Kšœ"˜"K˜—K˜šŸœœ˜7Kšœœœ˜2Kšœ œ%˜5Kšœ œ%˜4šŸ œœœœ˜#Kšœœ˜!Kšœœœ˜!K˜K˜—šŸ œœœœ˜#Kšœœ˜(Kšœœœ˜4š œœœœœœ˜FK˜'Kšœ˜—š œœœœœœ ˜NKšœ/˜/Kšœ˜—š œœœœœœ˜BKšœ-˜-Kšœ-˜-Kšœ˜—K˜—Kš œœœœ œ˜8š œœ œœ˜.šœœœ ˜Kšœœœ,˜Kšœœ˜—Kšœ˜—Kšœ˜—Kš œœœœœ˜=K˜#Kšœ+˜-Kšœ+˜-K˜K˜—K˜šŸ œœ"˜3Kšœœ˜0Kšœœœ˜&Kš œœœœœ˜<šœœœ˜!K˜Kšœ˜—K˜ K˜—K˜šŸœœœœ˜ šœœ˜˜˜ K˜Kšœœ˜%K˜K˜—K˜—šœ  œ˜!˜ K˜Kšœœœ˜3Kšœœ˜"Kš œœœœ œ˜?K˜—K˜—˜˜ K˜Kšœœœ˜5Kšœ#˜#Kšœœ˜#K˜—K˜—šœœ˜˜ K˜Kšœœœ˜8Kšœ&˜&Kšœœ˜'Kšœœ$œ.˜\Kšœœœ(˜QK˜—K˜—Kšœ#˜*—K˜—K˜šŸ œœ Iœ˜uš Ÿœœœœ œ  œ˜TKšœœ˜ Kšœœœ˜,šœ ˜šœ˜Kšœ œœ ˜/šŸ œœœœ˜$Kšœœœ˜!šœœœ˜ K˜Kšœ œœ7˜Lšœ ˜Kšœœ˜ Kšœœ˜ Kšœœ œ˜-Kšœœ˜—Kšœ˜—K˜—Kšœœœ˜2Kšœœ˜'Kšœœ˜šŸœœœ œœœœ œ˜jKšœ&˜(Kšœ œ˜K˜—Kšœœ!œœ˜1Kšœ$˜$šœœœ˜ K˜šœœ ˜-Kšœ3˜3Kšœœ˜ Kšœœ˜—Kšœ˜—šœ œ˜š Ÿœœ œœœ˜0Kšœœ0œ˜=K˜—šŸ œœœœ˜#Kšœœœ˜!Kšœœ˜1Kšœœœ˜6š Ÿ œœ œœœ˜8Kšœœ5œ˜BK˜—K˜@KšœT˜TKšœ˜K˜—K˜K˜Všœœœ˜ K˜šœœ ˜-Kšœœ˜:Kšœœ˜ Kšœœ˜—Kšœ˜—Kšœ#˜#K˜?Kšœ ˜šœ-œœ˜JK˜"Kšœ œœ,˜Ašœœ ˜!K˜/Kšœœ˜Kšœœ˜Kšœ˜—Kšœ˜—K˜—K˜—Kšœœ˜—K˜—Kšœœ˜2K˜—K˜Kšœœœ˜Kšœœœ˜K˜šŸ œœ 1œ˜[š Ÿœœœœ œ  œ˜TKšœœ˜ Kšœœœ˜,šœ ˜šœ˜Kšœ œœ ˜/Kšœœ˜šœœœ ˜/K˜&Kšœœœ#˜8Kšœœ˜Kšœœœ˜šŸœœœœ˜Kšœœœ˜$Kšœœ˜%Kšœ œ ˜šœœ ˜K˜Kšœœ˜Kšœœ%œ˜MKš œœ œœ œœ˜HKš œœœ œ œœ œ%˜lK˜—K˜—Kšœ#œ˜-šœ œ ˜K˜Kšœœ˜Kšœœ˜K˜—Kšœœ œ˜Kš œœ œœ˜šœ˜šœ ˜ K˜Kšœœ˜Kšœœ˜K˜—Kšœ#˜%K˜K˜—Kšœ˜—šœ œ˜š Ÿ œœ œœœ˜8Kšœœ/œ˜