GCCIGImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last Edited by: Preas, January 15, 1987 11:46:11 am PST
Don Curry December 4, 1987 4:18:30 pm PST
Provide operations on a channel intersection graph
DIRECTORY
CD, CDCells, CDRects, DABasics, GC, GCPrivate, GCCIG, IP, IPCoTab, IPCTG, IPTop, RefTab, RTBasic, CoreRouteFlat, Graphs0, Graphs0Path;
GCCIGImpl:
CEDAR
PROGRAM
IMPORTS CDCells, CDRects, GC, GCPrivate, IPCoTab, IPCTG, RefTab, RTBasic, CoreRouteFlat, Graphs0, Graphs0Path
EXPORTS GCCIG
SHARES GC = BEGIN
IntersectionInfo: TYPE = REF IntersectionInfoRec;
IntersectionInfoRec:
TYPE =
RECORD[
-- Info for intersection nodes
hCh: IPCTG.Channel ← NIL, -- Channels for this node
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: CoreRouteFlat.Instance ← NIL,
oNode: CoreRouteFlat.ONode ← NIL,
pPin: CoreRouteFlat.Pin ← [ ],
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]};
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]};
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};
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]};
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]};
Destroy:
PUBLIC
PROC [cig:
GCCIG.Graph] = {Graphs0.Destroy[cig.graph]};
InsertNet:
PUBLIC
PROC
[cig:
GCCIG.Graph, net: CoreRouteFlat.Net, connectionStrength:
GCCIG.ConnectionStrength]
RETURNS [nodeSetList: GCCIG.NodeSetList ← NIL] ~ {
Add the net to cig.
FOR ins:
LIST
OF CoreRouteFlat.InstONode ← net.instONodes, ins.rest
WHILE ins#
NIL
DO
pinNodes: GCCIG.NodeList ← InsertPin[cig, net, ins.first];
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"]}
ENDLOOP};
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: CoreRouteFlat.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.oNode, 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];
val: REF ANY ← RefTab.Fetch[channel.connections, net].val;
netDesc: GCPrivate.NetDesc ←
IF val =
NIL
THEN NEW[GCPrivate.NetDescRec]
ELSE NARROW[val];
DoNode[arc.node1];
DoNode[arc.node2];
[] ← RefTab.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: CoreRouteFlat.Net, instONode: CoreRouteFlat.InstONode]
RETURNS [pinNodes: GCCIG.NodeList ← NIL] ~ {
Add the pin to cig.
IF instONode.oNode.public
THEN {
-- this is a public object node
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."]};
side: DABasics.Side;
bottomChannel, rightChannel, topChannel, leftChannel: IPCTG.Channel;
FOR side
IN DABasics.Side
DO
topology: IPTop.Ref ← NARROW[cig.context.topology];
IF ~ParentFacesSide[net, side] THEN LOOP;
[bottomChannel, rightChannel, topChannel, leftChannel] ←
IPCTG.GetBoundingChannels[topology.ctg];
IF ~ChildrenFaceSide[cig, net, side]
THEN
[] ← Graphs0.EnumNodes[cig.graph, EachNode];
If the children don't face the side then channel intersection nodes must be sources and targets in the shortest path search.
ENDLOOP}
ELSE
FOR pins:
LIST
OF CoreRouteFlat.Pin ← instONode.oNode.pins, pins.rest
WHILE pins#
NIL
DO
oldArc: Graphs0.Arc ← FindArcForPin[cig, instONode.instance, pins.first];
arcInfo: ArcInfo ← NARROW[oldArc.arcInfo];
newNode: Graphs0.Node ← Graphs0.AddNewNode[cig.graph,
NEW[PinInfoRec ← [
instance: instONode.instance,
oNode: instONode.oNode,
pPin: pins.first,
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] ENDLOOP}; -- InsertPin --
ParentFacesSide:
PROC [net: CoreRouteFlat.Net, side: DABasics.Side]
RETURNS [faces:
BOOLEAN ←
FALSE] ~ {
FOR ins:
LIST
OF CoreRouteFlat.InstONode ← net.instONodes, ins.rest
WHILE ins#
NIL
DO
IF ~ins.first.oNode.public THEN LOOP;
FOR pins:
LIST
OF CoreRouteFlat.Pin ← ins.first.oNode.pins, pins.rest
WHILE pins#
NIL
DO
IF pins.first.side = side THEN RETURN[TRUE] ENDLOOP ENDLOOP};
ChildrenFaceSide:
PROC [cig:
GCCIG.Graph, net: CoreRouteFlat.Net, side: DABasics.Side]
RETURNS [faces: BOOLEAN ← FALSE] ~ {
RETURNS TRUE iff this net has a physical pin on a boundry for the higher level cell
topology: IPTop.Ref ← NARROW[cig.context.topology];
FOR ins:
LIST
OF CoreRouteFlat.InstONode ← net.instONodes, ins.rest
WHILE ins#
NIL
DO
IF ins.first.oNode.public THEN LOOP;
FOR pins:
LIST
OF CoreRouteFlat.Pin ← ins.first.oNode.pins, pins.rest
WHILE pins#
NIL
DO
ch:
IPCTG.Channel ← IPCoTab.GetPrinCh
[NARROW[ins.first.instance.any], SideToEdgeType[pins.first.side]];
IF IPCTG.IsBoundingChannel[topology.ctg, ch] THEN
IF pins.first.side = side THEN RETURN[TRUE] ENDLOOP ENDLOOP};
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: CoreRouteFlat.Instance, pin: CoreRouteFlat.Pin]
RETURNS [foundArc: Graphs0.Arc ← NIL] ~ {
ArcProc: Graphs0.EnumArcProc ~ {
arcCh: IPCTG.Channel ← NARROW[arc.arcInfo, ArcInfo].ch;
node1: Graphs0.Node ← NARROW[arc.node1];
node2: Graphs0.Node ← NARROW[arc.node2];
posNode1: INT ← PQPosOfNode[node1, ch.type].p;
posNode2: INT ← PQPosOfNode[node2, ch.type].p;
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[pin.side]];
range: CoreRouteFlat.Range ← CoreRouteFlat.TranslateRange[instance, pin];
pos: INT ← (range.min + range.max)/2;
IF ~Graphs0.EnumArcs[cig.graph, ArcProc]
THEN
GC.Error[programmingError, "Not suppose to happen."]};
SideToEdgeType:
PROC [side: DABasics.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: CoreRouteFlat.Range ← CoreRouteFlat.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 [DABasics.Position] ~ {
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: CoreRouteFlat.Range ← CoreRouteFlat.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] ~ { -- TRUE if node is at end of 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: DABasics.Position ← [8, 8];
pos: DABasics.Position ← 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: DABasics.Position ← PosOfNode[arc.node1];
pos2: DABasics.Position ← 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: DABasics.Position ←
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]};
END.