DIRECTORY
CD, CDCells, CDRects, CoreProperties, GC, GCPrivate, GCCIG, D2Basic, HashTable, IP, IPCoTab, IPCTG, IPTop, RTBasic, RTStructure, Graphs0, Graphs0Path;
GCCIGImpl:
CEDAR
PROGRAM
IMPORTS CDCells, CDRects, CoreProperties, GC, GCPrivate, HashTable, IPCoTab, IPCTG, RTBasic, RTStructure, Graphs0, Graphs0Path
EXPORTS GCCIG
RefINT: TYPE = REF INT;
IntersectionInfo: TYPE = REF IntersectionInfoRec;
IntersectionInfoRec:
TYPE =
RECORD[
-- Info for intersection nodes
hCh, vCh: IPCTG.Channel ← NIL, -- Channels for this node
intersection: IPCTG.Intersection ← NIL -- Intersection for this node
];
PinInfo: TYPE = REF PinInfoRec;
PinInfoRec:
TYPE =
RECORD[
-- Info for pin nodes
instance: RTStructure.Instance ← NIL,
oPin: RTStructure.ObjectPin ← NIL,
pPin: RTStructure.PhysicalPin ← NIL,
removedArc: Graphs0.Arc ← NIL
];
ArcInfo: TYPE = REF ArcInfoRec;
ArcInfoRec:
TYPE =
RECORD[
-- Info for pin nodes
cost: INT ← 0,
ch: IPCTG.Channel ← NIL
];
Create:
PUBLIC
PROC[context:
GC.Context]
RETURNS[cig:
GCCIG.Graph]={
ConnectHorizontalChannel:
IPCTG.EachChannelAction ={
EachIntersection:
IPCTG.EachIntersectionAction ={
lastNode ← NewArc[cig, ch, i, lastNode];
}; --EachIntersection--
lastInt: IPCTG.Intersection ← IPCTG.End[ch, neg];
lastNode: Graphs0.Node ← Graphs0.AddNewNode[cig.graph, NEW[IntersectionInfoRec ← [hCh: ch, vCh: lastInt.ch, intersection: lastInt]]];
lastInt.any ← lastNode;
[] ← AllIntersections[ch, EachIntersection];
[] ← NewArc[cig, ch, IPCTG.End[ch, pos], lastNode];
}; --CreateIntersectionsForChannel--
ConnectVerticalChannel:
IPCTG.EachChannelAction ={
EachIntersection:
IPCTG.EachIntersectionAction ={
currentNode: Graphs0.Node ← NARROW[OppsiteInt[ch, i].any];
[] ← Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, currentNode, ch], lastNode, currentNode];
lastNode ← currentNode;
}; --EachIntersection--
lastNode: Graphs0.Node ← NARROW[OppsiteInt[ch, IPCTG.End[ch, neg]].any];
posNode: Graphs0.Node ← NARROW[OppsiteInt[ch, IPCTG.End[ch, pos]].any];
[] ← AllIntersections[ch, EachIntersection];
[] ← Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, posNode, ch], lastNode, posNode];
}; --CreateIntersectionsForChannel--
graph: Graphs0.Graph ← Graphs0.Create[];
ctg: IPCTG.Ref ← NARROW[context.topology, IPTop.Ref].ctg;
cig ← NEW[GCCIG.GraphRec ← [context: context, graph: graph]];
[] ← IPCTG.DirectedChannels[ctg, ConnectHorizontalChannel, hor];
[] ← IPCTG.DirectedChannels[ctg, ConnectVerticalChannel, ver];
}; -- Create --
Destroy:
PUBLIC
PROC [cig:
GCCIG.Graph] ={
Graphs0.Destroy[cig.graph]}; -- Destroy --
InsertNet:
PUBLIC
PROC[cig:
GCCIG.Graph, net: RTStructure.Net, connectionStrength:
GCCIG.ConnectionStrength]
RETURNS [nodeSetList:
GCCIG.NodeSetList ←
NIL]~ {
Add the net to cig.
EachPin: RTStructure.EachNetPinAction ~ {
pinNodes: GCCIG.NodeList ← InsertPin[cig, net, nPin];
IF pinNodes #
NIL
THEN {
SELECT connectionStrength
FROM
goodInternal => {
FOR list:
GCCIG.NodeList ← pinNodes, list.rest
WHILE list #
NIL
DO
firstNode: Graphs0.Node ← list.first;
IF list.rest #
NIL
THEN {
secondNode: Graphs0.Node ← list.rest.first;
[] ← Graphs0.AddNewArc[cig.graph, NEW[ArcInfoRec ← [cost: 0, ch: NIL]], firstNode, secondNode]};
ENDLOOP;
nodeSetList ← CONS[pinNodes, nodeSetList]};
power => {
FOR list:
GCCIG.NodeList ← pinNodes, list.rest
WHILE list #
NIL
DO
nodes: GCCIG.NodeList ←NIL;
nodeSetList ← CONS[CONS[list.first, nodes], nodeSetList];
ENDLOOP};
highImpedance => nodeSetList ← CONS[pinNodes, nodeSetList];
ENDCASE => GC.Error[programmingError, "Not suppose to happen"]}};
[] ← RTStructure.EnumerateNetPins[net, EachPin];
}; -- InsertNet --
RemoveNodes:
PUBLIC
PROC[cig:
GCCIG.Graph, nodeSetList:
GCCIG.NodeSetList] ~ {
Remove a net from cig
FOR nodeSets:
GCCIG.NodeSetList ← nodeSetList, nodeSets.rest
WHILE nodeSets #
NIL
DO
FOR nodes:
GCCIG.NodeList ← nodeSets.first, nodes.rest
WHILE nodes #
NIL
DO
node: Graphs0.Node ← nodes.first;
WITH node.nodeInfo
SELECT
FROM
int: IntersectionInfo => NULL;
pin: PinInfo => {
arcs: Graphs0.ArcList ← Graphs0.RemoveNode[cig.graph, node];
oldArc: Graphs0.Arc ← NARROW[node.nodeInfo, PinInfo].removedArc;
FOR list: Graphs0.ArcList ← arcs, list.rest
WHILE list #
NIL
DO
IF list.first.node1 # node
AND list.first.node2 # node
THEN
GC.Error[programmingError, "Not suppose to happen."];
ENDLOOP;
[] ← Graphs0.AddNewArc[cig.graph, oldArc.arcInfo, oldArc.node1, oldArc.node2]};
ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
ENDLOOP;
ENDLOOP;
}; -- RemoveNodes --
ShortestPath:
PUBLIC
PROC[cig:
GCCIG.Graph, nodeSetList:
GCCIG.NodeSetList, net: RTStructure.Net] ~ {
Find shortest path among pins of net
arcCost: Graphs0Path.ArcCostProc ~ {
cost ← NARROW[arc.arcInfo, ArcInfo].cost};
arcTraversed: Graphs0Path.EnumArcProc ~ {
arcInfo: ArcInfo ← NARROW[arc.arcInfo];
ch: IPCTG.Channel ← NARROW[arcInfo.ch];
IF ch #
NIL
THEN {
DoNode:
PROC [node:
GCCIG.Node] ~ {
WITH node.nodeInfo
SELECT
FROM
int: IntersectionInfo => {
IF EndOfCh[ch, int, neg] THEN netDesc.bottomOrLeftExit ← TRUE;
IF EndOfCh[ch, int, pos] THEN netDesc.topOrRightExit ← TRUE};
pin: PinInfo => {
phyPin: GCPrivate.PhyPinDesc ← NEW[GCPrivate.PhyPinDescRec ← [pin.instance, pin.oPin, pin.pPin]];
IF ~GCPrivate.PinOnList[netDesc, phyPin]
THEN
netDesc.pinList ← CONS[phyPin, netDesc.pinList]};
ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
};
channel: GCPrivate.Channel ← NARROW[ch.any];
value: REF ANY ← HashTable.Fetch[channel.connections, net].value;
netDesc: GCPrivate.NetDesc ←
IF value =
NIL
THEN
NEW[GCPrivate.NetDescRec]
ELSE NARROW[value];
DoNode[arc.node1];
DoNode[arc.node2];
[] ← HashTable.Store[channel.connections, net, netDesc]}};
[] ← Graphs0Path.FindPath[graph: cig.graph, nodeSets: nodeSetList, arcCostProc: arcCost, arcDeliverProc: arcTraversed]};
Check:
PUBLIC
PROC [cig:
GCCIG.Graph] ={
Graphs0.Check[cig.graph]}; -- Check--
PaintShortestPath:
PUBLIC
PROC[cig:
GCCIG.Graph, nodeSetList:
GCCIG.NodeSetList]
RETURNS [object:
CD.Object] ~ {
Find shortest path among nodeSetList and construct a ChipNDale object
arcCost: Graphs0Path.ArcCostProc ~ {
cost ← NARROW[arc.arcInfo, ArcInfo].cost};
arcTraversed: Graphs0Path.EnumArcProc ~ {
layer: CD.Layer ← cig.context.rules.vertRules.branchLayer;
MakeCDArc[arc, object, layer]};
object ← PaintGraph[cig];
[] ← Graphs0Path.FindPath[graph: cig.graph, nodeSets: nodeSetList, arcCostProc: arcCost, arcDeliverProc: arcTraversed]};
PaintGraph:
PUBLIC
PROC [cig:
GCCIG.Graph]
RETURNS [object:
CD.Object ← CDCells.CreateEmptyCell[]] ~ {
EachNode: Graphs0.EnumNodeProc ~ {
layer: CD.Layer ← cig.context.rules.horizRules.trunkLayer;
MakeCDNode[node, object, layer]};
EachArc: Graphs0.EnumArcProc ~ {
layer: CD.Layer ← cig.context.rules.vertRules.trunkLayer;
MakeCDArc[arc, object, layer]};
[] ← Graphs0.EnumNodes[cig.graph, EachNode];
[] ← Graphs0.EnumArcs[cig.graph, EachArc];
RTBasic.RepositionCell[object]};
Internal Procedures
InsertPin:
PROC[cig:
GCCIG.Graph, net: RTStructure.Net, nPin: RTStructure.NetPin]
RETURNS [pinNodes:
GCCIG.NodeList ←
NIL] ~ {
Add the pin to cig.
IF nPin.oPin.heirarchyLevel = this
THEN {
this is an internal (private) pin
InsertPhysicalPin: RTStructure.EachPhysicalPinAction ~ {
PROC [oPin: ObjectPin, pPin: PhysicalPin] RETURNS [quit: BOOLEAN ← FALSE];
oldArc: Graphs0.Arc ← FindArcForPin[cig, nPin.instance, oPin, pPin];
arcInfo: ArcInfo ← NARROW[oldArc.arcInfo];
newNode: Graphs0.Node ← Graphs0.AddNewNode[cig.graph, NEW[PinInfoRec ← [instance: nPin.instance, oPin: oPin, pPin: pPin, removedArc: oldArc]]];
pinNodes ← CONS[newNode, pinNodes];
[] ← Graphs0.AddNewArc[cig.graph, ArcWeight[oldArc.node1, newNode, arcInfo.ch], oldArc.node1, newNode];
[] ← Graphs0.AddNewArc[cig.graph, ArcWeight[newNode, oldArc.node2, arcInfo.ch], newNode, oldArc.node2];
Graphs0.RemoveArc[cig.graph, oldArc]};
[] ← RTStructure.EnumeratePhysicalPins[nPin.oPin, InsertPhysicalPin]}
ELSE {
this is a public pin
EachNode: Graphs0.EnumNodeProc ~ {
WITH node.nodeInfo
SELECT
FROM
int: IntersectionInfo => {
useThisOne:
BOOLEAN ←
SELECT side
FROM
bottom => int.hCh = bottomChannel,
right => int.vCh = rightChannel,
top => int.hCh = topChannel,
left => int.vCh = leftChannel,
ENDCASE => FALSE;
IF useThisOne
AND ~MemberNode[node, pinNodes]
THEN
pinNodes ← CONS[node, pinNodes]};
pin: PinInfo => NULL;
ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."]};
sideProp: ATOM ← NARROW[CoreProperties.GetProp[net.properties, GC.sideProp]];
side: RTBasic.SideOrNone ← GetSide[sideProp];
topology: IPTop.Ref ← NARROW[cig.context.topology];
bottomChannel, rightChannel, topChannel, leftChannel: IPCTG.Channel;
[bottomChannel, rightChannel, topChannel, leftChannel] ← IPCTG.GetBoundingChannels[topology.ctg];
IF ~FacesSide[cig, net, side] THEN [] ← Graphs0.EnumNodes[cig.graph, EachNode]}}; -- InsertPin --
ArcWeight:
PROC [node1, node2: Graphs0.Node, ch:
IPCTG.Channel]
RETURNS [arcInfo: ArcInfo] ~ {
arcInfo ← NEW[ArcInfoRec ← [cost: ABS[PQPosOfNode[node1, ch.type].p - PQPosOfNode[node2, ch.type].p], ch: ch]]};
NewArc:
PROC [cig:
GCCIG.Graph, hCh:
IPCTG.Channel, int:
IPCTG.Intersection, lastNode: Graphs0.Node]
RETURNS [currentNode: Graphs0.Node]~ {
currentNode ← Graphs0.AddNewNode[cig.graph, NEW[IntersectionInfoRec ← [hCh: hCh, vCh: int.ch, intersection: int]]];
int.any ← currentNode;
[] ← Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, currentNode, hCh], lastNode, currentNode]};
AllIntersections:
PROC [ch:
IPCTG.Channel, p:
IPCTG.EachIntersectionAction]
RETURNS [quit:
BOOL] ~ {
Wrap:
IPCTG.EachIntersectionAction ~ {
IF i.type = 1 THEN quit ← p[i]};
quit ← IPCTG.Intersections[ch, neg, p]; -- enumerate all below and crossing intersections
IF ~quit THEN quit ← IPCTG.Intersections[ch, pos, Wrap]; -- enumerate above intersections
};
FindArcForPin:
PROC [cig:
GCCIG.Graph, instance: RTStructure.Instance, oPin: RTStructure.ObjectPin, pPin: RTStructure.PhysicalPin]
RETURNS [foundArc: Graphs0.Arc ←
NIL] ~ {
ArcProc: Graphs0.EnumArcProc ~ {
node1: Graphs0.Node ← NARROW[arc.node1];
posNode1: INT ← PQPosOfNode[node1, ch.type].p;
node2: Graphs0.Node ← NARROW[arc.node2];
posNode2: INT ← PQPosOfNode[node2, ch.type].p;
arcCh: IPCTG.Channel ← NARROW[arc.arcInfo, ArcInfo].ch;
norm: BOOLEAN ← posNode1 <= pos AND pos <= posNode2;
rev: BOOLEAN ← posNode2 <= pos AND pos <= posNode1;
IF ch = arcCh AND (norm OR rev) THEN {quit ← TRUE; foundArc ← arc}
};
ch: IPCTG.Channel ← IPCoTab.GetPrinCh[NARROW[instance.any], SideToEdgeType[pPin.side]];
range: RTStructure.Range ← RTStructure.TranslateRange[instance, pPin];
pos: INT ← (range.min + range.max)/2;
IF ~Graphs0.EnumArcs[cig.graph, ArcProc]
THEN
GC.Error[programmingError, "Not suppose to happen."]};
SideToEdgeType:
PROC [side: RTBasic.Side]
RETURNS [et:
IP.EdgeTypes] ~ {
et ←
SELECT side
FROM
top => north,
left => west,
bottom => south,
right => east,
ENDCASE => GC.Error[programmingError, "Call maintainer"]};
OppsiteInt:
PROC [ch:
IPCTG.Channel, i:
IPCTG.Intersection]
RETURNS [oppsiteI:
IPCTG.Intersection] ~ {
find intersection on oppsite channel corresponding to this one
IntTest:
IPCTG.EachIntersectionAction ~ {
IF i.ch = ch THEN {oppsiteI ← i; quit ← TRUE}};
quit: BOOLEAN ← AllIntersections[i.ch, IntTest];
IF ~quit THEN quit ← IntTest[IPCTG.End[i.ch, neg]];
IF ~quit THEN quit ← IntTest[IPCTG.End[i.ch, pos]];
IF ~quit THEN GC.Error[programmingError, "Not suppose to happen."]};
PQPosOfNode:
PROC [node: Graphs0.Node, direction:
IP.ChType]
RETURNS [RTBasic.PQPos] ~ {
find position of node in direction
p, q: INT;
WITH node.nodeInfo
SELECT
FROM
int: IntersectionInfo =>
IF direction = hor
THEN {
p ← int.vCh.coord; q ← int.hCh.coord}
ELSE {
p ← int.hCh.coord; q ← int.vCh.coord};
pin: PinInfo => {
range: RTStructure.Range ← RTStructure.TranslateRange[pin.instance, pin.pPin];
ch: IPCTG.Channel ← IPCoTab.GetPrinCh[NARROW[pin.instance.any], SideToEdgeType[pin.pPin.side]];
p ← (range.min + range.max)/2; q ← ch.coord};
ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
RETURN[[p, q]]};
PosOfNode:
PROC [node: Graphs0.Node]
RETURNS [D2Basic.Vector] ~ {
find position of node
x, y: INT;
WITH node.nodeInfo
SELECT
FROM
int: IntersectionInfo => {x ← int.vCh.coord; y ← int.hCh.coord};
pin: PinInfo => {
range: RTStructure.Range ← RTStructure.TranslateRange[pin.instance, pin.pPin];
middle: INT ← (range.min + range.max)/2;
ch: IPCTG.Channel ← IPCoTab.GetPrinCh[NARROW[pin.instance.any], SideToEdgeType[pin.pPin.side]];
IF ch.type = hor THEN {x ← middle; y ← ch.coord}
ELSE {x ← ch.coord; y ← middle}};
ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
RETURN[[x, y]]};
Length:
PUBLIC
PROC [nodeSetList:
GCCIG.NodeSetList]
RETURNS[n:
INT ← 0] = {
UNTIL nodeSetList =
NIL
DO
n ← n+1;
nodeSetList ← nodeSetList.rest;
ENDLOOP};
EndOfCh:
PROC [ch:
IPCTG.Channel, int: IntersectionInfo, pol:
IP.PolarityTypes]
RETURNS [found:
BOOLEAN ←
FALSE] ~ {
RETURN TRUE if node is at end co ch represented by pol
trial: IPCTG.Channel ← IF ch.type = hor THEN int.vCh ELSE int.hCh;
IF trial = IPCTG.End[ch, pol].ch THEN found ← TRUE};
MemberNode:
PROC [node:
GCCIG.Node, list:
GCCIG.NodeList]
RETURNS [
BOOL] = {
UNTIL list =
NIL
DO
IF list.first = node THEN RETURN[TRUE];
list ← list.rest;
ENDLOOP;
RETURN[FALSE]};
MakeCDNode:
PROC [node: Graphs0.Node, object:
CD.Object, nodeLayer:
CD.Layer] ~ {
size: D2Basic.Vector ← [8, 8];
pos: D2Basic.Vector ← PosOfNode[node];
nodeObj: CD.Object ← CDRects.CreateRect[size, nodeLayer];
[] ← GCPrivate.IncludeOb[object, nodeObj, [pos.x - size.x/2, pos.y - size.y/2]]};
MakeCDArc:
PROC [arc: Graphs0.Arc, object:
CD.Object, arcLayer:
CD.Layer] ~ {
width: INT ← 4;
pos1: D2Basic.Vector ← PosOfNode[arc.node1];
pos2: D2Basic.Vector ← PosOfNode[arc.node2];
xDim: INT ← MAX[ABS[pos1.x - pos2.x], width];
yDim: INT ← MAX[ABS[pos1.y - pos2.y], width];
arcObj: CD.Object ← CDRects.CreateRect[[xDim, yDim], arcLayer];
pos: D2Basic.Vector ←
IF pos1.x = pos2.x
THEN [pos1.x - width/2,
MIN[pos1.y, pos2.y]]
ELSE IF pos1.y = pos2.y THEN [MIN[pos1.x, pos2.x], pos1.y - width/2]
ELSE [MIN[pos1.x, pos2.x], MIN[pos1.y, pos2.y]];
[] ← GCPrivate.IncludeOb[object, arcObj, pos]};
FacesSide:
PROC [cig:
GCCIG.Graph, net: RTStructure.Net, side: RTBasic.SideOrNone]
RETURNS [faces:
BOOLEAN] ~ {
RETURNS TRUE iff this net has a physical pin on a boundry for the higher level cell
EachNetPin: RTStructure.EachNetPinAction ~ {
EachPhysicalPin: RTStructure.EachPhysicalPinAction ~ {
PROC [oPin: ObjectPin, pPin: PhysicalPin] RETURNS [quit: BOOLEAN ← FALSE];
ch: IPCTG.Channel ← IPCoTab.GetPrinCh[NARROW[nPin.instance.any], SideToEdgeType[pPin.side]];
IF
IPCTG.IsBoundingChannel[topology.ctg, ch]
THEN {
quit ← IF side = none THEN quit ← TRUE ELSE pPin.side = side}};
quit ← RTStructure.EnumeratePhysicalPins[nPin.oPin, EachPhysicalPin]};
topology: IPTop.Ref ← NARROW[cig.context.topology];
faces ← RTStructure.EnumerateNetPins[net, EachNetPin]};
GetSide:
PROC [atom:
ATOM]
RETURNS [side: RTBasic.SideOrNone] ~ {
side ←
SELECT atom
FROM
GC.bottomSideValue => bottom,
GC.rightSideValue => right,
GC.topSideValue => top,
GC.leftSideValue => left,
ENDCASE => none};
END.