LichenDataImplArrays3.Mesa
Last tweaked by Mike Spreitzer on May 12, 1989 10:40:58 am PDT
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, 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 b 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.