[Cyan]<DATools7.0>Lichen2>LichenStructureDeduction.Mesa!1

LichenStructureDeduction.Mesa

Last tweaked by Mike Spreitzer on May 6, 1988 10:43:15 am PDT

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 b 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 b 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.