LichenArrayFlattening.Mesa
Last tweaked by Mike Spreitzer on April 7, 1989 10:01:40 am PDT
DIRECTORY AbSets, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;
LichenArrayFlattening: CEDAR PROGRAM
IMPORTS AbSets, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics
EXPORTS LichenDataOps
=
BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps;
FlattenArrays: PUBLIC PROC [d: Design, cts: Set--of CellType--, fix: BOOL, pacify: IO.STREAM] RETURNS [oks: Set--of CellType--, errs: Fn--CellType b err msg--] ~ {
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]];
{err: ROPE ~ FlattenArray[ct, fix];
IF err=NIL THEN {IF NOT oks.AddA[ct] THEN ERROR ELSE NULL}
ELSE errs.AddNewAA[ct, err];
IF pacify#NIL THEN {
end: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
pacify.PutF[" %g\n", [real[BasicTime.PulsesToSeconds[end-start]]]]};
RETURN [FALSE]}};
oks ← Sets.CreateHashSet[d.eSpace];
errs ← BiRels.CreateHashTable[[d.eSpace, SetBasics.ropes[TRUE]]];
IF cts.Scan[PerCT].found THEN ERROR;
RETURN};
FlattenArray: PROC [outer: CellType, fix: BOOL ← TRUE] RETURNS [err: ROPE] ~ {
d: Design ~ outer.d;
oct: CellType ~ outer;
oa: Array ~ oct.asArray;
mct: CellType ~ oct.EltType[];
IF oa=NIL OR mct.asArray=NIL THEN RETURN ["not nested arrays"];
IF NOT d.physd THEN ERROR nyet --but should be easy to rip out--;
{ma: Array ~ mct.asArray;
rm: Int2 ~ Div[ma.size2, ma.basePeriod];
ict: CellType ~ mct.EltType[];
physXfm: Transform ~ VXfm[oa.fXfm.Apply[I2V[[0, 0]]].Val];
connXfm: Transform ~ ma.connToPhys.Compose[physXfm].Compose[oa.connToPhys];
connYfm: Transform ~ connXfm.Invert[];
mul: Int2 ~ connXfm.TransformSize[ma.size2];
xp: Int2 ~ connXfm.TransformSize[ma.basePeriod];
newPeriod: Int2 ~ [
X: IF oa.size2[X]=1 THEN xp[X] ELSE mul[X],
Y: IF oa.size2[Y]=1 THEN xp[Y] ELSE mul[Y]];
nrm: Int2 ~ Div[mul, newPeriod];
w00: Int2 ~ connXfm.TransformPos[[0, 0], mul];
dmul: Int2 ~ LIB.Sub[mul, [1, 1]];
newSize2: Int2 ~ Scale2[mul, oa.size2];
mRange: Range2 ~ SizeRange[ma.size2];
nRange: Range2 ~ SizeRange[newSize2];
cmin: CompositeArrayIndex ~ ma.ComposeAI[[0, 0]];
cmax: CompositeArrayIndex ~ ma.ComposeAI[LIB.Sub[ma.size2, [1, 1]]];
fXfm: Fn--phase b Transform-- ~ BiRels.CreateHashTable[[int2s, xfmSpace]];
offsets: OffsetSeq ~ NEW [OffsetSequence[Area[newPeriod]]];
IF mul[X]>2 AND oa.size2[X]>1 OR mul[Y]>2 AND oa.size2[Y]>1 OR oa.basePeriod#ALL[1] OR LIB.Scale2[rm, ma.basePeriod]#ma.size2 THEN RETURN ["Thorny case"] --only because not implemented yet (because not efficient with current data structures)--;
FOR nfx: NATURAL IN [0 .. newPeriod[X]) DO FOR nfy: NATURAL IN [0 .. newPeriod[Y]) DO
nf: Int2 ~ [nfx, nfy];
xnf: Int2 ~ connYfm.TransformPos[nf, ma.size2];
mf: Int2 ~ Mod[xnf, ma.basePeriod];
kt: Int2 ~ LIB.Sub[xnf, mf];
xfm: Transform ~ VXfm[ma.fXfm.Apply[I2V[mf]].Val].Compose[physXfm];
cnf: NATURAL ~ newPeriod[Y]*nf[X]+nf[Y];
cmf: NATURAL ~ ComposePhase[ma, mf];
oop: OffsetPat ~ oa.offsets[0];
mop: OffsetPat ~ ma.offsets[cmf];
no1: Int2 ~ Div[oop.o1, nrm];
wo: Int2 ~ Div[LIB.Sub[w00, connXfm.TransformPos[kt, mul]], newPeriod];
no0: Int2 ~ LIB.Sub[Add[oop.o0, physXfm.TransformVector[mop.o0]], Scale2[no1, wo]];
IF Scale2[no1, nrm] # oop.o1 THEN RETURN ["outer step not a multiple of inner size"];
fXfm.AddNewPair[[I2V[nf], XfmV[xfm]]];
offsets[cnf] ← [o0: no0, o1: no1];
ENDLOOP ENDLOOP;
{na: Array ~ CreateArrayPart[oct, ict, newSize2, newPeriod, fXfm, offsets];
ConvertOuterEdge: PROC [val: Sets.Value] RETURNS [BOOL] ~ {
ose: StatEdge ~ NARROW[val.VA];
dd: Int2 ~ connYfm.TransformVector[Scale2[dmul, ose.d]];
cd: CompositeArrayIndex ~ ma.ComposeAI[dd];
dwf: DumbWire ~ NARROW[ma.dumrep.apToWire.ApplyA[ose.SeSv[oa, FALSE].port].MA];
dwt: DumbWire ~ NARROW[ma.dumrep.apToWire.ApplyA[ose.SeSv[oa, TRUE].port].MA];
fis: Set--of CompositeArrayIndex-- ~ dwf.eps.SetOn[right];
tis: Set--of CompositeArrayIndex-- ~ dwt.eps.SetOn[right];
shift: BiRel ~ BiRels.CreateShiftAndClipper[shift: IS.IE[cd], clip: [min: cmin, max: cmax]];
used: Set--of CompositeArrayIndex-- ~ Sets.CreateHashSet[SetBasics.ints];
rangeF: Range2 ~ Range2Intersection[nRange, Range2Off[nRange, Neg[ose.d]]];
fx: NATURAL ~ IF ose.d[X]<0 THEN ma.size2[X]-1 ELSE 0;
fy: NATURAL ~ IF ose.d[Y]<0 THEN ma.size2[Y]-1 ELSE 0;
PerPair: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
IF NOT used.AddElt[pair[left]] THEN RETURN [FALSE];
{tp: Port ~ NARROW[dwt.eps.Lookup[goal: pair[left], order: Sets.alleq].MA];
fp: Port ~ NARROW[dwf.eps.Lookup[goal: pair[right], order: Sets.alleq].MA];
tai: Int2 ~ connXfm.TransformPos[ma.DecomposeAI[pair[left].VI], mul];
fai: Int2 ~ connXfm.TransformPos[ma.DecomposeAI[pair[right].VI], mul];
MakeArrayConnectionAtPhase[d, na, rangeF, fai, ose.d, fp, tp];
RETURN [FALSE]}};
IF shift.ScanRestriction[[tis, fis], PerPair].found THEN ERROR;
IF used.Empty THEN RETURN [TRUE];
RETURN [FALSE]};
ConvertInnerEdge: PROC [val: Sets.Value] RETURNS [BOOL] ~ {
mse: StatEdge ~ NARROW[val.VA];
delta: Int2 ~ connXfm.TransformVector[mse.d];
fA: Int2 ~ connXfm.TransformPos[mse.SeSv[ma, FALSE].phase, mul];
rangeF: Range2 ~ Range2Intersection[nRange, Range2Off[nRange, Neg[delta]]];
MakeArrayConnectionAtPhase[d, na, rangeF, fA, delta, mse.SeSv[ma, FALSE].port, mse.SeSv[ma, TRUE].port];
RETURN [FALSE]};
ConvertExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
op: Port ~ NARROW[pair[left].VA];
opai: PortAtIndex ~ VPai[pair[right]];
mp: Port ~ opai.port;
mmpai: Sets.MaybeValue ~ ma.statrep.apToPAI.ApplyA[mp];
IF mmpai.found THEN {
mpai: PortAtIndex ~ VPai[mmpai.it];
mai: Int2 ~ connXfm.TransformPos[mpai.ai, mul];
MakeArrayExport[d, na, op, mpai.port, Mul[opai.ai, mul, mai]];
RETURN [FALSE]
}
ELSE {
IF d.Atomic[mp] THEN ERROR;
RETURN [FALSE]}};
IF oa.statrep.edges.Scan[ConvertOuterEdge].found THEN RETURN ["difficult edge"];
IF ma.statrep.edges.Scan[ConvertInnerEdge].found THEN ERROR;
IF oa.statrep.apToPAI.Scan[ConvertExport].found THEN ERROR;
SetArrayPart[oct, ict, na];
FinishedMakingArrayConnections[oct];
IF fix THEN FixInterleavingsOfArray[oct];
IF mct.Unused THEN DeleteCellType[mct, NIL];
RETURN [NIL]}}};
UnorganizeArray: PUBLIC PROC [act: CellType] ~ {
d: Design ~ act.d;
a: Array ~ act.asArray;
ect: CellType ~ act.EltType;
seen: Set ~ Sets.CreateHashSet[a.dumrep.dwSpace];
wConv: OneToOne--DumbWire é Wire-- ~ BiRels.CreateHashOTO[[a.dumrep.dwSpace, d.eSpace]];
iConv: OneToOne--CompositeArrayIndex é CellInstance-- ~ BiRels.CreateHashOTO[[SetBasics.ints, d.eSpace]];
FilloutDumbWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
IF NOT seen.AddElt[dwv] THEN RETURN [FALSE];
{dw: DumbWire ~ NARROW[dwv.VA];
aPort: Port ~ NARROW[dw.eps.APair.P[][left].VA];
pKids: BiRel ~ d.SubSeq[aPort];
IF pKids#nilBiRel THEN FOR i: INT IN [0 .. pKids.Size.EN) DO
cdw: DumbWire ~ LichenArrayPrivate.GetDumbChild[act, aPort, dw, i];
[] ← FilloutDumbWire[AV[cdw]];
ENDLOOP;
RETURN [FALSE]}};
CopyDumbWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
IF wConv.Apply[dwv].found THEN RETURN [FALSE];
{dw: DumbWire ~ NARROW[dwv.VA];
composite: BOOL ~ dw.children # nilBiRel;
kids: Seq ← nilBiRel;
IF composite THEN {
n: NAT ~ dw.children.Size.EN;
FOR i: NAT IN [0 .. n) DO [] ← CopyDumbWire[dw.children.ApplyI[i].Val] ENDLOOP;
kids ← dw.children.Compose[wConv, [TRUE, FALSE]].CreateHashCopy[];
IF kids.Size.EN # n THEN ERROR};
{w: Wire ~ CreateWire[act, emptySteppySet, FALSE, FALSE, FALSE, kids];
epc: Fn ~ dw.eps.Collect[right];
MoveName: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
ep: Port ~ NARROW[pair[left].VA];
epNames: Set ~ ect.PNames[ep];
MoveIndex: PROC [caiv: Sets.Value] RETURNS [BOOL] ~ {
cai: CompositeArrayIndex ~ caiv.VI;
ai: Int2 ~ DecomposeAI[a, cai];
ain: SteppyName ~ AIName[a, ai];
KnowPartNames[act, w, w, ActualNames[FALSE, OneSteppy[ain], epNames], FALSE];
RETURN [FALSE]};
cais: Set ~ Sets.VS[pair[right]];
IF cais.Size.EN = a.size THEN KnowPartNames[act, w, w, epNames, FALSE]
ELSE IF cais.Scan[MoveIndex].found THEN ERROR;
RETURN [FALSE]};
wConv.AddNewAA[dw, w];
IF epc.Scan[MoveName].found THEN ERROR;
RETURN [FALSE]}}};
ConnectByDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
pcs: BiRel ~ dw.eps.Compose[iConv, [TRUE, FALSE]];
w: Wire ~ NARROW[wConv.Apply[dwv].MA];
ConnectPCs[d, w, pcs];
RETURN [FALSE]};
FixAtoms: PROC [pv: Sets.Value] RETURNS [BOOL] ~ {
p: Port ~ NARROW[pv.VA];
pNames: Set ← nilSet;
IF NOT d.Atomic[p] THEN RETURN [FALSE];
FOR x: NAT IN [0 .. a.size2[X]) DO FOR y: NAT IN [0 .. a.size2[Y]) DO
ai: Int2 ~ [x, y];
cai: CompositeArrayIndex ~ ComposeAI[a, ai];
ci: CellInstance ~ NARROW[iConv.ApplyI[cai].MA];
w: Wire ← ConndWire[ci, p];
IF w=NIL THEN {
ain: SteppyName ~ AIName[a, ai];
IF pNames=nilSet THEN pNames ← ect.PNames[p];
w ← CreateWire[act, ActualNames[FALSE, OneSteppy[ain], pNames], FALSE, FALSE, FALSE];
Connect[d, w, p, ci]};
ENDLOOP ENDLOOP;
RETURN [FALSE]};
ConvertExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
ap: Port ~ NARROW[pair[left].VA];
w: Wire ~ NARROW[wConv.Apply[pair[right]].MA];
Connect[d, w, ap, act];
RETURN [FALSE]};
IF a.buildPhase # statrepFixed THEN ERROR;
IF a.dumrep.wires.Scan[FilloutDumbWire].found THEN ERROR;
ForgetArray[act];
FinishCreatingUnorganized[act];
IF a.dumrep.wires.Scan[CopyDumbWire].found THEN ERROR;
FOR x: NAT IN [0 .. a.size2[X]) DO FOR y: NAT IN [0 .. a.size2[Y]) DO
ai: Int2 ~ [x, y];
tf: QuotRem ~ DivMod[ai, a.basePeriod];
cai: CompositeArrayIndex ~ ComposeAI[a, ai];
ain: SteppyName ~ AIName[a, ai];
xfm: Transform ← [];
offset: Int2 ← dullInt2;
IF d.physd THEN {
cf: CompositeArrayIndex ~ ComposePhase[a, tf.r];
xfm ← VXfm[a.fXfm.Apply[I2V[tf.r]].Val];
offset ← Mul[a.offsets[cf].o1, tf.q, a.offsets[cf].o0]};
{ci: CellInstance ~ Instantiate[ect, act, FALSE, xfm, offset, OneSteppy[ain]];
iConv.AddNewIA[cai, ci];
}ENDLOOP ENDLOOP;
IF a.dumrep.wires.Scan[ConnectByDumb].found THEN ERROR;
IF ect.CTParts[p].Scan[FixAtoms].found THEN ERROR;
IF a.dumrep.apToWire.Scan[ConvertExport].found THEN ERROR;
RETURN};
END.