[_CD4_]<datools7.0>PWRoute25>PWRouteImpl.mesa!3

PWRouteImpl.mesa

Copyright Ó 1985, 1986, 1987 by Xerox Corporation. All rights reversed.

Last Edited by: Preas, April 3, 1987 4:29:46 pm PST

DIRECTORY CD, CDBasics, CDCells, CDInstances, CDRects, CDSimpleRules, CDSymbolicObjects, GList, PW, PWPins, PWRoute, Rope, Route, RouteUtil, RTBasic, SymTab;

PWRouteImpl: CEDAR PROGRAM

IMPORTS CD, CDBasics, CDCells, CDInstances, CDRects, CDSimpleRules, CDSymbolicObjects, GList, PW, PWPins, Rope, Route, RouteUtil, RTBasic, SymTab

EXPORTS PWRoute =

BEGIN OPEN PWRoute;

-- AbutRoute: uses a channel router to connect adjacent objects

AbutRouteList: PROC [listOb, bottomOrLeftListOb, topOrRightListOb: PWRoute.Objects, params: RouterParams, isX: BOOL, routeType: RouteType]

RETURNS [obj: CD.Object] =

BEGIN

newListObj: PWRoute.Objects ← NIL;

obj1, obj2, topOrRightObj, bottomOrLeftObj, channel: CD.Object;

IF listOb = NIL THEN RETURN[NIL];

obj1 ← listOb.first; listOb ← listOb.rest;

newListObj ← CONS[obj1, NIL];

FOR l: PWRoute.Objects ← listOb, l.rest WHILE l # NIL DO

obj2 ← l.first;

IF topOrRightListOb = NIL THEN topOrRightObj ← NIL

ELSE {topOrRightObj ← topOrRightListOb.first;

topOrRightListOb ← topOrRightListOb.rest};

IF bottomOrLeftListOb = NIL THEN bottomOrLeftObj ← NIL

ELSE {bottomOrLeftObj ← bottomOrLeftListOb.first;

bottomOrLeftListOb ← bottomOrLeftListOb.rest};

channel ← MakeChannel[obj1, obj2, bottomOrLeftObj, topOrRightObj, NIL, params, isX, routeType];

newListObj ← CONS[obj2, CONS[channel, newListObj]];

obj1 ← obj2; -- just before looping

ENDLOOP;

newListObj ← Reverse[newListObj];

IF isX THEN obj ← PW.AbutListX[newListObj]

ELSE obj ← PW.AbutListY[newListObj];

END;

AbutChRouteListX: PUBLIC PROC [

listOb: PWRoute.Objects,

bottomListOb: PWRoute.Objects ← NIL,

topListOb: PWRoute.Objects ← NIL,

params: RouterParams ← defaultRouterParams]

RETURNS [obj: CD.Object] =

{obj ← AbutRouteList[listOb, bottomListOb, topListOb, params, TRUE, channel]};

AbutChRouteListY: PUBLIC PROC [

listOb: PWRoute.Objects,

leftListOb: PWRoute.Objects ← NIL,

rightListOb: PWRoute.Objects ← NIL,

params: RouterParams ← defaultRouterParams]

RETURNS [obj: CD.Object] =

{obj ← AbutRouteList[listOb, leftListOb, rightListOb, params, FALSE, channel]};

AbutSbRoute: PUBLIC PROC [

bottomOb, rightOb, topOb, leftOb: CD.Object ← NIL,

trunkDir: HorV ← horizontal,

params: RouterParams ← defaultRouterParams] RETURNS [obj: CD.Object] = {

IF trunkDir = horizontal THEN

obj ← MakeChannel[bottomOb, topOb, leftOb, rightOb, NIL, params, FALSE, switchBox]

ELSE

obj ← MakeChannel[leftOb, rightOb, bottomOb, topOb, NIL, params, TRUE, switchBox]};

-- Given two cells that we plan to abut, this module parses the corresponding edges, extract the pins, build nets according to the names on the pins, then calls the router to produce a cell containing the channel routing.

Net: TYPE = REF NetRec;

NetRec: TYPE = RECORD[

name: Rope.ROPE ← NIL, -- net name

pins: Route.PinList ← NIL]; -- the list of pins in the net

defaultRouterParams: PUBLIC RouterParams ← NEW[RouterParamsRec ← ["metal", "poly"]];

-- Gets all the pins on the edge; pack them into nets and put in the SymTab.Ref

ParsePins: PROC[obj: CD.Object, tab: SymTab.Ref, side: PWPins.Side, params: RouterParams] = {

EachPin: CDSymbolicObjects.InstEnumerator = {

[inst: CD.Instance] RETURNS [quit: BOOL ← FALSE]

IF PWPins.GetSide[obj, inst].side=side THEN InsertPin[tab, inst, side, params];

};

IF obj # NIL THEN [] ← PWPins.EnumerateEdgePins[obj, EachPin];

};

FromSideToSide: PROC [side: PWPins.Side] RETURNS [routeSide: Route.Side] = {

routeSide ← SELECT side FROM

left => left,

right => right,

top => top,

bottom => bottom,

ENDCASE => ERROR;

};

OtherSide: PROC [side: Route.Side] RETURNS [opposite: Route.Side] = {

opposite ← SELECT side FROM

left => right,

right => left,

top => bottom,

bottom => top,

ENDCASE => ERROR;

};

-- Group pins in net and insert in table

InsertPin: PROC [tab: SymTab.Ref, inst: CD.Instance, side: PWPins.Side, params: RouterParams] = {

found: BOOL;

val: REF;

net: Net;

pin: Route.Pin ← Route.CreatePin[inst, OtherSide[FromSideToSide[side]]];

pinName: Rope.ROPE ← CDSymbolicObjects.GetName[inst];

tabIndex: Rope.ROPE ← IF params.makeTabKeyProc=NIL THEN pinName ELSE params.makeTabKeyProc[inst, params.context];

[found, val] ← SymTab.Fetch[tab, tabIndex];

net ← IF ~found THEN NEW[NetRec ← [pinName]] ELSE NARROW[val];

net.pins ← CONS[pin, net.pins];

[] ← SymTab.Store[tab, tabIndex, net];

};

-- Read the table and ship the nets to the channel router

ShipNets: PROC [tab: SymTab.Ref, routingArea: Route.RoutingArea, trunkAtom: ATOM, params: RouterParams] = {

EnterOneNet: SymTab.EachPairAction =

BEGIN

netName: Rope.ROPE ← NARROW[key];

net: Net ← NARROW[val];

width: Route.Number ← IF params.wireWidthProc=NIL THEN 0 ELSE params.wireWidthProc[net.name, params.context];

properties: Route.Properties ← RouteUtil.PutNumberProp[NIL, Route.trunkWidthKey, width];

Route.IncludeNet[routingArea, net.name, net.pins, properties];

RETURN[FALSE];

END;

[] ← SymTab.Pairs[tab, EnterOneNet];

};

DoRoute: PUBLIC PROC [obj1, obj2, bottomOrLeftObj, topOrRightObj: CD.Object, params: RouterParams, isX: BOOL, routeType: RouteType]

RETURNS [result: Route.RoutingResult] = {

tab: SymTab.Ref;

sideCoords: Route.PositionVec; -- the positions of the sides in a "large" coord system

r1, r2, rbl, rtr, routingRect: CD.Rect ← [0, 0, 0, 0];

pBottom, pLeft, pTop, pRight: CD.Position;

trunkAtom: ATOM;

-- Make the design rules for proper spacing in this techno

rules: Route.DesignRules ←

IF isX THEN -- abutX

Route.CreateDesignRules[params.technologyKey,

CDSimpleRules.GetLayer[params.technologyKey, params.branchLayer],

CDSimpleRules.GetLayer[params.technologyKey, params.trunkLayer],

vertical]

ELSE -- abutY

Route.CreateDesignRules[params.technologyKey,

CDSimpleRules.GetLayer[params.technologyKey, params.trunkLayer],

CDSimpleRules.GetLayer[params.technologyKey, params.branchLayer],

horizontal];

-- Initialize the channel: no fancy option for now

routingArea: Route.RoutingArea ← Route.CreateRoutingArea["Channel", rules];

-- In prevision of the use of the IRect coord system, origins are [0, 0]

IF obj1 # NIL THEN r1 ← CD.InterestRect[obj1];

IF obj2 # NIL THEN r2 ← CD.InterestRect[obj2];

IF bottomOrLeftObj # NIL THEN rbl ← CD.InterestRect[bottomOrLeftObj];

IF topOrRightObj # NIL THEN rtr ← CD.InterestRect[topOrRightObj];

IF isX THEN { -- AbutX

pBottom ← [0, - rbl.y2 + rbl.y1];

pLeft ← [- r1.x2 + r1.x1, 0];

pTop ← [0, MAX[r1.y2 - r1.y1, r2.y2 - r2.y1]];

pRight ← [MAX[rbl.x2 - rbl.x1, rtr.x2 - rtr.x1], 0];

Route.IncludeRoutingAreaSide[routingArea, left, [r1.x1, r1.y1]];

Route.IncludeRoutingAreaSide[routingArea, right, [r2.x1, r2.y1]];

Route.IncludeRoutingAreaSide[routingArea, bottom, [rbl.x1, rbl.y1]];

Route.IncludeRoutingAreaSide[routingArea, top, [rtr.x1, rtr.y1]];

trunkAtom ← $verticalWidth}

ELSE { -- AbutY

pBottom ← [0, - r1.y2 + r1.y1];

pLeft ← [- rbl.x2 + rbl.x1, 0];

pTop ← [0, MAX[rbl.y2 - rbl.y1, rtr.y2 - rtr.y1]];

pRight ← [MAX[r1.x2 - r1.x1, r2.x2 - r2.x1], 0];

Route.IncludeRoutingAreaSide[routingArea, bottom, [r1.x1, r1.y1]];

Route.IncludeRoutingAreaSide[routingArea, top, [r2.x1, r2.y1]];

Route.IncludeRoutingAreaSide[routingArea, left, [rbl.x1, rbl.y1]];

Route.IncludeRoutingAreaSide[routingArea, right, [rtr.x1, rtr.y1]];

trunkAtom ← $horizontalWidth};

tab ← SymTab.Create[mod: 17, case: TRUE]; -- the table of all nets

-- Parse the objects, get the pins, make the nets, put in table

ParsePins[obj1, tab, IF isX THEN right ELSE top, params];

ParsePins[obj2, tab, IF isX THEN left ELSE bottom, params];

ParsePins[topOrRightObj, tab, IF isX THEN bottom ELSE left, params];

ParsePins[bottomOrLeftObj, tab, IF isX THEN top ELSE right, params];

-- Read the table and ship the nets to the channel router

ShipNets[tab, routingArea, trunkAtom, params];

-- Now route!

sideCoords ← [pBottom, pTop, pLeft, pRight];

routingRect ← [0, 0, pRight.x, pTop.y];

SELECT routeType FROM

channel => result ← Route.ChannelRoute[routingArea, sideCoords, routingRect, params.opt, params.signalSinglePinNets, params.signalCoincidentPins];

switchBox => result ← Route.SwitchBoxRoute[routingArea, sideCoords, routingRect, params.opt, params.signalSinglePinNets, params.signalCoincidentPins, params.okToDiddleLLPins, params.okToDiddleURPins];

ENDCASE;

IF result.incompleteNets # NIL AND params.signalIncomplete THEN Route.Signal[noResource, Rope.Cat["Incomplete routing of nets: ", RopeFromList[result.incompleteNets]]];

IF result.breakAtExitNets # NIL AND params.signalBreakAtExit THEN Route.Signal[noResource, Rope.Cat["Nets were divided at channel exit: ", RopeFromList[result.breakAtExitNets]]]};

GetRouting: PUBLIC PROC [result: Route.RoutingResult, retrieveRect: RefRect ← NIL, params: RouterParams ← defaultRouterParams] RETURNS [channel: CD.Object] ~ {

channel ← Route.RetrieveRouting[result, result.routingArea.name, retrieveRect, NIL, params.viaTable].object;

Route.Destroy[result.routingArea]};

MakeChannel: PUBLIC PROC [obj1, obj2, bottomOrLeftObj, topOrRightObj: CD.Object, retrieveRect: RefRect, params: RouterParams, isX: BOOL, routeType: RouteType] RETURNS [channel: CD.Object] = {

result: Route.RoutingResult← DoRoute[obj1, obj2, bottomOrLeftObj, topOrRightObj, params, isX, routeType];

channel ← GetRouting[result, retrieveRect, params].channel;

Route.Destroy[result.routingArea]};

KeepAll: PUBLIC SelectNamesProc = {keepIt ← TRUE};

XferPins: PUBLIC PROC [technologyKey: ATOM, template: CD.Object, objSide: PWPins.Side, minWidth: INT, routingLayerDes: Rope.ROPE, selectNameProc: PWRoute.SelectNamesProc ← KeepAll, xferPinsProc: PWRoute.XferPinsProc] RETURNS [cell: CD.Object ← NIL] = {

FindPins: CDSymbolicObjects.InstEnumerator = {

[inst: CD.Instance] RETURNS [quit: BOOL ← FALSE]

IF PWPins.GetSide[template, inst].side=objSide THEN {

pinLayer: CD.Layer ← CDSymbolicObjects.GetLayer[inst];

IF pinLayer # routingLayer THEN {

-- when PW is fixed clean this up

pwBug: CD.Instance ← CDInstances.NewInst[ob: inst.ob, trans: [[0,0], pwBugOrien]];

xferObj: CD.Object;

CDSymbolicObjects.SetLayer[pwBug, pinLayer];

xferObj ← xferPinsProc[technologyKey, pwBug, routingLayer, 0];

needsXfer ← TRUE;

width ← MAX[width, RTBasic.IRSize[xferObj].x]}}};

MapPins: PWRoute.ForEachPinProc = {

[inst: Instance] RETURNS [obj: Object]

obj ← NIL;

IF PWPins.GetSide[template, inst].side = objSide THEN {

pinInst: CD.Instance;

pinSize: CD.Position;

pinOb, wire: CD.Object;

-- when PW is fixed clean this up

pwBug: CD.Instance ← CDInstances.NewInst[ob: inst.ob, trans: [[0,0], pwBugOrien]];

CDSymbolicObjects.SetLayer[pwBug, CDSymbolicObjects.GetLayer[inst]];

wire ← xferPinsProc[technologyKey, pwBug, routingLayer, width];

pinSize ← CDBasics.OrientedSize[CDBasics.SizeOfRect[pwBug.ob.bbox], pwBug.trans.orient];

pinOb ← CDSymbolicObjects.CreatePin[pinSize];

obj ← CDCells.CreateEmptyCell[];

pinInst ← CDCells.IncludeOb[cell: obj, ob: pinOb, trans: [[width-pinSize.x, 0]]].newInst;

[] ← CDCells.IncludeOb[cell: obj, ob: wire];

CDSymbolicObjects.SetName[pinInst, CDSymbolicObjects.GetName[inst]];

CDSymbolicObjects.SetLayer[pinInst, routingLayer];

RTBasic.RepositionCell[obj];

};

width: INT ← MAX[minWidth, 0];

needsXfer: BOOLEAN ← width > 0;

routingLayer: CD.Layer ← CDSimpleRules.GetLayer[technologyKey, routingLayerDes];

-- when PW is fixed clean this up

pwBugOrien: CD.Orientation ← IF objSide=top OR objSide=bottom THEN rotate90 ELSE original; -- PW problem: inst has wrong orientation!!!

IF template # NIL THEN {

[] ← PWPins.EnumerateEdgePins[template, FindPins];

IF needsXfer THEN

cell ← PWPins.TransferCell[template, objSide, width, MapPins, selectNameProc];

};

defaultXferPins: PUBLIC XferPinsProc = {

XferPinsProc: TYPE = PROC [technologyKey: ATOM, inst: CD.Instance, routingLayer: CD.Layer, width: INT] RETURNS [cell: CD.Object] --

pinLayer: CD.Layer ← CDSymbolicObjects.GetLayer[inst];

polyLayer: CD.Layer ← CDSimpleRules.GetLayer[technologyKey, "poly"];

metalLayer: CD.Layer ← CDSimpleRules.GetLayer[technologyKey, "metal"];

metal2Layer: CD.Layer ← CDSimpleRules.GetLayer[technologyKey, "metal2"];

m1ToM12: INT ← MAX[CDSimpleRules.MinSpace[NIL, metalLayer, metalLayer], CDSimpleRules.MinSpace[NIL, metal2Layer, metal2Layer]];

sizeX, pinSizeY: INT;

cdLambda: INT ← CD.LayerTechnology[routingLayer].lambda;

pinSize: CD.Position ← CDBasics.OrientedSize[CDBasics.SizeOfRect[inst.ob.bbox], inst.trans.orient];

pinSizeY ← pinSize.y;

cell ← CDCells.CreateEmptyCell[];

SELECT TRUE FROM

pinLayer = routingLayer => {

sizeX ← width;

IF width > 0 THEN {

[] ← CDCells.IncludeOb[cell: cell, ob: CDRects.CreateRect[[sizeX, pinSizeY], pinLayer]]}};

pinLayer = polyLayer => {

pContact: CD.Object ← CDSimpleRules.Contact[NIL, polyLayer, metalLayer];

contactSize: CD.Position ← CDBasics.SizeOfRect[pContact.bbox];

wireP, mPContact: CD.Object;

sizeX ← m1ToM12 + contactSize.x;

wireP ← CDRects.CreateRect[[sizeX, pinSizeY], polyLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireP];

mPContact ← RouteUtil.StitchVias[[contactSize.x, pinSizeY], polyLayer, metalLayer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: mPContact, trans: [[m1ToM12, (pinSizeY-CDBasics.SizeOfRect[mPContact.bbox].y)/2]]];

IF routingLayer = metal2Layer THEN {

mVia: CD.Object ← CDSimpleRules.Contact[NIL, metalLayer, metal2Layer];

viaSize: CD.Position ← CDBasics.SizeOfRect[mVia.bbox];

wireM2: CD.Object ← CDRects.CreateRect[[m1ToM12, pinSizeY], metal2Layer];

m2M1Via: CD.Object;

[] ← CDCells.IncludeOb[cell: cell, ob: wireM2, trans: [[sizeX, 0]]];

sizeX ← sizeX + m1ToM12;

m2M1Via ← RouteUtil.StitchVias[[viaSize.x, pinSizeY], metalLayer, metal2Layer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: m2M1Via, trans: [[sizeX, (pinSizeY-CDBasics.SizeOfRect[m2M1Via.bbox].y)/2]]];

sizeX ← sizeX + viaSize.x};

IF width > sizeX THEN {

wireRL: CD.Object ← CDRects.CreateRect[[width - sizeX, pinSizeY], routingLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireRL, trans: [[sizeX, 0]]];

sizeX ← width}};

pinLayer = metalLayer => {

IF routingLayer = metal2Layer THEN {

mVia: CD.Object ← CDSimpleRules.Contact[NIL, metalLayer, metal2Layer];

viaSize: CD.Position ← CDBasics.SizeOfRect[mVia.bbox];

wireM, m2M1Via: CD.Object;

sizeX ← m1ToM12 + viaSize.x;

wireM ← CDRects.CreateRect[[sizeX, pinSizeY], metalLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireM];

m2M1Via ← RouteUtil.StitchVias[[viaSize.x, pinSizeY], metalLayer, metal2Layer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: m2M1Via, trans:[[m1ToM12, (pinSizeY-CDBasics.SizeOfRect[m2M1Via.bbox].y)/2]]];

IF width > sizeX THEN {

wireM2: CD.Object ← CDRects.CreateRect[[width - sizeX, pinSizeY], metal2Layer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireM2, trans: [[sizeX, 0]]];

sizeX ← width}}

ELSE {

pContact: CD.Object ← CDSimpleRules.Contact[NIL, polyLayer, metalLayer];

contactSize: CD.Position ← CDBasics.SizeOfRect[pContact.bbox];

wireM, mPContact: CD.Object;

sizeX ← m1ToM12 + contactSize.x;

wireM ← CDRects.CreateRect[[sizeX, pinSizeY], metalLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireM];

mPContact ← RouteUtil.StitchVias[[contactSize.x, pinSizeY], polyLayer, metalLayer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: mPContact, trans: [[CDBasics.SizeOfRect[wireM.bbox].x, (pinSizeY-CDBasics.SizeOfRect[mPContact.bbox].y)/2]]];

IF width > sizeX THEN {

wireP: CD.Object ← CDRects.CreateRect[[width - sizeX, pinSizeY], polyLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireP, trans: [[sizeX, 0]]];

sizeX ← width}}};

pinLayer = metal2Layer => {

mVia: CD.Object ← CDSimpleRules.Contact[NIL, metalLayer, metal2Layer];

viaSize: CD.Position ← CDBasics.SizeOfRect[mVia.bbox];

wireM2, m2M1Via: CD.Object;

sizeX ← m1ToM12 + viaSize.x;

wireM2 ← CDRects.CreateRect[[sizeX, pinSizeY], metal2Layer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireM2];

m2M1Via ← RouteUtil.StitchVias[[viaSize.x, pinSizeY], metalLayer, metal2Layer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: m2M1Via, trans: [[m1ToM12, (pinSizeY-CDBasics.SizeOfRect[m2M1Via.bbox].y)/2]]];

IF routingLayer = polyLayer THEN {

pContact: CD.Object ← CDSimpleRules.Contact[NIL, metalLayer, polyLayer];

contactSize: CD.Position ← CDBasics.SizeOfRect[pContact.bbox];

wireM: CD.Object ← CDRects.CreateRect[[m1ToM12 + contactSize.x, pinSizeY], metalLayer];

mPContact: CD.Object ← RouteUtil.StitchVias[[contactSize.x, pinSizeY], polyLayer, metalLayer, cdLambda, NIL];

[] ← CDCells.IncludeOb[cell: cell, ob: wireM, trans: [[sizeX, 0]]];

sizeX ← sizeX + m1ToM12;

[] ← CDCells.IncludeOb[cell: cell, ob: mPContact, trans: [[sizeX, (pinSizeY-CDBasics.SizeOfRect[mPContact.bbox].y)/2]]];

sizeX ← sizeX + contactSize.x};

IF width > sizeX THEN {

wireRL: CD.Object ← CDRects.CreateRect[[width - sizeX, pinSizeY], routingLayer];

[] ← CDCells.IncludeOb[cell: cell, ob: wireRL, trans: [[sizeX, 0]]];

sizeX ← width};

};

ENDCASE;

CDCells.SetInterestRect[design: NIL, cell: cell, r: [0, 0, sizeX, pinSizeY]]};

Reverse: PROC [objects: PWRoute.Objects] RETURNS [result: PWRoute.Objects ← NIL] = {

-- Reverse a list of objects

result ← NARROW [GList.Reverse[objects]]};

RopeFromList: PROC [list: LIST OF Rope.ROPE] RETURNS [rope: Rope.ROPE] ~ {

-- make a rope from a list of ropes

UNTIL list = NIL DO rope ← Rope.Cat[list.first, ", ", rope]; list ← list.rest ENDLOOP};

END.