LichenArrayRecovery.Mesa
Last tweaked by Mike Spreitzer on April 12, 1989 7:13:36 pm PDT
DIRECTORY AbSets, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;
LichenArrayRecovery: CEDAR PROGRAM
IMPORTS AbSets, BasicTime, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics
EXPORTS LichenDataOps
=
BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenArrayPrivate, LichenDataStructure, LichenDataOps;
MinimizeArraysPeriod: PUBLIC PROC [d: Design, cts: Set--of CellType--, pacify: IO.STREAM] RETURNS [report: Fn--CellType b period--] ~ {
PerCT: PROC [ctv: Sets.Value] RETURNS [BOOL] ~ {
ct: CellType ~ NARROW[ctv.VA];
start: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
IF pacify#NIL THEN pacify.PutRope[Describe[d, ct]];
{period: Int2 ~ MinimizeArrayPeriod[ct];
report.AddNewPair[[AV[ct], I2V[period]]];
IF pacify#NIL THEN {
end: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
pacify.PutF[" %g\n", [real[BasicTime.PulsesToSeconds[end-start]]]]};
RETURN [FALSE]}};
report ← BiRels.CreateHashTable[[d.eSpace, int2s]];
IF cts.Scan[PerCT].found THEN ERROR;
RETURN};
MinimizeArrayPeriod: PROC [act: CellType] RETURNS [Int2] ~ {
d: Design ~ act.d;
a: Array ~ act.asArray;
sr: StatRep ~ a.statrep;
CheckDown: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
se: StatEdge ~ NARROW[sev.VA];
sep: StatEdgeSpec ← se.SeSp[sr];
sep.vs[TRUE].phase ← SubMod[sep.vs[TRUE].phase, sep.vs[FALSE].phase, a.basePeriod];
sep.vs[FALSE].phase ← ALL[0];
IF FindStatEdge[sr, sep, FALSE].fse=NIL THEN RETURN [TRUE];
RETURN [FALSE]};
CheckUp: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
se: StatEdge ~ NARROW[sev.VA];
sep: StatEdgeSpec ~ se.SeSp[sr];
IF sep.vs[FALSE].phase = ALL[0] THEN {
FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[Y]) DO
dsep: StatEdgeSpec ← sep;
dsep.vs[FALSE].phase ← [fx, fy];
dsep.vs[TRUE].phase ← AddMod[dsep.vs[TRUE].phase, [fx, fy], a.basePeriod];
IF FindStatEdge[sr, dsep, FALSE].fse=NIL THEN RETURN [TRUE];
ENDLOOP ENDLOOP;
};
RETURN [FALSE]};
ShiftDown: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
se: StatEdge ~ NARROW[sev.VA];
sep: StatEdgeSpec ← se.SeSp[sr];
IF sep.vs[FALSE].phase = ALL[0] THEN {
sep.vs[TRUE].phase ← ALL[0];
IF sr.svEdge[TRUE].AddPair[[SvV[sep.vs[TRUE]], AV[se]]].had[rightToLeft]=none THEN ERROR}
ELSE RemStatEdge[d, sr, sep];
RETURN [FALSE]};
IF a.basePeriod=ALL[1] THEN RETURN [ALL[1]];
IF sr.edges.Scan[CheckDown].found THEN RETURN [a.basePeriod];
IF sr.edges.Scan[CheckUp].found THEN RETURN [a.basePeriod];
IF d.physd THEN {
xfms: Set ~ a.fXfm.SetOn[right];
qr: QuotRem ~ DivMod[a.offsets[0].o1, a.basePeriod];
IF xfms.NonTrivial OR qr.r#ALL[0] THEN RETURN [a.basePeriod];
FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[Y]) DO
cf: NAT ~ ComposePhase[a, [fx, fy]];
IF a.offsets[cf].o1 # a.offsets[0].o1 THEN RETURN [a.basePeriod];
IF a.offsets[cf].o0 # Mul[qr.q, [fx, fy], a.offsets[0].o0] THEN RETURN [a.basePeriod];
ENDLOOP ENDLOOP;
{theXfm: Sets.Value ~ xfms.TheElt;
a.offsets ← OffsetsFromList[LIST[[a.offsets[0].o0, qr.q]]];
a.fXfm.Erase[];
a.fXfm.AddNewPair[[I2V[ALL[0]], theXfm]];
}};
IF sr.edges.Scan[ShiftDown].found THEN ERROR;
RETURN [a.basePeriod ← ALL[1]]};
SimilarizeArrays: PUBLIC PROC [d: Design, acts: Set--of CellType--] RETURNS [uncrossed: Set--of CellType--] ~ {
ects: Set--of CellType-- ~ d.arrayElt.Image[acts];
SimilarizeGroup: PROC [ectv: Sets.Value] RETURNS [BOOL] ~ {
ect: CellType ~ NARROW[ectv.VA];
allActs: Set ~ d.arrayElt.Mapping[ectv, rightToLeft].Intersection[acts];
keeps: Set--of act-- ~ Sets.CreateHashSet[d.eSpace];
mergeds: Set--of act-- ~ Sets.CreateHashSet[d.eSpace];
TryAct: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
act: CellType ~ NARROW[actv.VA];
TryExisting: PROC [xctv: Sets.Value] RETURNS [BOOL] ~ {
xct: CellType ~ NARROW[xctv.VA];
equiv: BOOL;
assoc: OneToOne;
[equiv, assoc] ← StructurallyEquivalent[act, xct];
IF equiv THEN {
UndistinguishCellTypes[d, act, xct, assoc];
[] ← mergeds.AddA[xct];
RETURN [TRUE]}
ELSE equiv ← equiv;
RETURN [FALSE]};
IF NOT keeps.Scan[TryExisting].found THEN {
IF NOT keeps.AddElt[actv] THEN ERROR;
};
RETURN [FALSE]};
IF allActs.Scan[TryAct].found THEN ERROR;
IF NOT mergeds.Subset[d.cellTypes] THEN ERROR;
[] ← uncrossed.AddSet[mergeds.Difference[d.crossedCellTypes]];
RETURN [FALSE]};
SimplifyNames: PROC [ectv: Sets.Value] RETURNS [BOOL] ~ {
ect: CellType ~ NARROW[ectv.VA];
allActs: Set ~ d.arrayElt.Mapping[ectv, rightToLeft];
IF allActs.Trivial THEN {
act: CellType ~ NARROW[allActs.AnElt.MA];
[] ← d.ctName.DeleteA[act];
[] ← d.ctName.AddAA[act, ect.ACtName[].Cat["-array"]]}
ELSE d ← d;
RETURN [FALSE]};
uncrossed ← Sets.CreateHashSet[d.eSpace];
IF ects.Scan[SimilarizeGroup].found THEN ERROR;
IF ects.Scan[SimplifyNames].found THEN ERROR;
RETURN};
END.