DIRECTORY AbSets, BasicTime, BiRelBasics, BiRels, Convert, Histograms, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenStructuring, Process, RealFns, Rope, SetBasics; LichenStructureDeduction: CEDAR PROGRAM IMPORTS AbSets, BasicTime, BiRelBasics, BiRels, Convert, Histograms, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenStructuring, Process, RealFns, Rope, SetBasics EXPORTS LichenDataOps = BEGIN OPEN LichenDataOps, LichenDataStructure, Sets:AbSets, IS:IntStuff, LichenStructuring; base: REAL ~ RealFns.Power[2, 1.0/4]; minTime: REAL ~ 1.0/32; portTimes: Histograms.Histogram ~ Histograms.Create2D[iFactor: base, jFactor: base, iOffset: 1, jOffset: minTime, logI: TRUE, logJ: TRUE]; wireTimes: Histograms.Histogram ~ Histograms.Create2D[iFactor: base, jFactor: base, iOffset: 1, jOffset: minTime, logI: TRUE, logJ: TRUE]; Break: SIGNAL ~ CODE; breakCTN: ROPE _ NIL; breakKill: SteppyName _ noName; checkA: BOOL _ FALSE; checkB: BOOL _ FALSE; checkC: BOOL _ FALSE; mayCollide: BOOL _ FALSE; AddDeducedStructureToDesign: PUBLIC PROC [design: Design, pacify: IO.STREAM _ NIL] ~ { n: INT _ 0; PerCellType: PROC [val: REF ANY] ~ { ct: CellType ~ NARROW[val]; n _ n + 1; Process.CheckForAbort[]; IF breakCTN#NIL AND design.ctName.HasAA[ct, breakCTN] THEN Break; IF pacify#NIL THEN pacify.PutF["%g %g: %g; ", [rope[Convert.RopeFromTime[from: BasicTime.Now[], start: hours, end: seconds, useAMPM: FALSE, includeZone: FALSE]]], [integer[n]], [rope[Describe[design, ct, design]]]]; [] _ DeduceStructureForPorts[ct, pacify]; IF ct.asu#NIL THEN [] _ DeduceStructureForWires[ct, pacify]; IF pacify#NIL THEN pacify.PutRope[" .\n"]; RETURN}; IF pacify#NIL THEN pacify.PutF["Total: %g\n", [integer[design.cellTypes.Size.EN]]]; design.cellTypes.EnumA[PerCellType]; RETURN}; DeduceStructureForPorts: PUBLIC PROC [ct: CellType, pacify: IO.STREAM _ NIL] RETURNS [new: Set--of Port--] ~ { new _ AddDeducedStructureToTops[ct: ct, class: p, cohorts: ct.TopParts[p], Rename: RenamePort, Group: GroupPorts, timesHist: portTimes, pacify: pacify]; RETURN}; DeduceStructureForWires: PUBLIC PROC [ct: CellType, pacify: IO.STREAM _ NIL] RETURNS [new: Set--of Wire--] ~ { new _ AddDeducedStructureToTops[ct: ct, class: w, cohorts: ct.TopParts[w], Rename: RenameWire, Group: GroupWires, timesHist: wireTimes, pacify: pacify]; RETURN}; RenamePort: PROC [d: Design, thing: PW, old, new: SteppyName] ~ { port: Port ~ NARROW[thing]; ForgetPortName[d, port, old]; KnowPortName[d, port, new]; RETURN}; RenameWire: PROC [d: Design, thing: PW, old, new: SteppyName] ~ { w: Wire ~ NARROW[thing]; ForgetVertexName[d, w, old]; KnowVertexName[d, w, new]; RETURN}; GroupPorts: PROC [ct: CellType, sibs: Seq--of port--, parentNames: Set--of SteppyName--] RETURNS [parent: Port] ~ { d: Design ~ ct.d; parent _ CreatePort[ct, parentNames, FALSE, TRUE, TRUE, TRUE, TRUE, sibs]; RETURN}; GroupWires: PROC [ct: CellType, sibs: Seq--of wire--, parentNames: Set--of SteppyName--] RETURNS [parent: Wire] ~ { d: Design ~ ct.d; parent _ CreateWire[ct, parentNames, TRUE, TRUE, sibs]; RETURN}; setOfOne: Set ~ Sets.CreateSingleton[AV[NEW [INT _ 1]], nameStepSpace]; r0: REF INT ~ NEW [INT _ 0]; AddDeducedStructureToTops: PROC [ct: CellType, class: PWClass, cohorts: Set--of Ports or of Wires--, Rename: PROC [d: Design, thing: PW, old, new: SteppyName], Group: PROC [ct: CellType, sibs: Seq--of child thing--, parentNames: Set--of SteppyName--] RETURNS [parent: Thing], timesHist: Histograms.Histogram, pacify: IO.STREAM] RETURNS [new: Set--of PW--] ~ { d: Design ~ ct.d; sizeSum: LNAT ~ PWSetSize[d, cohorts]; start: BasicTime.Pulses ~ BasicTime.GetClockPulses[]; dag: StepDAG ~ CreateDAG[Rope.Cat["StepDAG for top ", PartClassName[class], "s of ", d.Describe[ct, d]], NIL, NIL]; InsertThing: PROC [cohort: Thing] ~ { PerName: PROC [val: Sets.Value] ~ { name: SteppyName ~ FixSteppyName[VSn[val]]; Process.CheckForAbort[]; InsertInDAG[dag, dag.rootNode, name.steps, cohort]; RETURN}; ct.fullName[class].EnumerateMapping[AV[cohort], PerName]; RETURN}; LeafizeInternal: PROC [parenta, deca: REF ANY] ~ { parent: StepNode ~ NARROW[parenta]; dec: Decomp ~ NARROW[deca]; mv: Sets.MaybeValue ~ dag.toThing.ApplyA[parent]; IF NOT mv.found THEN RETURN; IF NOT mayCollide THEN ERROR; IF NOT dec^.SetOn[left].Equal[setOfOne] THEN ERROR; {thing: Thing ~ mv.MA; downd: StepNode ~ GetDown[dag, parent, r0, TRUE]; parentNames: Set--of SteppyName-- ~ Sets.CreateHashSet[steppyNameSpace]; ChangeName: PROC [val: Sets.Value] ~ { old: SteppyName ~ VSn[val]; new: SteppyName ~ SNAppend[old, r0]; Rename[d, thing, old, new]; RETURN}; GetNames[dag, parent, parentNames, noName]; parentNames.Enumerate[ChangeName]; dag.toThing.RemOldAA[parent, thing]; dag.toThing.AddNewAA[downd, thing]; IF checkC THEN VerifyDAG[dag]; RETURN}}; candSize: Function--StepNode _ size-- ~ BiRels.GenCreate[spaces: [SetBasics.refs, SetBasics.ints], functional: [TRUE, FALSE], hints: [leftToRight: [[$Hash]], rightToLeft: [[$BalancedTree], [$Hash]]]]; SizeCand: PROC [canda: REF ANY] ~ { cand: StepNode ~ NARROW[canda]; g: CandGrade ~ GradeCand[dag, cand]; IF g.good THEN candSize.AddNewPair[[AV[cand], IV[g.size]]]; RETURN}; Groupit: PROC [canda: REF ANY] ~ { cand: StepNode ~ NARROW[canda]; parentNames: Set--of SteppyName-- ~ Sets.CreateHashSet[steppyNameSpace]; dec: Decomp ~ GetDecomp[dag, cand, FALSE]; aKid: StepNode ~ NARROW[dec^.APair.P[][right].VA]; IF GetDecomp[dag, aKid, FALSE]#NIL THEN { kids: Set--of StepNode-- ~ dec^.SetOn[right]; kids.EnumA[Groupit]; canda _ canda}; GetNames[dag, cand, parentNames, noName]; {seq: Seq ~ Sequify[d, dec^.Compose[right: dag.toThing, restricts: [TRUE, FALSE]]]; repl: Thing ~ Group[ct, seq, parentNames]; Delit: PROC [step, child: REF ANY] ~ {RemoveLeaf[dag, NARROW[child]]}; IF NOT new.AddElt[AV[repl]] THEN ERROR; dag.toThing.AddNewAA[cand, repl]; dec^.EnumAA[Delit]; IF checkA THEN VerifyDAG[dag]; RETURN}}; IF pacify#NIL THEN pacify.PutF[" %g %g ", [rope[PartClassName[class]]], [integer[sizeSum]]]; cohorts.EnumA[InsertThing]; IF checkA THEN VerifyDAG[dag]; dag.down.EnumAA[LeafizeInternal]; dag.prefixd _ TRUE; IF checkA THEN VerifyDAG[dag]; CommonizeLeaves[dag]; dag.leavesCommonized _ TRUE; IF checkA THEN VerifyDAG[dag]; DiscoverAndLowerSeqs[dag, dag.rootNode]; CommonizeDecomps[dag]; IF checkA THEN VerifyDAG[dag]; dag.cands.EnumA[SizeCand]; dag.cands _ candSize.SetOn[left]; IF checkA THEN VerifyDAG[dag]; new _ Sets.CreateHashSet[d.eSpace]; UNTIL candSize.Empty[] DO cand: StepNode ~ NARROW[candSize.Pop[[[Sets.alleq, Sets.bwd], right]].P[][left].VA[]]; KillCand[ct, class, dag, candSize, cand, one]; Groupit[cand]; pacify _ pacify; ENDLOOP; IF checkA THEN VerifyDAG[dag]; {finish: BasicTime.Pulses ~ BasicTime.GetClockPulses[]; seconds: REAL ~ BasicTime.PulsesToSeconds[finish - start]; timesHist.ChangeTransformed[sizeSum --fix so lg won't barf--+1, MAX[seconds, minTime]]; IF pacify#NIL THEN pacify.PutF["* %g s", [real[seconds]]]; RETURN}}; KillCand: PROC [ct: CellType, class: PartClass, dag: StepDAG, candSize: Function--StepNode _ size--, cand: StepNode, phase: {one, two, three--phase one enumerates all descendants; phase two kills all their candidate ancestors; phase three kills all their descendants--}] ~ { IF breakKill#noName THEN {mt: Sets.MaybeValue ~ dag.toThing.ApplyA[cand]; IF mt.found AND ct.fullName[class].HasPair[[mt.it, SnV[breakKill]]] THEN Break}; IF phase>one AND NOT candSize.DeleteA[cand] THEN RETURN; --now cand is either an ex-candidate or a descendant of one-- NULL; IF phase#three THEN {ups: Ups ~ GetUps[dag, cand, FALSE]; KillParent: PROC [parent: REF ANY, step: NameStep] ~ { KillCand[ct, class, dag, candSize, NARROW[parent], two]; RETURN}; IF ups#NIL THEN ups^.EnumAA[KillParent]}; {dec: Decomp ~ GetDecomp[dag, cand, FALSE]; KillKid: PROC [step: NameStep, child: REF ANY] ~ { KillCand[ct, class, dag, candSize, NARROW[child], IF phase=one THEN one ELSE three]; RETURN}; IF dec#NIL THEN dec^.EnumAA[KillKid]}; RETURN}; GetNames: PROC [dag: StepDAG, node: StepNode, parentNameSet: Set--of SteppyName--, sofar: SteppyName] ~ { IF node=dag.rootNode THEN { IF NOT parentNameSet.AddElt[SnV[sofar]] THEN ERROR; RETURN} ELSE { ups: Ups ~ GetUps[dag, node, FALSE]; PerUp: PROC [parenta: REF ANY, step: NameStep] ~ { parent: StepNode ~ NARROW[parenta]; next: SteppyName ~ SNPrepend[step, sofar]; GetNames[dag, parent, parentNameSet, next]; RETURN}; ups^.EnumAA[PerUp]; RETURN}; }; DiscoverAndLowerSeqs: PROC [dag: StepDAG, subroot: StepNode] ~ { dec: Decomp ~ GetDecomp[dag, subroot, FALSE]; DoLower: PROC [step, childa: REF ANY] ~ {DiscoverAndLowerSeqs[dag, NARROW[childa]]}; CheckName: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ { WITH pair[left].VA SELECT FROM x: ROPE => RETURN [TRUE]; x: REF INT => RETURN [FALSE]; ENDCASE => ERROR; }; IF dec=NIL THEN RETURN; dec^.EnumAA[DoLower]; IF dec^.Scan[CheckName].found THEN RETURN; {toDo: StepDAG ~ CreateDAG[NIL, subroot, dag]; FindPaths: PROC [step, child: REF ANY] ~ { WITH step SELECT FROM x: ROPE => ERROR; x: REF INT => FindPath[NARROW[child], subroot, x]; ENDCASE => ERROR; RETURN}; FindPath: PROC [from, to: StepNode, index: REF INT] ~ { leaf: BOOL ~ IsKidCand[dag, from]; IF leaf THEN { [] _ toDo.cands.AddA[to]; AddLink[toDo, to, index, from]; RETURN} ELSE { dec: Decomp ~ GetDecomp[dag, from, FALSE]; Subadd: PROC [step: NameStep, oldKida: REF ANY] ~ { oldKid: StepNode ~ NARROW[oldKida]; newKid: StepNode ~ GetDown[toDo, to, step, TRUE]; FindPath[oldKid, newKid, index]; RETURN}; dec^.EnumAA[Subadd]; RETURN}; }; PruneBadCands: PROC [parent: StepNode] ~ { ddec: Decomp ~ GetDecomp[toDo, parent, FALSE]; cand: BOOL ~ toDo.cands.HasMemA[parent]; bounds: IS.Interval _ IS.anEmptyInterval; badBranchSeen: BOOL _ FALSE; size: NATURAL _ 0; seen: Set--of StepNode-- ~ IF cand THEN Sets.CreateHashSet[] ELSE Sets.nilSet; PerPair: PROC [step, childa: REF ANY] ~ { child: StepNode ~ NARROW[childa]; IF NOT (cand AND IsKidCand[dag, child]) THEN { badBranchSeen _ TRUE; PruneBadCands[child]; RETURN} ELSE IF seen.AddA[child] THEN { ri: REF INT ~ NARROW[step]; size _ size + 1; bounds _ bounds.MBI[[ri^, ri^]]; IF NOT cand THEN ERROR; RETURN} ELSE { badBranchSeen _ TRUE; RETURN}; }; IF ddec#NIL THEN ddec^.EnumAA[PerPair]; IF NOT cand THEN RETURN; IF badBranchSeen OR NOT (parent#dag.rootNode AND bounds.min IN [0 .. 1] AND bounds.Length.EN=size AND size>1) THEN PruneCand[toDo, parent]; RETURN}; RootDownToDelete: PROC [seqStep: NameStep] RETURNS [ur: StepTriple] ~ { ur _ [subroot, seqStep, GetDown[dag, subroot, seqStep, FALSE]]; IF ur.child=NIL THEN ERROR}; MovePath: PROC [from, to: StepNode, DownToDelete: PROC [seqStep: NameStep] RETURNS [ur: StepTriple]] ~ { ddec: Decomp ~ GetDecomp[toDo, from, FALSE]; fromIsCand: BOOL ~ toDo.cands.HasMemA[from]; MoveDec: PROC [step: NameStep, childa: REF ANY] ~ { child: StepNode ~ NARROW[childa]; leaf1: BOOL ~ dag.toThing.HasMapA[child] OR dag.cands.HasMemA[child]; leaf2: BOOL ~ NOT toDo.down.HasMapA[child]; IF leaf1#leaf2 OR leaf1#fromIsCand THEN ERROR; IF leaf1 THEN { ur: StepTriple ~ DownToDelete[step]; IF ur.child#child THEN ERROR; RemoveLink[dag, ur.parent, ur.step, ur.child, do]; AddLink[dag, to, step, child]; IF checkB THEN VerifyDAG[dag]; RETURN} ELSE { SubDownToDelete: PROC [seqStep: NameStep] RETURNS [ur: StepTriple] ~ { urParent: StepNode ~ DownToDelete[seqStep].ur.child; urKid: StepNode ~ GetDown[dag, urParent, step, FALSE]; IF urKid=NIL THEN ERROR; RETURN [[urParent, step, urKid]]}; fake: StepNode ~ GetDown[dag, to, step, TRUE]; MovePath[child, fake, SubDownToDelete]; RETURN}; }; IF fromIsCand THEN IF NOT dag.cands.AddA[to] THEN ERROR; ddec^.EnumAA[MoveDec]; RETURN}; IF NOT dag.prefixd THEN ERROR--needed to compute leaf1 in MoveDec--; dec^.EnumAA[FindPaths]; PruneBadCands[subroot]; IF NOT toDo.down.Empty THEN { IF checkB THEN VerifyDAG[dag]; MovePath[subroot, subroot, RootDownToDelete]; IF checkA AND NOT checkB THEN VerifyDAG[dag]; }; RETURN}}; PWSetSize: PROC [d: Design, set: Set--of PW--] RETURNS [size: LNAT--number of leaves-- _ 0] ~ { AddSize: PROC [val: REF ANY] ~ {size _ size + PWSize[d, val]}; set.EnumA[AddSize]; RETURN}; PWSize: PROC [d: Design, x: PW] RETURNS [size: LNAT--number of leaves-- _ 1] ~ { kids: Seq ~ BiRels.DeRef[d.sub.ApplyA[x].MDA]; IF kids#nilBiRel THEN FOR i: INT IN [0 .. kids.Size.EN) DO child: PW ~ kids.ApplyI[i].MA; size _ size + PWSize[d, child]; x _ x; ENDLOOP; RETURN}; FixSteppyName: PROC [old: SteppyName] RETURNS [SteppyName] ~ { copied: BOOL _ FALSE; copy: TList _ []; IF skipFix THEN RETURN [old]; FOR cur: NameStepList _ old.steps, cur.rest WHILE cur#NIL DO {WITH cur.first SELECT FROM x: ROPE => {dotPos: INT ~ x.FindBackward["."]; IF dotPos<0 THEN GOTO Not; {sepPos: INT ~ x.Index[s2: "_", pos1: dotPos]; FOR i: INT IN (dotPos .. sepPos) DO IF x.InlineFetch[i] NOT IN ['0 .. '9] THEN GOTO Not; ENDLOOP; IF NOT copied THEN {copy _ CopyTil[[old.steps, cur]]; copied _ TRUE}; copy _ copy.Append[x.Substr[len: dotPos].Concat[x.Substr[start: sepPos]]].Append[NEW [INT _ Convert.IntFromRope[x.Substr[start: dotPos+1, len: sepPos - dotPos - 1]]]]; }}; x: REF INT => GOTO Not; ENDCASE => ERROR; EXITS Not => IF copied THEN copy _ copy.Append[cur.first]; }ENDLOOP; RETURN [IF copied THEN LSn[copy.head] ELSE old]}; skipFix: BOOL _ FALSE; Start: PROC ~ { [] _ portTimes.Show[viewerInit: [name: "Deduce port structure size * time"], base: 2, updatePeriod: 5]; [] _ wireTimes.Show[viewerInit: [name: "Deduce wire structure size * time"], base: 2, updatePeriod: 5]; RETURN}; Start[]; END. bLichenStructureDeduction.Mesa Last tweaked by Mike Spreitzer on May 6, 1988 10:43:15 am PDT ÊÔ˜™Icodešœ=™=—J˜KšÏk œHœ[˜®K˜šÏnœœ˜'KšœHœZ˜«Kšœ˜Kšœ˜—K˜Kšœœ%žœ œ˜[K˜Kšœœ˜%Kšœ œ ˜Kšœxœœ˜ŠKšœxœœ˜ŠK˜Kšžœœœ˜Kšœ œœ˜Kšœ˜Kšœœœ˜Kšœœœ˜Kšœœœ˜Kšœ œœ˜K˜š žœœœœœœ˜VKšœœ˜ šž œœœœ˜$Kšœœ˜Kšœ ˜ K˜Kšœ œœ#œ˜AKš œœœsœœ9˜×Kšœ)˜)Kšœœœ*˜K˜Kšœ˜—K˜š žœœœœŸœ ˜PKšœ)œ˜.š œœœœœœ˜:Kšœœœ˜Kšœ˜Kšœœ˜—Kšœ˜—K˜šž œœœ˜>Kšœœœ˜K˜Kšœ œœ˜šœ)œœ˜<šœœ œ˜šœœ œ˜.Kšœ œœ˜Kšœ œ"˜.šœœœ˜#Kš œœœ œœ˜4Kšœ˜—Kšœœœ-œ˜EKšœQœœN˜§K˜—Kšœœœœ˜Kšœœ˜—Kšœœœ˜:Kšœœ˜ —Kšœœœœ˜1Kšœ œœ˜—K˜šžœœ˜Kšœg˜gKšœg˜gKšœ˜—K˜K˜K˜Kšœ˜—…—4®Eä