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
f
x: Int
IN [0 .. a.basePeriod[X])
DO
FOR
f
y: 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:
BOOL ←
FALSE, se: StatEdge ←
NIL, ob:
BOOL ←
FALSE] ~ {
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
f
x:
LNAT
IN [0 .. a.basePeriod[X])
DO
FOR
f
y:
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.