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 _ 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 f ci-- ~ BiRels.EnumSeqOfSet[cis, [CompareCenters, TRUE, FALSE, ict]]; idxr: OneToOne--index f 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 _ Xfm-- ~ idxr.Compose[ct.d.ciXfm, [TRUE, FALSE]]; fXfm: Fn--phase _ Transform-- ~ BiRels.CreateHashTable[[int2s, xfmSpace]]; offsets: OffsetSeq ~ NEW [OffsetSequence[period]]; FOR fz: 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. `LichenArrayDeduction.Mesa Last tweaked by Mike Spreitzer on July 1, 1988 10:22:23 am PDT Э╩ ўЦ "cedar" styleШcodeЪЬЩKЪЬ>Щ>ЧKШKЪ╧k Ь&ЭЬGШxKШЪ╧nЬЭЬЭШ#KЪЭЬ&ЭЬ@ШoKШЧKШKЪЭЬЭЬЭЬЮЬ ЭЬЭЬ%ШbKШЪ ЮЬЭЬЭЬ ╧cЬЭЬ(ШeЪЮЬЭЬЭЬЭЬШ/KЪЬЭЬЭЬШKЪЬ ЭЬШ%KЪЭЬЭЬ[ШsKЪЭЬЭЬ ЭЬ ЭЬЭЬЭЬЭЬШLKЪЭЬЭЬШЧKЪЭЬЭЬЭЬШ#KЪЭЬШЧKШЪЮЬЭЬЭЬЭЬШAKЪЬЯЬШ,KЪ ЭЬЭЬЭЬЭЬЭЬШ"KЪЭЬЭЬЭЬЭЬЭЬЭЬШ/KЪЭЬЯЬШЧKШЪЮЬЭЬЯЬ ЭЬЭЬЭЬ ЯЬ Я╨cmЯ ЬШУЪЮЬЭЬЭЬЭЬШ0KЪЬЭЬЭЬШKЪЬ5Ш5KЪЭЬЭЬЭЬ!Ш3KЪЬЭЬШ#KЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ:KЪЭЬШЪЭЬЭЬЭЬШKЪЬ3Ш3KШDЧKЪЭЬЭЬШЧKШ#KЪЬ9ЭЬШAKЪЭЬЭЬЭЬШ$KЪЭЬШЧKШЪ ЮЬЭЬЭЬЭЬЭЬШEKЪЬЯЬШ,KЪЬ ЯЬШ2KЪЬЭЬЭЬШKЪЭЬЭЬЭЬШ'KЪЭЬЭЬЭЬЭЬШ.KЪ ЭЬЭЬЭЬЭЬЭЬ ШIKЪЬЭЬЭЬШ'KЪ ЬЭЬ*ЭЬЭЬЭЬШGЪЬЭЬЭЬЭШ#KЪЬЭЬШ KШ KШ KЪЭЬЭЬШЧKЪ ЬЯаЯЬ-ЭЬЭЬШ^ЪЬЯаЯЬШ0KШ&KЪЬЭЬЭЬШШKШKШЧЧKШKЪЭЬЭЬЭЬЭЬШ/KЪЬЭЬЭЬШ/KЪЬЭЬЭЬШ0KШKШKЪ╧gЬЭЬШ!ЪЬЭЬЭЬЭШKЪбЬ бЬШKЪбЬ бЬШKЪЭЬЭЬШЧKЪЭЬ7Ш=ЧKШЪ ЮЬЭЬ*ЭЬЭЬЭЬШyKЪ Ь ЯаЯЬЭЬЭЬШCKЪбЬЯаЯЬ-ШJKЪЬЭЬШ2Ъ ЭЬб╧dЬЭЬЭЬЭШ#KЪбЬбвЬШKЪ бЬЭЬбЬбвЬШ0ЪЭЬ ЭЬШKЪЬЭЬ бвЬЭЬШ.KЪЬбвЬ Ш*KШЧKЪЭЬШЧЪЭЬ ЭЬШKЪЬЭЬЭЬШ.KШKЪЭЬЭЬЭШ'KЪЬЭЬЭЬШ/KЪЬЭЬШ0ЪЭЬЭЬЭЬ ЭШKЪЬЭЬЭЬШ.KЪЭЬЭЬ+ЭЬЭЬШIKЪЭЬШЧKШЧЪ ЬЮЬЭЬЭЬЭЬШ7KЪЬ ЭЬЭЬШKЪЬЭЬЭЬШЪЮЬЭЬЭЬЭЬШ3KЪЬЭЬ ЭЬШ%ЪЭЬЭЬЭЬЭШ ШKЪЬЭЬ)ЭЬШ4ЪЮ ЬЭЬЭЬЭЬШ5KЪЬЭЬЭЬШKЪЬCШCKЪЭЬЭЬШЧЪЮЬЭЬЭЬЭЬШ3ЪЭЬЭЬЭЬЭШ ШKЪЬЭЬ)ЭЬШ4ЪЭЬЭЬ ЭЬШKЪЬЭЬ ЭЬШ%KЪЬwШwKШ ЧKШЧKЪЬЭЬШKЪЭЬЭЬШЧKЪЭЬЭЬШЧЪЭЬЭЬШKЪЭЬЭЬ$ЭЬЭЬШOKЪЬЭЬШЧKЪЭЬЭЬЭЬШ(KШ ЧKЪЬЭЬШKЪЭЬЭЬШЧKЪЭЬЭЬШЧKЪЭЬЭЬЭЬШ(KЪЭЬЭЬ(ЭЬЭЬШ>KЪЭЬЭЬШЧKЪЬ^бЬШnKЪЭЬ'ЭЬЭЬШ4KЪЬ#Ш#KШKЪЭЬЭЬШЧKШЪЮ ЬЭЬЭЬШMKЪЬЯЬ#Ш=KЪЬЯЬ#Ш=ЪЮЬЭЬЭЬЭЬШ6KЪЬЭЬЭЬШKШKЪЭЬЭЬЭЬЭЬШKЪЭЬЭЬЭЬЭЬЭЬЭЬШ:KЪЬ ЭЬШ3KЪЬ ЭЬШ2KШ"KШ"KЪЬ ЭЬ"ЭЬ"ЭЬШUKЪЬЭЬ"ЭЬ"ЭЬШTЪЭЬШKЪЭЬ5Ш9KЪЭЬ6Ш:ЧKЪЭЬЭЬШЧKЪЭЬ%ЭЬЭЬШ2KШ*KЪЬ*Ш*KЪЬ7ЭЬШ=KШ-KЪЬ>Ш>KЪЬ>Ш>KШ3KШKШKЪЭЬ#ЭЬЭЬШ0ЪЭЬЭЬШЪЮ ЬЭЬЭЬЭЬШ4KЪЬЭЬЭЬШKШ+KЪЬЭЬЭЬШKЪЬЭЬШЪЮ ЬЭЬЭЬЭЬШ4KЪЭЬЭЬ ЭЬЭЬЭЬ ЭЬЭЬЭЬШMKЪЬ ЭЬЭЬШЧKЪЭЬЭЬЭЬЭЬШKЪЭЬЭЬЭЬШ(KЪЭЬЭЬШЧKЪЭЬ-ЭЬЭЬШ:KШЧЪЭЬШЪЭШKШ^KЪЬ^Ш^KЪЬШKЪЬШKЪЭЬ ЭЬ ЭЬЭЬШ*KШKЪЬШKЪЭЬЭЬЭЬШ KШKШHKЪЬHШHKШKЪЬШKЪЬШKЪЬШKЪЭЬ ЭЬ ЭЬЭЬШ*KШKЪЬШKЪЬЭЬШ ЧKШ ЧKЪЭЬШ ЧKШЪ ЮЬЭЬЭЬЭЬЭЬ"ШbKЪЬЭЬШKЪЬЭЬЭЬШ"KЪЬЭЬЭЬШ"KЪЬШKЪЬШKЪЭЬЭЬЭЬШJЧKШKЪЭЬШЧЕЧ!b,╣