magic/garouter/gaStem.c

/*
 * 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);
}