LichenArrayDeduction.Mesa
Last tweaked by Mike Spreitzer on July 1, 1988 10:22:23 am PDT
DIRECTORY AbSets, BasicTime, BiRels, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;
LichenArrayDeduction:
CEDAR
PROGRAM
IMPORTS AbSets, BasicTime, BiRels, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics
=
BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps;
DeducePairness:
PUBLIC
PROC [cts: Set
--of CellType--]
RETURNS [successes, failures: Set ← nilSet] ~ {
DPCt:
PROC [val: Sets.Value]
RETURNS [
BOOL] ~ {
ct: CellType ~ NARROW[val.VA];
success: BOOL ~ DeduceCTPairness[ct];
IF successes=nilSet THEN {successes ← Sets.CreateHashSet[ct.d.eSpace]; failures ← Sets.CreateHashSet[ct.d.eSpace]};
IF NOT Sets.AddElt[IF success THEN successes ELSE failures, val] THEN ERROR;
RETURN [FALSE]};
IF cts.Scan[DPCt].found THEN ERROR;
RETURN};
DeduceCTPairness:
PROC [ct: CellType]
RETURNS [success:
BOOL] ~ {
cis: Set--of CellInstance-- ~ ct.CTParts[i];
IF ct.asu=NIL THEN RETURN [FALSE];
IF cis.Size[].EC MOD 2 # 0 THEN RETURN [FALSE];
ERROR --not yet implemented--};
DeduceArrayness:
PROC [d: Design, cts: Set
--of CellType--, 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 ~ DeduceCTArrayness[ct];
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};
DeduceCTArrayness:
PUBLIC
PROC [ct: CellType]
RETURNS [err:
ROPE] ~ {
cis: Set--of CellInstance-- ~ ct.CTParts[i];
icts: Set--of CellType-- ~ ct.d.ciType.Image[cis];
n: NATURAL ~ cis.Size[].EN;
IF n=0 THEN RETURN ["array of size 0"];
IF ct.asu=NIL THEN RETURN ["not unorganized"];
IF icts.Size[IS.two] # IS.one THEN RETURN ["non-uniform instance types"];
{ict: CellType ~ NARROW[icts.AnElt.MA];
nXfms: NATURAL ~ ct.d.ciXfm.ImageSize[cis, leftToRight, IS.IE[n+1]].EN;
period:
NATURAL ~
SELECT nXfms
FROM
< 1 => ERROR,
= 1 => 1,
<=n => n,
ENDCASE => ERROR;
sorted: OneToOne--index é ci-- ~ BiRels.EnumSeqOfSet[cis, [CompareCenters, TRUE, FALSE, ict]];
idxr: OneToOne
--index
é ci-- ~ BiRels.GenCreate[
spaces: [SetBasics.ints, ct.d.eSpace],
functional: ALL[TRUE],
hints: [
leftToRight: [[$Vector]],
rightToLeft: [[$Hash]] ]];
[] ← idxr.AddSet[sorted];
IF NOT idxr.SetOn[right].Equal[cis] THEN ERROR;
{ci0: CellInstance ~ NARROW[idxr.ApplyI[0].MA];
cin: CellInstance ~ NARROW[idxr.ApplyI[n-1].MA];
ctr0: Int2 ~ CiCtr[ci0, ict];
ctrn: Int2 ~ CiCtr[cin, ict];
dctr: Int2 ~ LIB.Sub[ctrn, ctr0];
dim: Dim2 ~
SELECT
TRUE
FROM
dctr[X] > dctr[Y] => X,
dctr[Y] > dctr[X] => Y,
ENDCASE => ERROR;
RETURN ConvertToArray[ct, ict, cis, n, period, dim, idxr]}}};
ConvertToArray:
PROC [ct, ict: CellType, cis: Set, n, period:
NATURAL, dim: Dim2, idxr: OneToOne]
RETURNS [err:
ROPE] ~ {
idxfm: Fn--index b Xfm-- ~ idxr.Compose[ct.d.ciXfm, [TRUE, FALSE]];
fXfm: Fn--phase b Transform-- ~ BiRels.CreateHashTable[[int2s, xfmSpace]];
offsets: OffsetSeq ~ NEW [OffsetSequence[period]];
FOR
f
z:
NATURAL
IN [0 .. period)
DO
f: Int2 ~ ConsInt2[dim, fz, 0];
fXfm.AddNewPair[[I2V[f], idxfm.ApplyI[fz].Val]];
IF period=n
THEN {
ci: CellInstance ~ NARROW[idxr.ApplyI[fz].MA];
offsets[fz] ← [o0: ci.offset, o1: [0, 0]];
};
ENDLOOP;
IF period#n
THEN {
ci0: CellInstance ~ NARROW[idxr.ApplyI[0].MA];
offsets[0].o0 ← ci0.offset;
IF n=1 THEN offsets[0].o1 ← [0, 0] ELSE
{ci1: CellInstance ~ NARROW[idxr.ApplyI[1].MA];
offsets[0].o1 ← LIB.Sub[ci1.offset, ci0.offset];
FOR i:
NATURAL
IN [2 .. n)
DO
cii: CellInstance ~ NARROW[idxr.ApplyI[i].MA];
IF cii.offset # LIB.Mul[offsets[0].o1, [i, i], offsets[0].o0] THEN ERROR;
ENDLOOP;
}};
{
ConvertWire:
PROC [val: Sets.Value]
RETURNS [
BOOL] ~ {
w: Wire ~ NARROW[val.VA];
note: BOOL ← TRUE;
Outer:
PROC [pairo: BiRels.Pair]
RETURNS [
BOOL] ~ {
porto: Port ~ NARROW[pairo[left].VA];
WITH pairo[right].
VA
SELECT
FROM
cio: CellInstance => {
io: LNAT ~ idxr.Apply[pairo[right], rightToLeft].MI;
NoteExPort:
PROC [apv: Sets.Value]
RETURNS [
BOOL] ~ {
ap: Port ~ NARROW[apv.VA];
MakeArrayExport[ct.d, ct.asArray, ap, porto, ConsInt2[dim, io, 0]];
RETURN [FALSE]};
Inner:
PROC [pairi: BiRels.Pair]
RETURNS [
BOOL] ~ {
WITH pairi[right].
VA
SELECT
FROM
cii: CellInstance => {
ii: LNAT ~ idxr.Apply[pairi[right], rightToLeft].MI;
IF ii-io
IN [0 .. 1]
THEN {
porti: Port ~ NARROW[pairi[left].VA];
MakeArrayNewConnection[ct.d, ct.asArray, ConsRange2[dim, [0, n+io-ii], [0, 1]], ConsInt2[dim, ii-io, 0], porto, porti];
ct ← ct};
};
cti: CellType => NULL;
ENDCASE => ERROR;
RETURN [FALSE]};
IF note
THEN {
IF ct.asu.exports.ScanMapping[AV[w], NoteExPort, rightToLeft].found THEN ERROR;
note ← FALSE};
IF w.conns.Scan[Inner].found THEN ERROR;
ct ← ct};
cto: CellType => NULL;
ENDCASE => ERROR;
RETURN [FALSE]};
IF w.conns.Scan[Outer].found THEN ERROR;
IF note AND ct.asu.exports.HasMapA[w, rightToLeft] THEN ERROR;
RETURN [FALSE]};
SetArrayPart[ct, ict, CreateArrayPart[ct, ict, ConsInt2[dim, n, 1], ConsInt2[dim, period, 1], fXfm, offsets]];
IF ct.CTParts[w].Scan[ConvertWire].found THEN ERROR;
FinishedMakingArrayConnections[ct];
ForgetUnorganized[ct];
RETURN [NIL]}};
DeduceIdxs:
PROC [ct: CellType, cis: Set]
RETURNS [upCells, dnCells: Set] ~ {
upPorts: Set--of ct port-- ~ Sets.CreateHashSet[ct.d.eSpace];
dnPorts: Set--of ct port-- ~ Sets.CreateHashSet[ct.d.eSpace];
StartParent:
PROC [val: Sets.Value]
RETURNS [
BOOL] ~ {
pct: CellType ~ NARROW[val.VA];
a: Array ~ pct.asArray;
IF a = NIL THEN ERROR;
IF NOT (a.size2[X]=1 OR a.size2[Y]=1) THEN RETURN [FALSE];
{lows: Set ~ a.statrep.portEdge[FALSE].SetOn[left];
highs: Set ~ a.statrep.portEdge[TRUE].SetOn[left];
ups: Set ~ lows.Difference[highs];
dns: Set ~ highs.Difference[lows];
samebad: INT ~ upPorts.Intersection[dns].Size.EN + dnPorts.Intersection[ups].Size.EN;
revbad: INT ~ upPorts.Intersection[ups].Size.EN + dnPorts.Intersection[dns].Size.EN;
IF samebad <= revbad
THEN {[] ← upPorts.AddSet[ups]; [] ← dnPorts.AddSet[dns]}
ELSE {[] ← upPorts.AddSet[dns]; [] ← dnPorts.AddSet[ups]};
RETURN [FALSE]}};
IF ct.CtArrays.Scan[StartParent].found THEN ERROR;
upCells ← Sets.CreateHashSet[ct.d.eSpace];
dnCells ← Sets.CreateHashSet[ct.d.eSpace];
{classified: Set ~ upCells.Union[b: dnCells, disjoint: TRUE];
toClassify: Set ~ cis.Difference[classified];
upWires: Set ← ct.asu.exports.Image[upPorts].CreateHashCopy[];
dnWires: Set ← ct.asu.exports.Image[dnPorts].CreateHashCopy[];
cws: Set ← upWires.Union[dnWires].CreateHashCopy[];
[] ← upWires.RemSet[dnWires];
[] ← dnWires.RemSet[upWires];
IF upWires.Empty[] # dnWires.Empty[] THEN ERROR;
IF upWires.Empty[]
THEN {
DivvyType:
PROC [val: Sets.Value]
RETURNS [
BOOL] ~ {
ict: CellType ~ NARROW[val.VA];
isn: Set ~ cis.Intersection[ict.CtInsts[]];
ninsts: LNAT ~ isn.Size[].EN;
i: LNAT ← 0;
DivvyInst:
PROC [val: Sets.Value]
RETURNS [
BOOL] ~ {
IF NOT Sets.AddElt[IF i MOD 2 = 0 THEN upCells ELSE dnCells, val] THEN ERROR;
i ← i+1; RETURN [FALSE]};
IF ninsts MOD 2 # 0 THEN ERROR;
IF isn.Scan[DivvyInst].found THEN ERROR;
RETURN [FALSE]};
IF ct.d.ciType.ScanImage[cis, DivvyType].found THEN ERROR;
ct ← ct}
ELSE {
DO
newUC: Set ~ ct.d.iwConns.Image[upWires, rightToLeft].Difference[classified].CreateHashCopy[];
newDC: Set ~ ct.d.iwConns.Image[dnWires, rightToLeft].Difference[classified].CreateHashCopy[];
[] ← newUC.RemSet[newDC];
[] ← newDC.RemSet[newUC];
IF newUC.Empty AND newDC.Empty THEN ERROR;
[] ← upCells.AddSet[newUC];
[] ← dnCells.AddSet[newDC];
IF toClassify.Empty[] THEN EXIT;
{
newUW: Set ~ ct.d.iwConns.Image[newUC].Difference[cws].CreateHashCopy[];
newDW: Set ~ ct.d.iwConns.Image[newDC].Difference[cws].CreateHashCopy[];
[] ← cws.AddSet[newUW];
[] ← cws.AddSet[newDW];
[] ← newUW.RemSet[newDW];
[] ← newDW.RemSet[newUW];
IF newUW.Empty AND newDW.Empty THEN ERROR;
[] ← upWires.AddSet[newUW];
[] ← dnWires.AddSet[newDW];
}ENDLOOP;
ct ← ct};
RETURN}};
CompareCenters:
PROC [data:
REF
ANY, v1, v2: Sets.Value]
RETURNS [SetBasics.PartialComparison] ~ {
ict: CellType ~ NARROW[data];
ci1: CellInstance ~ NARROW[v1.VA];
ci2: CellInstance ~ NARROW[v2.VA];
ctr1: Int2 ~ CiCtr[ci1, ict];
ctr2: Int2 ~ CiCtr[ci2, ict];
RETURN SetBasics.CompareIntI[INT[ctr1[X]]+ctr1[Y], INT[ctr2[X]]+ctr2[Y]]};
END.