mirror of
https://github.com/RTimothyEdwards/magic.git
synced 2026-08-29 17:39:28 +02:00
R. Timothy Edwards
04e91d640d
to material in a child cell, and the label is a point or line label, and the parent cell has no material other than the label in the immediate area, then the "interaction area" will have zero area, which will cause problems as area checks on a zero-sized area don't do anything useful. The solution is to ensure that interaction areas do not have zero area, but will expand around point labels. This should not have any other implications, because the interaction area is just a way to limit the amount of processing; larger interaction areas do not affect the extraction result (except in this case, where it fixes the error).
1159 lines
35 KiB
C
1159 lines
35 KiB
C
/*
|
|
* ExtHier.c --
|
|
*
|
|
* Circuit extraction.
|
|
* Lower-level procedures common both to ordinary subtree extraction,
|
|
* and to array extraction.
|
|
* The procedures in this file are not re-entrant.
|
|
*
|
|
* *********************************************************************
|
|
* * 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/extract/ExtHier.c,v 1.3 2010/06/24 12:37:17 tim Exp $";
|
|
#endif /* not lint */
|
|
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <math.h>
|
|
|
|
#include "utils/magic.h"
|
|
#include "utils/geometry.h"
|
|
#include "utils/geofast.h"
|
|
#include "tiles/tile.h"
|
|
#include "utils/hash.h"
|
|
#include "database/database.h"
|
|
#include "utils/malloc.h"
|
|
#include "textio/textio.h"
|
|
#include "utils/styles.h"
|
|
#include "windows/windows.h"
|
|
#include "dbwind/dbwind.h"
|
|
#include "debug/debug.h"
|
|
#include "extract/extract.h"
|
|
#include "extract/extractInt.h"
|
|
|
|
/* Local data */
|
|
|
|
/* Passed to search functions by extHierConnections */
|
|
ExtTree *extHierCumFlat; /* Cum buffer */
|
|
ExtTree *extHierOneFlat; /* Subtree being compared with extHierCumFlat */
|
|
|
|
/* List of free cells around for use in yanking subtrees */
|
|
ExtTree *extHierFreeOneList = (ExtTree *) NULL;
|
|
|
|
/* Appended to the name of each new CellDef created by extHierNewOne() */
|
|
int extHierOneNameSuffix = 0;
|
|
|
|
/* Forward declarations */
|
|
int extHierConnectFunc1();
|
|
int extHierConnectFunc2();
|
|
int extHierConnectFunc3();
|
|
Node *extHierNewNode();
|
|
|
|
/*
|
|
*----------------------------------------------------------------------
|
|
*
|
|
* extTestNMInteract --
|
|
*
|
|
* Determine if two tiles overlap, including split tiles. Since
|
|
* this is a much more complicated check than the simple overlap
|
|
* of two rectangular tiles, it is assumed that at least tile t1
|
|
* is a split tile, and does not check for simple rectangular
|
|
* overlap. The insideness test is the same used by
|
|
* DBSrPaintNMArea(), but in the context of extHierConnectFunc,
|
|
* the two tiles are already known, so just run the equations.
|
|
* Because this test is for electrical connectivity, touching
|
|
* shapes are equivalent to overlapping shapes.
|
|
*
|
|
* The information about which side of a triangular tile is to
|
|
* be checked for overlap is in the "dinfo" argument corresponding
|
|
* to the tile. If the tile is not a split tile, then "dinfo" is
|
|
* ignored.
|
|
*
|
|
* Tile t1 is always a split tile. Tile t2 may be a simple Manhattan
|
|
* tile, in which case the possibility that t2 has "infinite" width
|
|
* or height must be considered.
|
|
*
|
|
* Results:
|
|
* TRUE if the tiles overlap or touch, FALSE if not.
|
|
*
|
|
* Side effects:
|
|
* None.
|
|
*
|
|
*----------------------------------------------------------------------
|
|
*/
|
|
|
|
bool extTestNMInteract(Tile *t1, TileType di1, Tile *t2, TileType di2)
|
|
{
|
|
Rect rect1;
|
|
TileType tt1;
|
|
|
|
/* Turn the first tile into a Rect and a TileType containing
|
|
* the information about both diagonal and split side, and
|
|
* then call the function DBTestNMInteract() which is used by
|
|
* DBSrPaintNMArea() to determine interaction between non-
|
|
* Manhattan areas. Note that DBTestNMInteract() is called
|
|
* with the overlap_only flag set to FALSE because this should
|
|
* test for shapes either overlapping *or* touching.
|
|
*/
|
|
|
|
TiToRect(t1, &rect1);
|
|
tt1 = TiGetTypeExact(t1) | di1;
|
|
|
|
return DBTestNMInteract(&rect1, tt1, t2, di2, FALSE);
|
|
}
|
|
|
|
/*
|
|
*----------------------------------------------------------------------
|
|
* extHierSubShieldFunc --
|
|
*
|
|
* Simple callback function for extHierSubstrate() that halts the
|
|
* search if any substrate shield type is found in the search area
|
|
*
|
|
*----------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
extHierSubShieldFunc(tile, dinfo, clientdata)
|
|
Tile *tile; /* (unused) */
|
|
TileType dinfo; /* (unused) */
|
|
ClientData clientdata; /* (unused) */
|
|
{
|
|
return 1;
|
|
}
|
|
|
|
/*
|
|
*----------------------------------------------------------------------
|
|
* extHierSubstrate --
|
|
*
|
|
* Find the substrate node of a child cell and make a connection
|
|
* between parent and child substrates. If either of the
|
|
* substrate nodes is already in the hash table, then the table
|
|
* will be updated as necessary.
|
|
*
|
|
* This function also determines if a child cell's substrate is
|
|
* isolated by a substrate shield type, in which case no merge is
|
|
* done.
|
|
*
|
|
*----------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
extHierSubstrate(ha, use, x, y)
|
|
HierExtractArg *ha; // Contains parent def and hash table
|
|
CellUse *use; // Child use
|
|
int x, y; // Array subscripts, or -1 if not an array
|
|
{
|
|
NodeRegion *nodeList;
|
|
HashTable *table = &ha->ha_connHash;
|
|
HashEntry *he;
|
|
NodeName *nn;
|
|
Node *node1, *node2;
|
|
char *name1, *name2, *childname;
|
|
CellDef *def;
|
|
Rect subArea;
|
|
int pNum;
|
|
|
|
NodeRegion *extFindNodes();
|
|
|
|
/* Backwards compatibility with tech files that don't */
|
|
/* define a substrate plane or substrate connections. */
|
|
if (glob_subsnode == NULL) return;
|
|
|
|
/* If the substrate has already been extracted for this use */
|
|
/* then there is no need to do it again. */
|
|
if (use->cu_flags & CU_SUB_EXTRACTED) return;
|
|
|
|
/* Don't extract anything from cells marked "don't use". */
|
|
if (use->cu_def->cd_flags & CDDONTUSE) return;
|
|
|
|
def = (CellDef *)ha->ha_parentUse->cu_def;
|
|
|
|
/* Register the name of the parent's substrate */
|
|
/* The parent def's substrate node is in glob_subsnode */
|
|
|
|
name1 = extNodeName(glob_subsnode);
|
|
if (*name1 == '(' && !strcmp(name1, "(none)")) return; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name1);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node1 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
/* Find the child's substrate node */
|
|
nodeList = extFindNodes(use->cu_def, (Rect *) NULL, TRUE);
|
|
if (nodeList == NULL)
|
|
{
|
|
ExtResetTiles(use->cu_def, CLIENTDEFAULT);
|
|
return;
|
|
}
|
|
|
|
/* Check if the child's substrate node is covered by any substrate */
|
|
/* shield type (e.g., deep nwell). This is a stupid-simple check */
|
|
/* on the node's lower left point. This will fail if (1) only */
|
|
/* space exists on the substrate plane in the child cell, or (2) if */
|
|
/* some but not all devices in the child are covered by a shield */
|
|
/* type. Item (1) is handled by checking if the region point is */
|
|
/* outside the cell bound and using the cell bound as the search */
|
|
/* area if so. However, it really should look for a device in the */
|
|
/* subcell that connects to the substrate. Item (2) is up to the */
|
|
/* designer to avoid (but should be flagged as an extraction */
|
|
/* error). */
|
|
|
|
if (GEO_ENCLOSE(&nodeList->nreg_ll, &use->cu_def->cd_bbox))
|
|
{
|
|
GeoTransPoint(&use->cu_transform, &nodeList->nreg_ll, &subArea.r_ll);
|
|
subArea.r_ur.p_x = subArea.r_ll.p_x + 1;
|
|
subArea.r_ur.p_y = subArea.r_ll.p_y + 1;
|
|
}
|
|
else
|
|
{
|
|
/* Check area under all of the subcircuit (not just the part */
|
|
/* in the current interaction area). */
|
|
GeoTransRect(&use->cu_transform, &use->cu_def->cd_bbox, &subArea);
|
|
}
|
|
|
|
for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
|
|
{
|
|
if (TTMaskIntersect(&DBPlaneTypes[pNum],
|
|
&ExtCurStyle->exts_globSubstrateShieldTypes))
|
|
{
|
|
if (DBSrPaintArea((Tile *) NULL,
|
|
def->cd_planes[pNum], &subArea,
|
|
&ExtCurStyle->exts_globSubstrateShieldTypes,
|
|
extHierSubShieldFunc, (ClientData)NULL) != 0)
|
|
{
|
|
freeMagic(nodeList);
|
|
ExtResetTiles(use->cu_def, CLIENTDEFAULT);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Make sure substrate labels are represented */
|
|
ExtLabelRegions(use->cu_def, ExtCurStyle->exts_nodeConn, &nodeList,
|
|
&TiPlaneRect);
|
|
ExtResetTiles(use->cu_def, CLIENTDEFAULT);
|
|
|
|
name2 = extNodeName(temp_subsnode);
|
|
|
|
if (x >= 0 && y >= 0)
|
|
{
|
|
/* Process array information */
|
|
childname = mallocMagic(strlen(name2) + strlen(use->cu_id) + 14);
|
|
sprintf(childname, "%s[%d,%d]/%s", use->cu_id, y, x, name2);
|
|
}
|
|
else if (x >= 0 || y >= 0)
|
|
{
|
|
childname = mallocMagic(strlen(name2) + strlen(use->cu_id) + 9);
|
|
sprintf(childname, "%s[%d]/%s", use->cu_id, ((x >= 0) ? x : y),
|
|
name2);
|
|
}
|
|
else
|
|
{
|
|
childname = mallocMagic(strlen(name2) + strlen(use->cu_id) + 2);
|
|
sprintf(childname, "%s/%s", use->cu_id, name2);
|
|
}
|
|
he = HashFind(table, childname);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node2 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
freeMagic(childname);
|
|
|
|
if (node1 != node2)
|
|
{
|
|
if (node1->node_len < node2->node_len)
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node2.
|
|
*/
|
|
for (nn = node1->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node2;
|
|
nn->nn_node = node2;
|
|
nn->nn_next = node2->node_names->nn_next;
|
|
node2->node_names->nn_next = node1->node_names;
|
|
node2->node_len += node1->node_len;
|
|
freeMagic((char *)node1);
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node1.
|
|
*/
|
|
for (nn = node2->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node1;
|
|
nn->nn_node = node1;
|
|
nn->nn_next = node1->node_names;
|
|
node1->node_names = node2->node_names;
|
|
node1->node_len += node2->node_len;
|
|
freeMagic((char *)node2);
|
|
}
|
|
}
|
|
freeMagic(nodeList);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierConnections --
|
|
*
|
|
* Process connections between the two ExtTrees 'oneFlat' and 'cumFlat'.
|
|
* This consists of detecting overlaps or abutments between connecting
|
|
* tiles (maybe on different planes), and recording the connection in the hash
|
|
* table ha->ha_connHash.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side effects:
|
|
* Adds connections to ha->ha_connHash.
|
|
* Doesn't change resistance or capacitance of the connected
|
|
* nodes; that is the job of extHierAdjustments().
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
extHierConnections(ha, cumFlat, oneFlat)
|
|
HierExtractArg *ha;
|
|
ExtTree *cumFlat, *oneFlat;
|
|
{
|
|
int pNum;
|
|
CellDef *sourceDef = oneFlat->et_use->cu_def;
|
|
Label *lab;
|
|
|
|
extHierCumFlat = cumFlat;
|
|
extHierOneFlat = oneFlat;
|
|
for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
|
|
{
|
|
ha->hierPNum = pNum;
|
|
(void) DBSrPaintArea((Tile *) NULL,
|
|
sourceDef->cd_planes[pNum], &ha->ha_subArea,
|
|
&DBAllButSpaceBits, extHierConnectFunc1, (ClientData) ha);
|
|
}
|
|
|
|
/* Look for sticky labels in the child cell that are not */
|
|
/* connected to any geometry. */
|
|
|
|
if (!(ExtOptions & EXT_DOLABELCHECK)) return;
|
|
|
|
for (lab = sourceDef->cd_labels; lab; lab = lab->lab_next)
|
|
{
|
|
CellDef *cumDef;
|
|
Rect r;
|
|
TileTypeBitMask *connected;
|
|
|
|
if (!(lab->lab_flags & LABEL_STICKY)) continue;
|
|
|
|
r = lab->lab_rect;
|
|
if (!GEO_TOUCH(&r, &ha->ha_subArea)) continue;
|
|
GEOCLIP(&r, &ha->ha_subArea);
|
|
|
|
cumDef = cumFlat->et_use->cu_def;
|
|
connected = &DBConnectTbl[lab->lab_type];
|
|
pNum = DBPlane(lab->lab_type);
|
|
|
|
ha->hierOneTile = (Tile *)lab; /* Blatant hack recasting */
|
|
ha->hierType = lab->lab_type;
|
|
ha->hierPNumBelow = pNum;
|
|
|
|
DBSrPaintArea((Tile *) NULL,
|
|
cumFlat->et_use->cu_def->cd_planes[pNum], &r,
|
|
connected, extHierConnectFunc3, (ClientData) ha);
|
|
}
|
|
}
|
|
|
|
/*
|
|
* extHierConnectFunc1 --
|
|
*
|
|
* Called for each tile 'oneTile' in the ExtTree 'oneFlat' above
|
|
* that lies in the area ha->ha_subArea.
|
|
*
|
|
* Results:
|
|
* Returns 0 always.
|
|
*
|
|
* Side effects:
|
|
* None here, but see extHierConnectFunc2().
|
|
*/
|
|
|
|
int
|
|
extHierConnectFunc1(oneTile, dinfo, ha)
|
|
Tile *oneTile; /* Comes from 'oneFlat' in extHierConnections */
|
|
TileType dinfo; /* Split tile information (unused) */
|
|
HierExtractArg *ha; /* Extraction context */
|
|
{
|
|
CellDef *cumDef = extHierCumFlat->et_use->cu_def;
|
|
Rect r;
|
|
TileTypeBitMask mask, *connected;
|
|
TileType rtype;
|
|
Label *lab, *newlab;
|
|
int i;
|
|
unsigned n;
|
|
|
|
/*
|
|
* Find all tiles that connect to 'srcTile', but in the
|
|
* yank buffer cumDef. Adjust connectivity for each tile found.
|
|
* Widen the rectangle to detect connectivity by abutment.
|
|
*/
|
|
ha->hierOneTile = oneTile;
|
|
ha->hierType = TiGetTypeExact(oneTile);
|
|
|
|
if (IsSplit(oneTile))
|
|
{
|
|
/* For split tiles, move the tile type to lower (right side) field
|
|
* but retain the TT_SIDE bit, to indicate which side of hierOneTile
|
|
* is the connected side.
|
|
*/
|
|
ha->hierType = (dinfo & TT_SIDE) ? SplitRightType(oneTile) :
|
|
SplitLeftType(oneTile);
|
|
ha->hierType |= (dinfo & (TT_DIAGONAL | TT_DIRECTION | TT_SIDE));
|
|
}
|
|
|
|
connected = &(ExtCurStyle->exts_nodeConn[ha->hierType & TT_LEFTMASK]);
|
|
TITORECT(oneTile, &r);
|
|
GEOCLIP(&r, &ha->ha_subArea);
|
|
r.r_xbot--, r.r_ybot--, r.r_xtop++, r.r_ytop++;
|
|
for (i = PL_TECHDEPBASE; i < DBNumPlanes; i++)
|
|
{
|
|
ha->hierPNumBelow = i;
|
|
TTMaskAndMask3(&mask, connected, &DBPlaneTypes[i]);
|
|
if (!TTMaskIsZero(&mask))
|
|
{
|
|
if (IsSplit(oneTile))
|
|
DBSrPaintNMArea((Tile *) NULL, cumDef->cd_planes[i],
|
|
ha->hierType, &r,
|
|
((i == ha->hierPNum) ? &ExtCurStyle->exts_activeTypes
|
|
: connected), extHierConnectFunc2, (ClientData) ha);
|
|
else
|
|
DBSrPaintArea((Tile *) NULL, cumDef->cd_planes[i], &r,
|
|
((i == ha->hierPNum) ? &ExtCurStyle->exts_activeTypes
|
|
: connected), extHierConnectFunc2, (ClientData) ha);
|
|
}
|
|
}
|
|
|
|
/* Where labels have been saved from the parent cell, look for any */
|
|
/* that are inside the cell boundary and would connect to the tile. */
|
|
/* This allows the extractor to catch "sticky" labels that are not */
|
|
/* attached to a physical layer in the parent cell. */
|
|
|
|
if (!(ExtOptions & EXT_DOLABELCHECK)) return 0;
|
|
|
|
// NOTE by Tim, 9/10/2014: This generates phantom nodes when the
|
|
// labels are created by the "hard" node search; I think this code
|
|
// should be restricted to sticky labels only. But not certain.
|
|
// Definitely this causes problems in arrays, because the array node
|
|
// name may refer to a range of array elements, and the generated
|
|
// node only describes a single point.
|
|
|
|
for (lab = cumDef->cd_labels; lab; lab = lab->lab_next)
|
|
{
|
|
/* NOTE: Need a better way to access the sticky labels
|
|
* without running through the whole linked list. Pushing
|
|
* them to the list front may not work for reasons explained
|
|
* in extSubtreeAdjustInit().
|
|
*/
|
|
|
|
if (!(lab->lab_flags & LABEL_STICKY)) continue;
|
|
|
|
if (GEO_TOUCH(&r, &lab->lab_rect))
|
|
if (TTMaskHasType(connected, lab->lab_type))
|
|
{
|
|
HashTable *table = &ha->ha_connHash;
|
|
HashEntry *he;
|
|
NodeName *nn;
|
|
Node *node1, *node2;
|
|
char *name;
|
|
|
|
/* Register the name, like is done in extHierConnectFunc2 */
|
|
he = HashFind(table, lab->lab_text);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node1 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
name = (*ha->ha_nodename)(ha->hierOneTile, ha->hierType, ha->hierPNum,
|
|
extHierOneFlat, ha, TRUE);
|
|
if (*name == '(' && !strcmp(name, "(none)")) return 0; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node2 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
if (node1 != node2)
|
|
{
|
|
if (node1->node_len < node2->node_len)
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node2.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node1->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node2;
|
|
nn->nn_node = node2;
|
|
nn->nn_next = node2->node_names->nn_next;
|
|
node2->node_names->nn_next = node1->node_names;
|
|
node2->node_len += node1->node_len;
|
|
freeMagic((char *) node1);
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node1.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node2->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node1;
|
|
nn->nn_node = node1;
|
|
nn->nn_next = node1->node_names;
|
|
node1->node_names = node2->node_names;
|
|
node1->node_len += node2->node_len;
|
|
freeMagic((char *) node2);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return (0);
|
|
}
|
|
|
|
/*
|
|
* extHierConnectFunc2 --
|
|
*
|
|
* Called once for each tile 'cum' in extHierCumFlat->et_use->cu_def
|
|
* on the same plane as ha->hierOneTile that also overlaps or abuts
|
|
* the intersection of ha->hierOneTile with ha->ha_subArea, and for tiles
|
|
* in other planes that may connect.
|
|
*
|
|
* Results:
|
|
* Returns 0 always.
|
|
*
|
|
* Side effects:
|
|
* Makes a connection between the nodes of the two tiles
|
|
* if the types of ha->hierOneTile and 'cum' connect.
|
|
* Otherwise, if the tiles actually overlap (as opposed
|
|
* to merely abut), mark it with feedback as an error.
|
|
*/
|
|
|
|
int
|
|
extHierConnectFunc2(cum, dinfo, ha)
|
|
Tile *cum; /* Comes from extHierCumFlat->et_use->cu_def */
|
|
TileType dinfo; /* Split tile information */
|
|
HierExtractArg *ha; /* Extraction context */
|
|
{
|
|
HashTable *table = &ha->ha_connHash;
|
|
Node *node1, *node2;
|
|
TileType ttype;
|
|
HashEntry *he;
|
|
NodeName *nn;
|
|
char *name1, *name2;
|
|
Rect r;
|
|
|
|
/* Compute the overlap area */
|
|
r.r_xbot = MAX(LEFT(ha->hierOneTile), LEFT(cum));
|
|
r.r_xtop = MIN(RIGHT(ha->hierOneTile), RIGHT(cum));
|
|
r.r_ybot = MAX(BOTTOM(ha->hierOneTile), BOTTOM(cum));
|
|
r.r_ytop = MIN(TOP(ha->hierOneTile), TOP(cum));
|
|
|
|
/* If the tiles don't even touch, they don't connect */
|
|
if (r.r_xtop < r.r_xbot || r.r_ytop < r.r_ybot
|
|
|| (r.r_xtop == r.r_xbot && r.r_ytop == r.r_ybot))
|
|
return 0;
|
|
|
|
/* If either tile is a split tile, then check if the areas of
|
|
* interest overlap. The first argument to extTestNMInteract()
|
|
* must be a split tile.
|
|
*/
|
|
if (IsSplit(cum))
|
|
{
|
|
if (!extTestNMInteract(cum, dinfo, ha->hierOneTile, ha->hierType))
|
|
return 0;
|
|
}
|
|
else if (IsSplit(ha->hierOneTile))
|
|
{
|
|
if (!extTestNMInteract(ha->hierOneTile, ha->hierType, cum, dinfo))
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
* Only make a connection if the types of 'ha->hierOneTile' and 'cum'
|
|
* connect. If they overlap and don't connect, it is an error.
|
|
* If they do connect, mark their nodes as connected.
|
|
*/
|
|
|
|
ttype = TiGetTypeExact(cum);
|
|
|
|
if (IsSplit(cum))
|
|
ttype = (dinfo & TT_SIDE) ? SplitRightType(cum) : SplitLeftType(cum);
|
|
|
|
if (extConnectsTo(ha->hierType & TT_LEFTMASK, ttype, ExtCurStyle->exts_nodeConn))
|
|
{
|
|
name1 = (*ha->ha_nodename)(cum, dinfo, ha->hierPNumBelow, extHierCumFlat, ha, TRUE);
|
|
if (*name1 == '(' && !strcmp(name1, "(none)")) return 0; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name1);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node1 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
name2 = (*ha->ha_nodename)(ha->hierOneTile, ha->hierType, ha->hierPNum,
|
|
extHierOneFlat, ha, TRUE);
|
|
if (*name2 == '(' && !strcmp(name2, "(none)")) return 0; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name2);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node2 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
if (node1 != node2)
|
|
{
|
|
if (node1->node_len < node2->node_len)
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node2.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node1->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node2;
|
|
nn->nn_node = node2;
|
|
nn->nn_next = node2->node_names->nn_next;
|
|
node2->node_names->nn_next = node1->node_names;
|
|
node2->node_len += node1->node_len;
|
|
freeMagic((char *) node1);
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node1.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node2->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node1;
|
|
nn->nn_node = node1;
|
|
nn->nn_next = node1->node_names;
|
|
node1->node_names = node2->node_names;
|
|
node1->node_len += node2->node_len;
|
|
freeMagic((char *) node2);
|
|
}
|
|
}
|
|
}
|
|
else if (r.r_xtop > r.r_xbot && r.r_ytop > r.r_ybot)
|
|
{
|
|
char message[1024];
|
|
|
|
snprintf(message, sizeof(message),
|
|
"Illegal overlap between %s and %s (types do not connect)",
|
|
DBTypeLongNameTbl[ha->hierType & TT_LEFTMASK], DBTypeLongNameTbl[ttype]);
|
|
|
|
extNumErrors++;
|
|
if (!DebugIsSet(extDebugID, extDebNoFeedback))
|
|
DBWFeedbackAdd(&r, message,
|
|
ha->ha_parentUse->cu_def, 1, STYLE_MEDIUMHIGHLIGHTS);
|
|
}
|
|
|
|
return (0);
|
|
}
|
|
|
|
/*
|
|
* extHierConnectFunc3 --
|
|
*
|
|
* Called once for each tile 'cum' in extHierCumFlat->et_use->cu_def
|
|
* Similar to extHierConnectFunc2, but is called for a label in the
|
|
* parent cell that does not necessarily have associated geometry.
|
|
* Value passed in ha_oneTile is the label (recast for convenience;
|
|
* need to use a union type in HierExtractArg).
|
|
*/
|
|
|
|
int
|
|
extHierConnectFunc3(cum, dinfo, ha)
|
|
Tile *cum; /* Comes from extHierCumFlat->et_use->cu_def */
|
|
TileType dinfo; /* Split tile information */
|
|
HierExtractArg *ha; /* Extraction context */
|
|
{
|
|
HashTable *table = &ha->ha_connHash;
|
|
Node *node1, *node2;
|
|
TileType ttype;
|
|
HashEntry *he;
|
|
NodeName *nn;
|
|
char *name1, *name2;
|
|
Rect r;
|
|
Label *lab = (Label *)(ha->hierOneTile); /* Lazy recasting */
|
|
|
|
/* Compute the overlap area */
|
|
r.r_xbot = MAX(lab->lab_rect.r_xbot, LEFT(cum));
|
|
r.r_xtop = MIN(lab->lab_rect.r_xtop, RIGHT(cum));
|
|
r.r_ybot = MAX(lab->lab_rect.r_ybot, BOTTOM(cum));
|
|
r.r_ytop = MIN(lab->lab_rect.r_ytop, TOP(cum));
|
|
|
|
/* If the tiles don't even touch, they don't connect */
|
|
if (r.r_xtop < r.r_xbot || r.r_ytop < r.r_ybot)
|
|
return (0);
|
|
|
|
/*
|
|
* Only make a connection if the types of 'ha->hierOneTile' and 'cum'
|
|
* connect. If they overlap and don't connect, it is an error.
|
|
* If they do connect, mark their nodes as connected.
|
|
*/
|
|
|
|
ttype = TiGetTypeExact(cum);
|
|
|
|
if (IsSplit(cum))
|
|
ttype = (dinfo & TT_SIDE) ? SplitRightType(cum) : SplitLeftType(cum);
|
|
|
|
if (extConnectsTo(ha->hierType & TT_LEFTMASK, ttype, ExtCurStyle->exts_nodeConn))
|
|
{
|
|
name1 = (*ha->ha_nodename)(cum, ha->hierType, ha->hierPNumBelow,
|
|
extHierCumFlat, ha, TRUE);
|
|
if (*name1 == '(' && !strcmp(name1, "(none)")) return 0; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name1);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node1 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
name2 = lab->lab_text;
|
|
if (*name2 == '(' && !strcmp(name2, "(none)")) return 0; /* Don't process "(none)" nodes! */
|
|
he = HashFind(table, name2);
|
|
nn = (NodeName *) HashGetValue(he);
|
|
node2 = nn ? nn->nn_node : extHierNewNode(he);
|
|
|
|
if (node1 != node2)
|
|
{
|
|
if (node1->node_len < node2->node_len)
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node2.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node1->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node2;
|
|
nn->nn_node = node2;
|
|
nn->nn_next = node2->node_names->nn_next;
|
|
node2->node_names->nn_next = node1->node_names;
|
|
node2->node_len += node1->node_len;
|
|
freeMagic((char *) node1);
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* Both sets of names will now point to node1.
|
|
* We don't need to update node_cap since it
|
|
* hasn't been computed yet.
|
|
*/
|
|
for (nn = node2->node_names; nn->nn_next; nn = nn->nn_next)
|
|
nn->nn_node = node1;
|
|
nn->nn_node = node1;
|
|
nn->nn_next = node1->node_names;
|
|
node1->node_names = node2->node_names;
|
|
node1->node_len += node2->node_len;
|
|
freeMagic((char *) node2);
|
|
}
|
|
}
|
|
}
|
|
else if (r.r_xtop > r.r_xbot && r.r_ytop > r.r_ybot)
|
|
{
|
|
char message[1024];
|
|
|
|
snprintf(message, sizeof(message),
|
|
"Illegal overlap between %s and %s (types do not connect)",
|
|
DBTypeLongNameTbl[ha->hierType & TT_LEFTMASK], DBTypeLongNameTbl[ttype]);
|
|
|
|
extNumErrors++;
|
|
if (!DebugIsSet(extDebugID, extDebNoFeedback))
|
|
DBWFeedbackAdd(&r, message,
|
|
ha->ha_parentUse->cu_def, 1, STYLE_MEDIUMHIGHLIGHTS);
|
|
}
|
|
|
|
return (0);
|
|
}
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierAdjustments --
|
|
*
|
|
* Process adjustments to substrate capacitance, coupling capacitance,
|
|
* node perimeter, and node area between the subtree 'oneFlat' and the
|
|
* cumulative yank buffer 'cumFlat'. The subtree 'lookFlat' is used
|
|
* for looking up node names when handling capacitance/perimeter/area
|
|
* adjustment.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side effects:
|
|
* Updates capacitance in the table cumFlat->et_coupleHash.
|
|
* Updates capacitance, perimeter, and area recorded in the
|
|
* nodes of 'cumFlat'.
|
|
*
|
|
* Algorithm:
|
|
* For each capacitor recorded in oneFlat->et_coupleHash, find
|
|
* the corresponding nodes in 'cumFlat' and subtract the
|
|
* capacitance from the entry indexed by these nodes in the
|
|
* table cumFlat->et_coupleHash.
|
|
*
|
|
* For each node in oneFlat->et_nodes, find the corresponding
|
|
* node in 'lookFlat'. Look for the Node with this name in
|
|
* the table ha->ha_connHash, and subtract the oneFlat node's
|
|
* capacitance, perimeter, and area from it. If no Node is
|
|
* found in this table, don't do anything since the oneFlat
|
|
* node must not participate in any connections.
|
|
*
|
|
* The node in 'cumFlat' corresponding to one in 'oneFlat'
|
|
* is the one containing some point in 'oneFlat', since 'oneFlat'
|
|
* is a strict subset of 'cumFlat'.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
extHierAdjustments(ha, cumFlat, oneFlat, lookFlat)
|
|
HierExtractArg *ha;
|
|
ExtTree *cumFlat, *oneFlat, *lookFlat;
|
|
{
|
|
HashEntry *he, *heCum;
|
|
int n;
|
|
CoupleKey *ckpOne, ckCum;
|
|
NodeRegion *np;
|
|
HashSearch hs;
|
|
NodeName *nn;
|
|
Tile *tp;
|
|
char *name;
|
|
|
|
/* Update all coupling capacitors */
|
|
if (ExtOptions & EXT_DOCOUPLING)
|
|
{
|
|
HashStartSearch(&hs);
|
|
while ((he = HashNext(&oneFlat->et_coupleHash, &hs)))
|
|
{
|
|
ckpOne = ((CoupleKey *) he->h_key.h_words);
|
|
|
|
/* Find nodes in cumFlat->et_coupleHash */
|
|
NODETONODE(ckpOne->ck_1, cumFlat, ckCum.ck_1);
|
|
NODETONODE(ckpOne->ck_2, cumFlat, ckCum.ck_2);
|
|
if (ckCum.ck_1 == NULL || ckCum.ck_2 == NULL) continue;
|
|
|
|
/* Skip if the same; reverse to make smaller node pointer first */
|
|
if (ckCum.ck_1 == ckCum.ck_2) continue;
|
|
if (ckCum.ck_2 < ckCum.ck_1)
|
|
np = ckCum.ck_1, ckCum.ck_1 = ckCum.ck_2, ckCum.ck_2 = np;
|
|
|
|
/* Update the capacitor record in cumFlat->et_coupleHash */
|
|
heCum = HashFind(&cumFlat->et_coupleHash, (char *) &ckCum);
|
|
extSetCapValue(heCum, extGetCapValue(heCum) - extGetCapValue(he));
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Update all node values.
|
|
* Find the corresponding tile in the ExtTree lookFlat, then look
|
|
* for its name. If this name appear in the connection hash table,
|
|
* update the capacitance, perimeter, and area stored there; otherwise
|
|
* ignore it.
|
|
*
|
|
* The FALSE argument to (*ha->ha_nodename)() means that we don't bother
|
|
* looking for node names the hard way; if we didn't already have a valid
|
|
* node name then it couldn't appear in the table ha->ha_connHash in the
|
|
* first place.
|
|
*/
|
|
for (np = oneFlat->et_nodes; np; np = np->nreg_next)
|
|
{
|
|
TileType dinfo;
|
|
|
|
/* Ignore orphaned nodes (non-Manhattan shards outside the clip box) */
|
|
if (np->nreg_pnum == DBNumPlanes) continue;
|
|
|
|
tp = extNodeToTile(np, lookFlat, &dinfo);
|
|
|
|
/* Ignore regions that do not participate in extraction */
|
|
if (!extHasRegion(tp, CLIENTDEFAULT)) continue;
|
|
|
|
/* Ignore substrate nodes (failsafe: should not happen) */
|
|
if (TiGetTypeExact(tp) == TT_SPACE) continue;
|
|
|
|
if (tp && (name = (*ha->ha_nodename)(tp, dinfo, np->nreg_pnum, lookFlat, ha, FALSE))
|
|
&& (he = HashLookOnly(&ha->ha_connHash, name))
|
|
&& (nn = (NodeName *) HashGetValue(he)))
|
|
{
|
|
/* Adjust the capacitance and resistance on the node */
|
|
nn->nn_node->node_cap -= np->nreg_cap;
|
|
for (n = 0; n < ExtCurStyle->exts_numResistClasses; n++)
|
|
{
|
|
nn->nn_node->node_pa[n].pa_perim -= np->nreg_pa[n].pa_perim;
|
|
nn->nn_node->node_pa[n].pa_area -= np->nreg_pa[n].pa_area;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extOutputConns --
|
|
*
|
|
* Dump the contents of the hash table 'table' of connectivity and
|
|
* node R, C adjustments to the output file outf.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side effects:
|
|
* Outputs a number of "merge" records to the file 'outf'.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
extOutputConns(table, outf)
|
|
HashTable *table;
|
|
FILE *outf;
|
|
{
|
|
CapValue c; /* cap value */
|
|
NodeName *nn, *nnext;
|
|
Node *node;
|
|
int n;
|
|
NodeName *nfirst;
|
|
HashSearch hs;
|
|
HashEntry *he;
|
|
|
|
HashStartSearch(&hs);
|
|
while ((he = HashNext(table, &hs)))
|
|
{
|
|
nfirst = (NodeName *) HashGetValue(he);
|
|
|
|
/*
|
|
* If nfirst->nn_node == NULL, the name for this hash entry
|
|
* had been output previously as a member of the merge list
|
|
* for a node appearing earlier in the table. If so, we need
|
|
* only free the NodeName without any further processing.
|
|
*/
|
|
if ((node = nfirst->nn_node))
|
|
{
|
|
/*
|
|
* If there are N names for this node, output N-1 merge lines.
|
|
* Only the first merge line will contain the C, perimeter,
|
|
* and area updates.
|
|
*/
|
|
/* Note 3/1/2017: Cap value no longer used */
|
|
c = (node->node_cap) / ExtCurStyle->exts_capScale;
|
|
nn = node->node_names;
|
|
if ((nnext = nn->nn_next))
|
|
{
|
|
/* First merge */
|
|
fprintf(outf, "merge \"%s\" \"%s\" %lg",
|
|
nn->nn_name, nnext->nn_name, c);
|
|
for (n = 0; n < ExtCurStyle->exts_numResistClasses; n++)
|
|
fprintf(outf, " %"DLONG_PREFIX"d %d",
|
|
node->node_pa[n].pa_area,
|
|
node->node_pa[n].pa_perim);
|
|
fprintf(outf, "\n");
|
|
|
|
nn->nn_node = (Node *) NULL; /* Processed */
|
|
|
|
/* Subsequent merges */
|
|
for (nn = nnext; (nnext = nn->nn_next); nn = nnext)
|
|
{
|
|
fprintf(outf, "merge \"%s\" \"%s\"\n",
|
|
nn->nn_name, nnext->nn_name);
|
|
nn->nn_node = (Node *) NULL; /* Processed */
|
|
}
|
|
}
|
|
nn->nn_node = (Node *) NULL;
|
|
freeMagic((char *) node);
|
|
}
|
|
freeMagic((char *) nfirst);
|
|
}
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierNewNode --
|
|
*
|
|
* Create a new NodeName and Node to go with the HashEntry supplied.
|
|
* The NodeName will point to the new Node, which will point back to the
|
|
* NodeName.
|
|
*
|
|
* Results:
|
|
* Returns a pointer to the newly created Node.
|
|
*
|
|
* Side effects:
|
|
* Allocates memory.
|
|
* Sets (via HashSetValue) the value of HashEntry 'he' to the
|
|
* newly created NodeName.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
Node *
|
|
extHierNewNode(he)
|
|
HashEntry *he;
|
|
{
|
|
int n, nclasses;
|
|
NodeName *nn;
|
|
Node *node;
|
|
|
|
nclasses = ExtCurStyle->exts_numResistClasses;
|
|
n = (nclasses - 1) * sizeof (PerimArea) + sizeof (Node);
|
|
nn = (NodeName *) mallocMagic((unsigned) (sizeof (NodeName)));
|
|
node = (Node *) mallocMagic((unsigned) n);
|
|
|
|
nn->nn_node = node;
|
|
nn->nn_next = (NodeName *) NULL;
|
|
nn->nn_name = he->h_key.h_name;
|
|
node->node_names = nn;
|
|
node->node_cap = (CapValue) 0;
|
|
node->node_len = 1;
|
|
for (n = 0; n < nclasses; n++)
|
|
node->node_pa[n].pa_perim = node->node_pa[n].pa_area = 0;
|
|
HashSetValue(he, (char *) nn);
|
|
|
|
return (node);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierLabFirst --
|
|
* extHierLabEach --
|
|
*
|
|
* Filter functions passed to ExtFindRegions when tracing out labelled
|
|
* regions as part of a hierarchical circuit extraction.
|
|
*
|
|
* Results:
|
|
* extHierLabFirst returns a pointer to a new LabRegion.
|
|
* extHierLabEach returns 0 always.
|
|
*
|
|
* Side effects:
|
|
* Memory is allocated by extHierLabFirst(); it conses the newly
|
|
* allocated region onto the front of the existing region list.
|
|
* The node-naming info (reg_ll, reg_pnum) is updated by
|
|
* extHierLabEach().
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
/*ARGSUSED*/
|
|
ExtRegion *
|
|
extHierLabFirst(tile, dinfo, arg)
|
|
Tile *tile;
|
|
TileType dinfo; /* (unused) */
|
|
FindRegion *arg;
|
|
{
|
|
LabRegion *new;
|
|
|
|
new = (LabRegion *) mallocMagic((unsigned) (sizeof (LabRegion)));
|
|
new->lreg_next = (LabRegion *) NULL;
|
|
new->lreg_labels = (LabelList *) NULL;
|
|
new->lreg_pnum = DBNumPlanes;
|
|
|
|
/* Prepend it to the region list */
|
|
new->lreg_next = (LabRegion *) arg->fra_region;
|
|
arg->fra_region = (ExtRegion *) new;
|
|
|
|
return ((ExtRegion *) new);
|
|
}
|
|
|
|
/*ARGSUSED*/
|
|
int
|
|
extHierLabEach(tile, dinfo, pNum, arg)
|
|
Tile *tile;
|
|
TileType dinfo;
|
|
int pNum;
|
|
FindRegion *arg;
|
|
{
|
|
LabRegion *reg;
|
|
|
|
reg = (LabRegion *) arg->fra_region;
|
|
extSetNodeNum(reg, pNum, tile, dinfo);
|
|
return (0);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierNewOne --
|
|
*
|
|
* Allocate a new ExtTree for use in hierarchical extraction.
|
|
* This ExtTree will be used to hold an entire flattened subtree.
|
|
* We try to return one from our free list if one exists; if none
|
|
* are left, we create a new CellDef and CellUse and allocate a
|
|
* new ExtTree. The new CellDef has a name of the form __EXTTREEn__,
|
|
* where 'n' is a small integer.
|
|
*
|
|
* The HashTable et_coupleHash will be initialized but empty.
|
|
* The node list et_nodes, the next pointer et_next, and the CellDef
|
|
* pointer et_lookNames will all be set to NULL.
|
|
*
|
|
* Results:
|
|
* Returns a pointer to a new ExtTree.
|
|
*
|
|
* Side effects:
|
|
* See above.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
ExtTree *
|
|
extHierNewOne()
|
|
{
|
|
char defname[128];
|
|
CellDef *dummy;
|
|
ExtTree *et;
|
|
|
|
if (extHierFreeOneList)
|
|
{
|
|
et = extHierFreeOneList;
|
|
extHierFreeOneList = et->et_next;
|
|
}
|
|
else
|
|
{
|
|
et = (ExtTree *) mallocMagic((unsigned)(sizeof (ExtTree)));
|
|
(void) sprintf(defname, "__EXTTREE%d__", extHierOneNameSuffix++);
|
|
DBNewYank(defname, &et->et_use, &dummy);
|
|
}
|
|
|
|
et->et_next = (ExtTree *) NULL;
|
|
et->et_lookNames = (CellDef *) NULL;
|
|
et->et_nodes = (NodeRegion *) NULL;
|
|
if (ExtOptions & EXT_DOCOUPLING)
|
|
HashInit(&et->et_coupleHash, 32, HashSize(sizeof (CoupleKey)));
|
|
return (et);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* extHierFreeOne --
|
|
*
|
|
* Return an ExtTree allocated via extHierNewOne() above to the
|
|
* free list. Frees the HashTable et->et_coupleHash, any NodeRegions
|
|
* on the list et->et_nodes, any labels on the label list and any
|
|
* paint in the cell et->et_use->cu_def.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side effects:
|
|
* See above.
|
|
* The caller should NOT use et->et_next after this procedure
|
|
* has returned.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
extHierFreeOne(et)
|
|
ExtTree *et;
|
|
{
|
|
if (ExtOptions & EXT_DOCOUPLING)
|
|
extCapHashKill(&et->et_coupleHash);
|
|
if (et->et_nodes) ExtFreeLabRegions((LabRegion *) et->et_nodes);
|
|
extHierFreeLabels(et->et_use->cu_def);
|
|
DBCellClearDef(et->et_use->cu_def);
|
|
|
|
et->et_next = extHierFreeOneList;
|
|
extHierFreeOneList = et;
|
|
}
|