DIRECTORY AbSets, Basics, BasicTime, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics; LichenDataImplArrays2: CEDAR PROGRAM IMPORTS AbSets, BiRels, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics EXPORTS LichenArrayPrivate, LichenDataStructure, LichenDataOps = BEGIN OPEN LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps, LichenArrayPrivate, Sets:AbSets; FinishedMakingArrayConnections: PUBLIC PROC [act: CellType] ~ { a: Array ~ act.asArray; dwSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate _ [ Contains: DWContains, Equal: SetBasics.refs.Equal, AHash: SetBasics.refs.AHash, ACompare: SetBasics.refs.ACompare, Print: DWPrint, name: "dumb wires", data: act]]; epwl: Fn ~ BiRels.FnFromProc[EpToDumbWires, [act.d.eSpace, SetBasics.refs], a]; epwr: Fn ~ BiRels.FnFromProc[DumbWireToEps, [dwSpace, SetBasics.refs], a]; dumrep: DumRep ~ NEW [DumRepPrivate _ [ dwSpace: dwSpace, wires: Sets.CreateHashSet[dwSpace], epw: BiRels.CreateFromHalves[ spaces: [act.d.eSpace, dwSpace], halves: [[BiRels.roHalfClass, epwl], [BiRels.roHalfClass, epwr]]], dwSub: BiRels.FnFromProc[DW2Kids, [dwSpace, SetBasics.reps], act, FALSE, FALSE], dwParent: BiRels.FnFromProc[DW2Parent, ALL[dwSpace], act, FALSE, FALSE, ScanDWKids], epToWire: BiRels.CreateHashTable[[act.d.eSpace, SetBasics.refs]], apToWire: BiRels.CreateHashFn[spaces: [act.d.eSpace, dwSpace], invable: TRUE] ]]; PerStatEdge: PROC [ra: REF ANY] ~ --AASEU and AAASEP tell us we need to work upward-- { se: StatEdge ~ NARROW[ra]; DumbifyStatEdge[act, se, TRUE]; RETURN}; PerPort: PROC [pair: BiRels.Pair] ~ { ap: Port ~ NARROW[pair[left].VA]; pai: PortAtIndex ~ VPai[pair[right]]; dw: DumbWire ~ GetDumbWireForPort[act, pai.port, pai.ai, TRUE]; IF dw=NIL THEN ERROR; dumrep.apToWire.AddNewAA[ap, dw]; RETURN}; IF a.buildPhase#buildingStatrep THEN ERROR; a.buildPhase _ statrepFixed; a.dumrep _ dumrep; a.statrep.edges.EnumA[PerStatEdge, increasingSERank]; a.statrep.apToPAI.Enumerate[PerPort]; RETURN}; EpToDumbWires: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ { ep: Port ~ NARROW[v.VA]; a: Array ~ NARROW[data]; dws: RefBiRel ~ GetDumbWires[a, ep, FALSE]; IF dws=NIL THEN RETURN [Sets.noMaybe]; RETURN [[TRUE, dws^.SetOn[right].SV]]}; DumbWireToEps: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ { dw: DumbWire ~ NARROW[v.VA]; RETURN [[TRUE, dw.eps.SetOn[left].SV]]}; DW2Kids: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ { dw: DumbWire ~ NARROW[v.VA]; IF dw.children#nilBiRel THEN RETURN [[TRUE, dw.children.BV[]]]; RETURN [Sets.noMaybe]}; DW2Parent: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ { dw: DumbWire ~ NARROW[v.VA]; IF dw.parent#NIL THEN RETURN [[TRUE, AV[dw.parent]]]; RETURN [Sets.noMaybe]}; ScanDWKids: PROC [data: REF ANY, v: Sets.Value, Test: BiRels.Tester] RETURNS [mp: BiRels.MaybePair _ BiRels.noMaybePair] ~ { dw: DumbWire ~ NARROW[v.VA]; Pass: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ { tp: BiRels.Pair ~ [pair[right], AV[dw]]; IF Test[tp] THEN mp _ [TRUE, tp]; RETURN [mp.found]}; IF dw.children=nilBiRel THEN RETURN; [] _ dw.children.Scan[Pass]; RETURN}; DumbifyStatEdge: PUBLIC PROC [act: CellType, se: StatEdge, supering: BOOL] ~ --relies heavily on AASEU, and makes an amortized check of it-- { a: Array ~ act.asArray; svA: StatVertex ~ se.SeSv[a, FALSE]; epA: Port ~ svA.port; epB: Port ~ se.SeP[a, TRUE]; pepA: Port ~ act.d.PParent[epA]; pepB: Port ~ act.d.PParent[epB]; fullRangeA: Range2 ~ Range2Intersection[SizeRange[a.size2], Range2Off[SizeRange[a.size2], Neg[se.d]]]; iRangeA: Range2 ~ Range2Div[fullRangeA, a.basePeriod, svA.phase]; dwsA: Seq--cai _ DumbWire-- ~ GetDumbWires[a, epA, TRUE]^; dwsB: Seq--cai _ DumbWire-- ~ GetDumbWires[a, epB, TRUE]^; atomic: BOOL ~ act.d.Atomic[epA]; width: LNAT ~ IF atomic THEN 0 ELSE act.d.Width[epA]; IF act.d.Atomic[epB] # atomic THEN ERROR; IF NOT (atomic OR width = act.d.Width[epB]) THEN ERROR; FOR if: INT IN [iRangeA[X].min .. iRangeA[X].maxPlusOne) DO FOR ib: INT IN [iRangeA[Y].min .. iRangeA[Y].maxPlusOne) DO aiA: Int2 ~ [ if*a.basePeriod[X]+svA.phase[X], ib*a.basePeriod[Y]+svA.phase[Y]]; aiB: Int2 ~ Add[se.d, aiA]; caiA: CompositeArrayIndex ~ ComposeAI[a, aiA]; caiB: CompositeArrayIndex ~ ComposeAI[a, aiB]; dwA: DumbWire ~ GetDumbWire[act, epA, aiA, TRUE]; dwB: DumbWire ~ GetDumbWire[act, epB, aiB, TRUE]; pdA: BOOL ~ dwA#NIL AND dwA.parent#NIL; pdB: BOOL ~ dwB#NIL AND dwB.parent#NIL; dw: DumbWire _ NIL; IF pdA # pdB THEN ERROR--AASEU violated here--; IF dwA=dwB THEN {IF dwA#NIL THEN dw _ dwA ELSE { dw _ CreateDumbTop[act, epA]; AddDumbElt[a, dw, epA, aiA]; AddDumbElt[a, dw, epB, aiB]}} ELSE IF dwA=NIL THEN AddDumbElt[a, dw _ dwB, epA, aiA] ELSE IF dwB=NIL THEN AddDumbElt[a, dw _ dwA, epB, aiB] ELSE dw _ JoinDumbWires[a, dwA, dwB].survivor; IF supering THEN {dw _ dw; FOR i: LNAT IN [0 .. width) DO cepA: Port ~ NARROW[act.d.Sub[epA, i]]; cepB: Port ~ NARROW[act.d.Sub[epB, i]]; cdwA: DumbWire ~ GetDumbWire[act, cepA, aiA, FALSE]; cdwB: DumbWire ~ GetDumbWire[act, cepB, aiB, FALSE]; IF cdwA = NIL OR cdwA # cdwB THEN ERROR; EnsureDumbChild[act, dw, i, cdwA]; ENDLOOP; act _ act}; se _ se; ENDLOOP ENDLOOP; RETURN}; CreateDumbTop: PROC [act: CellType, rep: Port] RETURNS [tdw: TopDumbWire] ~ { a: Array ~ act.asArray; tdw _ CreateDumbWire[act, rep, NIL, LNAT.LAST]; IF NOT a.dumrep.wires.AddA[tdw] THEN ERROR; RETURN}; AddDumbElt: PROC [a: Array, dw: TopDumbWire, ep: Port, ai: Int2] ~ { cai: CompositeArrayIndex ~ ComposeAI[a, ai]; dws: RefBiRel--cai _ DumbWire-- ~ GetDumbWires[a, ep, TRUE]; dws^.AddNewIA[cai, dw]; dw.eps.AddNewPair[[AV[ep], IV[cai]]]; RETURN}; JoinDumbWires: PROC [a: Array, dwA, dwB: TopDumbWire] RETURNS [survivor, deceased: TopDumbWire] ~ { MoveIndex: PROC [ra: REF ANY] ~ { ep: Port ~ NARROW[ra]; dws: RefBiRel ~ GetDumbWires[a, ep, FALSE]; IF dws=NIL THEN ERROR; dws^.SubstituteA[dwB, dwA, right]; RETURN}; IF dwB.children#nilBiRel AND NOT dwB.children.Empty THEN ERROR; IF NOT a.dumrep.wires.RemA[dwB] THEN ERROR; dwB.eps.SetOn[left].EnumA[MoveIndex]; [] _ dwA.eps.AddSet[dwB.eps]; a.dumrep.apToWire.SubstituteA[dwB, dwA, right]; RETURN [dwA, dwB]}; GetDumbWireForPort: PROC [act: CellType, ep: Port, ai: Int2, mayAdd: BOOL] RETURNS [dw: DumbWire] ~ { a: Array ~ act.asArray; dw _ GetDumbWire[act, ep, ai, TRUE]; IF dw#NIL OR NOT mayAdd THEN RETURN; AddDumbSubtree[act, ai, ep]; dw _ GetDumbWire[act, ep, ai, TRUE]; RETURN}; AddDumbSubtree: PROC [act: CellType, ai: Int2, ep: Port] ~ --required by AASEU to not add ancestor dumb wires to any already in same tree-- { a: Array ~ act.asArray; Check: PROC [ep, done: Port] RETURNS [ok: BOOL _ TRUE] ~ { ok _ GetDumbWire[act, ep, ai, TRUE] = NIL; IF ok AND NOT act.d.Atomic[ep] THEN FOR i: LNAT IN [0 .. act.d.Width[ep]) WHILE ok DO cep: Port ~ NARROW[act.d.Sub[ep, i]]; ok _ cep=done OR Check[cep, NIL]; ENDLOOP; RETURN}; IF NOT Check[ep, NIL] THEN RETURN; {WorkUp: PROC [ep: Port] ~ { parent: Port ~ act.d.PParent[ep]; IF parent#NIL THEN { pdw: DumbWire ~ GetDumbWire[act, parent, ai, TRUE]; IF pdw#NIL THEN {WorkDown[pdw, parent]; RETURN}; IF Check[parent, ep] THEN {WorkUp[parent]; RETURN}; }; {tdw: TopDumbWire ~ CreateDumbTop[act, ep]; AddDumbElt[a, tdw, ep, ai]; WorkDown[tdw, ep]; RETURN}}; WorkDown: PROC [dw: DumbWire, ep: Port] ~ { IF NOT act.d.Atomic[ep] THEN FOR i: LNAT IN [0 .. act.d.Width[ep]) DO cep: Port ~ NARROW[act.d.Sub[ep, i]]; WorkDown[GetDumbChild[act, cep, dw, i], cep]; ENDLOOP; RETURN}; WorkUp[ep]; RETURN}}; ArrayEltPortsConnected: PUBLIC PROC [act: CellType, ai1, ai2: Int2, ep1, ep2: Port] RETURNS [BOOL] ~ { a: Array ~ act.asArray; IF a.buildPhase#statrepFixed THEN ERROR; {dw1: DumbWire ~ GetDumbWire[act, ep1, ai1, TRUE]; dw2: DumbWire ~ GetDumbWire[act, ep2, ai2, TRUE]; RETURN [dw1=dw2 AND dw1#NIL]}}; GetDumbWire: PROC [act: CellType, ep: Port, ai: Int2, mayUp: BOOL] RETURNS [dw: DumbWire] ~ { a: Array ~ act.asArray; d: Design ~ act.d; cai: CompositeArrayIndex ~ ComposeAI[a, ai]; Work: PROC [ep: Port] RETURNS [dw: DumbWire] ~ { dws: RefBiRel--cai _ DumbWire-- ~ GetDumbWires[a, ep, FALSE]; IF dws#NIL THEN dw _ NARROW[dws^.ApplyI[cai].MDA]; IF dw#NIL OR NOT mayUp THEN RETURN; {parent: Port ~ d.PParent[ep]; IF parent#NIL THEN { pdw: DumbWire ~ Work[parent]; IF pdw#NIL THEN RETURN [GetDumbChild[act, ep, pdw, d.PIndex[ep, parent]]]; }; RETURN}}; IF a.buildPhase#statrepFixed THEN ERROR; RETURN Work[ep]}; GetDumbChild: PUBLIC PROC [act: CellType, ep: Port, pdw: DumbWire, idx: LNAT] RETURNS [cdw: ChildDumbWire] ~ { cdw _ NARROW[pdw.children.ApplyI[idx].MDA]; IF cdw#NIL THEN RETURN; pdw.children.AddNewIA[idx, cdw _ CreateDumbWire[act, ep, pdw, idx] ]; RETURN}; EnsureDumbChild: PROC [act: CellType, pdw: DumbWire, idx: LNAT, cdw: DumbWire] ~ { SELECT pdw.children.ApplyI[idx].MDA FROM cdw => NULL; NIL => { IF cdw.parent#NIL THEN ERROR; pdw.children.AddNewIA[idx, cdw]; cdw.parent _ pdw; cdw.index _ idx}; ENDCASE => ERROR}; CreateDumbWire: PROC [act: CellType, ep: Port, parent: DumbWire, index: LNAT] RETURNS [dw: DumbWire] ~ { a: Array ~ act.asArray; atomic: BOOL ~ act.d.Atomic[ep]; kidMax: INT ~ IF atomic THEN -1 ELSE act.d.Width[ep]-1; dw _ CreateBareDumbWire[act]; dw.parent _ parent; dw.index _ index; IF NOT atomic THEN dw.children _ CreateDumbWireKids[a, kidMax]; RETURN}; GetArrayPortForPort: PUBLIC PROC [act: CellType, ai: Int2, ep: Port, mayAdd, addum, nameDum: BOOL] RETURNS [arrayPort: Port] ~ { d: Design ~ act.d; a: Array ~ act.asArray; IF a.buildPhase#statrepFixed THEN ERROR; {dw: DumbWire ~ GetDumbWireForPort[act, ep, ai, mayAdd]; IF dw=NIL THEN {IF mayAdd THEN --possible because of AASEU-- ERROR--trying to export a composite wire that doesn't really exist-- ELSE RETURN [NIL]}; {aPort: Port ~ NARROW[a.dumrep.apToWire.Lookup[goal: AV[dw], order: Sets.alleq].MDA]; IF aPort#NIL THEN RETURN [aPort]; IF NOT mayAdd THEN RETURN [NIL]; {ect: CellType ~ act.EltType[]; apKids: Seq--of array port-- _ nilBiRel; IF NOT d.Atomic[ep] THEN { epKids: Seq--of elt port-- ~ BiRels.DeRef[d.sub.ApplyA[ep].MA]; width: NATURAL ~ epKids.Size.EN; apKids _ CreateVector[bounds: [0, width-1], oneToOne: TRUE, dense: TRUE, rightSpace: d.eSpace]; FOR i: NATURAL IN [0 .. width) DO epKid: Port ~ NARROW[epKids.ApplyI[i].MA]; apKid: Port ~ GetArrayPortForPort[act, ai, epKid, mayAdd, TRUE, TRUE]; apKids.AddNewIA[i, apKid]; ENDLOOP; }; IF d.labelCellTypes.HasMemA[ect] THEN ERROR; arrayPort _ CreatePort[act, IF d.inheritNames THEN ActualNames[FALSE, OneSteppy[AIName[a, ai]], ect.PNames[ep]] ELSE emptySteppySet, FALSE, addum, nameDum, FALSE--taken care of below--, addum, addum, addum, apKids]; a.statrep.apToPAI.AddNewPair[[AV[arrayPort], PaiV[[ep, ai]]]]; a.dumrep.apToWire.AddNewAA[arrayPort, dw]; RETURN}}}}; MakeArrayExport: PUBLIC PROC [d: Design, a: Array, ap, ep: Port, ai: Int2] ~ { IF a.buildPhase#buildingStatrep THEN ERROR--not yet impl'd--; a.statrep.apToPAI.AddNewPair[[AV[ap], PaiV[[ep, ai]]]]; IF d.PParent[ep]#NIL OR NOT d.Atomic[ep] THEN ERROR--not yet implemented--; RETURN}; MakeArrayNewConnection: PUBLIC PROC [d: Design, a: Array, rangeA: Range2, delta: Int2, epA, epB: Port] ~ { IF delta[X]<0 OR delta[X]=0 AND delta[Y]<0 THEN { epC: Port ~ epA; epA _ epB; epB _ epC; rangeA _ Range2Off[rangeA, delta]; delta _ Neg[delta]}; {fullRangeA: Range2 ~ Range2Intersection[SizeRange[a.size2], Range2Off[SizeRange[a.size2], Neg[delta]]]; IF a.buildPhase#buildingStatrep THEN ERROR; IF ABS[delta[X]]>1 OR ABS[delta[Y]]>1 THEN ERROR; IF epA=epB AND delta=[0, 0] THEN --this self-connection is always implicitly present, let's not make it explicit-- RETURN; IF rangeA#fullRangeA THEN ERROR; FOR ff: NAT IN [0 .. a.basePeriod[X]) DO FOR fb: NAT IN [0 .. a.basePeriod[Y]) DO fA: Int2 ~ [ff, fb]; block: Range2 ~ Range2Div[fullRangeA, a.basePeriod, fA]; IF Range2Empty[block] THEN epB _ epB ELSE { fB: Int2 ~ AddMod[fA, delta, a.basePeriod]; svA: StatVertex ~ [epA, fA]; svB: StatVertex ~ [epB, fB]; --the use and/or implementation of this proc relies heavily on AASEU-- [] _ EnsureStatEdge[d, a.statrep, [vs: [svA, svB], d: delta], TRUE, TRUE, TRUE]; epA _ epA}; ENDLOOP ENDLOOP; RETURN}}; MakeArrayConnectionAtPhase: PUBLIC PROC [d: Design, a: Array, rangeA: Range2, fA, delta: Int2, epA, epB: Port] ~ { IF a.buildPhase#buildingStatrep THEN ERROR; IF delta[X]<0 OR delta[X]=0 AND delta[Y]<0 THEN { epC: Port ~ epA; epA _ epB; epB _ epC; rangeA _ Range2Off[rangeA, delta]; delta _ Neg[delta]}; IF fA[X]>=a.basePeriod[X] OR fA[Y]>=a.basePeriod[Y] THEN ERROR; IF ABS[delta[X]]>1 OR ABS[delta[Y]]>1 THEN ERROR; IF epA=epB AND delta=[0, 0] THEN --this self-connection is always implicitly present, let's not make it explicit-- RETURN; {fB: Int2 ~ AddMod[fA, delta, a.basePeriod]; svA: StatVertex ~ [epA, fA]; svB: StatVertex ~ [epB, fB]; fullRangeA: Range2 _ Range2Intersection[SizeRange[a.size2], Range2Off[SizeRange[a.size2], Neg[delta]]]; fullRangeA _ Range2MulB[Range2Div[fullRangeA, a.basePeriod, fA], a.basePeriod, fA]; rangeA _ Range2MulB[Range2Div[rangeA, a.basePeriod, fA], a.basePeriod, fA]; IF rangeA#fullRangeA THEN ERROR; --the use and/or implementation of this proc relies heavily on AASEU-- [] _ EnsureStatEdge[d, a.statrep, [vs: [svA, svB], d: delta], TRUE, TRUE, TRUE]; RETURN}}; END. bLichenDataImplArrays2.Mesa Last tweaked by Mike Spreitzer on August 22, 1988 2:51:20 pm PDT Κ4– "cedar" style˜code™Kšœ@™@—K˜KšΟk œ$œ[˜ŠK˜šΟnœœ˜$Kšœc˜jKšœ7˜>K˜—K˜Kš œœœœ:žœ˜iK˜šžœœœ˜?K˜šœœ˜5Kšžœ ˜Kšžœ˜Kšžœ˜Kšžœ˜"Kšžœ ˜K˜K˜ —KšœP˜PKšœK˜Kšœœ˜'Kšœ˜Kšœ#˜#˜K˜ KšœB˜B—KšœBœœ˜PKšœ'œœœ˜TKšœA˜AKšœHœ˜MK˜—š ž œœœœΟc3œ˜WKšœœ˜Kšœœ˜Kšœ˜—šžœœ˜%Kšœ œ œ˜!Kšœ%˜%Kšœ9œ˜?Kšœœœœ˜Kšœ!˜!Kšœ˜—Kšœœœ˜+Kšœ˜K˜Kšœ5˜5Kšœ%˜%Kšœ˜—K˜š ž œœœœœ˜TKšœ œœ˜Kšœ œ˜Kšœ$œ˜+Kšœœœœ˜&Kšœœœ˜'—K˜š ž œœœœœ˜TKšœœœ˜Kšœœœ˜(—K˜š žœœœœœ˜NKšœœœ˜Kš œœœœœ˜?Kšœ˜—K˜š ž œœœœœ˜PKšœœœ˜Kš œ œœœœœ˜5Kšœ˜—K˜š ž œœœœžœœ0˜|Kšœœœ˜šžœœœœ˜1Kšœ œ˜(Kšœ œœ˜!Kšœ ˜—Kšœœœ˜$K˜Kšœ˜—K˜š žœœœ)œŸ?œ˜ŽK˜Kšœœ˜$Kšœ˜Kšœœ˜Kšœ ˜ Kšœ ˜ KšœaΟgœ˜fKšœA˜AKšœ ŸΠcmŸ œœ˜:Kšœ Ÿ‘Ÿ œœ˜:Kšœœ˜!Kš œœœœœ˜5Kšœœœ˜)Kš œœ œœœ˜7šœΟdœœœ+œœ’œœœ+˜w˜ Kšœ’œ˜ Kšœ’œ˜!—Kšœ œ˜Kšœ.˜.Kšœ.˜.Kšœ+œ˜1Kšœ+œ˜1Kš œœœœ œ˜'Kš œœœœ œ˜'Kšœœ˜Kšœ œŸœ˜/š œ œœœœ œ˜0Kšœ˜K˜Kšœ˜—Kšœœœœ"˜6Kšœœœœ"˜6Kšœ*˜.šœ œ ˜šœœœ˜Kšœ œ˜'Kšœ œ˜'Kšœ-œ˜4Kšœ-œ˜4Kš œœœ œœ˜(K˜"Kšœ˜—K˜ —Kšœ˜Kšœœ˜—Kšœ˜—K˜šž œœœ˜MK˜Kšœœœœ˜/Kšœœœœ˜+Kšœ˜—K˜šž œœ4˜DKšœ,˜,Kšœ Ÿ‘Ÿ œœ˜Kšœ*˜*Kšœ˜ —K˜šžœœœ2˜NKšœœŸœ˜=Kšœœ˜7Kš œœœœœŸœ˜KKšœ˜—K˜šžœœœG˜jšœ œ œ œ˜1K˜&Kšœ"˜"K˜—Kšœh˜hKšœœœ˜+Kš œœ œœ œœ˜1Kš œ œœŸQœœ˜zKšœœœ˜ šœ ’œœœœœ ’œœœ˜QKš œ  ’œ ’œ˜Kšœ4 œ˜8šœœ œ˜+Kš œ œ˜+Kšœ œ˜Kšœ œ˜Kš ŸFœ4 œ œœœ˜—Kšœ ˜ —Kšœœ˜—Kšœ˜ —K˜šžœœœ' œ#˜rKšœœœ˜+šœ œ œ œ˜1K˜&Kšœ"˜"K˜—Kš œ œœ œœœ˜?Kš œœ œœ œœ˜1Kš œ œœŸQœœ˜zKšœ œ œ˜,Kšœ œ˜Kšœ œ˜Kšœg˜gKšœ< œ œ˜SKšœ4 œ œ˜KKšœœœ˜ Kš ŸFœ4 œ œœœ˜—Kšœ˜ —K˜Kšœ˜—…—3θD~