LichenChildishTransforms:
CEDAR
PROGRAM
IMPORTS LichenDataOps, LichenDataStructure, LichenSetTheory
EXPORTS LichenTransforms =
BEGIN OPEN LichenDataStructure, LichenTransforms, LichenDataOps, LichenSetTheory;
opCount: INT ← 0;
Analysis: TYPE = REF AnalysisPrivate;
AnalysisPrivate:
TYPE =
RECORD [
roles: NAT,
gcTypes: RefSeq--role b CellType--,
wag: WireAnswering,
doomedPorts: Set ← CreateHashSet[],
losses, gains: NAT ← 0
];
WireAnswering: TYPE = REF WireAnsweringPrivate;
WireAnsweringPrivate:
TYPE =
RECORD [
oldGCConnectionss: RefSeq--role b RefTable(gc port b wire connected to that port of sibling of first instance)--,
anses: Mapper--wire b WireAns--,
key: REF ANY];
WireAns:
TYPE =
REF WireAnsPrivate;
Data for the wire connected to a port of a grandchild.
WireAnsPrivate:
TYPE =
RECORD [
proto: Wire,
key: REF ANY,
analyzed: BOOL ← FALSE,
sawSelves: BoolSeq,
childPort: Port ← NIL,
gcPorts: PortList ← NIL,
sawBord:
BOOL ←
FALSE,
Connected to the child at least once
sawBords:
BOOL ←
FALSE,
Connected to the child by more than one port.
sawElse:
BOOL ←
FALSE,
Connected to something other than the child & grandchildren.
child: CellInstance ← NIL,
counterpart: Wire ← NIL
];
LowerChildren:
PUBLIC
PROC [design: Design, childType: CellType, sibber: Mapper
--child
b RefSeq of (sibling: Vertex)--]
RETURNS [gcs: RefSeq
--role
b grandchild--, children: Set
--of Vertex--] =
BEGIN
analysis: Analysis =
NEW [AnalysisPrivate ← [
roles: LAST[NAT],
wag:
NEW [WireAnsweringPrivate ← [
anses: CreateHashMapper[],
key: NEW [INT ← opCount ← opCount + 1]]]
]];
{OPEN analysis;
first: BOOL ← TRUE;
dif: BOOL ← FALSE;
oldPort: Port = childType.port;
newPort: Port;
parentTypes: Set = CreateHashSet[];
children ← CreateHashSet[];
{
SeeInstance:
PROC [child: CellInstance] = {
sibs: RefSeq--role b sibling-- = NARROW[sibber.Map[child]];
IF IsMirror[child] THEN ERROR; --AM2
IF first
THEN {
wag.oldGCConnectionss ← CreateRefSeq[sibs.length];
gcTypes ← CreateRefSeq[sibs.length];
FOR role:
NAT
IN [0 .. sibs.length)
DO
sib: CellInstance = NARROW[sibs[role]];
gcTypes[role] ← sib.type;
ENDLOOP;
};
IF Survey[child.containingCT, child, sibs, analysis, first] THEN dif ← TRUE;
first ← FALSE;
};
EnumerateInstances[childType, SeeInstance];
};
IF first OR dif THEN RETURN [NIL, NIL];
NoteChange[childType];
gcs ← CreateRefSeq[gcTypes.length];
FOR role:
NAT
IN [0 .. gcs.length)
DO
gcs[role] ← Instantiate[
type: NARROW[gcTypes[role]],
containingCT: childType];
ENDLOOP;
newPort ← oldPort;
{
MaybeDeleteOldChildPort:
PROC [cPort: Port, w: Vertex, e: Edge] = {
wire: Wire = NARROW[w];
IF doomedPorts.HasMember[cPort] THEN RemoveEdges[e];
};
EnumerateTopEdges[childType.asUnorganized.mirror, MaybeDeleteOldChildPort]};
FOR role:
NAT
IN [0 .. gcs.length)
DO
PerTopWire:
PROC [domain, range:
REF
ANY] = {
outerWire: Wire = NARROW[domain];
wa: WireAns = NARROW[range];
NewPort:
PROC
RETURNS [insideNet: Wire] = {
SELECT wa.counterpart
FROM
addPort => {
wa.counterpart ← insideNet ← CreateWire[containingCT: childType, copy: outerWire];
wa.childPort ← AddPort[[parent: newPort, wire: insideNet]];
AddEdge[[childType.asUnorganized.mirror, insideNet], wa.childPort];
};
dePort => ERROR;
# NIL => insideNet ← wa.counterpart;
ENDCASE => ERROR;
};
MakeDummy:
PROC
RETURNS [insideNet: Wire] = {
IF wa.counterpart # NIL THEN RETURN [wa.counterpart];
wa.counterpart ← insideNet ← CreateWire[containingCT: childType, copy: outerWire];
};
innerWire: Wire = IF wa.sawBord THEN wa.childPort.wire ELSE IF wa.sawElse THEN NewPort[] ELSE MakeDummy[];
FOR gcPorts: PortList ← wa.gcPorts, gcPorts.rest
WHILE gcPorts #
NIL
DO
AddEdges[[NARROW[gcs[role]], innerWire], gcPorts.first];
ENDLOOP;
};
wag.anses.EnumerateMapping[PerTopWire];
ENDLOOP;
CheckCellType[ct: childType, rep: ignore, norm: check, comparable: ignore, instances: FALSE];
{
TweakInstance:
PROC [child: CellInstance] = {
sibs: RefSeq--role b sibling--;
IF IsMirror[child] THEN ERROR; --AM2
[] ← UnionSingleton[children, child];
sibs ← NARROW[sibber.Map[child]];
IF sibs.length # gcs.length THEN ERROR --caller blew it--;
FOR role:
NAT
IN [0 .. sibs.length)
DO
sib: CellInstance = NARROW[sibs[role]];
PerEdge:
PROC [gcPort: Port, net: Vertex, e: Edge] = {
wa: WireAns = GetRPAns[wag, role, gcPort];
IF wa.sawElse
AND
NOT wa.sawBord
THEN {
IF wa.child # child
THEN {
AddEdges[[child, NARROW[net]], wa.childPort];
wa.child ← child};
};
IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[net] ELSE RemoveEdges[e];
};
IF sib.containingCT # child.containingCT THEN ERROR --caller blew it--;
EnumerateTopEdges[sib, PerEdge];
DeleteVertex[sib];
ENDLOOP;
NoteChange[child.containingCT];
[] ← parentTypes.UnionSingleton[child.containingCT];
};
EnumerateInstances[childType, TweakInstance]};
CheckCellTypes[parentTypes, ignore, check, ignore];
parentTypes.DestroySet[];
}END;
RaiseGrandchildren:
PUBLIC
PROC [design: Design, gcs: Set
--of Vertex--]
RETURNS [childType: CellType, sibber: Mapper
--child
b RefSeq (role
b sibling: Vertex)--] =
BEGIN
analysis: Analysis =
NEW [AnalysisPrivate ← [
roles: gcs.Size[],
gcTypes: CreateRefSeq[gcs.Size[]],
wag:
NEW [WireAnsweringPrivate ← [
oldGCConnectionss: CreateRefSeq[gcs.Size[]],
anses: CreateHashMapper[],
key: NEW [INT ← opCount ← opCount + 1]]]
]];
{OPEN analysis;
gcSeq: RefSeq--role b grandchild-- = CreateRefSeq[roles];
oldPort, newPort: Port;
addedPorts: Set = CreateHashSet[];
parentTypes: Set = CreateHashSet[];
{role: NAT ← 0;
AssignRole:
PROC [elt:
REF
ANY] = {
gc: CellInstance = NARROW[elt];
gcSeq[role] ← gc;
IF role = 0 THEN childType ← gc.containingCT;
IF gc.containingCT # childType THEN ERROR;
role ← role + 1};
gcs.Enumerate[AssignRole];
IF role # roles THEN ERROR};
oldPort ← newPort ← childType.port;
sibber ← CreateHashMapper[];
IF Survey[childType, NIL, gcSeq, analysis, TRUE] THEN ERROR;
{
DeleteDoomed:
PROC [elt:
REF
ANY] = {
RemovePort[NARROW[elt]];
};
doomedPorts.Enumerate[DeleteDoomed];
};
FOR role:
NAT
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcSeq[role]];
PerEdge:
PROC [gcPort: Port, wire: Wire] = {
wa: WireAns = GetRPAns[wag, role, gcPort, wire, FALSE];
IF NOT wa.analyzed THEN ERROR;
IF wa.sawElse
AND
NOT wa.sawBord
THEN {
SELECT wa.counterpart
FROM
addPort => {
wa.childPort ← AddPort[[parent: newPort, wire: wire]];
[] ← UnionSingleton[addedPorts, wa.childPort];
AddEdge[[childType.asUnorganized.mirror, wire], wa.childPort];
wa.counterpart ← addedPort};
addedPort => NULL;
ENDCASE => ERROR;
};
};
EnumerateTopConnections[gc, PerEdge];
ENDLOOP;
NoteChange[childType];
FOR role:
NAT
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcSeq[role]];
PerEdge:
PROC [gcPort: Port, wire: Wire, e: Edge] = {
wa: WireAns = GetRPAns[wag, role, gcPort, wire, FALSE];
IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[wire] ELSE RemoveEdge[e];
};
EnumerateTopEdges[gc, PerEdge];
DeleteVertex[gc];
ENDLOOP;
CheckCellType[ct: childType, rep: ignore, norm: check, comparable: ignore, instances: FALSE];
{
FixInstance:
PROC [child: CellInstance] = {
sibs: RefSeq = CreateRefSeq[roles];
cons: RefTable--child port b wire-- = CreateRefTable[];
IF IsMirror[child] THEN ERROR; --AM2
[] ← SetMapping[sibber, child, sibs];
FOR role:
NAT
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcSeq[role]];
sibs[role] ← Instantiate[gc.type, child.containingCT];
ENDLOOP;
{
PerConnection:
PROC [cPort: Port, net: Vertex, ce: Edge] = {
[] ← cons.Store[cPort, net];
IF doomedPorts.HasMember[cPort] THEN RemoveEdges[ce];
};
EnumerateTopEdges[child, PerConnection]};
{
LinkToNewPort:
PROC [elt:
REF
ANY] = {
cPort: Port = NARROW[elt];
outerNet: Wire = CreateWire[containingCT: child.containingCT, copy: ERROR nyet];
AddEdges[[child, outerNet], cPort];
[] ← cons.Store[cPort, outerNet];
};
addedPorts.Enumerate[LinkToNewPort]};
FOR role:
NAT
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs[role]];
PerPort:
PROC [gcPort: Port] = {
wa: WireAns = GetRPAns[wag, role, gcPort];
MakeDummyNet:
PROC [iNet: Wire]
RETURNS [oNet: Wire] = {
oNet ← wa.counterpart;
IF oNet =
NIL
OR wa.child # child
THEN {
oNet ← CreateWire[containingCT: child.containingCT, copy: iNet];
wa.counterpart ← oNet;
wa.child ← child;
};
};
AddEdge[
[sib,
IF wa.sawBord
OR wa.sawElse
THEN NARROW[cons.Fetch[wa.childPort].value]
ELSE MakeDummyNet[wa.proto]],
gcPort];
};
EnumeratePorts[sib.type, PerPort];
ENDLOOP;
NoteChange[child.containingCT];
[] ← parentTypes.UnionSingleton[child.containingCT];
};
EnumerateInstances[childType, FixInstance]};
CheckCellTypes[parentTypes, ignore, check, ignore];
parentTypes.DestroySet[];
}END;
Survey:
PROC [parent: CellType, child: Vertex, sibs: RefSeq
--role
b grandchild--, analysis: Analysis, first:
BOOL]
RETURNS [dif:
BOOL ←
FALSE] = {
OPEN analysis;
lwag: WireAnswering = NEW [WireAnsweringPrivate ← [CreateRefSeq[roles], CreateHashMapper[], wag.key]];
IF sibs.length # gcTypes.length
THEN {
Warning["Different number of siblings (%g, rather than %g) at %g", Int[sibs.length], Int[gcTypes.length], child];
dif ← TRUE}
ELSE
FOR role:
NAT
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs[role]];
SeeConnection:
PROC [gcPort: Port, wire: Wire] = {
lwa: WireAns = GetRPAns[lwag, role, gcPort, wire, TRUE];
wa: WireAns = GetRPAns[wag, role, gcPort, wire, first];
SeeBackConnection:
PROC [cPort: Port, v: Vertex] = {
ci: CellInstance = NARROW[v];
bord: BOOL = IF child # NIL THEN ci=child ELSE IsMirror[ci];
IF bord
THEN {
lwa.sawBords ← lwa.sawBord;
lwa.sawBord ← TRUE;
lwa.childPort ← cPort;
}
ELSE {sawSomeSelf:
BOOL ←
FALSE;
FOR j:
NAT
IN [0 .. roles)
DO
IF ci = sibs[j] THEN sawSomeSelf ← lwa.sawSelves[j] ← TRUE;
ENDLOOP;
IF NOT sawSomeSelf THEN lwa.sawElse ← TRUE;
};
};
IF first
THEN {
lwa.gcPorts ← CONS[gcPort, lwa.gcPorts];
};
IF
NOT lwa.analyzed
THEN {
lwa.analyzed ← TRUE;
lwa.sawSelves ← CreateBoolSeq[roles, FALSE];
EnumerateTransitiveConnections[wire, SeeBackConnection];
IF NOT lwa.sawSelves[role] THEN ERROR;
IF first
THEN {
wa^ ← lwa^;
IF wa.sawBord
AND
NOT (wa.sawElse
OR wa.sawBords)
THEN {
losses ← NoteLoss[wa, losses];
IF NOT doomedPorts.UnionSingleton[wa.childPort] THEN ERROR;
};
IF wa.sawElse AND NOT wa.sawBord THEN gains ← NoteGain[wa, gains];
}
ELSE {
Dif: PROC = {Warning["%g & %g are connected differently than the first pair", child, sib]; dif ← TRUE};
IF wa.sawBord # lwa.sawBord THEN Dif[];
IF wa.sawBords # lwa.sawBords THEN Dif[];
IF wa.sawElse # lwa.sawElse THEN Dif[];
FOR j:
NAT
IN [0 .. sibs.length)
DO
IF wa.sawSelves[j] # lwa.sawSelves[j] THEN Dif[];
ENDLOOP}};
};
IF sib.type # gcTypes[role]
THEN {
Warning["%g is a %g, not a %g", sib, sib.type, gcTypes[role]];
dif ← TRUE}
ELSE
IF sib = child
THEN {
Warning["Child %g sibbed to itself", child];
dif ← TRUE}
ELSE IF sib.containingCT # parent THEN ERROR
ELSE {
EnumerateTopConnections[sib, SeeConnection];
};
ENDLOOP;
};
dePort: Wire = NEW [wire VertexPrivate];
addPort: Wire = NEW [wire VertexPrivate];
addedPort: Wire = NEW [wire VertexPrivate];
GetRPAns:
PROC [wag: WireAnswering, role:
NAT, gcPort: Port, wire: Wire ←
NIL, mayChange:
BOOL ←
FALSE]
RETURNS [wa: WireAns] = {
kw: Wire;
rt: RefTable ← NARROW[wag.oldGCConnectionss[role]];
IF rt =
NIL
THEN {
IF NOT mayChange THEN ERROR;
wag.oldGCConnectionss[role] ← rt ← CreateRefTable[];
};
IF wire =
NIL
THEN {
wire ← NARROW[rt.Fetch[gcPort].value];
IF wire = NIL THEN ERROR;
};
kw ← NARROW[rt.Fetch[gcPort].value];
IF kw =
NIL
THEN {
IF NOT mayChange THEN ERROR;
IF NOT rt.Insert[gcPort, kw ← wire] THEN ERROR};
IF wire # kw THEN ERROR;
wa ← NARROW[wag.anses.Map[wire]];
IF wa =
NIL
OR wa.key # wag.key
THEN {
IF NOT mayChange THEN ERROR;
wa ← NEW [WireAnsPrivate ← [proto: wire, key: wag.key]];
IF wag.anses.SetMapping[wire, wa].hadMapping THEN ERROR;
};
};
NoteLoss:
PROC [wa: WireAns, oldLosses:
CARDINAL]
RETURNS [newLosses:
CARDINAL] = {
newLosses ← oldLosses;
SELECT wa.counterpart
FROM
NIL => {newLosses ← newLosses + 1; wa.counterpart ← dePort};
dePort => NULL;
addPort => ERROR;
ENDCASE => ERROR;
};
NoteGain:
PROC [wa: WireAns, oldGains:
CARDINAL]
RETURNS [newGains:
CARDINAL] = {
newGains ← oldGains;
SELECT wa.counterpart
FROM
NIL => {newGains ← newGains + 1; wa.counterpart ← addPort};
addPort => NULL;
dePort => ERROR;
ENDCASE => ERROR;
};
Int: PROC [i: INT] RETURNS [ra: REF ANY] = {ra ← NEW [INT ← i]};
END.