LichenArrayImpl.Mesa
Mike Spreitzer January 14, 1987 10:36:44 pm PST
DIRECTORY Basics, Convert, GList, HashTable, IntChainedHashTable, InterpreterOps, IntHashTable, IO, LichenDataOps, LichenDataStructure, LichenSetTheory, Rope;
LichenArrayImpl: CEDAR MONITOR
IMPORTS Basics, GList, HashTable, IntChainedHashTable, IntHashTable, LichenDataOps, LichenDataStructure, LichenSetTheory
EXPORTS LichenDataStructure, LichenDataOps
INVARIANT
tie.completion is redundant with the information in the rpd.links.
tie.completion = NIL iff tie.completion.nIncomplete = 0.
a RoledPortData has links iff needed or array is being created.
=
BEGIN OPEN ICHT: IntChainedHashTable, LichenSetTheory, LichenDataStructure, LichenDataOps;
GIPair: TYPE = ARRAY End OF NAT;
PackedArrayIndex: PUBLIC TYPE = INT;
PackArrayIndex: PUBLIC PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
= {RETURN [PackArrayIndexI[ai]]};
PackArrayIndexI: PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
= INLINE {RETURN [LOOPHOLE[Nat2[ai[Foo], ai[Bar]]]]};
UnpackArrayIndex: PUBLIC PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
= {RETURN [UnpackArrayIndexI[pai]]};
UnpackArrayIndexI: PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
= INLINE {RETURN [[LOOPHOLE[pai, Nat2][Foo], LOOPHOLE[pai, Nat2][Bar]]]};
Central: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [BOOL] = {
RETURN [
ai[Foo] > 0 AND ai[Foo]+1 < a.size[Foo] AND
ai[Bar] > 0 AND ai[Bar]+1 < a.size[Bar]];
};
ComputeGroupingsIndex: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [gi2, gii2: Nat2, gi, cgii: NAT] = {
ngii: Nat2 ← [1, 1];
Gi1D: PROC [d: Dim] = {
i: INT = ai[d];
SELECT TRUE FROM
i < a.groupingParmses[d].middle.min => gi2[d] ← i;
i >= a.groupingParmses[d].middle.maxPlusOne => gi2[d] ← i + a.groupingParmses[d].d;
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = i MOD t;
jiir: Range = Range1Div[a.groupingParmses[d].middle, t, f];
gi2[d] ← a.groupingParmses[d].middle.min + f;
gii2[d] ← i/a.jointsPeriod[d] - jiir.min;
ngii[d] ← RangeLength[jiir];
}};
gii2 ← [0, 0];
Gi1D[Foo]; Gi1D[Bar];
gi ← a.groupingParmses[Bar].sum * gi2[Foo] + gi2[Bar];
cgii ← ngii[Bar] * gii2[Foo] + gii2[Bar]};
ComputeJointGroupingsIndex: PUBLIC PROC [a: Array, j: Joint, jii: Nat2] RETURNS [jgi2: Nat2, jgi, ctii: NAT, jiir: Range2] = {
njgii: Nat2 ← [1, 1];
jgii2: Nat2 ← [0, 0];
Gi1D: PROC [d: Dim] = {
i: NAT = jii[d];
jiir[d] ← [min: i, maxPlusOne: i+1];
SELECT TRUE FROM
i < j.groupingParmses[d].middle.min => jgi2[d] ← i;
i >= j.groupingParmses[d].middle.maxPlusOne => jgi2[d] ← i + j.groupingParmses[d].d;
ENDCASE => {
jgi2[d] ← j.groupingParmses[d].middle.min;
jiir[d] ← j.groupingParmses[d].middle;
jgii2[d] ← i - jgi2[d];
njgii[d] ← RangeLength[jiir[d]];
}};
Gi1D[Foo]; Gi1D[Bar];
jgi ← j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar];
ctii ← njgii[Bar] * jgii2[Foo] + jgii2[Bar]};
AddTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, g: Group, to: GroupList] RETURNS [tied: GroupList] = {
IF g = NIL THEN RETURN [to];
IF FetchTie[j, side, jgi, g] # NIL THEN RETURN [CONS[g, to]];
IF g.stopLooking[d][side] THEN RETURN [to];
tied ← to;
FOR worse: GroupList ← g.worse, worse.rest WHILE worse # NIL DO
tied ← AddTiedGroups[d, j, side, jgi, worse.first, tied];
ENDLOOP;
tied ← tied;
};
AddListTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, gs, to: GroupList] RETURNS [tied: GroupList] = {
tied ← NIL;
FOR gs ← gs, gs.rest WHILE gs # NIL DO
tied ← AddTiedGroups[d, j, side, jgi, gs.first, tied];
ENDLOOP;
tied ← tied;
};
ArrayWireForGroup: PUBLIC PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, mayAdd: BOOL] RETURNS [aw: ArrayWire] = {
pai: PackedArrayIndex = PackArrayIndexI[index];
last: IntTable --PackedArrayIndex b ArrayWire-- = NARROW[a.toWire.Fetch[g].value];
IF last # NIL THEN {
aw ← NARROW[last.Fetch[pai].value];
IF aw # NIL THEN RETURN;
};
IF NOT mayAdd THEN RETURN [NIL];
aw ← NEW [ArrayWirePrivate ← [
elts: CreateHashSet[EqualArrayWireElement, HashArrayWireElement],
ports: CreateHashSet[]
]];
IF NOT a.wires.UnionSingleton[aw] THEN ERROR;
AddEltToArrayWire[a, aw, NEW [ArrayWireElementPrivate ← [index, g]]];
};
AddEltToArrayWire: PROC [a: Array, aw: ArrayWire, elt: ArrayWireElement] = {
AddElt: PROC [elt: ArrayWireElement] = {
last: IntTable --PackedArrayIndex b ArrayWire-- ← NARROW[a.toWire.Fetch[elt.group].value];
pai: PackedArrayIndex = PackArrayIndexI[elt.ai];
stack ← CONS[elt, stack];
IF last = NIL AND NOT a.toWire.Insert[elt.group, last ← CreateIntTable[]] THEN ERROR;
IF NOT last.Insert[pai, aw] THEN ERROR;
IF NOT aw.elts.UnionSingleton[elt] THEN ERROR;
};
NoteConnection: PROC [ain: ArrayIndex, gn: Group] = {
neighbor: ArrayWireElement = NEW [ArrayWireElementPrivate ← [ain, gn]];
IF aw.elts.HasMember[neighbor] THEN RETURN;
AddElt[neighbor];
};
stack: LIST OF ArrayWireElement ← NIL;
AddElt[elt];
WHILE stack # NIL DO
elt: ArrayWireElement = stack.first;
gi: NAT = ComputeGroupingsIndex[a, elt.ai].gi;
stack ← stack.rest;
EnumerateLocalConnections[a, elt.ai, gi, elt.group, NoteConnection];
stack ← stack;
ENDLOOP;
stack ← stack;
};
JoinArrayWires: PROC [a: Array, aw1, aw2: ArrayWire] ~ {
MoveElt: PROC [ra: REF ANY] ~ {
elt: ArrayWireElement ~ NARROW[ra];
last: IntTable --PackedArrayIndex b ArrayWire-- ~ NARROW[a.toWire.Fetch[elt.group].value];
pai: PackedArrayIndex = PackArrayIndexI[elt.ai];
IF NOT aw1.elts.UnionSingleton[elt] THEN ERROR;
IF last = NIL THEN ERROR;
IF NOT last.Replace[pai, aw1] THEN ERROR;
};
MovePort: PROC [ra: REF ANY] ~ {
ap: Port ~ NARROW[ra];
IF NOT aw1.ports.UnionSingleton[ap] THEN ERROR;
IF NOT a.portWire.Replace[ap, aw1] THEN ERROR;
};
aw2.elts.Enumerate[MoveElt];
aw2.ports.Enumerate[MovePort];
a.wires.RemoveElt[aw2];
};
EnumerateLocalConnections: PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, Consume: PROC [ain: ArrayIndex, gn: Group]] = {
FOR d: Dim IN Dim DO FOR side: End IN End DO
otherSide: End = OtherEnd[side];
lai: ArrayIndex = Int2Tweak[index, d, SELECT side FROM low => 0, high => -1, ENDCASE => ERROR];
hai: ArrayIndex = Int2Tweak[lai, d, 1];
IF lai[d] < 0 OR hai[d] >= a.size[d] THEN LOOP;
{jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
IF tie = NIL THEN LOOP;
IF tie.groups[side] # g THEN ERROR;
IF tie.groups[otherSide] # NIL THEN Consume[SELECT side FROM low => hai, high => lai, ENDCASE => ERROR, tie.groups[otherSide]];
}ENDLOOP ENDLOOP;
a ← a;
};
EqualArrayWireElement: PROC [k1, k2: REF ANY] RETURNS [BOOL] --HashTable.EqualProc-- ~ {
awe1: ArrayWireElement ~ NARROW[k1];
awe2: ArrayWireElement ~ NARROW[k2];
RETURN [awe1^ = awe2^];
};
HashArrayWireElement: PROC [k: REF ANY] RETURNS [CARDINAL] --HashTable.HashProc-- ~ {
awe: ArrayWireElement ~ NARROW[k];
aif: Basics.LongNumber = [lc[awe.ai[Foo] * 17701]];
aib: CARDINAL = awe.ai[Bar];
g: Basics.LongNumber = [lp[LOOPHOLE[awe.group]]];
RETURN [aib + aif.lo + aif.hi + g.lo + g.hi];
};
EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] = {
FOR act: CellType ← cellType.firstArray, act.asArray.nextArray WHILE act # NIL DO
Consume[act];
ENDLOOP;
};
Jgi2ToGi: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, side: End] RETURNS [gi2: Nat2, gi: NAT] = {
Do1: PROC [d: Dim] RETURNS [ji: NAT] = {
SELECT TRUE FROM
jgi2[d] < j.groupingParmses[d].middle.min => RETURN [jgi2[d]];
jgi2[d] >= j.groupingParmses[d].firstHigh => RETURN [jgi2[d]-j.groupingParmses[d].d];
ENDCASE => RETURN [j.groupingParmses[d].middle.min];
};
ji2: Int2 = [Foo: Do1[Foo], Bar: Do1[Bar]];
lai: ArrayIndex = [
Foo: phase[Foo] + a.jointsPeriod[Foo] * ji2[Foo],
Bar: phase[Bar] + a.jointsPeriod[Bar] * ji2[Bar]];
[gi2: gi2, gi: gi] ← ComputeGroupingsIndex[a, IF side = low THEN lai ELSE Int2Tweak[lai, d, 1]];
};
Jgi2ToGip: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2] RETURNS [gip: GIPair] = {
gip ← [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
};
AgiToAi: PROC [a: Array, gi2, gii2: Nat2] RETURNS [ai: ArrayIndex] = {
Do: PROC [d: Dim] RETURNS [INT] = {
SELECT TRUE FROM
gi2[d] < a.groupingParmses[d].middle.min => RETURN [gi2[d]];
gi2[d] >= a.groupingParmses[d].firstHigh => RETURN [gi2[d] - a.groupingParmses[d].d];
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = gi2[d] - a.groupingParmses[d].middle.min;
min: NAT = CeilDiv[MAX[a.groupingParmses[d].middle.min, f] - f, t];
RETURN [(gii2[d] + min) * t + f];
};
};
ai[Foo] ← Do[Foo];
ai[Bar] ← Do[Bar];
};
JGRListize: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, lowRange: Range2] RETURNS [jgrl: JGRList] = {
jiir: Range2 = Range2Div[lowRange, a.jointsPeriod, phase];
Enum: PROC [de: Dim, Per: PROC [NAT, NAT, NAT, NAT, NAT, INT, INT, Range, Range]] = {
D: INT = IF de = d THEN 1 ELSE 0;
fh: NAT = ((phase[de]+D) MOD a.jointsPeriod[de]);
giml: NAT = a.groupingParmses[de].middle.min + phase[de];
gimh: NAT = a.groupingParmses[de].middle.min + fh;
jirm: ARRAY End OF Range = [
low: Range1Div[a.groupingParmses[de].middle, a.jointsPeriod[de], phase[de]],
high: Range1Div[RangeOff[a.groupingParmses[de].middle, -D], a.jointsPeriod[de], phase[de]]];
nm: ARRAY End OF NAT = [low: RangeLength[jirm[low]], high: RangeLength[jirm[high]]];
gijl: NAT ← jiir[de].min;
gial: NAT ← gijl * a.jointsPeriod[de] + phase[de];
ji: NAT ← jiir[de].maxPlusOne-1;
ai: NAT ← ji * a.jointsPeriod[de] + phase[de] + D;
giah: INT ← ai + a.groupingParmses[de].d;
gijh: INT ← ji + j.groupingParmses[de].d;
lowLimit: NAT = MIN[j.groupingParmses[de].middle.min, jiir[de].maxPlusOne];
highLimit: NAT = MAX[j.groupingParmses[de].middle.maxPlusOne, jiir[de].min];
FOR gijl ← gijl, gijl+1 WHILE gijl < lowLimit DO
this: Range = [min: gijl, maxPlusOne: gijl+1];
nh: NAT ← 1;
giah: INT ← gial + D;
IF D=1 AND gial=a.groupingParmses[de].middle.min-1
THEN {giah ← gimh; nh ← nm[high]};
Per[gial, giah, gijl, 1, nh, gijl, gijl, this, this];
gial ← gial + a.jointsPeriod[de];
ENDLOOP;
FOR ji ← ji, ji-1 WHILE ji >= highLimit DO
this: Range = [min: ji, maxPlusOne: ji + 1];
nl: NAT ← 1;
jii0al: INT ← ji;
gial: INT ← giah - D;
IF D=1 AND giah=a.groupingParmses[de].firstHigh
THEN {gial ← giml; nl ← nm[low]; jii0al ← jirm[low].min};
Per[gial, giah, gijh, nl, 1, jii0al, ji, this, this];
giah ← giah - a.jointsPeriod[de];
gijh ← gijh - 1;
ENDLOOP;
IF RangesIntersect[jiir[de], j.groupingParmses[de].middle] THEN {
mjir: Range = [
min: MAX[j.groupingParmses[de].middle.min, jiir[de].min],
maxPlusOne: MIN[j.groupingParmses[de].middle.maxPlusOne, jiir[de].maxPlusOne]];
Per[
giml,
gimh,
j.groupingParmses[de].middle.min,
nm[low],
nm[high],
jirm[low].min,
jirm[high].min,
mjir,
j.groupingParmses[de].middle
];
};
};
PerFoo: PROC [gialf, giahf, gijf, ngiilf, ngiihf: NAT, jii0alf, jii0ahf: INT, jirf, fullJiirf: Range] = {
cf: BOOL = jirf = fullJiirf;
PerBar: PROC [gialb, giahb, gijb, ngiilb, ngiihb: NAT, jii0alb, jii0ahb: INT, jirb, fullJiirb: Range] = {
cb: BOOL = jirb = fullJiirb;
jgrl ← CONS[
[
gis: [
low: a.groupingParmses[Bar].sum * gialf + gialb,
high: a.groupingParmses[Bar].sum * giahf + giahb],
ngii: [low: [ngiilf, ngiilb], high: [ngiihf, ngiihb]],
firstJIIOfGI: [low: [jii0alf, jii0alb], high: [jii0ahf, jii0ahb]],
jgi2: [Foo: gijf, Bar: gijb],
jgi: j.groupingParmses[Bar].sum * gijf + gijb,
jiir: [Foo: jirf, Bar: jirb],
fullJiir: [Foo: fullJiirf, Bar: fullJiirb],
complete: cf AND cb
],
jgrl];
};
Enum[Bar, PerBar];
};
jgrl ← NIL;
Enum[Foo, PerFoo];
jgrl ← jgrl;
};
JGRList: TYPE = LIST OF READONLY JGR;
JGR: TYPE = RECORD [
gis: ARRAY End OF NAT,
ngii: ARRAY End OF ARRAY Dim OF NAT,
firstJIIOfGI: ARRAY End OF Int2,
jgi2: Nat2,
jgi: NAT,
jiir, fullJiir: Range2,
complete: BOOL
];
ngii[side] is the number of instances of gis[side] in the entire array.
firstJIIOfGI[side] is the jii of the first joint in the entire array that has gis[side] on side; note that this may include imaginary joints along the low sides of the array.
MakeArrayConnection: PUBLIC PROC [ct: CellType, d: Dim, lowRange: Range2, rp1, rp2: RoledPort, may: BOOL] RETURNS [connected: BOOL] = {
o: Dim = OtherDim[d];
a: Array = ct.asArray;
tf: NAT = a.jointsPeriod[Foo];
tb: NAT = a.jointsPeriod[Bar];
IF a = NIL THEN ERROR;
IF lowRange[d].min<0 OR lowRange[d].maxPlusOne>=a.size[d] THEN ERROR;
IF lowRange[o].min<0 OR lowRange[o].maxPlusOne>a.size[o] THEN ERROR;
IF a.jointsPeriod[d] > a.size[d] THEN ERROR;
FOR ff: NAT IN [0 .. tf) DO FOR fb: NAT IN [0 .. tb) DO
phase2: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase2];
jgrl: JGRList ← JGRListize[a, d, phase2, j, lowRange];
FOR jgrl ← jgrl, jgrl.rest WHILE jgrl # NIL DO
jgr: JGR = jgrl.first;
njgiib: NAT = RangeLength[jgr.fullJiir[Bar]];
g1: Group = GetGroup[a, jgr.gis[rp1.side], rp1.port, may];
g2: Group = GetGroup[a, jgr.gis[rp2.side], rp2.port, may];
tie: Tie;
rpd1, rpd2: RoledPortData;
IF g1 = NIL OR g2 = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase2, j, jgr.jgi2, jgr.jgi, jgr.fullJiir, rp1, rp2, g1, g2, jgr.gis[rp1.side], jgr.gis[rp2.side], may];
IF tie = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
IF may AND tie.completion # NIL THEN {
FOR jiif: INT IN [jgr.jiir[Foo].min .. jgr.jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jgr.jiir[Bar].min .. jgr.jiir[Bar].maxPlusOne) DO
lai: ArrayIndex = [
Foo: jiif*a.jointsPeriod[Foo] + ff,
Bar: jiib*a.jointsPeriod[Bar] + fb];
giis: ARRAY End OF NAT = [
low: jgr.ngii[low][Bar] * (jiif - jgr.firstJIIOfGI[low][Foo]) + jiib - jgr.firstJIIOfGI[low][Bar],
high: jgr.ngii[high][Bar] * (jiif - jgr.firstJIIOfGI[high][Foo]) + jiib - jgr.firstJIIOfGI[high][Bar]];
ctii: NAT = njgiib * (jiif - jgr.fullJiir[Foo].min) + jiib - jgr.fullJiir[Bar].min;
Merge[a, d, lai, j, jgr.jgi, tie, rpd1, rpd2, ctii];
tie ← BestTie[tie];
IF tie.completion = NIL THEN GOTO Completed;
ENDLOOP ENDLOOP;
EXITS Completed => tie ← tie;
};
ENDLOOP;
ENDLOOP ENDLOOP;
connected ← TRUE;
IF NOT may THEN RETURN;
FOR f: NAT IN [NAT[lowRange[Foo].min] .. NAT[lowRange[Foo].maxPlusOne]) DO FOR b: NAT IN [NAT[lowRange[Bar].min] .. NAT[lowRange[Bar].maxPlusOne]) DO
ais: ARRAY End OF ArrayIndex = [[f, b], Int2Tweak[[f, b], d, 1]];
gis: ARRAY End OF NAT = [ComputeGroupingsIndex[a, ais[low]].gi, ComputeGroupingsIndex[a, ais[high]].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
aw1: ArrayWire = ArrayWireForGroup[a, ais[rp1.side], gis[rp1.side], g1, FALSE];
aw2: ArrayWire = ArrayWireForGroup[a, ais[rp2.side], gis[rp2.side], g2, FALSE];
IF aw1 = aw2 THEN NULL
ELSE IF aw2 = NIL THEN AddEltToArrayWire[a, aw1, NEW [ArrayWireElementPrivate ← [ais[rp2.side], g2]]]
ELSE IF aw1 = NIL THEN AddEltToArrayWire[a, aw2, NEW [ArrayWireElementPrivate ← [ais[rp1.side], g1]]]
ELSE JoinArrayWires[a, aw1, aw2];
ENDLOOP ENDLOOP;
};
GetGroup: PUBLIC PROC [a: Array, gi: NAT, ep: Port, mayAdd: BOOL] RETURNS [g: Group] = {
gs: Groupings = NARROW[a.groupingses[gi]];
g ← NARROW[gs.toGroup.Fetch[ep].value];
IF g = NIL AND mayAdd THEN {
g ← MakeGroup[a, gi, gs, ep];
IF gs.toGroup.Fetch[ep].value # g THEN ERROR};
};
MakeGroup: PROC [a: Array, gi: NAT, gs: Groupings, port: Port] RETURNS [g: Group] = {
g ← NEW [GroupPrivate ← [ports: LIST[port]]];
IF NOT gs.groups.UnionSingleton[g] THEN ERROR;
IF NOT gs.toGroup.Insert[port, g] THEN ERROR;
FOR d: Dim IN Dim DO
FOR side: End IN End DO
EnsureRPD[a, d, [side: side, port: port]];
ENDLOOP;
ENDLOOP;
g ← g};
EnsureRPD: PROC [a: Array, d: Dim, rp: RoledPort] = {
rpd: RoledPortData ← FetchRPD[a, d, rp];
IF rpd = NIL THEN {
rpd ← NewRoleData[a, d, rp];
};
rpd ← rpd};
NewRoleData: PROC [a: Array, d: Dim, rp: RoledPort] RETURNS [rpd: RoledPortData] = {
rpd ← NEW [RoledPortDataPrivate ← [
port: rp.port,
side: rp.side,
index: a.nrp[d],
links: NIL
]];
IF a.roles[d].length # rpd.index THEN ERROR;
VarRefSeqAppend[a.roles[d], rpd];
a.nrp[d] ← a.nrp[d] + 1;
IF NOT a.toRole[d][rp.side].Store[rp.port, rpd] THEN ERROR;
AddLinks[a, d, rpd];
};
GetTieAndRPD: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, rp1, rp2: RoledPort, g1, g2: Group, gi1, gi2: NAT, may: BOOL] RETURNS [tie: Tie, rpd1, rpd2: RoledPortData] = {
tie1: Tie = GetTie[a, d, phase, j, rp1.side, jgi2, jgi, jiir, g1, gi1, may];
tie2: Tie = GetTie[a, d, phase, j, rp2.side, jgi2, jgi, jiir, g2, gi2, may];
tie ← SELECT TRUE FROM
tie1 = tie2 => tie1,
NOT may => NIL,
ENDCASE => JoinTies[a, d, phase, j, jgi2, jgi, jiir, LIST[tie1, tie2], TRUE];
IF may AND tie.completion # NIL THEN {
rpd1 ← FetchRPD[a, d, rp1];
rpd2 ← FetchRPD[a, d, rp2];
};
};
GetTie: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, side: End, jgi2: Nat2, jgi: NAT, jiir: Range2, g: Group, gi: NAT, may: BOOL] RETURNS [tie: Tie] = {
tie ← FetchTie[j, side, jgi, g];
IF tie = NIL AND may THEN {
cn: Completion ← NIL;
IF g.ports # NIL AND g.ports.rest # NIL THEN {
ntii: NAT = RangeArea[jiir];
tii, ni: NAT ← 0;
D: Nat2 ← [0, 0];
cn ← NEW [CompletionPrivate[ntii]];
IF side = high THEN D[d] ← 1;
FOR jiif: INT IN [jiir[Foo].min .. jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jiir[Bar].min .. jiir[Bar].maxPlusOne) DO
lai: ArrayIndex = [jiif*a.jointsPeriod[Foo]+phase[Foo], jiib*a.jointsPeriod[Bar]+phase[Bar]];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF NOT (cn[tii] ← ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side]) THEN ni ← ni + 1;
ENDLOOP ENDLOOP;
cn.nIncomplete ← ni;
IF ni = 0 THEN cn ← NIL;
};
tie ← NEW [TiePrivate ← [
groups: ALL[NIL],
completion: cn
]];
tie.groups[side] ← g;
g.stopLooking[d][side] ← TRUE;
AddTie[j, jgi, tie];
};
};
JoinTies: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, ties: TieList, mayJoinGroups: BOOL] RETURNS [tie: Tie] = {
ntii: NAT = RangeArea[jiir];
groups: ARRAY End OF Group ← ALL[NIL];
urTies: TieList = ties;
doomeds: TieList ← NIL;
gi2s: ARRAY End OF Nat2;
gis: ARRAY End OF NAT;
hPhase: Nat2 ← phase;
hPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
FOR ts: TieList ← ties, ts.rest WHILE ts # NIL DO
tie: Tie = ts.first;
IF tie.better # NIL THEN ERROR;
IF GList.Member[tie, ts.rest] THEN ERROR;
ENDLOOP;
FOR side: End IN End DO
olds: GroupList ← NIL;
[gi2s[side], gis[side]] ← Jgi2ToGi[a, d, phase, j, jgi2, side];
FOR ts: TieList ← ties, ts.rest WHILE ts # NIL DO
g: Group = BestGroup[ts.first.groups[side]];
IF g # NIL AND NOT GList.Member[g, olds] THEN olds ← CONS[g, olds];
ENDLOOP;
groups[side] ← IF olds # NIL THEN IF olds.rest = NIL THEN olds.first ELSE IF mayJoinGroups THEN JoinGroups[a, phase, gi2s[side], olds, NARROW[a.groupingses[gis[side]]]] ELSE ERROR ELSE NIL;
ENDLOOP;
FOR side: End IN End DO
best: Group = groups[side] ← BestGroup[groups[side]];
FOR worses: GroupList ← AddTiedGroups[d, j, side, jgi, best, NIL], worses.rest WHILE worses # NIL DO
worse: Group = worses.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, doomeds] THEN doomeds ← CONS[tie, doomeds];
ENDLOOP;
ENDLOOP;
FOR ts: TieList ← urTies, ts.rest WHILE ts # NIL DO
IF NOT GList.Member[ts.first, doomeds] THEN ERROR;
ENDLOOP;
tie ← NEW [TiePrivate ← [groups: groups]];
FOR ts: TieList ← doomeds, ts.rest WHILE ts # NIL DO
doomed: Tie = ts.first;
Incompletify[a, d, doomed, ntii];
doomed.better ← tie;
ENDLOOP;
FinishIncompletion[a, d, phase, tie, ntii];
FOR ts: TieList ← doomeds, ts.rest WHILE ts # NIL DO
doomed: Tie = ts.first;
DeleteTie[j, jgi, doomed];
ENDLOOP;
AddTie[j, jgi, tie];
FOR sideg: End IN End DO --make sure all ties for group on this side are joined
gPhase: Nat2 = IF sideg = low THEN phase ELSE hPhase;
g: Group = groups[sideg];
IF g # NIL THEN {
FOR de: Dim IN Dim DO
FOR sidee: End IN End DO
Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
oldTies: TieList ← NIL;
FOR ws: GroupList ← AddTiedGroups[de, j, sidee, jgi, g, NIL], ws.rest WHILE ws # NIL DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, sidee, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, oldTies] THEN oldTies ← CONS[tie, oldTies];
ENDLOOP;
IF oldTies # NIL AND (oldTies.rest # NIL OR oldTies.first.groups[sidee] # g) THEN {
jiir: Range2 = Jgi2ToLair[a, gPhase, j, jgi2].jiir;
newTie: Tie = JoinTies[a, de, gPhase, j, jgi2, jgi, jiir, oldTies, FALSE];
IF newTie.groups[sidee] # g THEN ERROR;
oldTies ← oldTies;
};
oldTies ← oldTies;
};
EnumerateJointsForGi[a, de, sidee, gPhase, gi2s[sideg], Consume];
g.stopLooking[de][sidee] ← TRUE;
ENDLOOP;
ENDLOOP;
IF g.stopLooking = ALL[ALL[TRUE]] THEN KillWorse[g];
};
ENDLOOP;
tie ← tie;
};
KillWorse: PROC [g: Group] = {
FOR ws: GroupList ← g.worse, ws.rest WHILE ws # NIL DO
KillWorse[ws.first];
ENDLOOP;
g.worse ← NIL;
};
JoinGroups: PROC [a: Array, phase: Nat2, gi2: Nat2, groups: GroupList, gs: Groupings] RETURNS [g: Group] = {
bests: GroupList ← NIL;
ports: PortList ← NIL;
FOR raws: GroupList ← groups, raws.rest WHILE raws # NIL DO
IF raws.first = NIL THEN LOOP;
IF raws.first.ports = NIL THEN ERROR;
{best: Group = BestGroup[raws.first];
IF NOT GList.Member[best, bests] THEN {
bests ← CONS[best, bests];
ports ← NARROW[GList.Append[best.ports, ports]];
};
}ENDLOOP;
IF bests = NIL THEN ERROR;
IF bests.rest = NIL THEN RETURN [bests.first];
g ← NEW [GroupPrivate ← [ports: ports, worse: bests]];
FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
IF NOT gs.toGroup.Replace[pl.first, g] THEN ERROR;
ENDLOOP;
IF NOT gs.groups.UnionSingleton[g] THEN ERROR;
FOR worse: GroupList ← bests, worse.rest WHILE worse # NIL DO
gs.groups.RemoveElt[worse.first];
worse.first.better ← g;
ENDLOOP;
FOR d: Dim IN Dim DO
FOR side: End IN End DO
Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
otherSide: End = OtherEnd[side];
otherGs: Groupings = NARROW[a.groupingses[otherGi]];
otherSideGroups: GroupList ← NIL;
FOR ws: GroupList ← AddListTiedGroups[d, j, side, jgi, bests, NIL], ws.rest WHILE ws # NIL DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF tie.groups[otherSide] # NIL THEN otherSideGroups ← CONS[tie.groups[otherSide], otherSideGroups];
ENDLOOP;
IF otherSideGroups # NIL AND otherSideGroups.rest # NIL THEN [] ← JoinGroups[a, otherPhase, otherGi2, otherSideGroups, otherGs];
};
EnumerateJointsForGi[a, d, side, phase, gi2, Consume];
ENDLOOP;
ENDLOOP;
g ← g;
};
EnumerateJointsForGi: PROC [a: Array, d: Dim, side: End, phase, gi2: Nat2, Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint]] = {
lowPhase, highPhase: Nat2 ← phase;
IF side = high THEN {
lowPhase[d] ← (phase[d] + a.jointsPeriod[d] - 1) MOD a.jointsPeriod[d];
}
ELSE {
highPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
};
{j: Joint = GetArrayJoint[a, d, lowPhase];
otherPhase: Nat2 = IF side = low THEN highPhase ELSE lowPhase;
otherGi2, jgi2: Nat2 ← [LAST[NAT], LAST[NAT]];
Do1: PROC [de: Dim, Consume1: PROC] = {
SELECT TRUE FROM
de # d => {
otherGi2[de] ← gi2[de];
SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => jgi2[de] ← gi2[de] / a.jointsPeriod[de];
gi2[de] >= a.groupingParmses[de].firstHigh => {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d};
ENDCASE => jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
side = low => SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
jgi2[de] ← gi2[de] / a.jointsPeriod[de];
IF gi2[de]+1 < a.groupingParmses[de].middle.min THEN otherGi2[de] ← gi2[de]+1
ELSE IF HasMiddle[a.groupingParmses[de]] THEN otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de]
ELSE otherGi2[de] ← a.groupingParmses[de].middle.maxPlusOne;
Consume1[];
};
gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
otherGi2[de] ← gi2[de] + 1;
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[de] = (a.groupingParmses[de].middle.maxPlusOne MOD a.jointsPeriod[de]) AND a.groupingParmses[de].firstHigh < a.groupingParmses[de].sum THEN {
jgi2[de] ← j.groupingParmses[de].firstHigh;
otherGi2[de] ← a.groupingParmses[de].firstHigh;
Consume1[];
};
};
side = high => SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de] > 0 THEN {
otherGi2[de] ← gi2[de] - 1;
jgi2[de] ← otherGi2[de] / a.jointsPeriod[de];
Consume1[];
};
gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de] > 0 THEN {
lai, jii: NAT;
IF gi2[de] > a.groupingParmses[de].firstHigh THEN {
otherGi2[de] ← gi2[de]-1;
lai ← otherGi2[de] - a.groupingParmses[de].d;
jii ← lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
}
ELSE IF HasMiddle[a.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].firstHigh;
}
ELSE {
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
jgi2[de] ← j.groupingParmses[de].firstHigh;
};
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[de] = (a.groupingParmses[de].middle.min MOD a.jointsPeriod[de]) AND a.groupingParmses[de].middle.min > 0 THEN {
jgi2[de] ← j.groupingParmses[de].middle.min-1;
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
Consume1[];
};
};
ENDCASE => ERROR;
};
PerFoo: PROC = {Do1[Bar, PerBoth]};
PerBoth: PROC = {
Consume[otherPhase, otherGi2, jgi2, a.groupingParmses[Bar].sum*otherGi2[Foo] + otherGi2[Bar], j.groupingParmses[Bar].sum*jgi2[Foo] + jgi2[Bar], j];
};
Do1[Foo, PerFoo];
}};
AddTie: PROC [j: Joint, jgi: NAT, tie: Tie] = {
ties: Set--of Tie-- = NARROW[j.ties[jgi]];
IF NOT ties.UnionSingleton[tie] THEN ERROR;
FOR side: End IN End DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
g: Group = tie.groups[side];
IF g # NIL THEN {
IF NOT last.Insert[g, tie] THEN ERROR;
};
ENDLOOP;
};
DeleteTie: PROC [j: Joint, jgi: NAT, tie: Tie] = {
ties: Set--of Tie-- = NARROW[j.ties[jgi]];
ties.RemoveElt[tie];
FOR side: End IN End DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
IF tie.groups[side] # NIL AND NOT last.Delete[tie.groups[side]] THEN ERROR;
ENDLOOP;
};
PortPair: TYPE = ARRAY [1 .. 2] OF Port;
MergeStack: TYPE = LIST OF MergeStackFrame;
MergeStackFrame: TYPE = RECORD [
lai: ArrayIndex,
d: Dim,
side: End,
pair: PortPair];
Merge: PROC [a: Array, d: Dim, lai: ArrayIndex, j: Joint, jgi: NAT, tie: Tie, rpd1, rpd2: RoledPortData, ctii: NAT] = {
stack: MergeStack ← NIL;
Consider: PROC [ai: ArrayIndex, d: Dim, eltSide: End, pair: PortPair] = {
jointSide: End = OtherEnd[eltSide];
o: Dim = OtherDim[d];
lai: ArrayIndex = IF eltSide = high THEN ai ELSE Int2Tweak[ai, d, -1];
IF lai[d] IN [0 .. a.size[d]-1) AND lai[o] IN [0 .. a.size[o]) THEN {
stack ← CONS[[lai, d, jointSide, pair], stack];
};
};
DO
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
clai: INT = jSize[Bar] * lai[Foo] + lai[Bar];
r1: NAT = GetRoot[a, d, rpd1, clai];
r2: NAT = GetRoot[a, d, rpd2, clai];
IF r1 # r2 THEN {
o: Dim = OtherDim[d];
hai: Int2 = Int2Tweak[lai, d, 1];
IF tie.completion[ctii] THEN ERROR;
FOR side: End IN End DO
g: Group = tie.groups[side];
ai: ArrayIndex = IF side = low THEN lai ELSE hai;
pair: PortPair ← ALL[NIL];
otherSide: End = OtherEnd[side];
IF rpd1.side = side AND rpd2.side = side THEN pair ← [rpd1.port, rpd2.port]
ELSE {
IF g # NIL THEN FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: RoledPortData = FetchRPD[a, d, [side, pl.first]];
r: NAT = GetRoot[a, d, rpd, clai];
i: INT = SELECT r FROM r1 => 1, r2 => 2, ENDCASE => 3;
IF i IN [1 .. 2] AND pair[i] = NIL THEN {
pair[i] ← pl.first;
IF pair[3-i] # NIL THEN EXIT};
ENDLOOP;
};
IF pair[1] # NIL AND pair[2] # NIL THEN {
Consider[ai, d, side, pair];
Consider[ai, o, side, pair];
Consider[ai, o, otherSide, pair];
};
ENDLOOP;
IF r1 < r2 THEN SetNext[a, d, r2, clai, r1] ELSE SetNext[a, d, r1, clai, r2];
IF tie.completion[ctii] ← ComputeTieCompleteAt[a, d, tie, clai] THEN {
IF (tie.completion.nIncomplete ← tie.completion.nIncomplete - 1) = 0 THEN CompletifyTie[a, d, tie];
};
};
DO
IF stack = NIL THEN GOTO Dun;
{msf: MergeStackFrame = stack.first;
stack ← stack.rest;
d ← msf.d;
lai ← msf.lai;
{ai: ArrayIndex = IF msf.side = low THEN lai ELSE Int2Tweak[lai, d, 1];
gi: NAT = ComputeGroupingsIndex[a, ai].gi;
jii: Nat2 = [
Foo: lai[Foo] / a.jointsPeriod[Foo],
Bar: lai[Bar] / a.jointsPeriod[Bar]];
phase: Nat2 = [
Foo: lai[Foo] - jii[Foo] * a.jointsPeriod[Foo],
Bar: lai[Bar] - jii[Bar] * a.jointsPeriod[Bar]];
rp1: RoledPort = [msf.side, msf.pair[1]];
rp2: RoledPort = [msf.side, msf.pair[2]];
g1: Group = GetGroup[a, gi, rp1.port, TRUE];
g2: Group = GetGroup[a, gi, rp2.port, TRUE];
jgi2: Nat2;
jiir: Range2;
j ← GetArrayJoint[a, d, phase];
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase, j, jgi2, jgi, jiir, rp1, rp2, g1, g2, gi, gi, TRUE];
IF tie.completion # NIL THEN EXIT;
}}ENDLOOP;
ENDLOOP;
EXITS
Dun => a ← a;
};
Incompletify: PROC [a: Array, d: Dim, tie: Tie, ntii: NAT] = {
IF tie.completion # NIL THEN RETURN;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← 0;
FOR tii: NAT IN [0 .. tie.completion.length) DO
tie.completion[tii] ← TRUE;
ENDLOOP;
tie ← tie;
};
CompletifyTie: PROC [a: Array, d: Dim, tie: Tie] = {
IF tie.completion = NIL THEN ERROR;
tie.completion ← NIL;
};
FinishIncompletion: PROC [a: Array, d: Dim, phase: Nat2, tie: Tie, ntii: NAT] = {
IF tie.completion # NIL THEN ERROR;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← ntii;
FOR ctii: NAT IN [0 .. ntii) DO tie.completion[ctii] ← FALSE ENDLOOP;
};
AddLinks: PROC [a: Array, d: Dim, rpd: RoledPortData] = {
IF rpd.links # NIL THEN ERROR;
IF rpd.index = 0 THEN RETURN;
{
linksNeeded: NAT = Nat2Area[Nat2Tweak[a.size, d, -1]];
linkSize, wordsNeeded: NAT;
lgLinksPerWord: Sublg;
[linkSize, lgLinksPerWord] ← ChooseLinkSize[rpd.index+1];
wordsNeeded ← CeilDiv[linkSize * linksNeeded, Basics.bitsPerWord];
rpd.links ← NEW [LinksPrivate[wordsNeeded]];
rpd.links.linkSize ← linkSize;
rpd.links.negLinkSize ← - linkSize;
rpd.links.negLgLinksPerWord ← - lgLinksPerWord;
rpd.links.lgLinksPerWord ← lgLinksPerWord;
FOR clai: NAT IN [0 .. linksNeeded) DO
SetNext[a, d, rpd.index, clai, rpd.index];
ENDLOOP;
rpd ← rpd;
}};
ChooseLinkSize: PROC [nrp: NAT] RETURNS [linkSize: NAT, lgLinksPerWord: Sublg] = {
SELECT nrp FROM
<=1 => ERROR;
<=2 => RETURN [1, Basics.logBitsPerWord];
<=4 => RETURN [2, Basics.logBitsPerWord-1];
<=16 => RETURN [4, Basics.logBitsPerWord-2];
<=256 => RETURN [8, Basics.logBitsPerWord-3];
<=32767 => RETURN [16, Basics.logBitsPerWord-4];
ENDCASE => ERROR;
};
RPDNeedsLinks: PUBLIC PROC [a: Array, d: Dim, rpd: RoledPortData] RETURNS [needs: BOOL] = {
phase: NAT ← 0;
needs ← FALSE;
FOR ff: INT IN [0 .. a.jointsPeriod[Foo]) DO FOR fb: INT IN [0 .. a.jointsPeriod[Bar]) DO
j: Joint = NARROW[a.joints[d][phase]];
jgi: NAT ← 0;
FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO
FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
gi: NAT = Jgi2ToGi[a, d, [ff, fb], j, [jgif, jgib], rpd.side].gi;
gs: Groupings = NARROW[a.groupingses[gi]];
g: Group = NARROW[gs.toGroup.Fetch[rpd.port].value];
IF g # NIL THEN {
tie: Tie = FetchTie[j, rpd.side, jgi, g];
IF tie # NIL AND tie.completion # NIL THEN RETURN [TRUE];
};
jgi ← jgi + 1;
ENDLOOP;
ENDLOOP;
phase ← phase + 1;
ENDLOOP ENDLOOP;
needs ← needs;
};
GroupCompleteAt: PROC [a: Array, gi: NAT, g: Group, ai: ArrayIndex] RETURNS [complete: BOOL] = {
complete ← FALSE;
FOR d: Dim IN Dim DO
Try: PROC [side: End, lai: ArrayIndex] RETURNS [determined: BOOL] = {
jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie = NIL THEN RETURN [FALSE];
complete ← tie.completion = NIL OR ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side];
determined ← TRUE;
};
IF
(ai[d] < a.size[d]-1 AND Try[low, ai]) OR
(ai[d] > 0 AND Try[high, Int2Tweak[ai, d, -1]])
THEN EXIT;
ENDLOOP;
RETURN;
};
ComputeGroupCompleteAt: PROC [a: Array, g: Group, clai: NAT, d: Dim, side: End--of joint--] RETURNS [complete: BOOL] = {
root: NAT;
first: BOOL ← TRUE;
someNIL, someNonNIL: BOOL ← FALSE;
complete ← TRUE;
{FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: RoledPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
ComputeTieCompleteAt: PUBLIC PROC [a: Array, d: Dim, tie: Tie, clai: NAT] RETURNS [complete: BOOL] = {
root: NAT;
first: BOOL ← TRUE;
someNIL, someNonNIL: BOOL ← FALSE;
complete ← TRUE;
{FOR side: End IN End DO
g: Group = tie.groups[side];
IF g # NIL THEN FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: RoledPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
WordPtr: TYPE = LONG POINTER TO WORD;
GetNext: PUBLIC PROC [rp: RoledPortData, clai: NAT] RETURNS [next: NAT] = TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next ← Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
}};
ArrayEltPortsConnectedByJoint: PUBLIC PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: RoledPort] RETURNS [hypothetically, really: BOOL] = {
o: Dim = OtherDim[d];
IF NOT (lowIndex[d] IN [0 .. a.size[d]-1) AND lowIndex[o] IN [0 .. a.size[o])) THEN RETURN [FALSE, FALSE];
{phase: Nat2 = [
Foo: lowIndex[Foo] MOD a.jointsPeriod[Foo],
Bar: lowIndex[Bar] MOD a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jii: Nat2 = [
Foo: lowIndex[Foo] / a.jointsPeriod[Foo],
Bar: lowIndex[Bar] / a.jointsPeriod[Bar]];
jgi2: Nat2;
jgi, ctii: NAT;
jiir: Range2;
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
{gis: ARRAY End OF NAT = [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE, FALSE];
{tie1: Tie = FetchTie[j, rp1.side, jgi, g1];
tie2: Tie = FetchTie[j, rp2.side, jgi, g2];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie1 # tie2 OR tie1 = NIL THEN RETURN [FALSE, FALSE]
ELSE IF tie1.completion = NIL THEN RETURN [TRUE, TRUE]
ELSE {
rpd1: RoledPortData = FetchRPD[a, d, rp1];
rpd2: RoledPortData = FetchRPD[a, d, rp2];
clai: INT = jSize[Bar] * lowIndex[Foo] + lowIndex[Bar];
really ← GetRoot[a, d, rpd1, clai] = GetRoot[a, d, rpd2, clai];
hypothetically ← TRUE;
};
}}}};
ArrayEltPortsConnected: PUBLIC PROC [a: Array, ai1, ai2: ArrayIndex, ep1, ep2: Port] RETURNS [hypothetically: BOOL] = {
gi1: NAT = ComputeGroupingsIndex[a, ai1].gi;
gi2: NAT = ComputeGroupingsIndex[a, ai2].gi;
g1: Group = GetGroup[a, gi1, ep1, FALSE];
g2: Group = GetGroup[a, gi2, ep2, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE];
{aw1: ArrayWire = ArrayWireForGroup[a, ai1, gi1, g1, TRUE];
aw2: ArrayWire = ArrayWireForGroup[a, ai2, gi2, g2, TRUE];
RETURN [aw1 = aw2];
}};
GroupsHypotheticallyConnected: PUBLIC PROC [a: Array, j: Joint, jgi: NAT, gs: ARRAY End OF Group] RETURNS [BOOL] = {
Get: PROC [side: End] RETURNS [tie: Tie] = {
rt: RefTable = NARROW[j.toTie[side][jgi]];
tie ← NARROW[rt.Fetch[gs[side]].value]};
RETURN [Get[low] = Get[high]];
};
GetRoot: PUBLIC PROC [a: Array, d: Dim, rp: RoledPortData, clai: NAT] RETURNS [root: NAT] = TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next: NAT = Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
IF next = rp.index THEN RETURN [rp.index];
{rp2: RoledPortData = NARROW[a.roles[d].refs[next]];
IF next # rp2.index THEN ERROR;
root ← GetRoot[a, d, rp2, clai];
IF root # next THEN {
leftShift: INTEGER = - rightShift;
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[mask, leftShift]];
shiftedRoot: WORD = Basics.BITSHIFT[root, leftShift];
word: WORD = Basics.BITOR[shiftedRoot, Basics.BITAND[shiftedMask, wordPtr^]];
wordPtr^ ← word;
};
}}};
SetNext: PROC [a: Array, d: Dim, index, clai, next: NAT] = TRUSTED {
IF index = 0 THEN ERROR;
{rpd: RoledPortData = NARROW[a.roles[d].refs[index]];
ls: Links = rpd.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
leftShift: INTEGER = ls.linkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[last[ls.linkSize], leftShift]];
shiftedNext: WORD = Basics.BITSHIFT[next, leftShift];
word: WORD = Basics.BITOR[shiftedNext, Basics.BITAND[shiftedMask, wordPtr^]];
IF Basics.BITAND[shiftedNext, shiftedMask] # 0 THEN ERROR;
wordPtr^ ← word;
}};
last: ARRAY [0 .. Basics.bitsPerWord] OF WORD = [
00000H,
00001H, 00003H, 00007H, 0000FH,
0001FH, 0003FH, 0007FH, 000FFH,
001FFH, 003FFH, 007FFH, 00FFFH,
01FFFH, 03FFFH, 07FFFH, 0FFFFH];
EnsurePortForGroups: PUBLIC PROC [act: CellType, gis, giis: ARRAY End OF Nat2, gss: GroupListPair] RETURNS [ap: Port] = {
a: Array = act.asArray;
ais: ARRAY End OF ArrayIndex = [AgiToAi[a, gis[low], giis[low]], AgiToAi[a, gis[high], giis[high]]];
Enumerate: PROC [Consume: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL ← FALSE]] RETURNS [aborted: BOOL] = {
FOR side: End IN End DO
FOR gs: GroupList ← gss[side], gs.rest WHILE gs # NIL DO
g: Group = gs.first;
FOR ps: PortList ← g.ports, ps.rest WHILE ps # NIL DO
IF Consume[ais[side], ps.first] THEN RETURN [TRUE];
ENDLOOP;
ENDLOOP;
ENDLOOP;
aborted ← FALSE;
};
Search: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL ← FALSE] = {
stop ← (NOT Central[a, ai]) AND (ap ← GetArrayPortForPort[a, ai, ep]) # NIL;
};
Export: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL ← FALSE] = {
IF NOT Central[a, ai] THEN SetArrayPortForPort[a, ai, ep, ap];
};
IF Enumerate[Search] THEN RETURN;
IF act.port = NIL THEN ERROR --is it true that a cell type always has a port?--;
ap ← FullyAddPort[[parent: act.port]].port;
IF Enumerate[Export] THEN ERROR;
};
CrossATie: PUBLIC PROC [ct: CellType, d: Dim, fromP: Port, fromS: End] RETURNS [toP: Port] = {
toS: End = OtherEnd[fromS];
a: Array = ct.asArray;
tf: INT = a.jointsPeriod[Foo];
tb: INT = a.jointsPeriod[Bar];
candidates: PortList ← NIL;
first: BOOL ← TRUE;
FOR ff: INT IN [0 .. tf) DO FOR fb: INT IN [0 .. tb) DO
phase: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase];
FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
jgi2: Nat2 = [jgif, jgib];
jgi: NAT = j.groupingParmses[Bar].sum * jgif + jgib;
gif: NAT = Jgi2ToGi[a, d, phase, j, jgi2, fromS].gi;
gf: Group = GetGroup[a, gif, fromP, FALSE];
IF gf = NIL THEN RETURN [NIL];
{tie: Tie = FetchTie[j, fromS, jgi, gf];
IF tie = NIL THEN RETURN [NIL];
{gt: Group = tie.groups[toS];
IF gt = NIL THEN NULL
ELSE IF first THEN {first ← FALSE; candidates ← gt.ports}
ELSE candidates ← NARROW[GList.Intersection[candidates, gt.ports]];
IF candidates = NIL THEN RETURN [NIL];
}}ENDLOOP ENDLOOP;
ENDLOOP ENDLOOP;
toP ← IF candidates # NIL THEN candidates.first ELSE NIL;
};
RetractFalseHypotheses: PUBLIC PROC [act: CellType] = {
IF NOT IsIncompleteArray[act] THEN RETURN;
{a: Array = act.asArray;
SplitGroups[a];
RemakeTies[act, a];
act ← act;
}};
RPDPairList: TYPE = LIST OF RPDPair;
RPDPair: TYPE = REF RPDPairPrivate;
RPDPairPrivate: TYPE = ARRAY End OF RoledPortData;
undef: NAT = LAST[NAT];
RefinableSubset: TYPE = REF RefinableSubsetPrivate;
RefinableSubsetPrivate: TYPE = RECORD [
elts: Set--of RPDPair--,
oldKey, nextRoot: NAT ← undef
];
SplitGroups: PROC [a: Array] = {
dt: Dim = IF a.size[Foo] > 1 THEN Foo ELSE IF a.size[Bar] > 1 THEN Bar ELSE ERROR;
d1: Dim = IF RangeLength[a.groupingParmses[Foo].middle] < RangeLength[a.groupingParmses[Bar].middle] THEN Foo ELSE Bar;
d2: Dim = OtherDim[d1];
FOR ff: NAT IN [0 .. a.jointsPeriod[Foo]) DO FOR fb: NAT IN [0 .. a.jointsPeriod[Bar]) DO
phase: Nat2 = [ff, fb];
wir: Range2 = Range2Div[SizeRange[a.size], a.jointsPeriod, phase];
mcir: Range2 = Range2Div[GPMiddle[a.groupingParmses],a.jointsPeriod,phase];
hasMiddle: ARRAY Dim OF BOOL = [HasMiddle[a.groupingParmses[Foo]], HasMiddle[a.groupingParmses[Bar]]];
SelStart: PROC [d: Dim] RETURNS [mgi: NAT] = {
mgi ← SELECT TRUE FROM
hasMiddle[d] => a.groupingParmses[d].middle.min + phase[d],
a.groupingParmses[d].middle.maxPlusOne <= 0 => 0,
a.groupingParmses[d].middle.maxPlusOne < a.size[d] => ERROR,
ENDCASE => a.groupingParmses[d].middle.min-1;
};
mgi2: Nat2 = [SelStart[Foo], SelStart[Bar]];
mgi: NAT = a.groupingParmses[Bar].sum * mgi2[Foo] + mgi2[Bar];
gsm: Groupings = NARROW[a.groupingses[mgi]];
rfblSetsm: Set--of RefinableSubset-- = CreateHashSet[];
rfblSetse, rfblSetsc: Set--of RefinableSubset--;
toNew: IntHashTable.Table = IntHashTable.Create[];
need: ARRAY [1 .. 4] OF BOOL = [
wir[d1].min < mcir[d1].min,
mcir[d1].maxPlusOne < wir[d1].maxPlusOne,
wir[d2].min < mcir[d2].min AND hasMiddle[d1],
mcir[d2].maxPlusOne < wir[d2].maxPlusOne AND hasMiddle[d1]];
Prep: PROC [i: [1 .. 4]] RETURNS [Set--of RefinableSubset--] = {
IF need[i] THEN {
FOR j: [1 .. 4] IN (i .. 4] DO
IF need[j] THEN RETURN[CopyRefinableSubsets[rfblSetsm]];
ENDLOOP;
RETURN[rfblSetsm]};
RETURN [NIL]};
GetEltRoot: PROC [a: Array, d: Dim, elt: REF ANY, side: End, clai: NAT] RETURNS [root: NAT] = {
rpdPair: RPDPair = NARROW[elt];
root ← GetRoot[a, d, rpdPair[side], clai];
};
MakeGroupSets[a, dt, gsm, rfblSetsm];
IF hasMiddle[Foo] AND hasMiddle[Bar] THEN {
RefineOverRange[a, dt, phase, rfblSetsm, toNew, mcir, GetEltRoot];
SetGroups[gsm, rfblSetsm];
};
rfblSetse ← Prep[1];
FOR ci1: INT DECREASING IN [wir[d1].min .. mcir[d1].min) DO
egi2: Nat2 = ConsNat2[d1, ci1*a.jointsPeriod[d1]+phase[d1], mgi2[d2]];
egi: NAT = a.groupingParmses[Bar].sum * egi2[Foo] + egi2[Bar];
gse: Groupings = NARROW[a.groupingses[egi]];
IF hasMiddle[d2] THEN {
RefineOverRange[a, dt, phase, rfblSetse, toNew, ConsRange2[d1, [ci1, ci1+1], mcir[d2]], GetEltRoot];
SetGroups[gse, rfblSetse];
};
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
cgi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2], egi2[d1]];
cgi: NAT = a.groupingParmses[Bar].sum * cgi2[Foo] + cgi2[Bar];
gsc: Groupings = NARROW[a.groupingses[cgi]];
RefineOverRange[a, dt, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [ci1, mcir[d1].maxPlusOne]], GetEltRoot];
SetGroups[gsc, rfblSetsc];
ENDLOOP;
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
cgi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2] + a.groupingParmses[d2].d, egi2[d1]];
cgi: NAT = a.groupingParmses[Bar].sum * cgi2[Foo] + cgi2[Bar];
gsc: Groupings = NARROW[a.groupingses[cgi]];
RefineOverRange[a, dt, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [ci1, mcir[d1].maxPlusOne]], GetEltRoot];
SetGroups[gsc, rfblSetsc];
ENDLOOP;
ENDLOOP;
rfblSetse ← Prep[2];
FOR ci1: INT IN [mcir[d1].maxPlusOne .. wir[d1].maxPlusOne) DO
egi2: Nat2 = ConsNat2[d1, ci1*a.jointsPeriod[d1]+phase[d1] + a.groupingParmses[d1].d, mgi2[d2]];
egi: NAT = a.groupingParmses[Bar].sum * egi2[Foo] + egi2[Bar];
gse: Groupings = NARROW[a.groupingses[egi]];
IF hasMiddle[d2] THEN {
RefineOverRange[a, dt, phase, rfblSetse, toNew, ConsRange2[d1, [ci1, ci1+1], mcir[d2]], GetEltRoot];
SetGroups[gse, rfblSetse];
};
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
cgi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2], egi2[d1]];
cgi: NAT = a.groupingParmses[Bar].sum * cgi2[Foo] + cgi2[Bar];
gsc: Groupings = NARROW[a.groupingses[cgi]];
RefineOverRange[a, dt, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [mcir[d1].min, ci1+1]], GetEltRoot];
SetGroups[gsc, rfblSetsc];
ENDLOOP;
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
cgi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2] + a.groupingParmses[d2].d, egi2[d1]];
cgi: NAT = a.groupingParmses[Bar].sum * cgi2[Foo] + cgi2[Bar];
gsc: Groupings = NARROW[a.groupingses[cgi]];
RefineOverRange[a, dt, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [mcir[d1].min, ci1+1]], GetEltRoot];
SetGroups[gsc, rfblSetsc];
ENDLOOP;
ENDLOOP;
IF hasMiddle[d1] THEN {
rfblSetse ← Prep[3];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
egi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2], mgi2[d1]];
egi: NAT = a.groupingParmses[Bar].sum * egi2[Foo] + egi2[Bar];
gse: Groupings = NARROW[a.groupingses[egi]];
RefineOverRange[a, dt, phase, rfblSetse, toNew, ConsRange2[d2, [ci2, ci2+1], mcir[d1]], GetEltRoot];
SetGroups[gse, rfblSetse];
ENDLOOP;
};
IF hasMiddle[d1] THEN {
rfblSetse ← Prep[4];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
egi2: Nat2 = ConsNat2[d2, ci2*a.jointsPeriod[d2]+phase[d2] + a.groupingParmses[d2].d, mgi2[d1]];
egi: NAT = a.groupingParmses[Bar].sum * egi2[Foo] + egi2[Bar];
gse: Groupings = NARROW[a.groupingses[egi]];
RefineOverRange[a, dt, phase, rfblSetse, toNew, ConsRange2[d2, [ci2, ci2+1], mcir[d1]], GetEltRoot];
SetGroups[gse, rfblSetse];
ENDLOOP;
};
a ← a;
ENDLOOP ENDLOOP;
a ← a;
};
MakeGroupSets: PROC [a: Array, dt: Dim, gs: Groupings, rfblSets: Set--of RefinableSubset--] = {
StartSet: PROC [ra: REF ANY] = {
g: Group = NARROW[ra];
rfblSet: RefinableSubset = NEW [RefinableSubsetPrivate ← [elts: CreateHashSet[] ]];
FOR ports: PortList ← g.ports, ports.rest WHILE ports # NIL DO
rpdPair: RPDPair = NEW [RPDPairPrivate ← [
low: NARROW[a.toRole[dt][low].Fetch[ports.first].value],
high: NARROW[a.toRole[dt][high].Fetch[ports.first].value] ]];
IF NOT rfblSet.elts.UnionSingleton[rpdPair] THEN ERROR;
ENDLOOP;
IF NOT rfblSets.UnionSingleton[rfblSet] THEN ERROR;
};
gs.groups.Enumerate[StartSet];
};
SetGroups: PROC [gs: Groupings, rfblSets: Set--of RefinableSubset--] = {
Transfer: PROC [ra: REF ANY] = {
rfblSet: RefinableSubset = NARROW[ra];
g: Group = NEW [GroupPrivate ← []];
TransferPort: PROC [ra: REF ANY] = {
rpdPair: RPDPair = NARROW[ra];
IF rpdPair[low] = NIL OR rpdPair[high] = NIL THEN ERROR;
{port: Port = rpdPair[low].port;
g.ports ← CONS[port, g.ports];
IF NOT gs.toGroup.Store[port, g] THEN ERROR;
}};
rfblSet.elts.Enumerate[TransferPort];
IF NOT gs.groups.UnionSingleton[g] THEN ERROR;
};
gs.toGroup.Erase[];
gs.groups ← CreateHashSet[];
rfblSets.Enumerate[Transfer];
};
CopyRefinableSubsets: PROC [original: Set--of RefinableSubset--] RETURNS [copy: Set--of RefinableSubset--] = {
CopyRefinableSubset: PROC [ra: REF ANY] = {
urSet: RefinableSubset = NARROW[ra];
newSet: RefinableSubset = NEW [RefinableSubsetPrivate ← [elts: CreateHashSet[] ]];
MoveRPD: PROC [ra: REF ANY] = {
IF NOT newSet.elts.UnionSingleton[ra] THEN ERROR;
};
urSet.elts.Enumerate[MoveRPD];
IF NOT copy.UnionSingleton[newSet] THEN ERROR;
};
copy ← CreateHashSet[];
original.Enumerate[CopyRefinableSubset];
copy ← copy;
};
RefineOverRange: PROC [a: Array, dt: Dim, phase: Nat2, rfblSets: Set--of RefinableSubset--, toNew: IntHashTable.Table, cir: Range2, GetEltRoot: PROC [a: Array, d: Dim, elt: REF ANY, side: End, clai: NAT] RETURNS [root: NAT]] = {
jSize: Nat2 = Nat2Tweak[a.size, dt, -1];
FOR cif: INT IN [cir[Foo].min .. cir[Foo].maxPlusOne) DO FOR cib: INT IN [cir[Bar].min .. cir[Bar].maxPlusOne) DO
lai: Nat2 ← Nat2Add[Nat2Mul[[cif, cib], a.jointsPeriod], phase];
side: End ← low;
clai: NAT ← jSize[Bar]*lai[Foo] + lai[Bar];
oldKey: NAT ← 0;
ResetSet: PROC [ra: REF ANY] = {
rfblSet: RefinableSubset = NARROW[ra];
rfblSet.oldKey ← oldKey;
oldKey ← oldKey + 1;
rfblSet.nextRoot ← undef};
RefineSet: PROC [ra: REF ANY] = {
rfblSet: RefinableSubset = NARROW[ra];
RefineElt: PROC [ra: REF ANY] = {
elt: REF ANY = ra;
root: NAT = GetEltRoot[a, dt, elt, side, clai];
SELECT rfblSet.nextRoot FROM
root => NULL;
undef => rfblSet.nextRoot ← root;
ENDCASE => {
both: Basics.LongNumber = [num[rfblSet.oldKey, root]];
newSet: RefinableSubset ← NARROW[toNew.Fetch[both.li].value];
IF newSet = NIL THEN {
newSet ← NEW [RefinableSubsetPrivate ← [
elts: CreateHashSet[],
oldKey: rfblSet.oldKey,
nextRoot: root]];
IF NOT toNew.Insert[both.li, newSet] THEN ERROR;
IF NOT rfblSets.UnionSingleton[newSet] THEN ERROR;
};
IF NOT newSet.elts.UnionSingleton[elt] THEN ERROR;
rfblSet.elts.RemoveElt[elt];
};
};
rfblSet.elts.Enumerate[RefineElt];
};
IF lai[dt] = jSize[dt] THEN {
side ← high;
lai[dt] ← lai[dt] - 1;
clai ← clai - (IF dt=Foo THEN jSize[Bar] ELSE 1)};
rfblSets.Enumerate[ResetSet];
rfblSets.Enumerate[RefineSet];
toNew.Erase[];
ENDLOOP ENDLOOP;
};
RemakeTies: PROC [act: CellType, a: Array] = {
d1: Dim = IF RangeLength[a.groupingParmses[Foo].middle] < RangeLength[a.groupingParmses[Bar].middle] THEN Foo ELSE Bar;
d2: Dim = OtherDim[d1];
FOR ff: NAT IN [0 .. a.jointsPeriod[Foo]) DO FOR fb: NAT IN [0 .. a.jointsPeriod[Bar]) DO FOR dj: Dim IN Dim DO
phase: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, dj, phase];
IF j.size = 0 THEN LOOP;
{wir: Range2 = SizeRange[j.size2];
mcir: Range2 = GPMiddle[j.groupingParmses];
hasMiddle: ARRAY Dim OF BOOL = [HasMiddle[a.groupingParmses[Foo]], HasMiddle[a.groupingParmses[Bar]]];
SelStart: PROC [di: Dim] RETURNS [mji: NAT] = {
mji ← SELECT TRUE FROM
hasMiddle[di] => j.groupingParmses[di].middle.min,
a.groupingParmses[di].middle.maxPlusOne <= 0 => 0,
a.groupingParmses[di].middle.maxPlusOne < j.size2[di] => ERROR,
ENDCASE => a.groupingParmses[di].middle.min-1;
};
mji2: Nat2 = [SelStart[Foo], SelStart[Bar]];
mji: NAT = j.groupingParmses[Bar].sum * mji2[Foo] + mji2[Bar];
tsm: Set--of Tie-- = NARROW[j.ties[mji]];
rfblSetsm: Set--of RefinableSubset-- = CreateHashSet[];
rfblSetse, rfblSetsc: Set--of RefinableSubset--;
toNew: IntHashTable.Table = IntHashTable.Create[];
need: ARRAY [1 .. 4] OF BOOL = [
wir[d1].min < mcir[d1].min,
mcir[d1].maxPlusOne < wir[d1].maxPlusOne,
wir[d2].min < mcir[d2].min AND hasMiddle[d1],
mcir[d2].maxPlusOne < wir[d2].maxPlusOne AND hasMiddle[d1]];
Prep: PROC [i: [1 .. 4]] RETURNS [Set--of RefinableSubset--] = {
IF need[i] THEN {
FOR j: [1 .. 4] IN (i .. 4] DO
IF need[j] THEN RETURN[CopyRefinableSubsets[rfblSetsm]];
ENDLOOP;
RETURN[rfblSetsm]};
RETURN [NIL]};
GetEltRoot: PROC [a: Array, d: Dim, elt: REF ANY, side: End, clai: NAT] RETURNS [root: NAT] = {
rpd: RoledPortData = NARROW[elt];
IF side # low THEN ERROR;
root ← GetRoot[a, d, rpd, clai];
};
MakeTieSets[a, dj, tsm, rfblSetsm];
IF hasMiddle[Foo] AND hasMiddle[Bar] THEN {
RefineOverRange[a, dj, phase, rfblSetsm, toNew, mcir, GetEltRoot];
SetTies[act, a, dj, phase, j, mji2, rfblSetsm];
};
rfblSetse ← Prep[1];
FOR ci1: INT DECREASING IN [wir[d1].min .. mcir[d1].min) DO
eji2: Nat2 = ConsNat2[d1, ci1, mji2[d2]];
IF hasMiddle[d2] THEN {
RefineOverRange[a, dj, phase, rfblSetse, toNew, ConsRange2[d1, [ci1, ci1+1], mcir[d2]], GetEltRoot];
SetTies[act, a, dj, phase, j, eji2, rfblSetse];
};
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
cji2: Nat2 = ConsNat2[d2, ci2, eji2[d1]];
RefineOverRange[a, dj, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [ci1, mcir[d1].maxPlusOne]], GetEltRoot];
SetTies[act, a, dj, phase, j, cji2, rfblSetsc];
ENDLOOP;
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
cji2: Nat2 = ConsNat2[d2, ci2 + j.groupingParmses[d2].d, eji2[d1]];
RefineOverRange[a, dj, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [ci1, mcir[d1].maxPlusOne]], GetEltRoot];
SetTies[act, a, dj, phase, j, cji2, rfblSetsc];
ENDLOOP;
ENDLOOP;
rfblSetse ← Prep[2];
FOR ci1: INT IN [mcir[d1].maxPlusOne .. wir[d1].maxPlusOne) DO
eji2: Nat2 = ConsNat2[d1, ci1 + j.groupingParmses[d1].d, mji2[d2]];
IF hasMiddle[d2] THEN {
RefineOverRange[a, dj, phase, rfblSetse, toNew, ConsRange2[d1, [ci1, ci1+1], mcir[d2]], GetEltRoot];
SetTies[act, a, dj, phase, j, eji2, rfblSetse];
};
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
cji2: Nat2 = ConsNat2[d2, ci2, eji2[d1]];
RefineOverRange[a, dj, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [mcir[d1].min, ci1+1]], GetEltRoot];
SetTies[act, a, dj, phase, j, cji2, rfblSetsc];
ENDLOOP;
rfblSetsc ← CopyRefinableSubsets[rfblSetse];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
cji2: Nat2 = ConsNat2[d2, ci2 + j.groupingParmses[d2].d, eji2[d1]];
RefineOverRange[a, dj, phase, rfblSetsc, toNew, ConsRange2[d2, [ci2, ci2+1], [mcir[d1].min, ci1+1]], GetEltRoot];
SetTies[act, a, dj, phase, j, cji2, rfblSetsc];
ENDLOOP;
ENDLOOP;
IF hasMiddle[d1] THEN {
rfblSetse ← Prep[3];
FOR ci2: INT DECREASING IN [wir[d2].min .. mcir[d2].min) DO
eji2: Nat2 = ConsNat2[d2, ci2, mji2[d1]];
RefineOverRange[a, dj, phase, rfblSetse, toNew, ConsRange2[d2, [ci2, ci2+1], mcir[d1]], GetEltRoot];
SetTies[act, a, dj, phase, j, eji2, rfblSetse];
ENDLOOP;
};
IF hasMiddle[d1] THEN {
rfblSetse ← Prep[4];
FOR ci2: INT IN [mcir[d2].maxPlusOne .. wir[d2].maxPlusOne) DO
eji2: Nat2 = ConsNat2[d2, ci2 + j.groupingParmses[d2].d, mji2[d1]];
RefineOverRange[a, dj, phase, rfblSetse, toNew, ConsRange2[d2, [ci2, ci2+1], mcir[d1]], GetEltRoot];
SetTies[act, a, dj, phase, j, eji2, rfblSetse];
ENDLOOP;
};
a ← a;
}ENDLOOP ENDLOOP ENDLOOP;
a ← a;
};
MakeTieSets: PROC [a: Array, dj: Dim, ts: Set--of Tie--, rfblSets: Set--of RefinableSubset--] = {
StartSet: PROC [ra: REF ANY] = {
t: Tie = NARROW[ra];
rfblSet: RefinableSubset = NEW [RefinableSubsetPrivate ← [elts: CreateHashSet[] ]];
FOR side: End IN End DO
IF t.groups[side] # NIL THEN FOR ports: PortList ← t.groups[side].ports, ports.rest WHILE ports # NIL DO
rpd: RoledPortData = NARROW[a.toRole[dj][side].Fetch[ports.first].value];
IF rpd = NIL THEN ERROR;
IF NOT rfblSet.elts.UnionSingleton[rpd] THEN ERROR;
ENDLOOP;
ENDLOOP;
IF rfblSet.elts.Size[] = 0 THEN ERROR;
IF NOT rfblSets.UnionSingleton[rfblSet] THEN ERROR;
};
ts.Enumerate[StartSet];
};
RoledGroupList: TYPE = LIST OF RoledGroup;
RoledGroup: TYPE = REF RoledGroupPrivate;
RoledGroupPrivate: TYPE = RECORD [side: End, g: Group];
GroupPairList: TYPE = LIST OF GroupPair;
GroupPairRef: TYPE = REF GroupPair;
GroupPair: TYPE = ARRAY End OF Group;
SetTies: PROC [act: CellType, a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, rfblSets: Set--of RefinableSubset--] = {
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
jgi: NAT = j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar];
gip: GIPair = Jgi2ToGip[a, d, phase, j, jgi2];
oldTS: Set--of Tie-- = NARROW[j.ties[jgi]];
newTS: Set--of Tie-- = CreateHashSet[];
g2t: ARRAY End OF RefTable--Group b Tie-- = [NARROW[j.toTie[low][jgi]], NARROW[j.toTie[high][jgi]]];
Transfer: PROC [ra: REF ANY] = {
rfblSet: RefinableSubset = NARROW[ra];
groupses: ARRAY End OF GroupList ← ALL[NIL];
TransferPort: PROC [ra: REF ANY] = {
rpd: RoledPortData = NARROW[ra];
g: Group = PortToGroup[a, gip[rpd.side], rpd.port];
groupses[rpd.side] ← NARROW[GList.Union[groupses[rpd.side], NARROW[LIST[g], GroupList]]];
};
rfblSet.elts.Enumerate[TransferPort];
IF groupses[low] # NIL AND groupses[high] # NIL THEN {
t: Tie = NEW [TiePrivate ← [groups: [groupses[low].first, groupses[high].first]]];
IF NOT newTS.UnionSingleton[t] THEN ERROR;
FOR side: End IN End DO
IF NOT g2t[side].Store[t.groups[side], t] THEN ERROR;
ENDLOOP;
};
};
toPair: ARRAY End OF RefTable = [CreateRefTable[], CreateRefTable[]];
Patch: PROC [ra: REF ANY] = {
oldTie: Tie = NARROW[ra];
lair: Range2 = Jgi2ToLair[a, phase, j, jgi2].lair;
gpl: GroupPairList ← NIL;
size: NAT ← 0;
toPair[low].Erase[];
toPair[high].Erase[];
FOR side: End IN End DO
otherSide: End = OtherEnd[side];
oldG: Group = oldTie.groups[side];
IF oldG # NIL THEN FOR ports: PortList ← oldG.ports, ports.rest WHILE ports # NIL DO
newG: Group = PortToGroup[a, gip[side], ports.first];
IF toPair[side].Fetch[newG].found THEN LOOP;
{newTie: Tie = FetchTie[j, side, jgi, newG];
IF newTie # NIL AND newTie.groups[side] # newG THEN ERROR;
gpl ← CONS[[NIL, NIL], gpl];
size ← size + 1;
IF newTie # NIL THEN gpl.first ← newTie.groups ELSE gpl.first[side] ← newG;
IF NOT toPair[side].Store[newG, gpl] THEN ERROR;
IF newTie # NIL AND NOT toPair[otherSide].Store[gpl.first[otherSide], gpl] THEN ERROR;
}ENDLOOP;
ENDLOOP;
{rootToPairs: ICHT.Table = ICHT.Create[-1, size/4*6+5];
FOR laif: INT IN [lair[Foo].min .. lair[Foo].maxPlusOne) DO FOR laib: INT IN [lair[Bar].min .. lair[Bar].maxPlusOne) DO
lai: ArrayIndex = [laif, laib];
hai: ArrayIndex = Int2Tweak[lai, d, 1];
clai: NAT = jSize[Bar]*laif + laib;
gis, giis: ARRAY End OF Nat2;
FOR gps: GroupPairList ← gpl, gps.rest WHILE gps # NIL DO
rpd: RoledPortData = IF gps.first[low] # NIL THEN FetchRPD[a, d, [low, gps.first[low].ports.first]] ELSE FetchRPD[a, d, [high, gps.first[high].ports.first]];
root: NAT = GetRoot[a, d, rpd, clai];
pairs: REF GroupListPair ← NARROW[rootToPairs.Fetch[root].value];
IF pairs = NIL AND NOT rootToPairs.Store[root, pairs ← NEW [GroupListPair ← [NIL, NIL]]] THEN ERROR;
IF gps.first[low] # NIL THEN pairs[low] ← CONS[gps.first[low], pairs[low]];
IF gps.first[high] # NIL THEN pairs[high] ← CONS[gps.first[high], pairs[high]];
ENDLOOP;
[gi2: gis[low], gii2: giis[low]] ← ComputeGroupingsIndex[a, lai];
[gi2: gis[high], gii2: giis[high]] ← ComputeGroupingsIndex[a, hai];
{lastPort: Port ← NIL;
Export: PROC [key: INT, value: REF ANY] RETURNS [quit: BOOL ← FALSE] --ICHT.EachPairAction-- = {
pairs: REF GroupListPair = NARROW[value];
thisPort: Port = EnsurePortForGroups[act, gis, giis, pairs^];
ConnectInstance: PROC [ci: CellInstance] = {
w1: Wire = FindTransitiveConnection[ci, lastPort];
w2: Wire = FindTransitiveConnection[ci, thisPort];
IF w1 # w2 THEN [] ← MergeNets[w1, w2];
};
ConnectArrayElts: PROC [pct: CellType] = {
pa: Array = pct.asArray;
IF NOT MakeArrayConnection[pct, Foo, SizeRange[Nat2Tweak[pa.size, Foo, -1]], [low, lastPort], [low, thisPort], TRUE] THEN ERROR;
IF NOT MakeArrayConnection[pct, Foo, SizeRange[Nat2Tweak[pa.size, Foo, -1]], [high, lastPort], [high, thisPort], TRUE] THEN ERROR;
};
IF lastPort # NIL THEN {
EnumerateInstances[act, ConnectInstance];
EnumerateArrays[act, ConnectArrayElts];
};
lastPort ← thisPort;
};
[] ← rootToPairs.Pairs[Export];
rootToPairs.Erase[];
}ENDLOOP ENDLOOP;
}};
j.ties[jgi] ← newTS;
FOR side: End IN End DO g2t[side].Erase[] ENDLOOP;
rfblSets.Enumerate[Transfer];
oldTS.Enumerate[Patch];
};
TrimArray: PUBLIC PROC [a: Array] = {
FOR d: Dim IN Dim DO
FOR ff: NAT IN [0 .. a.jointsPeriod[Foo]) DO FOR fb: NAT IN [0 .. a.jointsPeriod[Bar]) DO
phase: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase];
FOR jgi: NAT IN [0 .. j.ties.length) DO
ties: Set--of Tie-- = NARROW[j.ties[jgi]];
PruneTie: PROC [ra: REF ANY] = {
tie: Tie = NARROW[ra];
IF tie.completion = NIL AND (tie.groups[low] = NIL OR tie.groups[high] = NIL) THEN DeleteTie[j, jgi, tie];
};
ties.Enumerate[PruneTie];
ENDLOOP;
ENDLOOP ENDLOOP;
ENDLOOP;
FOR d: Dim IN Dim DO
FOR index: NAT IN [0 .. a.roles[d].length) DO
rpd: RoledPortData = NARROW[a.roles[d].refs[index]];
IF rpd.links # NIL AND NOT RPDNeedsLinks[a, d, rpd] THEN rpd.links ← NIL;
ENDLOOP;
ENDLOOP;
};
END.