DIRECTORY AbSets, Asserting, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransforms, LichenTransformsPrivate, Rope, SetBasics; LichenSplitMerge: CEDAR PROGRAM IMPORTS AbSets, Asserting, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransformsPrivate, Rope, SetBasics EXPORTS LichenTransforms = BEGIN OPEN LichenArrayStuff, LichenNavigation, LichenDataStructure, LichenTransforms, LichenDataOps, LichenTransformsPrivate, Ints:IntStuff, Sets:AbSets; PortAns: TYPE ~ REF PortAnsPrivate; PortAnsPrivate: TYPE ~ RECORD [ from, to: Port, doFrom: PortAction _ leave, doTo: PortAction[dontAdd..addPort] _ dontAdd ]; SplitType: PUBLIC PROC [design: Design, fizz: ConstSet--of CellInstance--] RETURNS [from, to: CellType, pairs: ConstOneToOne--instance of from or ancestor f instance of to or ancestor--] ~ { cs: Seq--role f fizzee-- ~ BiRels.EnumSeqOfSet[fizz]; analysis: Analysis ~ NEW [AnalysisPrivate _ [ roles: fizz.Size.EN, subjTypes: cs.Compose[instanceType, [TRUE, FALSE]].CreateVectorCopy[oneToOne: TRUE].Freeze, wag: NEW [WireAnsweringPrivate _ [ oldSubjConnectionss: CreateRefSeq[fizz.Size.EN], anses: BiRels.CreateHashFn[] ]], doomedPorts: Sets.CreateHashSet[] ]]; {OPEN analysis; connectionsV: VarOneToOne--port of to f port of from-- ~ BiRels.CreateHashOTO[]; pairsV: VarOneToOne ~ BiRels.CreateHashOTO[]; nameParts: LOLORA _ NIL; toName, subTail: ROPE; IF roles=0 THEN Error["Null fission"]; from _ NIL; {i: INT _ 0; PerElt: PROC [ra: REF ANY] ~ {v: CellInstance ~ NARROW[ra]; IF v.type=NIL OR v.containingCT=NIL THEN ERROR; IF from=NIL THEN from _ v.containingCT ELSE IF from#v.containingCT THEN Error["Fission of vertices not all having same parent"]; nameParts _ CONS[Listify[v.VertexNames], nameParts]; IF subjTypes.ApplyI[i].MA # v.type THEN ERROR; i _ i + 1; }; fizz.EnumA[PerElt]; IF i # cs.Size.EN THEN ERROR; }; IF NOT from.designs.HasMemA[design] THEN ERROR; subTail _ RopeCrossCat[nameParts]; toName _ RopeCrossCat[LIST[Select[nameReln, 1, from.otherPublic], LIST[subTail]]]; subTail _ Rope.Concat["-", subTail]; to _ CreateCellType[design: design, cellTypeName: toName, class: NIL, inheritNames: from.inheritNames, internals: TRUE]; IF Survey[from, NIL, cs, analysis, TRUE] THEN ERROR; {MoveWire: PROC [left, right: REF ANY] ~ { wire: Wire ~ NARROW[left]; wa: WireAns ~ NARROW[right]; IF NOT wa.analyzed THEN ERROR; IF wa.counterpart # NIL THEN ERROR; wa.counterpart _ CreateWire[containingCT: to, copy: wire, names: [wire.VertexNames.Copy.data.VA]]; SELECT wa.doFrom FROM addPort => { wa.fromPort _ AddPort[[parent: from.port, wire: wire]]; AddEdge[[from.asUnorganized.mirror, wire], wa.fromPort]}; leave, dontAdd, dePort => NULL; ENDCASE => ERROR; SELECT wa.doTo FROM addPort => { wa.toPort _ AddPort[[parent: to.port, wire: wa.counterpart]]; IF wa.fromPort=NIL THEN ERROR; connectionsV.AddNewAA[wa.toPort, wa.fromPort]; AddEdge[[to.asUnorganized.mirror, wa.counterpart], wa.toPort]}; dontAdd => NULL; ENDCASE => ERROR; }; wag.anses.EnumAA[MoveWire]; }; FOR role: NATURAL IN [0 .. roles) DO fci: CellInstance ~ NARROW[cs.ApplyI[role].MA]; tci: CellInstance ~ Instantiate[fci.type, to, noListData, fci.other]; MoveConnection: PROC [subjPort: Port, fwire: Wire] ~ { wa: WireAns = GetRPAns[wag, role, subjPort, fwire, FALSE]; IF NOT wa.analyzed THEN ERROR; AddEdges[[tci, wa.counterpart], subjPort]; }; EnumerateTopConnections[fci, MoveConnection]; ENDLOOP; {connections: ConstOneToOne ~ connectionsV.Freeze; doomedPortsC: ConstSet ~ doomedPorts.Freeze; FixArrays[design, from, to, connections, doomedPortsC, portToInternalWire, subTail, pairsV]; FixInstances[from, to, connections, doomedPortsC, portToInternalWire, pairsV]; FOR i: INT IN [0 .. cs.Size.EN) DO DeleteVertex[NARROW[cs.ApplyI[i].MA]]; ENDLOOP; {KillWireAndPort: PROC [left, right: REF ANY] ~ { wire: Wire ~ NARROW[left]; wa: WireAns ~ NARROW[right]; IF NOT wa.analyzed THEN ERROR; IF wa.counterpart=NIL THEN ERROR; SELECT wa.doFrom FROM addPort => NULL; leave, dontAdd => NULL; dePort => RemovePort[wa.fromPort]; ENDCASE => ERROR; IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[wire]; design _ design; }; wag.anses.EnumAA[KillWireAndPort]; }; pairs _ pairsV.Freeze; }}}; SubComponenting: TYPE ~ ARRAY BOOL OF Function--sv _ component of subgraph of static graph--; FixArrays: PROC [ design: Design, fromAncestorCT, toAncestorCT: CellType, eltConnections: ConstOneToOne--port of toAncestorCT f port of fromAncestorCT--, doomedFromPorts: ConstSet--of port of fromAncestorCT--, eltTPToWire: UWFunction--port of toAncestorCT _ prototypical wire--, subTail: ROPE--to append to name of from array--, pairs: VarOneToOne--instance of from or ancestor f instance of to or ancestor-- ] ~ { SplitArray: PROC [fromArrayCT: CellType] ~ { fa: Array ~ fromArrayCT.asArray; faName: ROPE ~ NARROW[Asserting.FnVal[nameReln, fromArrayCT.otherPublic]]; taName: ROPE ~ faName.Cat[subTail]; toArrayCT: CellType ~ CreateArray[design, taName, NIL, toAncestorCT, fa.size2, fa.basePeriod, fromArrayCT.inheritNames, NIL, NIL]; ta: Array ~ toArrayCT.asArray; arrayConnectionsV: VarOneToOne--port of toArrayCT f port of fromArrayCT-- ~ BiRels.CreateHashOTO[]; arrayTPToWireV: VarFunction--port of ta _ wire-- ~ BiRels.CreateHashFn[]; doomedArrayPortsV: VarSet--of port of fa-- ~ Sets.CreateHashSet[]; NotDoomed: PROC [fep: Port] RETURNS [BOOL] ~ {RETURN [NOT doomedFromPorts.HasMemA[fep]]}; HasNew: PROC [fep: Port] RETURNS [BOOL] ~ {RETURN [eltConnections.ApplyA[fep, rightToLeft].found]}; toNewComp: SubComponenting ~ CreateSubComponents[fa, HasNew]; inSameNewComp: BiRel--between svs of fa-- ~ toNewComp[TRUE].Compose[toNewComp[TRUE].Invert]; nonDoomedSVs: Set--of sv of fa-- ~ FilterSVs[fa, NotDoomed]; inNonDoomedNewComp: Set--of sv of fa-- ~ inSameNewComp.Image[nonDoomedSVs]; crossings: LIST OF RECORD [hasNew, hasnt: StatVertex, d: Int2] _ NIL; NoteCrossing: PROC [in, out: StatVertex, d: Int2] ~ { IF inNonDoomedNewComp.HasMemA[in] THEN crossings _ CONS[[in, out, d], crossings]}; tNewStat: StatRep ~ CopySubGraph[fa, HasNew, eltConnections.Invert.AsConst, NoteCrossing]; sizeRange: Range2 ~ SizeRange[fa.size2]; SetStatRep[toArrayCT, tNewStat, FALSE]; FOR crossings _ crossings, crossings.rest WHILE crossings # NIL DO rA: Range2 ~ Range2Intersection[sizeRange, Range2Off[sizeRange, Int2Neg[crossings.first.d]]]; irA: Range2 ~ Range2Div[rA, fa.basePeriod, crossings.first.hasNew.phase]; FOR if: NATURAL IN [NATURAL[irA[Foo].min] .. NATURAL[irA[Foo].maxPlusOne]) DO FOR ib: NATURAL IN [NATURAL[irA[Bar].min] .. NATURAL[irA[Bar].maxPlusOne]) DO aiA: ArrayIndex ~ Int2Mul[[if, ib], fa.basePeriod, crossings.first.hasNew.phase]; aiB: ArrayIndex ~ Int2Add[aiA, crossings.first.d]; tep: Port ~ NARROW[eltConnections.ApplyA[crossings.first.hasNew.port, rightToLeft].MA]; tepw: Wire ~ NARROW[eltTPToWire.ApplyA[tep].MA]; fap: Port--of fromArrayCT-- ~ GetArrayPortForPort[fromArrayCT, aiB, crossings.first.hasnt.port, TRUE]; tap: Port--of toArrayCT-- ~ GetArrayPortForPort[toArrayCT, aiA, tep, TRUE]; np: BiRels.HadPair ~ arrayConnectionsV.AddAA[tap, fap]; IF np#ALL[none] AND np#ALL[same] THEN ERROR; [] _ arrayTPToWireV.AddAA[tap, tepw]; design _ design; ENDLOOP ENDLOOP; ENDLOOP; {fNewStat: StatRep ~ CopySubGraph[fa, NotDoomed, refsID, NIL]; FindRep: PROC [left, right: REF ANY] ~ { fap: Port ~ NARROW[left]; dw: DumbWire ~ NARROW[right]; fep: Port ~ ScanPortsInDumbWire[fa, dw, NotDoomed].ep; IF fep#NIL THEN { ai: ArrayIndex ~ GetInstForPortInDumbWire[fa, dw, fep]; IF ai=ALL[-1] THEN ERROR; fNewStat.apToPAI.AddNewAA[fap, NEW [PortAtIndexPrivate _ [fep, ai]]]} ELSE IF NOT doomedArrayPortsV.AddA[fap] THEN ERROR; RETURN}; fa.dumrep.apToWire.EnumAA[FindRep]; SetStatRep[fromArrayCT, fNewStat, TRUE]; {arrayConnections: ConstFunction ~ arrayConnectionsV.Freeze; doomedArrayPorts: ConstSet ~ doomedArrayPortsV.Freeze; arrayTPToWire: ConstFunction ~ arrayTPToWireV.Freeze; KillDoomedArrayPort: PROC [ra: REF ANY] ~ { p: Port--of fromArrayCT-- ~ NARROW[ra]; RemovePort[p]; RETURN}; FixArrays[design, fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, subTail, pairs]; FixInstances[fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, pairs]; doomedArrayPorts.EnumA[KillDoomedArrayPort]; RETURN}}}; fromAncestorCT.EnumerateArrays[SplitArray]; RETURN}; refsID: ConstOneToOne ~ BiRels.CreateFullIDSubset[SetBasics.refs]; FilterSVs: PROC [a: Array, Pf: PROC [Port] RETURNS [BOOL]] RETURNS [pass: Set--of sv of a-- _ Sets.CreateHashSet[statVerts]] ~ { PerVertex: PROC [sv: StatVertex] RETURNS [BOOL] ~ { IF Pf[sv.port] THEN IF NOT pass.AddA[sv] THEN ERROR; RETURN[FALSE]}; [] _ ScanStatVertices[a, PerVertex]; RETURN}; CreateSubComponents: PROC [a: Array, Pf: PROC [Port] RETURNS [BOOL]] RETURNS [toComp: SubComponenting] ~ { nComps: INT _ 0; Start: PROC [sv: StatVertex] RETURNS [pass: BOOL _ FALSE] ~ { b: BOOL ~ Pf[sv.port]; IF toComp[b].ApplyA[sv].found THEN RETURN; {comp: REF INT ~ NEW [INT _ nComps]; ExploreFrom: PROC [sv: StatVertex] ~ { ExploreEdge: PROC [se:StatEdge, ob:BOOL] RETURNS [pass:BOOL_FALSE] ~{ osv: StatVertex ~ se.vs[ob]; IF Pf[osv.port]#b THEN RETURN; SELECT toComp[b].AddAA[osv, comp].had[leftToRight] FROM same => NULL; different => ERROR; none => ExploreFrom[osv]; ENDCASE => ERROR; RETURN}; toComp[b].AddNewAA[sv, comp]; [] _ ScanStatEdgesFrom[a.statrep, sv, ExploreEdge]; RETURN}; ExploreFrom[sv]; nComps _ nComps+1}}; toComp _ [ FALSE: BiRels.CreateHashFn[invable: TRUE], TRUE: BiRels.CreateHashFn[invable: TRUE]]; [] _ ScanStatVertices[a, Start]; RETURN}; CopySubGraph: PROC [a: Array, Pf: PROC [Port] RETURNS [BOOL], portMap: ConstOneToOne, NoteCrossing: PROC [in, out: StatVertex, d: Int2]] RETURNS [subCopy: StatRep] ~ { AddEdge: PROC [vs: ARRAY BOOL OF StatVertexPrivate, d: Int2] ~ { vs[FALSE].port _ NARROW[portMap.ApplyA[vs[FALSE].port].MA]; vs[TRUE].port _ NARROW[portMap.ApplyA[vs[TRUE].port].MA]; [] _ AddStatEdge[subCopy, [ vs: [ FALSE: NEW [StatVertexPrivate _ vs[FALSE]], TRUE: NEW [StatVertexPrivate _ vs[TRUE]]], d: d]]; RETURN}; PassCrosser: PROC [in, out: StatVertex, d: Int2] ~ {NoteCrossing[in, out, d]}; subCopy _ CreateStatRep[]; EnumerateSubGraph[a, include, Pf, AddEdge, PassCrosser]; RETURN}; EnumerateSubGraph: PROC [a: Array, directs: {include, exclude}, Pf: PROC [Port] RETURNS [BOOL], PerEdge: PROC [vs: ARRAY BOOL OF StatVertexPrivate, d: Int2], PerCrosser: PROC [in, out: StatVertex, d: Int2]] ~ { seenFailures: Set--of StatVertex-- ~ Sets.CreateHashSet[statVerts]; PerVertex: PROC [sv: StatVertex] RETURNS [pass: BOOL _ FALSE] ~ { IF Pf[sv.port] THEN { PassEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [pass: BOOL _ FALSE] ~ { IF Pf[se.vs[ob].port] THEN {IF directs=include THEN PerEdge[[se.vs[FALSE]^, se.vs[TRUE]^], se.d]} ELSE {IF PerCrosser#NIL THEN PerCrosser[sv, se.vs[ob], IF ob THEN se.d ELSE Int2Neg[se.d]]}; RETURN}; IF directs=include OR PerCrosser#NIL THEN IF ScanStatEdgesFrom[a.statrep, sv, PassEdge].found THEN ERROR; RETURN} ELSE { IF seenFailures.AddA[sv] THEN { seenSuccesses: Set--of PortAtIndex-- ~ Sets.CreateHashSet[portsAtIndices]; indices: Function--StatVertex _ ArrayIndex-- ~ BiRels.CreateHashFn[invable: FALSE]; foundCycle: BOOL _ FALSE; ExploreFrom: PROC [sv: StatVertex, ai: ArrayIndex] ~ { ExploreEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [pass: BOOL _ FALSE] ~ { osv: StatVertex ~ se.vs[ob]; oai: ArrayIndex ~ Int2Add[ai, IF ob THEN se.d ELSE Int2Neg[se.d]]; IF Pf[osv.port] THEN [] _ seenSuccesses.AddA[NEW [PortAtIndexPrivate _ [osv.port, ai]]] ELSE IF seenFailures.AddA[osv] THEN ExploreFrom[osv, oai] ELSE IF NARROW[indices.ApplyA[osv].MA, REF ArrayIndex]^ # oai THEN foundCycle _ TRUE; RETURN}; indices.AddNewAA[sv, NEW [ArrayIndex _ ai]]; IF ScanStatEdgesFrom[a.statrep, sv, ExploreEdge].found THEN ERROR; RETURN}; ExploreFrom[sv, WidenNat2[sv.phase]]; IF seenSuccesses.Empty[] THEN RETURN; IF foundCycle THEN ERROR nyet; IF seenSuccesses.Size[Ints.two].CompareI[2] NULL; 2 => subAns _ Rope.Cat["{", subAns, "|"]; ENDCASE => subAns _ subAns.Concat["|"]; subAns _ subAns.Concat[NARROW[lora.first]]; ENDLOOP; IF n > 1 THEN subAns _ subAns.Concat["}"]; IF ans # NIL THEN ans _ ans.Concat["-"]; ans _ ans.Concat[subAns]; ENDLOOP; ans _ ans; }; END. ^LichenSplitMerge.Mesa Last tweaked by Mike Spreitzer on February 1, 1988 4:20:40 pm PST Ê<˜™IcodešœA™A—J˜KšÏk œ©˜²K˜šÑbnxœœ˜Kšœ–˜Kšœ˜—K˜KšœœtÏnœ Ÿœ˜™K˜Kšœ œœ˜#šœœœ˜K˜Kšœ˜Kšœ,˜,K˜—K˜šŸ œœœ Ïcœœ* Ðcm œ˜¾Kšœ ¡  œ˜5šœœ˜-Kšœœ˜Kšœ%œœœ ˜[šœœ˜"Kšœ,œ˜0Kšœ˜Kšœ˜—K˜!Kšœ˜—Kšœœ ˜Kšœ  ¡ œ˜PKšœ-˜-Kšœ œœ˜Kšœœ˜Kšœ œ˜&Kšœœ˜ Kšœœ˜ š Ÿœœœœœ˜;Kš œœœœœœ˜/Kš œœœœœœ9˜€Kšœ œ$˜4Kšœœ œœ˜.K˜ K˜—Kšœ˜Kšœ œœœ˜K˜Kšœœœœ˜/Kšœ"˜"Kšœœ(œ ˜RK˜$KšœAœ.œ˜xKš œœœœœ˜4š œŸœœœœ˜*Kšœ œ˜Kšœœ˜Kšœœ œœ˜Kšœœœœ˜#Kšœ]œ˜bšœ ˜šœ ˜ Kšœ7˜7Kšœ9˜9—Kšœœ˜Kšœœ˜—šœ ˜šœ ˜ Kšœ=˜=Kšœ œœœ˜Kšœ.˜.Kšœ?˜?—Kšœ œ˜Kšœœ˜—K˜—Kšœ˜K˜šœœœ˜$Kšœœœ˜/KšœE˜EšŸœœ"˜6Kšœ3œ˜:Kšœœ œœ˜Kšœ*˜*K˜—K˜-Kšœ˜—Kšœ2˜2Kšœ,˜,Kšœ\˜\KšœN˜Nš œœœœ˜"Kšœ œœ˜&Kšœ˜—š œŸœœœœ˜1Kšœ œ˜Kšœœ˜Kšœœ œœ˜Kšœœœœ˜!šœ ˜Kšœ œ˜Kšœœ˜Kšœ"˜"Kšœœ˜—Kšœœ œœ˜;K˜K˜—Kšœ"˜"K˜Kšœ˜K˜—K˜Kš œœœœœ  ¡ (œ˜]K˜šŸ œ˜šœ˜K˜Kšœ'˜'Kšœ ¡ œ˜OKšœ œ˜7Kšœ ¡ œ˜DKšœ  #œ˜1Kšœ ¡ ˜O—Kšœ˜šŸ œœ˜,K˜ Kšœœœ5˜JKšœœ˜#Kšœ2œCœœ˜‚Kšœ˜Kšœ ¡ œ˜cKšœ  ¡ œ˜IKšœ œ˜BšŸ œœ œœ˜*Kšœœœ ˜.—šŸœœ œœ˜'Kšœœ2˜;—Kšœ=˜=Kšœ œ œœ ˜\Kšœ œ˜šŸœœœœ˜(Kšœ œ˜Kšœœ˜Kšœ6˜6šœœœ˜Kšœ7˜7Kšœœœœ˜Kšœœ#˜E—Kš œœœœœ˜3Kšœ˜—Kšœ#˜#Kšœ"œ˜(Kšœ<˜Kšœ  œ@˜\Kšœœœ˜šœœœ ˜Kšœœœ˜-KšœD˜Dšœœœ ˜Kšœœœ˜-KšœT˜TK˜Kšœ˜—K˜Kšœ˜—K˜—Kšœ˜—K˜—Kšœ&œœ˜3Kšœ˜—K˜šŸ œ˜šœ˜Kšœ'˜'Kšœ ¡ œ˜LKšœ œ˜7Kšœ ¡ œ˜AKšœ ¡ ˜O—Kšœ˜šŸ œœ˜)K˜&Kšœ8˜8š Ÿœœœœœ˜GKšœœ˜ šœ6œœ˜JKš œœœœœ˜FKšœ˜—šœœœ˜šœ6œœ˜JKšœœœ˜šŸœœ˜"Kšœ  œœœ˜"Kšœ œ˜.Kš œœœœœ˜$Kšœœœœ˜K˜K˜—Kšœœ˜.Kšœœ˜š œœœœœ˜-Kšœ3œœ˜TK˜K˜—Kšœ˜—K˜—K˜—Kšœ(œ˜.Kšœ"˜"K˜Kšœ˜—Kšœ0œ˜7Kšœ˜—K˜šŸœœ œœ˜1šŸœœœœ˜Kšœœ˜!Kšœœ"˜-Kšœ˜—Kšœœ˜ Kšœ˜Kšœ˜—K˜šŸœœ"œœ˜mšŸœœ%˜1Kšœ6˜6Kšœœœ˜6Kšœœ˜!K˜—Kšœ7˜7K˜—K˜š Ÿ œœ œœœ˜;Kšœœ˜ šœœ œ˜6Kšœœœ˜"Kšœœœ˜Kšœœ˜šœœœ˜.K˜ šœ˜ Kšœœ˜ K˜)Kšœ ˜'—Kšœœ˜+Kšœ˜—Kšœœ˜*Kšœœœ˜(K˜Kšœ˜—K˜ K˜—K˜Kšœ˜—…—;"M¼