luke
/
magic
mirror of https://github.com/RTimothyEdwards/magic.git
1
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
magic/garouter/gaStem.c

1179 lines
34 KiB
C
Raw Permalink Blame History

/*
* gaStem.c -
*
* Assignment of routing-grid pin locations to terminals.
*
* *********************************************************************
* * Copyright (C) 1985, 1990 Regents of the University of California. *
* * Permission to use, copy, modify, and distribute this *
* * software and its documentation for any purpose and without *
* * fee is hereby granted, provided that the above copyright *
* * notice appear in all copies. The University of California *
* * makes no representations about the suitability of this *
* * software for any purpose. It is provided "as is" without *
* * express or implied warranty. Export of this software outside *
* * of the United States of America may require an export license. *
* *********************************************************************
*/
#ifndef lint
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/garouter/gaStem.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
#endif /* not lint */
#include <stdio.h>
#include "utils/magic.h"
#include "utils/geometry.h"
#include "utils/hash.h"
#include "utils/heap.h"
#include "tiles/tile.h"
#include "database/database.h"
#include "windows/windows.h"
#include "utils/main.h"
#include "dbwind/dbwind.h"
#include "utils/signals.h"
#include "netmenu/netmenu.h"
#include "gcr/gcr.h"
#include "router/router.h"
#include "grouter/grouter.h"
#include "garouter/garouter.h"
#include "gaInternal.h"
#include "utils/netlist.h"
#include "textio/textio.h"
#include "utils/styles.h"
#include "utils/malloc.h"
#include "drc/drc.h"
#include "debug/debug.h"
/*
* If TRUE, leave feedback for each location for a terminal that
* is unusable. If FALSE, only leave feedback if ALL locations
* for a particular terminal are unusable.
*/
bool GAStemWarn = FALSE;
/* Used locally */
int gaMaxAbove; /* The maximum distance any routing material extends
* above (or to the right of) a routing grid line.
*/
int gaMaxBelow; /* Same as above, but for material below or to the
* left of routing grid lines.
*/
int gaMinAbove; /* Minimum distance any routing material extends
* above (or to the right of) a routing grid line.
*/
/*
* The following are conservative distances around each of
* metal, poly, and contact types that must be clear of material.
*/
int gaMetalClear, gaPolyClear, gaContactClear;
/* Statistics */
int gaNumDegenerate;
int gaNumLocs;
int gaNumPairs;
int gaNumInt, gaNumExt, gaNumNoChan;
int gaNumInNorm;
int gaNumOverlap;
int gaNumNetBlock;
int gaNumPinBlock;
int gaNumMazeStem, gaNumSimpleStem;
int gaNumSimplePaint, gaNumMazePaint, gaNumExtPaint;
/* Forward declarations */
int gaStemContainingChannelFunc();
bool gaStemAssign();
int gaStemGridRange();
void gaStemPaint();
bool gaStemNetClear();
bool gaStemInternalFunc();
bool gaStemInternal();
bool gaStemGrow();
/*
* ----------------------------------------------------------------------------
*
* gaStemAssignAll --
*
* Assign one or two crossing points to each terminal location.
* Terminal locations must lie inside river-routing channels;
* they are assigned crossings on either side of the channel
* as long as those crossings are reachable by river-routing.
*
* If terminal locations aren't grid-aligned, this code takes
* care of figuring out which grid-aligned crossing point to
* use and ensuring that this point is reachable from the terminal.
*
* Results:
* None.
*
* Side effects:
* Adds one additional NLTermLoc to the netlist for each
* terminal location that is given two crossing points.
* When it isn't possible to assign any crossing points
* to a NLTermLoc, it is deleted from the list and we
* leave feedback.
*
* ----------------------------------------------------------------------------
*/
void
gaStemAssignAll(routeUse, netList)
CellUse *routeUse;
NLNetList *netList;
{
TileType t;
/* Statistics */
gaNumDegenerate = 0;
gaNumLocs = 0;
gaNumInt = 0;
gaNumExt = 0;
gaNumNoChan = 0;
gaNumPairs = 0;
gaNumInNorm = 0;
gaNumOverlap = 0;
gaNumNetBlock = 0;
gaNumPinBlock = 0;
gaNumMazeStem = 0;
gaNumSimpleStem = 0;
/*
* Compute the distance around metal, poly, and contact that
* must be clear of material.
*/
gaMetalClear = gaPolyClear = 0;
for (t = TT_TECHDEPBASE; t < DBNumTypes; t++)
{
if (RtrMetalSeps[t] > gaMetalClear) gaMetalClear = RtrMetalSeps[t];
if (RtrPolySeps[t] > gaPolyClear) gaPolyClear = RtrPolySeps[t];
}
gaContactClear = MAX(gaMetalClear + RtrMetalSurround,
gaPolyClear + RtrPolySurround);
/* Max distance any routing material extends above a grid line */
gaMaxAbove = MAX(RtrMetalWidth, RtrPolyWidth);
gaMaxAbove = MAX(gaMaxAbove, RtrContactWidth - RtrContactOffset);
/* Min distance any routing material extends above a grid line */
gaMinAbove = MIN(RtrMetalWidth, RtrPolyWidth);
gaMinAbove = MIN(gaMinAbove, RtrContactWidth - RtrContactOffset);
/* Max distance any routing material extends below a grid line */
gaMaxBelow = RtrContactOffset;
/* Assign the stems (gaStemAssign() does the real work) */
RtrStemProcessAll(routeUse, netList, GAStemWarn, gaStemAssign);
if (DebugIsSet(gaDebugID, gaDebVerbose))
{
TxPrintf("%d terminals processed.\n", gaNumLocs);
TxPrintf("%d internal, %d external, %d no channel.\n",
gaNumInt, gaNumExt, gaNumNoChan);
TxPrintf("%d paired internal stems.\n", gaNumPairs);
TxPrintf("%d degenerate.\n", gaNumDegenerate);
TxPrintf("%d discarded because inside normal channels.\n", gaNumInNorm);
TxPrintf("%d discarded because overlapped channel boundaries.\n",
gaNumOverlap);
TxPrintf("%d possible stems blocked by other terminals.\n",
gaNumNetBlock);
TxPrintf("%d possible stems to blocked pins.\n", gaNumPinBlock);
TxPrintf("%d simple paths, %d maze paths.\n",
gaNumSimpleStem, gaNumMazeStem);
}
}
/*
* ----------------------------------------------------------------------------
*
* gaStemAssign --
*
* Do the real work of gaStemAssignAll() above -- assign one or two
* crossing points to the terminal location 'loc'.
*
* Results:
* TRUE if successful, FALSE if no locations could be assigned.
*
* Side effects:
* May add one additional NLTermLoc to the list for 'loc',
* in the position immediately following loc, if this location
* is given two crossing points. The caller should be aware
* of this in traversing a linked list of NLTermLocs.
*
* ----------------------------------------------------------------------------
*/
bool
gaStemAssign(routeUse, doWarn, loc, term, net, netList)
CellUse *routeUse; /* Cell being routed */
bool doWarn; /* If TRUE, leave feedback for each error */
NLTermLoc *loc; /* Location considered */
NLTerm *term; /* Terminal of which loc is a location */
NLNet *net; /* Net to which it belongs */
NLNetList *netList; /* Netlist (searched for blocking terminals) */
{
GCRChannel *ch;
gaNumLocs++;
/*
* See if this location lies inside a river-routing channel.
* If it does, return the channel containing it.
*/
if ((ch = gaStemContainingChannel(routeUse, doWarn, loc)))
{
if (ch->gcr_type != CHAN_HRIVER && ch->gcr_type != CHAN_VRIVER)
goto fail;
gaNumInt++;
return (gaStemInternal(routeUse, doWarn, loc, net, ch, netList));
}
/* Not inside a river-routing channel. Try for a nearby normal channel */
if (RtrStemAssignExt(routeUse, doWarn, loc, term, net))
{
gaNumExt++;
return (TRUE);
}
if (doWarn)
{
DBWFeedbackAdd(&loc->nloc_rect,
"No crossing reachable from terminal",
routeUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
}
fail:
gaNumNoChan++;
return (FALSE);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemContainingChannel --
*
* Find the channel containing 'loc' if there is one. This channel,
* if it exists, should be a river-routing channel. If it isn't,
* we leave feedback if 'doWarn' is TRUE.
*
* If loc is degenerate, it can't lie on the border of a channel
* (this restriction may be lifted later; it's just a pain to
* deal with now).
*
* It is illegal for loc to straddle a channel boundary.
*
* Results:
* Returns the channel as described above, or NULL if loc
* didn't lie in a channel or it violated one of the above
* conditions.
*
* Side effects:
* Leaves feedback in the event of errors, if 'doWarn' is TRUE.
*
* ----------------------------------------------------------------------------
*/
GCRChannel *
gaStemContainingChannel(routeUse, doWarn, loc)
CellUse *routeUse; /* For errors */
bool doWarn; /* If TRUE, leave feedback if error */
NLTermLoc *loc; /* Find a channel for this terminal */
{
GCRChannel *ch;
Rect area;
/* Special handling is required for degenerate locs */
area = loc->nloc_rect;
if (GEO_RECTNULL(&area))
if (!gaStemGrow(&area))
goto overlap;
/* Ensure that only one channel is overlapped */
ch = (GCRChannel *) NULL;
if (DBSrPaintArea((Tile *) NULL, RtrChannelPlane, &area,
&DBAllTypeBits, gaStemContainingChannelFunc, (ClientData) &ch))
goto overlap;
/* Illegal to be inside a normal channel */
if (ch && ch->gcr_type == CHAN_NORMAL)
{
gaNumInNorm++;
if (doWarn)
{
DBWFeedbackAdd(&area,
"Terminal is inside a normal routing channel",
routeUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
}
}
return (ch);
overlap:
gaNumOverlap++;
if (doWarn)
{
DBWFeedbackAdd(&area,
"Terminal overlaps a channel boundary",
routeUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
}
return ((GCRChannel *) NULL);
}
/*
* gaStemContainingChannelFunc --
*
* Called via DBSrPaintArea on behalf of gaStemContainingChannel above
* for each tile overlapping the area of a terminal, to determine
* whether more than one channel is overlapped by that terminal.
*
* Results:
* Returns 0 normally, or 1 if *pCh was non-zero and
* the channel associated with tile was different from
* *pCh.
*
* Side effects:
* Sets *pCh to the channel associated with tile if there
* was one.
*
* ----------------------------------------------------------------------------
*/
int
gaStemContainingChannelFunc(tile, pCh)
Tile *tile;
GCRChannel **pCh;
{
GCRChannel *ch;
if ((ch = (GCRChannel *) tile->ti_client))
{
if (*pCh)
{
if (ch != *pCh)
return (1);
}
else *pCh = ch;
}
return (0);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemGrow --
*
* The terminal being processed (described by the initial value of *area)
* is degenerate, so figure out which side is of interest and grow *area
* in that direction.
*
* If *area is entirely contained by a channel or empty space,
* we don't have to do anything. If it lies on the border
* of a channel, then currently we reject it.
*
* Results:
* TRUE if area is entirely contained in either channel or empty
* space; FALSE otherwise.
*
* Side effects:
* Modifies *area as described above.
*
* ----------------------------------------------------------------------------
*/
bool
gaStemGrow(area)
Rect *area;
{
Rect r;
GCRChannel *ch;
r = *area;
if (r.r_xbot == r.r_xtop) r.r_xbot--, r.r_xtop++;
if (r.r_ybot == r.r_ytop) r.r_ybot--, r.r_ytop++;
gaNumDegenerate++;
/* OK if either zero or one channel is overlapped */
ch = (GCRChannel *) NULL;
if (DBSrPaintArea((Tile *) NULL, RtrChannelPlane, &r,
&DBAllTypeBits, gaStemContainingChannelFunc, (ClientData) &ch) == 0)
return (TRUE);
return (FALSE);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemInternal --
*
* Having determined that 'loc' lies entirely within a river-routing
* channel, try to bring it out to both sides of the channel.
*
* If the terminal permits a grid aligned route, "simple" routes are
* tried first. A simple route is a grid aligned straight line from
* terminal to pin with a possible layer change at the terminal and
* another at the grid point just prior to the pin. If simple routes
* are not possible, the mzrouter() is called.
*
* Marks the pins in the channel OUTSIDE the river-routing channel with
* net (the ones INSIDE the river-routing channel are left blank,
* so the channel router won't try connecting them). Also sets gcr_pSeg
* for the outside pins to GCR_STEMSEGID to tell the global router that
* they are stem tips; the global router will reassign a real segment
* number to the crossing point when the stem tip is used.
*
* Each NLTermLoc has nloc_chan set to the channels on the outside
* of 'ch', rather than 'ch' itself, in order to be consistent with
* gaStemExternal.
*
* Results:
* TRUE if we succeeded in assigning one (or two) crossing points;
* FALSE if none could be assigned.
*
* Side effects:
* See above.
* May add one additional NLTermLoc to the list for 'loc',
* in the position immediately following loc, if this location
* is given two crossing points.
*
* ----------------------------------------------------------------------------
*/
bool
gaStemInternal(routeUse, doWarn, loc, net, ch, netList)
CellUse *routeUse; /* Cell being routed */
bool doWarn; /* If TRUE, leave feedback on all errors */
NLTermLoc *loc; /* Terminal being processed */
NLNet *net; /* Used for marking pins */
GCRChannel *ch; /* Channel containing loc */
NLNetList *netList; /* Netlist (searched for blocking terminals) */
{
int min, max, start, lo, hi;
/* Compute the grid lines that can be used for this terminal */
gaStemGridRange(ch->gcr_type, &loc->nloc_rect, &min, &max, &start);
/*
* Try each possibility until we find a grid line that is usable,
* or until we've run out of possibilities. Work outward from
* the starting point. We don't make any attempt to pick the
* best grid line, so if we see one early that can only be routed
* to one side, and one later that can be routed to both, we still
* pick the earlier. The greedy strategy is simpler, and also we
* expect that usually there will only be a single grid line per
* terminal.
*/
if (gaStemInternalFunc(routeUse, loc, net, ch, start, netList))
return (TRUE);
for (lo = start - RtrGridSpacing, hi = start + RtrGridSpacing;
lo >= min || hi <= max;
lo -= RtrGridSpacing, hi += RtrGridSpacing)
{
if (lo >= min)
if (gaStemInternalFunc(routeUse, loc, net, ch, lo, netList))
return (TRUE);
if (hi <= max)
if (gaStemInternalFunc(routeUse, loc, net, ch, hi, netList))
return (TRUE);
}
if (doWarn)
{
DBWFeedbackAdd(&loc->nloc_rect,
"Terminal can't be brought out to either channel boundary",
routeUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
}
return (FALSE);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemInternalFunc --
*
* Try "simple" (straight line) routes and failing that mzroutes from
* terminal to pins on both sides of the channel.
* If it is possible to connect to one or both sides of the channel
* mark loc->nloc_stem,
* loc->nloc_chan, and loc->nloc_dir with the location of the
* crossing chosen (add a new loc to the list if two crossings were
* chosen), and mark the pins in the channels OUTSIDE of the crossings
* as described in the comments to gaStemInternal() above. The pin
* used for the crossing is stored in loc->nloc_pin.
*
* NOTE: loc->nloc_chan is the channel on the OUTSIDE of 'ch',
* rather than 'ch' itself.
*
* Results:
* TRUE on success, FALSE on failure.
*
* Side effects:
* See above, and also the comments to gaStemInternal().
*
* ----------------------------------------------------------------------------
*/
bool
gaStemInternalFunc(routeUse, loc, net, ch, gridLine, netList)
CellUse *routeUse;
NLTermLoc *loc;
NLNet *net;
GCRChannel *ch;
int gridLine;
NLNetList *netList;
{
GCRPin *pin1, *pin2;
NLTermLoc *loc2;
Point p1, p2;
int dir1, dir2;
/*
* Compute the areas that must be searched to ensure that
* river-routes to the outside of the channel are possible.
*/
switch (ch->gcr_type)
{
case CHAN_HRIVER:
p1.p_x = ch->gcr_area.r_xbot;
p1.p_y = gridLine;
p2.p_x = ch->gcr_area.r_xtop;
p2.p_y = gridLine;
dir1 = GEO_WEST;
dir2 = GEO_EAST;
break;
case CHAN_VRIVER:
p1.p_x = gridLine;
p1.p_y = ch->gcr_area.r_ybot;
p2.p_x = gridLine;
p2.p_y = ch->gcr_area.r_ytop;
dir1 = GEO_SOUTH;
dir2 = GEO_NORTH;
break;
}
if (DebugIsSet(gaDebugID, gaDebStems))
{
TxPrintf("Loc: ll=(%d,%d) ur=(%d,%d)\n",
loc->nloc_rect.r_xbot, loc->nloc_rect.r_ybot,
loc->nloc_rect.r_xtop, loc->nloc_rect.r_ytop);
TxPrintf("Try crossings: L=(%d,%d) and R=(%d,%d)\n",
p1.p_x, p1.p_y, p2.p_x, p2.p_y);
}
pin1 = gaStemCheckPin(routeUse, loc, ch, dir1, &p1, netList);
pin2 = gaStemCheckPin(routeUse, loc, ch, dir2, &p2, netList);
if (DebugIsSet(gaDebugID, gaDebStems))
{
if (pin1) TxPrintf("Success L=(%d,%d)\n", p1.p_x, p1.p_y);
if (pin2) TxPrintf("Success R=(%d,%d)\n", p2.p_x, p2.p_y);
if (pin1 == NULL && pin2 == NULL)
TxPrintf("FAILURE ON BOTH CROSSINGS\n");
TxMore("--------");
}
if (pin1 == (GCRPin *) NULL && pin2 == (GCRPin *) NULL)
return (FALSE);
if (pin1)
{
loc->nloc_dir = dir1;
loc->nloc_stem = p1;
loc->nloc_chan = pin1->gcr_linked->gcr_ch;
loc->nloc_pin = pin1->gcr_linked;
/* Mark the crossing OUTSIDE ch */
pin1->gcr_linked->gcr_pId = (GCRNet *) net;
pin1->gcr_linked->gcr_pSeg = GCR_STEMSEGID;
}
if (pin2)
{
if (pin1)
{
/* Allocate a new NLTermLoc to hold the second crossing */
loc2 = (NLTermLoc *) mallocMagic(sizeof (NLTermLoc));
*loc2 = *loc;
loc->nloc_next = loc2;
loc = loc2;
gaNumPairs++;
}
loc->nloc_dir = dir2;
loc->nloc_stem = p2;
loc->nloc_chan = pin2->gcr_linked->gcr_ch;
loc->nloc_pin = pin2->gcr_linked;
/* Mark the crossing OUTSIDE ch */
pin2->gcr_linked->gcr_pId = (GCRNet *) net;
pin2->gcr_linked->gcr_pSeg = GCR_STEMSEGID;
}
return (TRUE);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemCheckPin --
*
* Determine if the crossing point at 'point' is reachable from 'loc'.
* Simple connections are tried first. If these fail, the mzrouter module
* is called.
*
* It must normally be possible to connect to either layer in the
* adjacent channel (channel routing isn't guaranteed to leave a
* signal on a particular layer since the layer used depends on the
* channel orientation). However, if one layer is blocked in the
* channel, then we only need to connect to the other layer.
*
* Results:
* Returns the pin belonging to 'ch' and using the crossing
* point at 'point' if a river-route is possible, or NULL
* if no river-route is possible.
*
* Side effects:
* None.
*
* ----------------------------------------------------------------------------
*/
GCRPin *
gaStemCheckPin(routeUse, terminalLoc, ch, side, gridPoint, netList)
CellUse *routeUse; /* Cell being routed */
NLTermLoc *terminalLoc; /* Terminal */
GCRChannel *ch; /* Channel whose pin we are to use */
int side; /* Direction 'gridPoint' lies relative to 'loc' */
Point *gridPoint; /* Crossing point to use */
NLNetList *netList; /* Searched for obstructing terminals */
{
TileTypeBitMask destMask;
GCRPin *pin;
SimpleStem simple;
short code;
/*
* Discard this pin immediately if any of the following are true:
* - it is already occupied by a net
* - it isn't adjacent to a usable channel (i.e, it has no gcr_linked
* pin or its gcr_linked pin is blocked)
* - there's another terminal from this netlist in the way
*/
pin = RtrPointToPin(ch, side, gridPoint);
if (pin->gcr_pId != (GCRNet *) NULL
|| pin->gcr_linked == (GCRPin *) NULL
|| pin->gcr_linked->gcr_pId != (GCRNet *) NULL)
{
gaNumPinBlock++;
return ((GCRPin *) NULL);
}
if (!gaStemNetClear(&terminalLoc->nloc_rect, gridPoint, side, netList))
{
gaNumNetBlock++;
return ((GCRPin *) NULL);
}
/*
* What types are present at the pin location?
* Only worry about connecting to layers that aren't
* present in the channel. The code above assumes
* that two-layer blockages at channel boundaries
* will cause their corresponding pins to be marked
* as blocked.
*/
code = pin->gcr_ch->gcr_result[pin->gcr_x][pin->gcr_y];
destMask = DBZeroTypeBits;
if ((code & GCRBLKM) == 0) TTMaskSetType(&destMask, RtrMetalType);
if ((code & GCRBLKP) == 0) TTMaskSetType(&destMask, RtrPolyType);
ASSERT(!TTMaskEqual(&destMask, &DBZeroTypeBits), "gaStemCheckPin");
/*
* Try to do things the simple way first, considering routes
* of a very stylized nature: straight across with at most one
* layer change over the terminal, and another on the grid line
* just before the channel boundary. This avoids having to
* call the maze router if we don't need to.
*/
if (DebugIsSet(gaDebugID, gaDebNoSimple))
goto hardway;
if (!gaStemSimpleInit(routeUse, terminalLoc, gridPoint, side, &simple))
goto hardway;
if (TTMaskHasType(&destMask, RtrMetalType)
&& !gaStemSimpleRoute(&simple, RtrMetalType, (CellDef *) NULL))
{
goto hardway;
}
if (TTMaskHasType(&destMask, RtrPolyType)
&& !gaStemSimpleRoute(&simple, RtrPolyType, (CellDef *) NULL))
{
goto hardway;
}
/* Win */
gaNumSimpleStem++;
return pin;
hardway:
/* Simple connections have failed, so try using mzrouter. A connection
* must be possible from EITHER ROUTING LAYER, so we know we can connect
* no matter how the channel is routed.
*
* NULL writeUse is used so no paint is generated, we just check
* if the connections are possible, deferring the actual stem generation
* until after channel routing, so we know what layers to connect to.
*/
{
bool writeFlag = FALSE;
TileTypeBitMask polyMask, metalMask;
TTMaskSetOnlyType(&polyMask, RtrPolyType);
TTMaskSetOnlyType(&metalMask, RtrMetalType);
if(gaMazeRoute(routeUse, terminalLoc, gridPoint, &polyMask, side,
writeFlag) &&
gaMazeRoute(routeUse, terminalLoc, gridPoint, &metalMask, side,
writeFlag))
{
gaNumMazeStem++;
return pin;
}
else
{
return ((GCRPin *) NULL);
}
}
}
/*
* ----------------------------------------------------------------------------
*
* gaStemNetClear --
*
* Determine whether the area between termArea and the crossing point
* 'point' is clear of other terminals that might want to share the
* same grid line. The purpose of this procedure is primarily to avoid
* doing something silly in the following situation (both terminals share
* the same horizontal grid line in a CHAN_HRIVER river-routing channel):
*
* +---------------------------+
* | |
* | +---+ +---+ |
* | | A | | B | |
* | +---+ +---+ |
* | |
* +---------------------------+
*
* Here, terminal "A" should only be brought out to the left, and "B"
* only to the right of the channel, since to do otherwise would block
* a terminal completely.
*
* +++ Currently, we consider a path from termArea to point blocked
* +++ by another terminal T only if T can use a single grid line,
* +++ and this grid line is the same as that of point.
*
* Results:
* TRUE if no terminals share the same grid line, FALSE otherwise.
*
* Side effects:
* None.
*
* ----------------------------------------------------------------------------
*/
bool
gaStemNetClear(termArea, point, side, netList)
Rect *termArea; /* Area of the starting terminal */
Point *point; /* Crossing point where we want to end up */
int side; /* Direction of point relative to termArea */
NLNetList *netList; /* Netlist to check for terminals to avoid */
{
int min, max, start, type, grid;
NLTermLoc *loc;
NLTerm *term;
NLNet *net;
Rect r;
/*
* First cut: determine a search area large enough so that any
* terminals lying entirely outside of it can't possibly conflict
* with this one.
*/
switch (side)
{
default:
ASSERT(FALSE, "side");
/* fall-thru */
case GEO_NORTH:
r.r_xbot = point->p_x - RtrSubcellSepUp;
r.r_xtop = point->p_x + RtrSubcellSepDown;
r.r_ybot = termArea->r_ytop;
r.r_ytop = point->p_y + RtrSubcellSepDown;
type = CHAN_VRIVER;
break;
case GEO_SOUTH:
r.r_xbot = point->p_x - RtrSubcellSepUp;
r.r_xtop = point->p_x + RtrSubcellSepDown;
r.r_ybot = point->p_y - RtrSubcellSepUp;
r.r_ytop = termArea->r_ybot;
type = CHAN_VRIVER;
break;
case GEO_WEST:
r.r_ybot = point->p_y - RtrSubcellSepUp;
r.r_ytop = point->p_y + RtrSubcellSepDown;
r.r_xbot = point->p_x - RtrSubcellSepUp;
r.r_xtop = termArea->r_xbot;
type = CHAN_HRIVER;
break;
case GEO_EAST:
r.r_ybot = point->p_y - RtrSubcellSepUp;
r.r_ytop = point->p_y + RtrSubcellSepDown;
r.r_xbot = termArea->r_xtop;
r.r_xtop = point->p_x + RtrSubcellSepDown;
type = CHAN_HRIVER;
break;
}
grid = (type == CHAN_HRIVER) ? point->p_y : point->p_x;
/* Only need to do work if a terminal lies inside this search area */
for (net = netList->nnl_nets; net; net = net->nnet_next)
{
if (!GEO_OVERLAP(&net->nnet_area, &r))
continue;
for (term = net->nnet_terms; term; term = term->nterm_next)
{
for (loc = term->nterm_locs; loc; loc = loc->nloc_next)
if (GEO_OVERLAP(&loc->nloc_rect, &r))
{
/* Only reject if both prefer same grid location */
gaStemGridRange(type, &loc->nloc_rect, &min,&max,&start);
if (start == grid)
return (FALSE);
}
}
}
return (TRUE);
}
/*
* ----------------------------------------------------------------------------
*
* gaStemGridRange --
*
* Determine the range of grid lines usable by the terminal whose
* area is 'r', for a river-routing channel whose type is 'type'
* (one of CHAN_HRIVER or CHAN_VRIVER). Usable grid lines are at
* most one grid line away from the relevant boundary of 'r'.
* Pick a starting grid line that is as close to the center of the
* range of usable grid points and that is also between the top
* and bottom (for CHAN_HRIVER) or left and right (for CHAN_VRIVER)
* of 'r'.
*
* Results:
* 0 on success, -1 on error (no side effects).
*
* Side effects:
* Sets *pMinGrid, *pMaxGrid, and *pStart.
*
* ----------------------------------------------------------------------------
*/
int
gaStemGridRange(type, r, pMinGrid, pMaxGrid, pStart)
int type;
Rect *r;
int *pMinGrid, *pMaxGrid, *pStart;
{
int min, max, start;
switch (type)
{
case CHAN_HRIVER:
{
min = RTR_GRIDDOWN(r->r_ybot, RtrOrigin.p_y);
max = RTR_GRIDDOWN(r->r_ytop - gaMaxAbove, RtrOrigin.p_y);
start = (max + min)/2;
start = RTR_GRIDDOWN(start, RtrOrigin.p_y);
if (start < r->r_ybot && (start + RtrGridSpacing) < r->r_ytop)
{
start += RtrGridSpacing;
}
break;
}
case CHAN_VRIVER:
{
min = RTR_GRIDDOWN(r->r_xbot, RtrOrigin.p_x);
max = RTR_GRIDDOWN(r->r_xtop - gaMaxAbove, RtrOrigin.p_x);
start = (max + min)/2;
start = RTR_GRIDDOWN(start, RtrOrigin.p_x);
if (start < r->r_xbot && (start + RtrGridSpacing) < r->r_xtop)
{
start += RtrGridSpacing;
}
break;
}
default:
{
ASSERT(FALSE, "Bad channel type in gaStemGridRange");
return -1;
}
}
max = MAX(max, start);
min= MIN(min, start);
*pMaxGrid = max;
*pMinGrid = min;
*pStart = start;
return 0;
}
/*
* ----------------------------------------------------------------------------
*
* gaStemPaintAll --
*
* Paint each stem that turned out to be connected.
* See gaStemPaint() for details.
*
* Results:
* None.
*
* Side effects:
* Adds paint to 'routeUse->cu_def'.
*
* ----------------------------------------------------------------------------
*/
void
gaStemPaintAll(routeUse, netList)
CellUse *routeUse;
NLNetList *netList;
{
NLTermLoc *loc;
NLTerm *term;
int numInt;
NLNet *net;
gaNumSimplePaint = 0;
gaNumMazePaint = 0;
gaNumExtPaint = 0;
RtrMilestoneStart("Painting stems");
for (net = netList->nnl_nets; net; net = net->nnet_next)
{
for (term = net->nnet_terms; term; term = term->nterm_next)
for (loc = term->nterm_locs; loc; loc = loc->nloc_next)
{
if (SigInterruptPending)
goto out;
if (loc->nloc_dir > 0)
gaStemPaint(routeUse, loc);
}
RtrMilestonePrint();
}
out:
RtrMilestoneDone();
if (DebugIsSet(gaDebugID, gaDebVerbose))
{
numInt = gaNumSimplePaint + gaNumMazePaint;
TxPrintf("%d simple, %d maze, %d total internal stems.\n",
gaNumSimplePaint, gaNumMazePaint, numInt);
TxPrintf("%d external stems painted.\n", gaNumExtPaint);
TxPrintf("%d total stems painted.\n", numInt + gaNumExtPaint);
}
}
/*
* ----------------------------------------------------------------------------
*
* gaStemPaint --
*
* Paint a single stem.
* Terminals that don't lie inside a river-routing channel are "external"
* and are handled by the standard router stem-generator. Terminals that
* lie inside a river-routing channel are "internal"; they are connected
* to their stem tips on the channel boundary using simple routes if
* possible, and failing that using the Magic maze-router (mzrouter).
*
* Results:
* None.
*
* Side effects:
* Adds paint to 'routeUse->cu_def'.
*
* ----------------------------------------------------------------------------
*/
void
gaStemPaint(routeUse, terminalLoc)
CellUse *routeUse;
NLTermLoc *terminalLoc;
{
TileTypeBitMask terminalLayerMask; /* Possible layers for stem at
terminal */
TileTypeBitMask pinLayerMask; /* Possible layers for stem at pin */
Rect errArea;
char *errReason;
GCRPin *pin;
short flags;
/*
* Find the pin used for this stem. If this pin wasn't actually
* used by the global router, there's no point in routing a stem
* to it so we return.
*/
pin = terminalLoc->nloc_pin;
if (pin->gcr_pId == (GCRNet *) NULL)
return;
/*
* Figure out which layers are OK to start routing and which
* layers are OK to finish up on. Perform a sanity check:
* if the destination layer isn't one of the legal routing
* layers, just return. (This will catch pins that were
* supposed to be routed by the channel router, but which
* it was unable to connect to).
*/
flags = pin->gcr_ch->gcr_result[pin->gcr_x][pin->gcr_y];
if (!rtrStemMask(routeUse, terminalLoc, flags,
&terminalLayerMask, &pinLayerMask))
{
errReason = "Terminal is not on a legal routing layer";
GEO_EXPAND(&terminalLoc->nloc_rect, 1, &errArea);
goto failure;
}
if (!TTMaskHasType(&pinLayerMask, RtrMetalType)
&& !TTMaskHasType(&pinLayerMask, RtrPolyType))
{
/* To do: connect down to pin layer with contacts. */
/* Or, just let the maze router handle this. */
}
/*
* The terminal could be internal (terminalLoc->nloc_rect lies
* inside a river-routing channel) or external (terminalLoc->nloc_rect
* lies outside of a channel but the stem tip borders on a normal
* routing channel). In the latter case, use the old stem
* generation code (temporary measure until we get our own
* code working).
*/
if (!RtrMazeStems && (pin->gcr_linked == (GCRPin *) NULL))
{
/* Terminal didn't lie in a river-routing channel */
(void) RtrStemPaintExt(routeUse, terminalLoc);
gaNumExtPaint++;
return;
}
ASSERT(pin->gcr_linked->gcr_ch->gcr_type != CHAN_NORMAL, "gaStemPaint");
/*
* Try a simple stem.
*/
if (!RtrMazeStems)
{
SimpleStem simple;
Point *gridPoint = &(terminalLoc->nloc_stem);
int side = terminalLoc->nloc_dir;
if (gaStemSimpleInit(routeUse, terminalLoc, gridPoint, side, &simple))
{
/* try ending on "metal" */
if (TTMaskHasType(&pinLayerMask, RtrMetalType))
{
if(gaStemSimpleRoute(&simple,RtrMetalType,routeUse->cu_def))
{
gaNumSimplePaint++;
return;
}
}
/* didn't work, so try ending on "poly" */
if (TTMaskHasType(&pinLayerMask, RtrPolyType))
{
if(gaStemSimpleRoute(&simple,RtrPolyType,routeUse->cu_def))
{
gaNumSimplePaint++;
return;
}
}
}
}
/*
* Try the maze router.
*/
if (RtrMazeStems)
{
Point *pinPoint = &(terminalLoc->nloc_stem);
int side = terminalLoc->nloc_dir;
bool writeResult = TRUE;
extern CellDef *gaMazeTopDef; /* Forward declaration quick hack. */
/* Note that by not running the gate array router, we may not */
/* have initialized the maze router at this point. */
if ((gaMazeTopDef == NULL) && (EditCellUse != NULL))
if (gaMazeInit(EditCellUse) == FALSE)
goto totalLoss;
if(gaMazeRoute(routeUse, terminalLoc, pinPoint, &pinLayerMask, side,
writeResult))
{
gaNumMazePaint++;
if(DebugIsSet(gaDebugID,gaDebShowMaze))
/* Feedback all maze routes so we can check them
* (this will cause all maze routes to be reported as
* routing errors)
*/
{
Rect area;
area = terminalLoc->nloc_rect;
GeoIncludePoint(&terminalLoc->nloc_stem, &area);
if (GEO_RECTNULL(&area))
{
GEO_EXPAND(&area, 1, &area);
}
DBWFeedbackAdd(&area,
"MAZE ROUTE",
routeUse->cu_def,
1,
STYLE_PALEHIGHLIGHTS);
}
return;
}
}
/*
* Total loss.
* This should never happen! But there are a few cases when it can,
* such as if we have given a difficult path to route from the channel,
* over obstructions, to the pin, requiring the maze router, and the
* maze router is not set up in the technology file.
*/
totalLoss:
errReason = "Couldn't maze route final connection";
errArea = terminalLoc->nloc_rect;
GeoIncludePoint(&terminalLoc->nloc_stem, &errArea);
if (GEO_RECTNULL(&errArea))
{
GEO_EXPAND(&errArea, 1, &errArea);
}
failure:
DBWFeedbackAdd(&errArea, errReason, routeUse->cu_def, 1,
STYLE_PALEHIGHLIGHTS);
}
Reference in New Issue View Git Blame Copy Permalink