DIRECTORY AbSets, BiRelBasics, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics; LichenDataImplArrays3: CEDAR PROGRAM IMPORTS AbSets, BiRelBasics, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics EXPORTS LichenDataOps = BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenArrayPrivate, LichenDataStructure, LichenDataOps; MayDeletePorts: PUBLIC PROC [ct: CellType, ports: Set--of port--, timid, isWholeTrees: BOOL] RETURNS [whyNot: ROPE _ NIL] ~ { d: Design ~ ct.d; PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ { act: CellType ~ NARROW[actv.VA]; a: Array ~ act.asArray; verts: Set--of StatVertex-- ~ Sets.CreateHashSet[a.statrep.svSpace]; edges: Set ~ a.statrep.portEdge[FALSE].Image[ports] .Union[a.statrep.portEdge[TRUE].Image[ports]]; CheckEdge: PROC [sev: Sets.Value] RETURNS [BOOL] ~ { se: StatEdge ~ NARROW[sev.VA]; FOR b: BOOL IN BOOL DO sv: StatVertex ~ se.SeSv[a, b]; IF ports.HasMemA[sv.port] THEN { IF sv#se.SeSv[a, NOT b] AND NOT verts.AddElt[SvV[sv]] --this test is stronger than it needs to be, but maybe there's no arising case that exercises the difference-- THEN { whyNot _ IO.PutFR["deleting static vertex %g@%g,%g in %g might partition a component", [rope[Describe[d, sv.port, ct]]], [integer[sv.phase[X]]], [integer[sv.phase[Y]]], [rope[Describe[d, act, d]]]]; RETURN [TRUE]}}; ENDLOOP; RETURN [FALSE]}; [] _ edges.Scan[CheckEdge]; IF whyNot#NIL THEN RETURN [TRUE]; {losers, abandoned: Set; [losers, abandoned] _ ArrayLosers[act, ports, FALSE]; IF NOT timid THEN ERROR --not implemented--; IF NOT abandoned.Empty THEN whyNot _ IO.PutFR["would abandon ports %g of %g", [rope[abandoned.FormatSet[length: INT.LAST, order: act.nameOrder[p]]]], [rope[act.ACtName[]]]] ELSE whyNot _ MayDeletePorts[act, losers, timid, TRUE]; RETURN [whyNot#NIL]}}; IF NOT isWholeTrees THEN ERROR --case not implemented--; [] _ d.arrayElt.ScanMapping[AV[ct], PerArray, rightToLeft]; RETURN}; NoteExEltPorts: PUBLIC PROC [ect: CellType, eps: Set, mayHaveConsequences: BOOL, log: IO.STREAM _ NIL] ~ { d: Design ~ ect.d; PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ { act: CellType ~ NARROW[actv.VA]; a: Array ~ act.asArray; edges: Set ~ a.statrep.portEdge[FALSE].Image[eps] .Union[a.statrep.portEdge[TRUE].Image[eps]] .CreateHashCopy[]; losers, abandoned: Set; IF a.buildPhase # statrepFixed THEN ERROR; [losers, abandoned] _ ArrayLosers[act, eps, TRUE]; IF NOT abandoned.Empty THEN ERROR --shouldn't arise--; {notLosers: Set ~ losers.Negate; Undumb: PROC [epv: Sets.Value] RETURNS [BOOL] ~ { ep: Port ~ NARROW[epv.VA]; dws: REF Fn ~ NARROW[a.dumrep.epToWire.Apply[epv].MDA]; PerWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ { dw: DumbWire ~ NARROW[dwv.VA]; IF NOT dw.eps.DeleteA[ep] THEN ERROR; IF dw.eps.Empty THEN { aps: Set ~ a.dumrep.epToWire.Mapping[AV[dw], rightToLeft]; IF NOT aps.Intersection[notLosers].Empty THEN ERROR; IF NOT a.dumrep.wires.RemA[dw] THEN ERROR; --let DeletePorts[aps] fix apToWire--}; RETURN [FALSE]}; IF dws#NIL AND dws^.SetOn[right].Scan[PerWire].found THEN ERROR; RETURN [FALSE]}; [] _ a.statrep.edges.RemSet[edges] --AAASEP says we don't have to worry about creating the child edges, if any--; [] _ a.statrep.portEdge[FALSE].DeleteSet[edges, right]; [] _ a.statrep.portEdge[TRUE].DeleteSet[edges, right]; [] _ a.statrep.svEdge[FALSE].DeleteSet[edges, right]; [] _ a.statrep.svEdge[TRUE].DeleteSet[edges, right]; IF a.buildPhase = statrepFixed THEN { IF eps.Scan[Undumb].found THEN ERROR; [] _ a.dumrep.epToWire.DeleteSet[eps]}; IF NOT losers.Empty THEN { IF NOT mayHaveConsequences THEN ERROR; IF log#NIL THEN log.PutF["DelPs %g of %g exded.\n", [rope[losers.FormatSet[length: INT.LAST, order: act.nameOrder[p]]]], [rope[Describe[d, act, d]]]]; DeletePorts[act, losers, TRUE, FALSE, log]; log _ log}; RETURN [FALSE]}}; [] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft]; RETURN}; NoteEltPortMerge: PUBLIC PROC [ect: CellType, kept: Port, lost: Set--of port--] ~ { d: Design ~ ect.d; PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ { act: CellType ~ NARROW[actv.VA]; a: Array ~ act.asArray; kdws: REF Fn _ GetDumbWires[a, kept, FALSE]; PerLoser: PROC [lv: Sets.Value] RETURNS [BOOL] ~ { loser: Port ~ NARROW[lv.VA]; ldws: REF Fn ~ GetDumbWires[a, loser, FALSE]; FixDW: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ { dw: DumbWire ~ NARROW[dwv.VA]; dw.eps.SubstituteA[loser, kept, left]; RETURN [FALSE]}; IF ldws#NIL THEN { IF kdws=NIL THEN kdws _ GetDumbWires[a, kept, TRUE]; {had: BiRels.HadSetPair ~ kdws^.AddSet[ldws^, BiRels.addIfNew]; IF had[leftToRight][different] THEN ERROR; IF ldws^.SetOn[right].Scan[FixDW].found THEN ERROR; IF NOT a.dumrep.epToWire.DeleteA[loser] THEN ERROR}}; RETURN [FALSE]}; FixEdge: PROC [ev: Sets.Value] RETURNS [BOOL] ~ --probably relies on AAASEP-- { se: StatEdge ~ NARROW[ev.VA]; FOR b: BOOL IN BOOL DO sv: StatVertex ~ se.SeSv[a, b]; IF lost.HasMemA[sv.port] THEN { [] _ a.statrep.portEdge[b].AddAA[kept, se]; [] _ a.statrep.svEdge[b].AddPair[[SvV[[kept, sv.phase]], AV[se]]]}; ENDLOOP; RETURN [FALSE]}; FixExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ { pai: PortAtIndex ~ VPai[pair[right]]; IF lost.HasMemA[pai.port] THEN { had: BiRels.HadPair ~ a.statrep.apToPAI.AddPair[[pair[left], PaiV[[kept, pai.ai]]], BiRels.addIfOld]; IF had[leftToRight] # different THEN ERROR}; RETURN [FALSE]}; edges: Set ~ a.statrep.portEdge[FALSE].Image[lost] .Union[a.statrep.portEdge[TRUE].Image[lost]] .CreateHashCopy[]; IF a.buildPhase # statrepFixed THEN ERROR; IF lost.Scan[PerLoser].found THEN ERROR; IF edges.Scan[FixEdge].found THEN ERROR; IF a.statrep.apToPAI.Scan[FixExport].found THEN ERROR; TrimStatrep[act, a, edges]; RETURN [FALSE]}; [] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft]; RETURN}; ArrayLosers: PROC [act: CellType, eps: Set, replace: BOOL] RETURNS [losers, abandoned: Set] ~ { d: Design ~ act.d; a: Array ~ act.asArray; starts: Set ~ Sets.CreateHashSet[d.eSpace]; roots: Set ~ Sets.CreateHashSet[d.eSpace]; cousins: Set ~ d.ancest.Image[roots, rightToLeft]; CheckExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ { pai: PortAtIndex ~ VPai[pair[right]]; IF eps.HasMemA[pai.port] THEN { ap: Port ~ NARROW[pair[left].VA]; dw: DumbWire ~ NARROW[a.dumrep.apToWire.ApplyA[ap].MA]; repl: Port ~ NARROW[dw.eps.SetOn[left].Difference[eps].AnElt.MDA]; IF repl=NIL THEN {[] _ starts.AddA[ap]; [] _ roots.AddA[d.PWRoot[ap]]} ELSE IF replace THEN { epcai: BiRels.Pair ~ dw.eps.ScanMapping[AV[repl], Sets.AcceptAny].P; cai: NAT ~ epcai[right].VI; ai: Int2 ~ DecomposeAI[a, cai]; IF epcai[left] # AV[repl] THEN ERROR; [] _ a.statrep.apToPAI.AddPair[[AV[ap], PaiV[[repl, ai]] ]]}; }; RETURN [FALSE]}; IF a.buildPhase # statrepFixed THEN ERROR; IF a.statrep.apToPAI.Scan[CheckExport].found THEN ERROR; losers _ d.ancest.Image[starts].CreateHashCopy[]; abandoned _ cousins.Difference[losers]; RETURN}; intSets: Sets.Space ~ Sets.CreateSetSpace[SetBasics.ints]; TryToMergeDumbWires: PUBLIC PROC [d: Design, act: CellType, wires: Set] RETURNS [balks: Set] ~ { a: Array ~ act.asArray; balks _ Sets.CreateHashSet[a.dumrep.dwSpace]; IF wires.Trivial THEN RETURN; DO AddEdge: PROC [sep: StatEdgeSpec] ~ { [] _ EnsureStatEdge[d, a.statrep, sep, FALSE, TRUE, FALSE]; RETURN}; anDw: DumbWire ~ NARROW[wires.AnElt.MA]; dumby: DumbWire ~ CreateBareDumbWire[act]; losers: Set ~ wires.Difference[Sets.CreateSingleA[anDw, a.dumrep.dwSpace]]; StartDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ { dw: DumbWire ~ NARROW[dwv.VA]; [] _ dumby.eps.AddSet[dw.eps]; IF dw.children#nilBiRel THEN ERROR; IF dw.parent#NIL THEN ERROR; RETURN [FALSE]}; FixExport: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ { dw: DumbWire ~ NARROW[dwv.VA]; IF dw#anDw THEN a.dumrep.apToWire.SubstituteA[dw, anDw, right]; RETURN [FALSE]}; IF wires.Scan[StartDumb].found THEN ERROR; {givenCai: Set ~ dumby.eps.SetOn[right]; splort: BOOL ~ givenCai.NonTrivial; allCai: Set ~ IF splort THEN Sets.IIAsSet[[0, a.size-1]] ELSE Sets.CreateSingleton[givenCai.TheElt, SetBasics.ints]; allEp: Set ~ a.dumrep.epw.Image[wires, rightToLeft].CreateHashCopy[]; allEps: BiRel ~ BiRels.CreateProduct[[allEp, allCai]]; missedEps: BiRel ~ allEps.Difference[dumby.eps]; IF missedEps.NonEmpty THEN { missedEp: Set ~ missedEps.SetOn[left].CreateHashCopy[]; theirWires: Set ~ a.dumrep.epw.Image[missedEp]; ourLosses: Set ~ wires.Intersection[theirWires].CreateHashCopy[]; [] _ balks.AddSet[ourLosses]; [] _ wires.RemSet[ourLosses]; IF wires.Trivial THEN RETURN ELSE LOOP}; IF wires.Scan[FixExport].found THEN ERROR; {edges: Set ~ a.statrep.portEdge[FALSE].Image[allEp] .Union[a.statrep.portEdge[TRUE].Image[allEp]] .CreateHashCopy[]; theCai: CompositeArrayIndex ~ givenCai.AnElt.MI; theAi: Int2 ~ DecomposeAI[a, theCai]; thePhase: Int2 ~ Mod[theAi, a.basePeriod]; anEp: Port ~ NARROW[anDw.eps.SetOn[left].AnElt.MA]; epSofar: Set ~ Sets.CreateHashSet[d.eSpace]; caiSofar: Set _ Sets.CreateSingleI[theCai, SetBasics.ints]; epsSofar: BiRel _ BiRels.CreateProduct[[epSofar, caiSofar]]; splable: BOOL _ splort; FinishDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ { dw: DumbWire ~ NARROW[dwv.VA]; missedEps: Set ~ dw.eps.SetOn[left].Difference[epSofar]; DO missedEp: Port ~ NARROW[missedEps.AnElt.MDA]; IF missedEp#NIL THEN { IF splort THEN FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[X]) DO AddEdge[[vs: [[anEp, [fx, fy]], [missedEp, [fx, fy]]], d: ALL[0]]]; ENDLOOP ENDLOOP ELSE AddEdge[[vs: [[anEp, thePhase], [missedEp, thePhase]], d: ALL[0]]]; IF NOT epSofar.AddA[missedEp] THEN ERROR; LOOP}; IF NOT splable THEN EXIT; {missedCaiMv: Sets.MaybeValue ~ dw.eps.SetOn[right].Difference[caiSofar].AnElt; IF NOT missedCaiMv.found THEN EXIT; {missedAi: Int2 ~ DecomposeAI[a, missedCaiMv.it.VI]; mep: Port ~ NARROW[dw.eps.Mapping[missedCaiMv.it, rightToLeft].AnElt.MA]; doDim: ARRAY Dim2 OF BOOL ~ [a.size2[X]>1, a.size2[Y]>1]; FOR dim: Dim2 IN Dim2 DO IF doDim[dim] THEN FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[X]) DO delta: Int2 ~ ConsInt2[dim, 1, 0]; f: Int2 ~ [fx, fy]; IF a.size2[dim]>f[dim]+1 THEN AddEdge[[vs: [[mep, f], [mep, AddMod[f, delta, a.basePeriod]]], d: delta]]; ENDLOOP ENDLOOP; ENDLOOP; splable _ FALSE; caiSofar _ allCai; }}ENDLOOP; RETURN [FALSE]}; FinishEP: PROC [epv: Sets.Value] RETURNS [BOOL] ~ { ep: Port ~ NARROW[epv.VA]; dws: Fn--composite array index _ DumbWire-- ~ LichenArrayPrivate.GetDumbWires[a, ep, FALSE]^; [] _ dws.AddSet[BiRels.CreateProduct[[allCai, Sets.CreateSingleA[anDw, a.dumrep.dwSpace]]]]; RETURN [FALSE]}; IF NOT epSofar.AddA[anEp] THEN ERROR; IF wires.Scan[FinishDumb].found THEN ERROR; IF allEp.Scan[FinishEP].found THEN ERROR; [] _ anDw.eps.AddSet[allEps]; IF NOT a.dumrep.wires.RemSet[losers].had.all THEN ERROR; TrimStatrep[act, a, edges]; RETURN}}; ENDLOOP; }; END. bLichenDataImplArrays3.Mesa Last tweaked by Mike Spreitzer on August 15, 1988 4:23:11 pm PDT Κ E– "cedar" style˜code™Kšœ@™@—K˜KšΟk œ(œ[˜ŽK˜šΟnœœ˜$KšœœT˜{Kšœ˜K˜—K˜Kš œœœ žœ œœ9˜vK˜šžœœœΟc œœœ œœ˜}K˜šžœœœœ˜4Kšœœœ˜ K˜Kšœ Ÿœ)˜DKšœ œ)œ˜bšž œœœœ˜4Kšœœœ˜š œœœœ˜Kšœ˜šœœ˜ š œœœœŸnœœ˜«Kšœ œ»˜ΖKšœœ˜——Kšœ˜—Kšœœ˜—Kšœ˜Kš œœœœœ˜!Kšœ˜Kšœ.œ˜5Kš œœœœŸœ˜,Kš œœœ œIœœ4˜¬Kšœ-œ˜7Kšœ œ˜—Kš œœœœŸœ˜8Kšœœ˜;Kšœ˜—K˜šžœœœ0œœœœ˜jKšœ˜šžœœœœ˜4Kšœœœ˜ Kšœ˜Kšœ œ'œ ˜pKšœ˜Kšœœœ˜*Kšœ,œ˜2Kš œœœœŸœ˜6K˜ šžœœœœ˜1Kšœ œœ˜Kšœœœœ˜7šžœœœœ˜2Kšœœœ˜Kšœœœœ˜%šœœ˜Kšœ%œ˜:Kšœœ#œœ˜4Kšœœœœ˜*KšŸ%œ˜'—Kšœœ˜—Kš œœœ'œœ˜@Kšœœ˜—Kšœ#ŸMœ˜qKšœœ˜7Kšœœ˜6Kšœœ˜5Kšœœ˜4šœœ˜%Kšœœœ˜%Kšœ'˜'—šœœœ˜Kšœœœœ˜&Kš œœœDœœ;˜–Kšœœœ˜+Kšœ ˜ —Kšœœ˜—Kšœœ˜