LichenDataImplArrays2.Mesa
Last tweaked by Mike Spreitzer on August 22, 1988 2:51:20 pm PDT
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 b DumbWire-- ~ GetDumbWires[a, epA, TRUE]^;
dwsB: Seq--cai b 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 i
f:
INT
IN [iRangeA[X].min .. iRangeA[X].maxPlusOne)
DO
FOR i
b:
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 b 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 b 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
f
f:
NAT
IN [0 .. a.basePeriod[X])
DO
FOR
f
b:
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.