TilingImpl.mesa
Copyright Ó 1986, 1987, 1988 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet on September 19, 1986 1:48:15 pm PDT
Bertrand Serlet May 9, 1988 0:03:18 am PDT
Barth, October 16, 1986 6:39:20 pm PDT
Jean-Marc Frailong January 17, 1988 9:33:06 pm PST
DIRECTORY
Core, CoreClasses, CoreCreate, CoreOps, CoreProperties,
GList,
PatchWork,
Pipal, PipalCore, PipalInt, PipalMos,
RefTab, Tiling;
TilingImpl:
CEDAR
PROGRAM
IMPORTS CoreClasses, CoreCreate, CoreOps, CoreProperties, GList, PatchWork, PipalCore, PipalInt, PipalMos, RefTab
EXPORTS Tiling
~ BEGIN OPEN Tiling;
Conveniences
CellType : TYPE = Core.CellType;
Properties : TYPE = Core.Properties;
ROPE: TYPE = Core.ROPE;
Wire: TYPE = Core.Wire;
WireSeq: TYPE = Core.WireSeq;
Wires: TYPE = Core.Wires;
PA: TYPE = CoreCreate.PA;
WR: TYPE = CoreCreate.WR;
Object: TYPE = Pipal.Object;
Utilities
PubActs: TYPE = REF PubActsRec;
PubActsRec:
TYPE =
RECORD [pubActs:
SEQUENCE size:
NAT
OF
RECORD [pub, act: Wire]];
PutTilePubActs:
PROC [tile: Tile, pubs, acts: Wires] = {
size: NAT ← GList.Length[pubs];
seq: PubActs ← NEW [PubActsRec[size]];
IF size#GList.Length[acts] THEN ERROR;
FOR i:
NAT
IN [0 .. size)
DO
seq[i] ← [pub: pubs.first, act: acts.first];
pubs ← pubs.rest; acts ← acts.rest;
ENDLOOP;
tile.properties ← CoreProperties.PutProp[tile.properties, $TilingClassPubActs, seq];
};
GetTilePubActs:
PROC [tile: Tile]
RETURNS [seq: PubActs] = {
seq ← NARROW [CoreProperties.GetProp[tile.properties, $TilingClassPubActs]];
};
PutTileInstance:
PROC [tile: Tile, instance: CoreClasses.CellInstance] = {
tile.properties ← CoreProperties.PutProp[tile.properties, $TilingClassInstance, instance];
};
GetTileInstance:
PROC [tile: Tile]
RETURNS [instance: CoreClasses.CellInstance] = {
RETURN [NARROW [CoreProperties.GetProp[tile.properties, $TilingClassInstance]]];
};
Replace:
PROC [fused: RefTab.Ref, old: Wire]
RETURNS [new: Wire] = {
new ← RootWire[fused, old];
FOR i: NAT IN [0 .. old.size) DO new[i] ← Replace[fused, old[i]] ENDLOOP;
};
RootWire:
PROC [fused: RefTab.Ref, wire: Wire]
RETURNS [root: Wire] = {
root ← NARROW [RefTab.Fetch[fused, wire].val];
IF root=NIL THEN RETURN [wire];
IF root=wire THEN ERROR;
root ← RootWire[fused, root];
[] ← RefTab.Replace[fused, wire, root];
};
Fuse:
PROC [fused: RefTab.Ref, wire1, wire2: Wire] = {
root1: Wire = RootWire[fused, wire1];
root2: Wire = RootWire[fused, wire2];
IF root1=root2 THEN RETURN;
IF root1.size#root2.size THEN ERROR;
[] ← RefTab.Store[fused, root1, root2];
FOR i: NAT IN [0 .. root1.size) DO Fuse[fused, root1[i], root2[i]] ENDLOOP;
};
FuseNeighbors:
PROC [neighbor: NeighborProc, tile1, tile2: Tile, fused: RefTab.Ref] = {
ct1: CellType = tile1.type;
ct2: CellType = tile2.type;
FOR list:
LIST
OF PipalCore.WirePair ← neighbor[ct1, ct2], list.rest
WHILE list#
NIL
DO
Fuse[fused, CoreClasses.CorrespondingActual[GetTileInstance[tile1], list.first.wire1], CoreClasses.CorrespondingActual[GetTileInstance[tile2], list.first.wire2]];
ENDLOOP;
};
CreateActual:
PROC [subPublicToActual: RefTab.Ref, public: WireSeq]
RETURNS [actual: WireSeq] = {
actual ← NARROW [RefTab.Fetch[subPublicToActual, public].val];
IF actual#NIL THEN RETURN;
actual ← CoreOps.CreateWires[size: public.size];
[] ← RefTab.Store[subPublicToActual, public, actual];
FOR i:
NAT
IN [0 .. public.size)
DO
actual[i] ← CreateActual[subPublicToActual, public[i]];
ENDLOOP;
};
CreateInstance:
PROC [public: WireSeq, tile: Tile, xindex, yindex:
NAT]
RETURNS [instance: CoreClasses.CellInstance]= {
subPublicToActual: RefTab.Ref = RefTab.Create[];
actual: WireSeq = CoreOps.CreateWires[size: tile.type.public.size];
make a simpler renaming table [public of tile -> public of me.public]
FOR list:
LIST
OF
PA ← tile.renaming, list.rest
WHILE list#
NIL
DO
pub: Wire = CoreCreate.FindWire[tile.type.public, list.first.public];
act: Wire = CoreCreate.FindWire[public, list.first.actual];
IF pub=NIL OR act=NIL THEN ERROR; -- bad renaming list
[] ← RefTab.Store[subPublicToActual, pub, act];
ENDLOOP;
FOR i:
NAT
IN [0 .. tile.type.public.size)
DO
actual[i] ← CreateActual[subPublicToActual, tile.type.public[i]];
ENDLOOP;
instance ← CoreClasses.CreateInstance[actual: actual, type: tile.type, props: CoreProperties.Props[[$TilingXIndex, NEW [NAT ← xindex]], [$TilingYIndex, NEW [NAT ← yindex]]]];
};
Tiling
tilingClass:
PUBLIC Core.CellClass ←
NEW [Core.CellClassRec ← [name: "Tiling", recast: RecastTiling, layersProps:
FALSE, properties: CoreProperties.Props[[$Layout, $Recast]]]];
CreateTiling:
PUBLIC
PROC [public: WireSeq, tileArray: TileArray, neighborX, neighborY: NeighborProc, name:
ROPE ←
NIL, props: Properties ←
NIL]
RETURNS [tiling: CellType] = {
tiling ← CoreOps.CreateCellType[
class: tilingClass,
public: public,
data: NEW [TilingDataRec ← [tileArray: tileArray, neighborX: neighborX, neighborY: neighborY]],
name: name, props: props
];
};
RecastTiling: Core.RecastProc = {
ReplaceAndAddToPublicHT:
PROC [old: Wire]
RETURNS [new: Wire] ~ {
new ← RootWire[fused, old];
[] ← RefTab.Insert[publicHT, new, NIL];
FOR i: NAT IN [0 .. old.size) DO new[i] ← ReplaceAndAddToPublicHT[old[i]] ENDLOOP;
};
tilingData: TilingData = NARROW [me.data];
public: WireSeq = CoreOps.CopyWire[me.public];
fused: RefTab.Ref = CoreOps.CreateBindingTable[me.public, public]; -- keys are fused to values
tiles: TileArray = tilingData.tileArray;
sizeX: NAT = tiles[0].size;
sizeY: NAT = tiles.size;
internalsOnly: Wires ← NIL;
instances: LIST OF CoreClasses.CellInstance ← NIL;
publicHT: RefTab.Ref ← RefTab.Create[]; --used as a speedup to CoreOps.RecursiveMember[public, wire]
Create instances (even with not the right wires yet)
FOR i:
NAT
IN [0 .. sizeY)
DO
IF tiles[i].size#sizeX THEN ERROR;
FOR j:
NAT
IN [0 .. sizeX)
DO
tile: Tile = tiles[i][j];
instance: CoreClasses.CellInstance ← CreateInstance[me.public, tile, j, i];
IF NOT CoreOps.CorrectConform[instance.actual, instance.type.public] THEN ERROR;
PutTileInstance[tile, instance];
instances ← CONS [instance, instances];
ENDLOOP;
ENDLOOP;
Find who to fuse, first progressing in rows
FOR i:
NAT
IN [0 .. sizeY)
DO
FOR j:
NAT
IN [1 .. sizeX)
DO
FuseNeighbors[tilingData.neighborX, tiles[i][j-1], tiles[i][j], fused];
ENDLOOP;
ENDLOOP;
Find who to fuse, progressing in columns
FOR j:
NAT
IN [0 .. sizeX)
DO
FOR i:
NAT
IN [1 .. sizeY)
DO
FuseNeighbors[tilingData.neighborY, tiles[i-1][j], tiles[i][j], fused];
ENDLOOP;
ENDLOOP;
Replace the public and note all public wires in publicHT
FOR i:
NAT
IN [0 .. public.size)
DO
public[i] ← ReplaceAndAddToPublicHT[public[i]];
ENDLOOP;
Replace in instances the actuals
FOR list:
LIST
OF CoreClasses.CellInstance ← instances, list.rest
WHILE list#
NIL
DO
instance: CoreClasses.CellInstance = list.first;
instance.actual ← Replace[fused, instance.actual];
IF NOT CoreOps.Conform[instance.actual, instance.type.public] THEN ERROR; -- the tiles shorts parts of the public together
Compute the internal only wires
FOR k:
NAT
IN [0 .. instance.actual.size)
DO
wire: Wire = instance.actual[k];
IF NOT RefTab.Fetch[publicHT, wire].found AND NOT CoreOps.Member[internalsOnly, wire] THEN internalsOnly ← CONS [wire, internalsOnly];
ENDLOOP;
ENDLOOP;
IF NOT CoreOps.Conform[public, me.public] THEN ERROR; -- the tiles shorts parts of the public together
-- Preparing the decoration by storing on each tile the list of publics which decorations should be offset and added and the list of corresponding actuals [part of public].
FOR i:
NAT
IN [0 .. sizeY)
DO
FOR j:
NAT
IN [0 .. sizeX)
DO
IF i=0
OR i=sizeY-1
OR j=0
OR j=sizeX-1
THEN {
tile: Tile = tiles[i][j];
pubs, acts: Wires ← NIL;
DecorateIfOutside:
PROC [pub: Wire] = {
act: Wire = RootWire[fused, CoreClasses.CorrespondingActual[GetTileInstance[tile], pub]];
IF act=NIL THEN ERROR;
IF NOT RefTab.Fetch[publicHT, act].found THEN RETURN;
IF CoreOps.Member[pubs, pub] THEN RETURN; -- already seen
pubs ← CONS [pub, pubs];
acts ← CONS [act, acts];
};
CoreOps.VisitRootAtomics[tile.type.public, DecorateIfOutside];
PutTilePubActs[tile, pubs, acts];
};
ENDLOOP;
ENDLOOP;
Cleanup
FOR i:
NAT
DECREASING
IN [0 .. sizeY)
DO
FOR j:
NAT
DECREASING
IN [0 .. sizeX)
DO
PutTileInstance[tiles[i][j], NIL];
ENDLOOP;
ENDLOOP;
new ← CoreClasses.CreateRecordCell[
public: public,
internal: CoreOps.UnionWire[public, CoreOps.CreateWire[internalsOnly]],
instances: instances,
name: CoreOps.GetCellTypeName[me],
props: CoreProperties.Props[[$Layout, $Tiling], [$Tiles, tiles]],
giveNames: TRUE
];
};
XYTile: PipalMos.XYTileProc = {
tiles: TileArray = NARROW [data];
RETURN [PatchWork.Layout[tiles[y][x].type]];
};
IJAbutBox:
PROC [tiles: TileArray, i, j:
NAT]
RETURNS [PipalInt.Rectangle] = {
RETURN [PipalInt.AbutBox[PatchWork.Layout[tiles[i][j].type]]];
};
LayoutTiling: PatchWork.LayoutProc = {
tiles: TileArray = NARROW [CoreProperties.GetCellTypeProp[cellType, $Tiles]];
sizeX: NAT = tiles[0].size;
sizeY: NAT = tiles.size;
We check that sizes of the IR verify the assumptions
FOR i:
NAT
IN [0 .. sizeY)
DO
height: INT = IJAbutBox[tiles, i, 0].size.y;
FOR j:
NAT
IN [1 .. sizeX)
DO
IF height#IJAbutBox[tiles, i, j].size.y THEN ERROR; -- assumption not verified
ENDLOOP;
ENDLOOP;
FOR j:
NAT
IN [0 .. sizeX)
DO
width: INT = IJAbutBox[tiles, 0, j].size.x;
FOR i:
NAT
IN [1 .. sizeY)
DO
IF width#IJAbutBox[tiles, i, j].size.x THEN ERROR; -- assumption not verified
ENDLOOP;
ENDLOOP;
obj ← PipalMos.CreateTiling[sizeX, sizeY, XYTile, tiles];
};
DecorateTiling: PatchWork.DecorateProc = {
tiles: TileArray = NARROW [CoreProperties.GetCellTypeProp[cellType, $Tiles]];
sizeX: NAT = tiles[0].size;
sizeY: NAT = tiles.size;
offset: PipalInt.Position ← PipalInt.zeroVector;
ir: PipalInt.Rectangle ← PipalInt.AbutBox[obj];
We tile and decorate
FOR i:
NAT
IN [0 .. sizeY)
DO
offset.x ← 0;
FOR j:
NAT
IN [0 .. sizeX)
DO
tile: Tile = tiles[i][j];
seq: PubActs = GetTilePubActs[tile];
IF seq#
NIL
THEN
FOR i:
NAT
IN [0 .. seq.size)
DO
trans: PipalInt.Transformation = [PipalInt.Sub[offset, IJAbutBox[tiles, i, j].base]];
pubPort: Object ← PipalCore.GetPort[PipalCore.layoutDecoration, seq[i].pub];
IF pubPort#Pipal.void
THEN PipalCore.AddPort[
PipalCore.layoutDecoration,
seq[i].act,
PipalMos.CreateClipEnum[ir, PipalInt.TransformObject[trans, pubPort]]
];
ENDLOOP;
offset.x ← offset.x + IJAbutBox[tiles, i, j].size.x;
ENDLOOP;
offset.y ← offset.y + IJAbutBox[tiles, i, 0].size.y;
ENDLOOP;
};
Predefined NeighborProcs
cache: RefTab.Ref ← PipalCore.CreateNeighborsCache[];
LayoutNeighborX:
PUBLIC NeighborProc = {
[] ← PatchWork.Layout[ct1]; -- to make sure the cellType is decorated
[] ← PatchWork.Layout[ct2]; -- to make sure the cellType is decorated
publicPairs ← PipalCore.CachedEnumerateNeighbors[PipalCore.layoutDecoration, PipalMos.LayoutTouch, TRUE, ct1, ct2, cache];
};
LayoutNeighborY:
PUBLIC NeighborProc = {
[] ← PatchWork.Layout[ct1]; -- to make sure the cellType is decorated
[] ← PatchWork.Layout[ct2]; -- to make sure the cellType is decorated
publicPairs ← PipalCore.CachedEnumerateNeighbors[PipalCore.layoutDecoration, PipalMos.LayoutTouch, FALSE, ct1, ct2, cache];
};
SchematicsNeighborX:
PUBLIC NeighborProc ={
publicPairs ← PipalCore.CachedEnumerateNeighbors[PipalCore.schematicsDecoration, PipalMos.SchematicTouch, TRUE, ct1, ct2, cache];
};
SchematicsNeighborY:
PUBLIC NeighborProc ={
publicPairs ← PipalCore.CachedEnumerateNeighbors[PipalCore.schematicsDecoration, PipalMos.SchematicTouch, FALSE, ct1, ct2, cache];
};