LichenDataImplArrays1.Mesa
Last tweaked by Mike Spreitzer on August 26, 1988 3:43:49 pm PDT
DIRECTORY AbSets, Basics, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;
LichenDataImplArrays1: CEDAR PROGRAM
IMPORTS AbSets, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics
EXPORTS LichenArrayPrivate, LichenDataStructure, LichenDataOps
=
BEGIN OPEN LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps, LichenArrayPrivate, Sets:AbSets;
CreateArray: PUBLIC PROC [d: Design, eltType: CellType, size, basePeriod: Int2, fXfm: Fn--phase b Transform--, offsets: OffsetSeq, names: Set--of ROPE--] RETURNS [act: CellType] ~ {
act ← CreateCellType[d, array, emptyRange2, names];
SetArrayPart[act, eltType, CreateArrayPart[act, eltType, size, basePeriod, fXfm, offsets]];
RETURN};
SetArrayPart: PUBLIC PROC [act, ect: CellType, a: Array] ~ {
sizeRange: Range2 ~ SizeRange[a.size2];
act.asArray ← a;
[] ← act.d.arrayElt.AddAA[act, ect];
IF a.offsets=NIL THEN ect ← ect
ELSE FOR fx: Int IN [0 .. a.basePeriod[X]) DO FOR fy: Int IN [0 .. a.basePeriod[Y]) DO
f: Int2 ~ [fx, fy];
cf: NATURAL ~ ComposePhase[a, f];
div: Range2 ~ Range2Div[sizeRange, a.basePeriod, f];
xfm: Transform ~ VXfm[a.fXfm.Apply[I2V[f]].Val];
IF Range2Empty[div] OR Range2Empty[ect.bbox] THEN act ← act ELSE {
min: Int2 ~ Mul[Range2Min[div], a.offsets[cf].o1, a.offsets[cf].o0];
max: Int2 ~ Mul[Range2Max[div], a.offsets[cf].o1, a.offsets[cf].o0];
act.bbox ← Range2Mbb[act.bbox, Range2Mbb[TransOffRange2[xfm, min, ect.bbox], TransOffRange2[xfm, max, ect.bbox]]];
a ← a};
ENDLOOP ENDLOOP;
a ← a;
RETURN};
CreateArrayPart: PUBLIC PROC [act, ect: CellType, size, basePeriod: Int2, fXfm: Fn, offsets: OffsetSeq] RETURNS [Array] ~ {
d: Design ~ act.d;
aName: ROPE ~ act.ACtName[];
svSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate ← [
Contains: SVContains,
Equal: SVEqual,
AHash: SVHash,
ACompare: SVCompare,
Print: SVPrint,
name: Rope.Cat["stat verts of ", aName],
data: act]];
paiSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate ← [
Contains: PAIContains,
Equal: PAIEqual,
AHash: PAIHash,
ACompare: PAICompare,
Print: PAIPrint,
name: Rope.Cat["pais of ", aName],
data: act]];
edgeSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate ← [
Contains: SEContains,
Equal: SetBasics.reps.Equal,
AHash: SetBasics.reps.AHash,
ACompare: SetBasics.reps.ACompare,
Print: SEPrint,
name: Rope.Cat["stat edges of ", aName],
data: act]];
a: Array ~ NEW [ArrayPrivate ← [
size2: size,
size: Area[size],
basePeriod: basePeriod,
fXfm: fXfm,
offsets: offsets,
connToPhys: [],
statrep: NEW [StatRepPrivate ← [
edgeSpace: edgeSpace, paiSpace: paiSpace, svSpace: svSpace,
svNameOrder: [SVNameCompare, TRUE, FALSE, act],
edgeNameOrder: [SENameCompare, TRUE, FALSE, act],
edges: Sets.CreateHashSet[edgeSpace],
paiToEP: BiRels.FnFromProc[PaiExtract, [paiSpace, d.eSpace], $p, TRUE],
paiToX: BiRels.FnFromProc[PaiExtract, [paiSpace, SetBasics.ints], $x, TRUE],
paiToY: BiRels.FnFromProc[PaiExtract, [paiSpace, SetBasics.ints], $y, TRUE],
portEdge: [
FALSE: BiRels.CreateHashReln[spaces: [d.eSpace, edgeSpace], functional: [FALSE, TRUE]],
TRUE: BiRels.CreateHashReln[spaces: [d.eSpace, edgeSpace], functional: [FALSE, TRUE]]
],
svEdge: [
FALSE: BiRels.CreateHashReln[spaces: [svSpace, edgeSpace], functional: [FALSE, TRUE]],
TRUE: BiRels.CreateHashReln[spaces: [svSpace, edgeSpace], functional: [FALSE, TRUE]]
],
apToPAI: BiRels.CreateHashFn[[d.eSpace, paiSpace]]
]]
]];
IF fXfm#nilBiRel THEN {
IF fXfm.Size.EN # Area[basePeriod] THEN ERROR;
IF offsets#NIL THEN {
o00: Int2 ~ EltCtr[a, ect, [0, 0]];
FOR dim: Dim2 IN Dim2 DO
IF size[dim]>1 THEN {
on: Int2 ~ EltCtr[a, ect, ConsInt2[dim, size[dim]-1, 0]];
a.connToPhys.mirror[dim] ← on[dim] < o00[dim]};
ENDLOOP;
offsets ← offsets}};
RETURN [a]};
PaiExtract: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ {
pai: PortAtIndex ~ VPai[v];
SELECT data FROM
$p => RETURN [[TRUE, AV[pai.port] ]];
$x => RETURN [[TRUE, IV[pai.ai[X]] ]];
$y => RETURN [[TRUE, IV[pai.ai[Y]] ]];
ENDCASE => ERROR};
SVContains: PUBLIC PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
WITH v.ra SELECT FROM
port: Port => RETURN [TRUE];
ENDCASE => RETURN [FALSE]};
SVHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [CARDINAL] ~ {
act: CellType ~ NARROW[data];
sv: StatVertex ~ VSv[v];
RETURN [act.d.eSpace.SHash[AV[sv.port]] + Int2Hash[sv.phase]]};
SVEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
RETURN [SVCompare[data, v1, v2]=equal]};
SVCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
act: CellType ~ NARROW[data];
sv1: StatVertex ~ VSv[v1];
sv2: StatVertex ~ VSv[v2];
IF (c ← act.d.eSpace.SCompare[AV[sv1.port], AV[sv2.port]]) # equal THEN RETURN;
c ← Int2Compare[sv1.phase, sv2.phase];
RETURN};
SVNameCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
act: CellType ~ NARROW[data];
ect: CellType ~ act.EltType[];
sv1: StatVertex ~ VSv[v1];
sv2: StatVertex ~ VSv[v2];
IF (c ← ect.nameOrder[p].PCompare[AV[sv1.port], AV[sv2.port]]) # equal THEN RETURN;
c ← Int2Compare[sv1.phase, sv2.phase];
RETURN};
SVPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
act: CellType ~ NARROW[data];
sv: StatVertex ~ VSv[v];
act.d.eSpace.SPrint[AV[sv.port], to, depth, length, verbose];
PrintQual[to, "~", act.asArray.basePeriod, sv.phase];
RETURN};
PAIContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
WITH v.ra SELECT FROM
port: Port => RETURN [TRUE];
ENDCASE => RETURN [FALSE]};
PAIHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [CARDINAL] ~ {
act: CellType ~ NARROW[data];
pai: PortAtIndex ~ VPai[v];
RETURN [act.d.eSpace.SHash[AV[pai.port]] + Int2Hash[pai.ai]]};
PAIEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
RETURN [PAICompare[data, v1, v2]=equal]};
PAICompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
act: CellType ~ NARROW[data];
pai1: PortAtIndex ~ VPai[v1];
pai2: PortAtIndex ~ VPai[v2];
IF (c ← act.d.eSpace.SCompare[AV[pai1.port], AV[pai2.port]]) # equal THEN RETURN;
c ← Int2Compare[pai1.ai, pai2.ai];
RETURN};
PAIPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
act: CellType ~ NARROW[data];
pai: PortAtIndex ~ VPai[v];
act.d.eSpace.SPrint[AV[pai.port], to, depth, length, verbose];
PrintQual[to, "@", act.asArray.size2, pai.ai];
RETURN};
SEContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
IF v.i#0 THEN RETURN [FALSE];
WITH v.ra SELECT FROM
se: StatEdge => RETURN [TRUE];
ENDCASE => RETURN [FALSE]};
increasingSERank: PUBLIC Sets.Order ~ [SERankCompare, TRUE, FALSE, $up];
decreasingSERank: PUBLIC Sets.Order ~ [SERankCompare, TRUE, FALSE, $dn];
SERankCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [SetBasics.TotalComparison] ~ {
se1: StatEdge ~ NARROW[v1.VA];
se2: StatEdge ~ NARROW[v2.VA];
SELECT data FROM
$up => RETURN SetBasics.CompareIntI[se1.rank, se2.rank];
$dn => RETURN SetBasics.CompareIntI[se2.rank, se1.rank];
ENDCASE => ERROR};
SENameCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
act: CellType ~ NARROW[data];
sr: StatRep ~ act.asArray.statrep;
se1: StatEdge ~ NARROW[v1.VA];
se2: StatEdge ~ NARROW[v2.VA];
IF (c ← sr.svNameOrder.PCompare[se1.SeRSvV[sr, FALSE], se2.SeRSvV[sr, FALSE]]) # equal THEN RETURN;
IF (c ← sr.svNameOrder.PCompare[se1.SeRSvV[sr, TRUE], se2.SeRSvV[sr, TRUE]]) # equal THEN RETURN;
c ← Int2Compare[se1.d, se2.d];
RETURN};
SEPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
act: CellType ~ NARROW[data];
sr: StatRep ~ act.asArray.statrep;
se: StatEdge ~ NARROW[v.VA];
sr.svSpace.SPrint[se.SeRSvV[sr, FALSE], to, depth-1, length, verbose];
to.PutRope[" -> "];
sr.svSpace.SPrint[se.SeRSvV[sr, TRUE], to, depth-1, length, verbose];
PrintQual[to, " by ", act.asArray.size2, se.d];
RETURN};
DWContains: PUBLIC PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
IF v.i#0 THEN RETURN [FALSE];
WITH v.ra SELECT FROM
dw: DumbWire => RETURN [TRUE];
ENDCASE => RETURN [FALSE];
};
DWPrint: PUBLIC PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
act: CellType ~ NARROW[data];
dw: DumbWire ~ NARROW[v.VA];
pai: PortAtIndex ~ SomePAI[act, dw];
IF pai.port#NIL THEN {
to.PutRope["{"];
act.d.eSpace.SPrint[AV[pai.port], to, depth, length, verbose];
PrintQual[to, "@", act.asArray.size2, pai.ai];
to.PutRope["}"]}
ELSE to.PutF["%bB", [cardinal[LOOPHOLE[dw]]]];
RETURN};
PrintQual: PROC [to: IO.STREAM, intro: ROPE, size2, qual: Int2] ~ {
IF size2[X]=1
THEN IF size2[Y]=1
THEN NULL
ELSE to.PutF["%g%g", [rope[intro]], [integer[qual[Y]]]]
ELSE IF size2[Y]=1
THEN to.PutF["%g%g", [rope[intro]], [integer[qual[X]]]]
ELSE to.PutF["%g<%g,%g>", [rope[intro]], [integer[qual[X]]], [integer[qual[Y]]]];
};
ScanStatEdgesFrom: PUBLIC PROC [sr: StatRep, from: StatVertex, start: ARRAY BOOL OF BOOL, Test: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL]] RETURNS [found: BOOLFALSE, se: StatEdge ← NIL, ob: BOOLFALSE] ~ {
FOR ob IN BOOL DO
sb: BOOL ~ NOT ob;
TestEdge: PROC [ra: Sets.Value] RETURNS [pass: BOOL] ~ {
se: StatEdge ~ NARROW[ra.VA];
pass ← Test[se, ob];
RETURN};
IF start[sb] THEN {
mp: BiRels.MaybePair ~ sr.svEdge[sb].ScanMapping[SvV[from], TestEdge];
IF mp.found THEN RETURN [TRUE, NARROW[mp.it[right].VA], ob]};
ENDLOOP;
RETURN};
RedundantEdge: PUBLIC PROC [act: CellType, avoid: StatEdge, a: Array, sep: StatEdgeSpec] RETURNS [redundant: BOOL] ~ {
range: Range2 ~ Int2sRange[ALL[0], sep.d];
seen: Set ~ Sets.CreateHashSet[a.statrep.paiSpace];
goal: PortAtIndex ~ [sep.vs[TRUE].port, sep.d];
SearchFrom: PROC [src: PortAtIndex] RETURNS [ans: BOOL] ~ {
TryEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL] ~ {
IF se=avoid THEN RETURN [FALSE];
{dest: PortAtIndex ~ [se.SeP[a, ob], IF ob THEN LIB.Add[src.ai, se.d] ELSE LIB.Sub[src.ai, se.d]];
IF dest = goal THEN RETURN [TRUE];
RETURN [InRange[dest.ai, range] AND SearchFrom[dest]]}};
IF NOT seen.AddElt[PaiV[src]] THEN RETURN [FALSE];
ans ← ScanStatEdgesFrom[a.statrep, [src.port, Mod[src.ai, a.basePeriod]], ALL[TRUE], TryEdge].found;
IF NOT seen.RemElt[PaiV[src]] THEN ERROR;
RETURN};
IF sep.d = ALL[0] AND sep.vs[FALSE] = sep.vs[TRUE] THEN RETURN [TRUE];
redundant ← SearchFrom[[sep.vs[FALSE].port, ALL[0]]];
RETURN};
TrimStatrep: PUBLIC PROC [act: CellType, a: Array, edges: Set--of StatEdge-- ← nilSet] ~ {
CheckEdge: PROC [ev: Sets.Value] RETURNS [BOOL] ~ {
se: StatEdge ~ NARROW[ev.VA];
IF NOT a.statrep.edges.HasMember[ev] THEN RETURN [FALSE];
IF NOT RedundantEdge[act, se, a, se.SeSp[a.statrep]] THEN {
IF se.d[X]#0 AND se.d[Y]#0 THEN nTough ← nTough + 1;
RETURN [FALSE]};
RemStatEdge[act.d, a.statrep, se.SeSp[a.statrep]];
RETURN [FALSE]};
IF edges=nilSet THEN edges ← a.statrep.edges;
IF edges.Scan[CheckEdge].found THEN ERROR;
RETURN};
nTough: INT ← 0;
CreateBareDumbWire: PUBLIC PROC [act: CellType] RETURNS [DumbWire] ~ {
RETURN [NEW [DumbWirePrivate ← [
eps: BiRels.GenCreate[
spaces: [act.d.eSpace, SetBasics.ints],
mappable: [TRUE, TRUE],
hints: [
leftToRight: [
fn: [$Hash],
set: [$Vector, LIST[
[$Bounds, NEW [SetBasics.IntInterval ← [0, act.asArray.size-1]] ]
]]],
rightToLeft: [
set: [$Hash],
fn: [$Vector]] ]]
]]]};
CreateDumbWireKids: PUBLIC PROC [a: Array, len: LNAT] RETURNS [Seq--of DumbWire--] ~ {
RETURN BiRels.CreateVector[
bounds: [0, len],
rightSpace: a.dumrep.dwSpace]};
NoteNewArrayPort: PUBLIC PROC [act: CellType, ap: Port] ~ {
d: Design ~ act.d;
a: Array ~ act.asArray;
portKids: Seq--of Port-- ~ d.SubSeq[ap];
dumKids: Seq--of DumbWire-- ~ portKids.Compose[a.dumrep.apToWire];
width: LNAT ~ portKids.Size.EN;
pdw: DumbWire;
IF a.buildPhase#statrepFixed THEN ERROR;
IF portKids=nilBiRel THEN ERROR;
IF width=0 THEN ERROR;
IF width # dumKids.Size.EN THEN RETURN;
FOR i: LNAT IN [0 .. width) DO
WITH dumKids.ApplyI[i].MA SELECT FROM
cdw: DumbWire => {
IF cdw.parent=NIL THEN RETURN;
IF i=0 THEN {IF (pdw ← cdw.parent).children.Size.EN # width THEN RETURN}
ELSE IF pdw#cdw.parent THEN RETURN;
IF cdw.index # i THEN RETURN};
ENDCASE => RETURN;
ENDLOOP;
{pai: PortAtIndex ~ act.SomePAI[pdw];
IF pai.port=NIL THEN ERROR;
a.statrep.apToPAI.AddNewPair[[AV[ap], pai.PaiV]];
a.dumrep.apToWire.AddNewAA[ap, pdw];
RETURN}};
NoteNewEltPort: PUBLIC PROC [act: CellType, ep: Port] ~ {
IF act.d.Atomic[ep] THEN RETURN;
{d: Design ~ act.d; a: Array ~ act.asArray;
width: LNAT ~ d.Width[ep];
cp0: Port ~ NARROW[d.Sub[ep, 0]];
TryUpEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL] ~ {
parentSEP: StatEdgeSpec ~ ParentSEP[d, se.SeSp[a.statrep]];
sb: BOOL ~ NOT ob;
oep: Port ~ parentSEP.vs[ob].port;
IF parentSEP.vs[sb].port # ep THEN ERROR;
IF oep = NIL THEN RETURN [FALSE];
IF d.Width[oep] # width THEN RETURN [FALSE];
IF d.Sub[oep, 0] # se.SeP[a, ob] THEN RETURN [FALSE];
FOR i: LNAT IN [1 .. width) DO
IF FindStatEdge[a.statrep, ChildSEP[d, parentSEP, i], FALSE].fse = NIL THEN RETURN [FALSE];
ENDLOOP;
{pse: StatEdge ~ EnsureStatEdge[d, a.statrep, parentSEP, FALSE, TRUE, FALSE];
IF pse=NIL OR FindStatEdge[a.statrep, parentSEP, FALSE].fse#pse THEN ERROR;
SELECT a.buildPhase FROM
buildingStatrep => NULL;
statrepFixed => DumbifyStatEdge[act, pse, TRUE];
ENDCASE => ERROR;
RETURN [FALSE]}};
FOR fx: LNAT IN [0 .. a.basePeriod[X]) DO FOR fy: LNAT IN [0 .. a.basePeriod[Y]) DO
IF ScanStatEdgesFrom[a.statrep, [cp0, [fx, fy]], ALL[TRUE], TryUpEdge].found THEN ERROR;
ENDLOOP ENDLOOP;
RETURN}};
SeSp: PUBLIC PROC [se: StatEdge, sr: StatRep] RETURNS [StatEdgeSpec]
~ {RETURN [[vs: [se.SeRSv[sr, FALSE], se.SeRSv[sr, TRUE]], d: se.d]]};
END.