145
153
/** Cost of making a turn. */ private static final int COSTTURNING = 1;
146
154
/** Cost of having coordinates that are off-grid. */ private static final int COSTOFFGRID = 15;
148
/** Bit set in network ID for virtual blockage. */ private static final int OFFSETVIRTUAL = 1;
149
/** Bit set in network ID for blockage on end A. */ private static final int OFFSETENDA = 2;
150
/** Bit set in network ID for blockage on end B. */ private static final int OFFSETENDB = 4;
157
/** Bit set in network ID for fake endpoint blockage. */ private static final int BLOCKAGEFAKEENDPOINT = 1;
158
/** Bit set in network ID for blockage on end A. */ private static final int BLOCKAGEENDA = 2;
159
/** Bit set in network ID for blockage on end B. */ private static final int BLOCKAGEENDB = 4;
160
/** Bit set in network ID for user-supplied blockage. */ private static final int BLOCKAGEFAKEUSERSUPPLIED = 8;
161
/** Number of bits to shift to skip blockage bits */ private static final int SHIFTBLOCKBITS = 4;
152
public static SearchVertex svAborted = new SearchVertex(0, 0, 0, 0, null, null, 0, null);
153
public static SearchVertex svExhausted = new SearchVertex(0, 0, 0, 0, null, null, 0, null);
154
public static SearchVertex svLimited = new SearchVertex(0, 0, 0, 0, null, null, 0, null);
155
public static SearchVertex svAbandoned = new SearchVertex(0, 0, 0, 0, null, null, 0, null);
163
public static SearchVertex svAborted = new SearchVertex(0, 0, 0, 0, 0, null, null, 0, null, 0);
164
public static SearchVertex svExhausted = new SearchVertex(0, 0, 0, 0, 0, null, null, 0, null, 0);
165
public static SearchVertex svLimited = new SearchVertex(0, 0, 0, 0, 0, null, null, 0, null, 0);
166
public static SearchVertex svAbandoned = new SearchVertex(0, 0, 0, 0, 0, null, null, 0, null, 0);
157
168
/** number of metal layers in the technology. */ private static int numMetalLayers;
159
/** Environment */ protected Environment env;
170
/** Environment */ private Environment env;
160
171
/** Cell in which routing occurs. */ private Cell cell;
161
172
/** true to run to/from and from/to routing in parallel */ private boolean parallelDij;
162
173
/** for logging errors */ private ErrorLogger errorLogger;
163
174
/** Cell size. */ private Rectangle2D cellBounds;
175
/** Cell-wide routing limit */ private ERectangle routingBoundsLimit;
164
176
/** Technology to use for routing. */ private Technology tech;
165
/** metal layers in the technology. */ private Layer[] metalLayers;
177
/** metal layers in the technology. */ private Layer[][] metalLayers;
178
/** single layer to use for each metal level. */ private Layer[] primaryMetalLayer;
166
179
/** via layers in the technology. */ private Layer[] viaLayers;
167
/** arcs to use for each metal layer. */ private ArcProto[] metalArcs;
180
/** layer that removes metal in the technology. */ private Map<Layer,Layer> removeLayers;
181
/** arcs to use for each metal layer. */ private ArcProto[][] metalArcs;
182
/** pure-layer nodes to use for each metal layer. */ private PrimitiveNode[][] metalPureLayerNodes;
183
/** single arc to use for each metal layer. */ private ArcProto[] primaryMetalArc;
184
/** maximum default arc width. */ private double[] maxDefArcWidth;
185
/** minimum area for a layer. */ private double[] minimumArea;
186
/** minimum resolution for technology. */ private double minResolution;
187
/** size of 2X arcs. */ private double[] size2X;
188
/** maximum length of tapers. */ private double[] taperLength;
168
189
/** favoritism for each metal layer. */ private boolean[] favorArcs;
169
190
/** avoidance for each metal layer. */ private boolean[] preventArcs;
170
/** vias to use to go up from each metal layer. */ private MetalVias[] metalVias;
171
/** metal gridding for the cell. */ private double[][] metalGrid;
191
/** arcs that can only be tapers. */ private boolean[] taperOnlyArcs;
192
/** vias to use to go up from each metal layer. */ private MetalVias[] metalVias, metalVias2X;
193
/** metal gridding for the cell. */ private SeaOfGatesTrack[][] metalGrid;
172
194
/** metal gridding range for the cell. */ private double[] metalGridRange;
173
/** maximum possible DRC surround around the metal. */ private double[] metalSurround;
174
/** worst spacing rule for a given metal layer. */ private double[] worstMetalSurround;
175
/** minimum spacing between the centers of two vias. */ private double[] viaSurround;
195
/** spacing rules for a given metal layer. */ private double[] metalSurroundX, metalSurroundY;
196
/** minimum spacing between the corners of two vias. */ private double[] viaSurround;
197
/** minimum size of two vias. */ private double[] viaSize;
176
198
/** R-Trees for routing blockages */ private BlockageTrees rTrees;
177
199
/** converts Networks to unique integers */ private Map<Network, Integer> netIDs;
178
200
/** preferences */ private SeaOfGates.SeaOfGatesOptions prefs;
179
/** interaction with outer environment */ public Handler handler;
201
/** interaction with outer environment */ private Handler handler;
180
202
/** EditingPreferences */ private EditingPreferences ep;
181
203
/** cell-specific parameters */ private SeaOfGatesCellParameters sogp;
182
204
/** taps that need to be added to spine routes */ private List<NeededRoute> tapRoutes;
1199
1414
overridePreventArcs[metNum] = false;
1204
public double[][] getXRoutingGrid() { return gridLocationsX; }
1206
public double[][] getYRoutingGrid() { return gridLocationsY; }
1417
forceGridArcs = new boolean[numMetalLayers];
1418
for(int i=0; i<numMetalLayers; i++)
1420
forceGridArcs[i] = false;
1421
for(int c=0; c<metalArcs[i].length; c++)
1422
if (sogp.isGridForced(metalArcs[i][c])) forceGridArcs[i] = true;
1425
// determine the taper widths
1426
aTaperWid = getTaperWidth(aPi, aZ);
1427
bTaperWid = getTaperWidth(bPi, bZ);
1428
aTaperLen = taperLength[aZ];
1429
bTaperLen = taperLength[bZ];
1430
if (aTaperWid == getUntaperedArcWidth(aZ)) aTaperLen = -1;
1431
if (bTaperWid == getUntaperedArcWidth(bZ)) bTaperLen = -1;
1434
public boolean getRoutedSucess() { return routedSuccess; }
1435
public Wavefront getWavefront() { return winningWF; }
1436
public Wavefront getWavefrontAtoB() { return dirAtoB; }
1437
public Wavefront getWavefrontBtoA() { return dirBtoA; }
1438
public String getErrorMessage() { return errorMessage; }
1440
public void setDebugging(Boolean fromA) { debuggingRouteFromA = fromA; }
1443
* Method to check the validity of the endpoints with respect to forced gridding.
1444
* If the grid is being forced and the endpoints are not on grid,
1445
* routing may fail (and a warning will be issued here).
1447
public void checkGridValidity()
1449
if (forceGridArcs[aZ])
1452
if (sogp.isHorizontalEven())
1454
if ((aZ%2) == 0) hor = false;
1457
if ((aZ%2) != 0) hor = false;
1459
if (!hor && !isOnXGrid(aZ, getAX()))
1461
List<EPoint> offGrid = new ArrayList<EPoint>(); offGrid.add(EPoint.fromLambda(aX, aY)); offGrid.add(EPoint.fromLambda(aX, aY));
1462
warn("Route " + routeName + ", end (" + TextUtils.formatDistance(aX) + "," + TextUtils.formatDistance(aY) + "," +
1463
describeMetal(aZ,aC) + ") is not on X grid (nearest X grids are at " + TextUtils.formatDistance(getLowerXGrid(aZ, aX).getCoordinate()) +
1464
" and " + TextUtils.formatDistance(getUpperXGrid(aZ, aX).getCoordinate()) + "). Route may fail.", cell, offGrid, null);
1466
if (hor && !isOnYGrid(aZ, aY))
1468
List<EPoint> offGrid = new ArrayList<EPoint>(); offGrid.add(EPoint.fromLambda(aX, aY)); offGrid.add(EPoint.fromLambda(aX, aY));
1469
warn("Route " + routeName + ", end (" + TextUtils.formatDistance(aX) + "," + TextUtils.formatDistance(aY) + "," +
1470
describeMetal(aZ,aC) + ") is not on Y grid (nearest Y grids are at " + TextUtils.formatDistance(getLowerYGrid(aZ, aY).getCoordinate()) +
1471
" and " + TextUtils.formatDistance(getUpperYGrid(aZ, aY).getCoordinate()) + "). Route may fail.", cell, offGrid, null);
1474
if (forceGridArcs[bZ])
1477
if (sogp.isHorizontalEven())
1479
if ((bZ%2) == 0) hor = false;
1482
if ((bZ%2) != 0) hor = false;
1484
if (!hor && !isOnXGrid(bZ, bX))
1486
List<EPoint> offGrid = new ArrayList<EPoint>(); offGrid.add(EPoint.fromLambda(bX, bY)); offGrid.add(EPoint.fromLambda(bX, bY));
1487
warn("Route " + routeName + ", end (" + TextUtils.formatDistance(bX) + "," + TextUtils.formatDistance(bY) + "," +
1488
describeMetal(bZ,bC) + ") is not on X grid (nearest X grids are at " + TextUtils.formatDistance(getLowerXGrid(bZ, bX).getCoordinate()) +
1489
" and " + TextUtils.formatDistance(getUpperXGrid(bZ, bX).getCoordinate()) + "). Route may fail.", cell, offGrid, null);
1491
if (hor && !isOnYGrid(bZ, bY))
1493
List<EPoint> offGrid = new ArrayList<EPoint>(); offGrid.add(EPoint.fromLambda(bX, bY)); offGrid.add(EPoint.fromLambda(bX, bY));
1494
warn("Route " + routeName + ", end (" + TextUtils.formatDistance(bX) + "," + TextUtils.formatDistance(bY) + "," +
1495
describeMetal(bZ,bC) + ") is not on Y grid (nearest Y grids are at " + TextUtils.formatDistance(getLowerYGrid(bZ, bY).getCoordinate()) +
1496
" and " + TextUtils.formatDistance(getUpperYGrid(bZ, bY).getCoordinate()) + "). Route may fail.", cell, offGrid, null);
1501
public FixpRectangle getAGriddedRect() { return aRectGridded; }
1503
public FixpRectangle getBGriddedRect() { return bRectGridded; }
1505
public SeaOfGatesTrack[][] getXRoutingGrid() { return gridLocationsX; }
1507
public SeaOfGatesTrack[][] getYRoutingGrid() { return gridLocationsY; }
1209
1510
* Method to construct grids for all layers in the vicinity of this route.
1211
1512
public void buildGrids(Rectangle2D bounds)
1213
gridLocationsX = new double[numMetalLayers][];
1214
gridLocationsY = new double[numMetalLayers][];
1514
gridLocationsX = new SeaOfGatesTrack[numMetalLayers][];
1515
gridLocationsY = new SeaOfGatesTrack[numMetalLayers][];
1216
1517
// first make the grid positions for each layer
1217
1518
for(int metNum=1; metNum<=numMetalLayers; metNum++)
1219
1520
int metIndex = metNum - 1;
1220
double[] thisGrid = metalGrid[metIndex];
1521
SeaOfGatesTrack[] thisGrid = metalGrid[metIndex];
1221
1522
if (thisGrid == null) continue;
1222
1523
if (!sogp.isForceHorVer() && !sogp.isFavorHorVer()) continue;
1223
1524
boolean hor = true;
1399
1736
return isOnGrid(gridLocationsY[metNum], value);
1402
private double findLowerValue(double[] thisGrid, double value)
1404
if (thisGrid == null) return value;
1405
int lo = 0, hi = thisGrid.length - 1;
1406
if (value <= thisGrid[lo]) return value;
1407
if (value >= thisGrid[hi]) return value;
1409
for(int i=0; i<1000; i++)
1411
int med = (hi + lo) / 2;
1412
if (value >= thisGrid[med] && value < thisGrid[med+1]) return thisGrid[med];
1413
if (value < thisGrid[med]) hi = med; else lo = med;
1418
private double findUpperValue(double[] thisGrid, double value)
1420
if (thisGrid == null) return value;
1422
int lo = 0, hi = thisGrid.length - 1;
1423
if (value <= thisGrid[lo]) return value;
1424
if (value >= thisGrid[hi]) return value;
1426
for(int i=0; i<1000; i++)
1428
int med = (hi + lo) / 2;
1429
if (value > thisGrid[med] && value <= thisGrid[med+1]) return thisGrid[med+1];
1430
if (value <= thisGrid[med]) hi = med; else lo = med;
1435
private double findClosestValue(double[] thisGrid, double value)
1437
if (thisGrid == null) return value;
1439
int lo = 0, hi = thisGrid.length - 1;
1440
if (value <= thisGrid[lo]) return value;
1441
if (value >= thisGrid[hi]) return value;
1443
for(int i=0; i<1000; i++)
1445
int med = (hi + lo) / 2;
1446
if (value >= thisGrid[med] && value <= thisGrid[med+1])
1739
private SeaOfGatesTrack findLowerValue(SeaOfGatesTrack[] thisGrid, double value)
1741
if (thisGrid == null) return new SeaOfGatesTrack(value, 0);
1742
int lo = 0, hi = thisGrid.length - 1;
1743
if (DBMath.isLessThanOrEqualTo(value, thisGrid[lo].getCoordinate())) return thisGrid[lo];
1744
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[hi].getCoordinate())) return thisGrid[hi];
1746
for(int i=0; i<1000; i++)
1748
int med = (hi + lo) / 2;
1749
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[med].getCoordinate()) &&
1750
DBMath.isLessThan(value, thisGrid[med+1].getCoordinate())) return thisGrid[med];
1751
if (DBMath.isLessThan(value, thisGrid[med].getCoordinate())) hi = med; else lo = med;
1753
return new SeaOfGatesTrack(value, 0);
1756
private SeaOfGatesTrack findUpperValue(SeaOfGatesTrack[] thisGrid, double value)
1758
if (thisGrid == null) return new SeaOfGatesTrack(value, 0);
1760
int lo = 0, hi = thisGrid.length - 1;
1761
if (DBMath.isLessThanOrEqualTo(value, thisGrid[lo].getCoordinate())) return thisGrid[lo];
1762
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[hi].getCoordinate())) return thisGrid[hi];
1764
for(int i=0; i<1000; i++)
1766
int med = (hi + lo) / 2;
1767
if (DBMath.isGreaterThan(value, thisGrid[med].getCoordinate()) &&
1768
DBMath.isLessThanOrEqualTo(value, thisGrid[med+1].getCoordinate())) return thisGrid[med+1];
1769
if (DBMath.isLessThanOrEqualTo(value, thisGrid[med].getCoordinate())) hi = med; else lo = med;
1771
return new SeaOfGatesTrack(value, 0);
1774
private SeaOfGatesTrack findClosestValue(SeaOfGatesTrack[] thisGrid, double value)
1776
if (thisGrid == null) return new SeaOfGatesTrack(value, 0);
1778
int lo = 0, hi = thisGrid.length - 1;
1779
if (DBMath.isLessThanOrEqualTo(value, thisGrid[lo].getCoordinate())) return thisGrid[lo];
1780
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[hi].getCoordinate())) return thisGrid[hi];
1782
for(int i=0; i<1000; i++)
1784
int med = (hi + lo) / 2;
1785
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[med].getCoordinate()) &&
1786
DBMath.isLessThan(value, thisGrid[med+1].getCoordinate()))
1448
if (value - thisGrid[med] < thisGrid[med+1] - value)
1788
if (DBMath.isLessThan(value - thisGrid[med].getCoordinate(), thisGrid[med+1].getCoordinate() - value))
1449
1789
return thisGrid[med];
1450
1790
return thisGrid[med+1];
1452
if (value <= thisGrid[med]) hi = med; else lo = med;
1792
if (DBMath.isLessThanOrEqualTo(value, thisGrid[med].getCoordinate())) hi = med; else lo = med;
1794
return new SeaOfGatesTrack(value, 0);
1457
private boolean isOnGrid(double[] thisGrid, double value)
1797
private boolean isOnGrid(SeaOfGatesTrack[] thisGrid, double value)
1459
1799
if (thisGrid != null)
1461
1801
int lo = 0, hi = thisGrid.length - 1;
1462
if (value < thisGrid[lo]) return false;
1463
if (value > thisGrid[hi]) return false;
1802
if (DBMath.isLessThan(value, thisGrid[lo].getCoordinate())) return false;
1803
if (DBMath.isGreaterThan(value, thisGrid[hi].getCoordinate())) return false;
1465
1805
for(int i=0; i<1000; i++)
1467
1807
int med = (hi + lo) / 2;
1468
if (value >= thisGrid[med] && value <= thisGrid[med+1])
1808
if (DBMath.isGreaterThanOrEqualTo(value, thisGrid[med].getCoordinate()) &&
1809
DBMath.isLessThanOrEqualTo(value, thisGrid[med+1].getCoordinate()))
1470
if (value == thisGrid[med] || thisGrid[med+1] == value)
1811
if (DBMath.areEquals(value, thisGrid[med].getCoordinate()) ||
1812
DBMath.areEquals(thisGrid[med+1].getCoordinate(), value))
1474
if (value <= thisGrid[med]) hi = med; else lo = med;
1816
if (DBMath.isLessThanOrEqualTo(value, thisGrid[med].getCoordinate())) hi = med; else lo = med;
1518
1860
return Math.floor(v);
1521
public Wavefront[] makeWavefronts()
1864
* Method to determine whether a contact can be placed that will connect existing metal to new metal.
1865
* @param np the contact.
1866
* @param newMetal the new metal layer (0-based).
1867
* @param offendingMetal the existing metal layer (0-based).
1868
* @param offendingMetalColor the mask color of the existing metal layer.
1869
* @param conX the X coordinate of the contact.
1870
* @param conY the Y coordinate of the contact.
1871
* @param conWid the width of the contact.
1872
* @param conHei the height of the contact.
1873
* @param orient the orientation of the contact.
1874
* @return true if the contact fits (the offending metal already exists and the new metal is available).
1876
private boolean canPlaceContact(PrimitiveNode np, int newMetal, int offendingMetal, int offendingMetalColor,
1877
double conX, double conY, double conWid, double conHei, Orientation orient, boolean endA)
1879
NodeInst dummyNi = NodeInst.makeDummyInstance(np, ep, EPoint.fromLambda(conX, conY), conWid, conHei, orient);
1880
Poly[] conPolys = tech.getShapeOfNode(dummyNi);
1881
FixpTransform trans = null;
1882
MutableInteger mi = new MutableInteger(netID.intValue() + (endA ? BLOCKAGEENDA : BLOCKAGEENDB));
1883
if (orient != Orientation.IDENT) trans = dummyNi.rotateOut();
1884
for (int p = 0; p < conPolys.length; p++)
1886
Poly conPoly = conPolys[p];
1887
Layer conLayer = conPoly.getLayer();
1888
if (!conLayer.getFunction().isMetal()) continue;
1889
if (trans != null) conPoly.transform(trans);
1890
Rectangle2D conRect = conPoly.getBounds2D();
1892
// if this is the offending metal layer, check to see that the geometry already exists
1893
boolean found = false;
1894
for(int c=0; c<metalLayers[offendingMetal].length; c++)
1895
if (conLayer == metalLayers[offendingMetal][c] &&
1896
conLayer.getFunction().getMaskColor() == offendingMetalColor) found = true;
1899
if (!isPointInMetal(conRect.getMinX(), conRect.getMinY(), offendingMetal, mi) ||
1900
!isPointInMetal(conRect.getMinX(), conRect.getMaxY(), offendingMetal, mi) ||
1901
!isPointInMetal(conRect.getMaxX(), conRect.getMaxY(), offendingMetal, mi) ||
1902
!isPointInMetal(conRect.getMaxX(), conRect.getMinY(), offendingMetal, mi) ||
1903
!isPointInMetal(conRect.getCenterX(), conRect.getCenterY(), offendingMetal, mi))
1905
// offending layer is not there: cannot place contact
1910
// if this is the new metal layer, make sure there is room for it
1912
for(int c=0; c<metalLayers[newMetal].length; c++)
1913
if (conLayer == metalLayers[newMetal][c]) found = true;
1916
double[] fromSurround = getSpacingRule(newMetal, maxDefArcWidth[newMetal], -1);
1917
double halfWidth = conRect.getWidth() / 2;
1918
double halfHeight = conRect.getHeight() / 2;
1919
SOGBound block = getMetalBlockage(netID, newMetal, halfWidth, halfHeight, fromSurround, conRect.getCenterX(), conRect.getCenterY());
1920
if (block != null) return false;
1927
* Method to determine whether a point is covered by a metal layer on a given network.
1928
* @param x the X coordinate to search.
1929
* @param y the Y coordinate to search.
1930
* @param metalNo the metal number to consider.
1931
* @param netID the netID that must be on the metal (null to ignore this).
1934
private boolean isPointInMetal(double x, double y, int metalNo, MutableInteger netID)
1936
// get the R-Tree data for the metal layer
1937
BlockageTree bTree = rTrees.getMetalTree(primaryMetalLayer[metalNo]);
1940
if (bTree.isEmpty()) return false;
1942
Rectangle2D searchArea = new Rectangle2D.Double(x, y, 0, 0);
1943
for (Iterator<SOGBound> sea = bTree.search(searchArea); sea.hasNext();)
1945
SOGBound sBound = sea.next();
1946
if (sBound.containsPoint(x, y))
1950
if (!sBound.isSameBasicNet(netID)) continue;
1951
int endBits = BLOCKAGEENDA | BLOCKAGEENDB;
1952
if ((sBound.getNetID().intValue()&endBits) != (netID.intValue()&endBits)) continue;
1964
* Method to determine the size and orientation of a contact.
1965
* @param mv the MetalVia describing the contact.
1966
* @param wid where the width will be stored.
1967
* @param hei where the height will be stored.
1968
* @return the orientation to use.
1970
private Orientation getMVSize(MetalVia mv, double x, double y, double lastX, double lastY, MutableDouble wid, MutableDouble hei)
1972
PrimitiveNode np = mv.via;
1973
Orientation orient = Orientation.fromJava(mv.orientation * 10, false, false);
1974
SizeOffset so = np.getProtoSizeOffset();
1975
double minWid = minWidth;
1976
double minHei = minWidth;
1977
double xOffset = so.getLowXOffset() + so.getHighXOffset();
1978
double yOffset = so.getLowYOffset() + so.getHighYOffset();
1979
double conWid = Math.max(np.getDefWidth(ep) - xOffset, minWid) + xOffset;
1980
double conHei = Math.max(np.getDefHeight(ep) - yOffset, minHei) + yOffset;
1981
if (mv.horMetal >= 0)
1983
double arcWid = getArcWidth(mv.horMetal, x, y, lastX, lastY) + mv.horMetalInset;
1984
if (arcWid > conHei) conHei = arcWid;
1986
if (mv.verMetal >= 0)
1988
double arcWid = getArcWidth(mv.verMetal, x, y, lastX, lastY) + mv.verMetalInset;
1989
if (arcWid > conWid) conWid = arcWid;
1991
wid.setValue(conWid);
1992
hei.setValue(conHei);
1997
* Method to tell whether an endpoint of the route is invalid.
1998
* @param endA true if the A end is being examined, false for the B end.
1999
* @param pi the port of the end being examined.
2000
* @return true if the endpoint is invalid and cannot be routed.
2001
* Gives error message if true.
2003
private boolean invalidPort(boolean endA, PortInst pi)
2005
// first see if any metal layer on this end is available
2006
ArcProto[] conns = getPossibleConnections(pi.getPortProto());
2007
for (int j = 0; j < conns.length; j++)
2009
ArcProto ap = conns[j];
2010
if (ap.getTechnology() != tech) continue;
2011
if (!ap.getFunction().isMetal()) continue;
2012
if (preventArc(conns[j].getFunction().getLevel() - 1)) continue;
2016
// determine location of contact
2017
double x = endA ? aX : bX, y = endA ? aY : bY;
2018
Map<Integer,List<PrimitiveNode>> whatWasChecked = new HashMap<Integer,List<PrimitiveNode>>();
2019
Map<Integer,java.awt.Point> contactInvalidColors = new HashMap<Integer,java.awt.Point>();
2020
int realOffendingMetal = 0;
2022
// no metal layers available: see if a contact can be placed to shift to a valid layer
2023
EPoint pt = pi.getCenter();
2024
double conX = pt.getX(), conY = pt.getY();
2025
double endCoord = 0;
2026
if (sogp.isContactAllowedDownToAvoidedLayer() || sogp.isContactAllowedUpToAvoidedLayer())
2028
// first see if an adjoining layer is available
2029
for (int j = 0; j < conns.length; j++)
2031
ArcProto ap = conns[j];
2032
if (ap.getTechnology() != tech) continue;
2033
if (!ap.getFunction().isMetal()) continue;
2034
int offendingMetal = conns[j].getFunction().getLevel() - 1;
2035
int offendingMetalColor = conns[j].getMaskLayer();
2037
int newMetalColor = 0;
2038
int lowerMetal = offendingMetal - 1;
2039
int upperMetal = offendingMetal + 1;
2040
List<MetalVia> mvs = null;
2041
if (sogp.isContactAllowedUpToAvoidedLayer() && lowerMetal >= 0 && !preventArc(lowerMetal))
2043
// can drop down one metal layer to connect
2044
mvs = metalVias[lowerMetal].getVias();
2045
newMetal = lowerMetal;
2047
if (sogp.isContactAllowedDownToAvoidedLayer() && upperMetal < numMetalLayers && !preventArc(upperMetal))
2049
// can move up one metal layer to connect
2050
mvs = metalVias[upperMetal-1].getVias();
2051
newMetal = upperMetal;
2053
if (mvs == null) continue;
2055
// see if any contacts can be placed
2056
List<PrimitiveNode> checkedThese = whatWasChecked.get(Integer.valueOf(newMetal));
2057
if (checkedThese == null) whatWasChecked.put(Integer.valueOf(newMetal), checkedThese = new ArrayList<PrimitiveNode>());
2058
boolean hasContacts = false;
2059
for (MetalVia mv : mvs)
2061
if (mv.horMetal == offendingMetal && mv.verMetal == newMetal)
2063
if (mv.horMetalColor != offendingMetalColor || mv.verMetalColor != newMetalColor) continue;
2064
} else if (mv.verMetal == offendingMetal && mv.horMetal == newMetal)
2066
if (mv.verMetalColor != offendingMetalColor || mv.horMetalColor != newMetalColor) continue;
2069
checkedThese.add(mv.via);
2073
realOffendingMetal = offendingMetal;
2074
contactInvalidColors.put(Integer.valueOf(newMetal), new java.awt.Point(offendingMetalColor, newMetalColor));
2076
MetalVia viaToPlace = null;
2077
double viaToPlaceX = 0, viaToPlaceY = 0;
2078
double viaSizeX = 0, viaSizeY = 0;
2079
Orientation viaOrient = Orientation.IDENT;
2081
if (sogp.isHorizontalEven())
2083
if ((newMetal%2) == 0) hor = false;
2086
if ((newMetal%2) != 0) hor = false;
2089
// adjust location of contact to be on grid
2090
if (forceGridArcs[newMetal])
2092
int index = 0, dir = 0;
2095
if (gridLocationsY[newMetal] != null)
2097
double otherY = endA ? bY : aY;
2100
conY = getLowerYGrid(newMetal, conY).getCoordinate();
2104
conY = getUpperYGrid(newMetal, conY).getCoordinate();
2107
for(index=0; index<gridLocationsY[newMetal].length; index++)
2108
if (gridLocationsY[newMetal][index].getCoordinate() == conY) break;
2112
if (gridLocationsX[newMetal] != null)
2114
double otherX = endA ? bX : aX;
2117
conX = getLowerXGrid(newMetal, conX).getCoordinate();
2121
conX = getUpperXGrid(newMetal, conX).getCoordinate();
2124
for(index=0; index<gridLocationsX[newMetal].length; index++)
2125
if (gridLocationsX[newMetal][index].getCoordinate() == conX) break;
2129
// try all values on the grid, heading toward goal
2130
int startIndex = index;
2132
// code to travel as far as possible rather than stopping at first valid location
2135
endCoord = endA ? bY : aY;
2138
endCoord = endA ? bX : aX;
2143
// more code to travel as far as possible rather than stopping at first valid location
2144
boolean tooFar = false;
2149
if (conY < endCoord) tooFar = true;
2152
if (conY > endCoord) tooFar = true;
2158
if (conX < endCoord) tooFar = true;
2161
if (conX > endCoord) tooFar = true;
2164
if (tooFar && viaToPlace != null) break;
2166
newMetalColor = (hor ? gridLocationsY[newMetal][index].getMaskNum() : gridLocationsX[newMetal][index].getMaskNum());
2167
for (MetalVia mv : mvs)
2169
if (mv.horMetal == offendingMetal && mv.verMetal == newMetal)
2171
if (mv.horMetalColor != offendingMetalColor || mv.verMetalColor != newMetalColor) continue;
2172
} else if (mv.verMetal == offendingMetal && mv.horMetal == newMetal)
2174
if (mv.verMetalColor != offendingMetalColor || mv.horMetalColor != newMetalColor) continue;
2176
PrimitiveNode np = mv.via;
2177
MutableDouble conWid, conHei;
2178
Orientation orient = getMVSize(mv, x, y, x, y, conWid = new MutableDouble(0), conHei = new MutableDouble(0));
2179
if (canPlaceContact(np, newMetal, offendingMetal, offendingMetalColor, conX, conY, conWid.doubleValue(), conHei.doubleValue(), orient, endA))
2181
// offending layer is already there, so via can be dropped from it
2183
viaToPlaceX = conX; viaToPlaceY = conY;
2184
viaSizeX = conWid.doubleValue(); viaSizeY = conHei.doubleValue();
2193
if (index < 0 || index >= gridLocationsY[newMetal].length) break;
2194
conY = gridLocationsY[newMetal][index].getCoordinate();
2197
if (index < 0 || index >= gridLocationsX[newMetal].length) break;
2198
conX = gridLocationsX[newMetal][index].getCoordinate();
2201
if (viaToPlace == null)
2203
// heading away from goal (last resort)
2205
index = startIndex + dir;
2208
newMetalColor = (hor ? gridLocationsY[newMetal][index].getMaskNum() : gridLocationsX[newMetal][index].getMaskNum());
2209
for (MetalVia mv : mvs)
2211
if (mv.horMetal == offendingMetal && mv.verMetal == newMetal)
2213
if (mv.horMetalColor != offendingMetalColor || mv.verMetalColor != newMetalColor) continue;
2214
} else if (mv.verMetal == offendingMetal && mv.horMetal == newMetal)
2216
if (mv.verMetalColor != offendingMetalColor || mv.horMetalColor != newMetalColor) continue;
2218
PrimitiveNode np = mv.via;
2219
MutableDouble conWid, conHei;
2220
Orientation orient = getMVSize(mv, x, y, x, y, conWid = new MutableDouble(0), conHei = new MutableDouble(0));
2221
if (canPlaceContact(np, newMetal, offendingMetal, offendingMetalColor, conX, conY, conWid.doubleValue(), conHei.doubleValue(), orient, endA))
2223
// offending layer is already there, so via can be dropped from it
2225
viaToPlaceX = conX; viaToPlaceY = conY;
2226
viaSizeX = conWid.doubleValue(); viaSizeY = conHei.doubleValue();
2231
if (viaToPlace != null) break;
2236
if (index < 0 || index >= gridLocationsY[newMetal].length) break;
2237
conY = gridLocationsY[newMetal][index].getCoordinate();
2240
if (index < 0 || index >= gridLocationsX[newMetal].length) break;
2241
conX = gridLocationsX[newMetal][index].getCoordinate();
2247
SeaOfGatesTrack sogt;
2250
sogt = getClosestYGrid(newMetal, conY);
2253
sogt = getClosestXGrid(newMetal, conX);
2255
newMetalColor = sogt.getMaskNum();
2257
// no forced gridding: just find a via at this coordinate
2258
for (MetalVia mv : mvs)
2260
if (mv.horMetal == offendingMetal && mv.verMetal == newMetal)
2262
if (mv.horMetalColor != offendingMetalColor || mv.verMetalColor != newMetalColor) continue;
2263
} else if (mv.verMetal == offendingMetal && mv.horMetal == newMetal)
2265
if (mv.verMetalColor != offendingMetalColor || mv.horMetalColor != newMetalColor) continue;
2267
PrimitiveNode np = mv.via;
2268
MutableDouble conWid, conHei;
2269
Orientation orient = getMVSize(mv, x, y, x, y, conWid = new MutableDouble(0), conHei = new MutableDouble(0));
2270
if (canPlaceContact(np, newMetal, offendingMetal, offendingMetalColor, conX, conY, conWid.doubleValue(), conHei.doubleValue(), orient, endA))
2272
// offending layer is already there, so via can be dropped from it
2274
viaToPlaceX = conX; viaToPlaceY = conY;
2275
viaSizeX = conWid.doubleValue(); viaSizeY = conHei.doubleValue();
2281
if (viaToPlace != null)
2283
String msg = "Route '" + routeName + "' at (" + TextUtils.formatDistance(pt.getX()) + "," +
2284
TextUtils.formatDistance(pt.getY()) + ") from port " + pi.getPortProto().getName() + " on node " +
2285
describe(pi.getNodeInst()) + " is disallowed on Metal " + (offendingMetal+1) + " so inserting " +
2286
viaToPlace.via.describe(false);
2287
if (!DBMath.areEquals(pt.getX(), viaToPlaceX) || !DBMath.areEquals(pt.getY(), viaToPlaceY))
2288
msg += " at (" + TextUtils.formatDistance(viaToPlaceX) + "," + TextUtils.formatDistance(viaToPlaceY) + ")";
2289
msg += " and routing from Metal " + (newMetal+1);
2293
double dX = viaToPlaceX-aX, dY = viaToPlaceY-aY;
2296
Point[] pts = aPoly.getPoints();
2297
for(int i=0; i<pts.length; i++)
2298
pts[i].setLocation(pts[i].getX()+dX, pts[i].getY()+dY);
2299
aRect.setRect(aX, aY, 0, 0);
2300
// aRect.setRect(aRect.getMinX()+dX, aRect.getMinY()+dY, aRect.getWidth(), aRect.getHeight());
2301
double aLX = getLowerXGrid(aZ, aRect.getMinX()).getCoordinate();
2302
double aHX = getUpperXGrid(aZ, aRect.getMaxX()).getCoordinate();
2303
double aLY = getLowerYGrid(aZ, aRect.getMinY()).getCoordinate();
2304
double aHY = getUpperYGrid(aZ, aRect.getMaxY()).getCoordinate();
2305
aRectGridded = FixpRectangle.from(new Rectangle2D.Double(aLX, aLY, aHX-aLX, aHY-aLY));
2308
jumpBound = new Rectangle2D.Double(Math.min(aX, bX), Math.min(aY, bY), Math.abs(aX-bX), Math.abs(aY-bY));
2309
replaceA = viaToPlace;
2310
replaceAZ = offendingMetal;
2311
if (offendingMetalColor > 0)
2312
replaceAC = offendingMetalColor-1;
2314
// reset taper width on this end since contact will be placed
2315
aTaperWid = getUntaperedArcWidth(newMetal);
2319
double dX = viaToPlaceX-bX, dY = viaToPlaceY-bY;
2322
Point[] pts = bPoly.getPoints();
2323
for(int i=0; i<pts.length; i++)
2324
pts[i].setLocation(pts[i].getX()+dX, pts[i].getY()+dY);
2325
bRect.setRect(bX, bY, 0, 0);
2326
// bRect.setRect(bRect.getMinX()+dX, bRect.getMinY()+dY, bRect.getWidth(), bRect.getHeight());
2327
double bLX = getLowerXGrid(bZ, bRect.getMinX()).getCoordinate();
2328
double bHX = getUpperXGrid(bZ, bRect.getMaxX()).getCoordinate();
2329
double bLY = getLowerYGrid(bZ, bRect.getMinY()).getCoordinate();
2330
double bHY = getUpperYGrid(bZ, bRect.getMaxY()).getCoordinate();
2331
bRectGridded = FixpRectangle.from(new Rectangle2D.Double(bLX, bLY, bHX-bLX, bHY-bLY));
2334
jumpBound = new Rectangle2D.Double(Math.min(aX, bX), Math.min(aY, bY), Math.abs(aX-bX), Math.abs(aY-bY));
2335
replaceB = viaToPlace;
2336
replaceBZ = offendingMetal;
2337
if (offendingMetalColor > 0)
2338
replaceBC = offendingMetalColor-1;
2340
// reset taper width on this end since contact will be placed
2341
bTaperWid = getUntaperedArcWidth(newMetal);
2345
// add contact to blockages
2346
NodeInst dummyNi = NodeInst.makeDummyInstance(viaToPlace.via, ep, EPoint.fromLambda(viaToPlaceX, viaToPlaceY),
2347
viaSizeX, viaSizeY, viaOrient);
2348
Poly[] conPolys = tech.getShapeOfNode(dummyNi);
2349
FixpTransform trans = null;
2350
if (viaOrient != Orientation.IDENT) trans = dummyNi.rotateOut();
2351
for (int p = 0; p < conPolys.length; p++)
2353
Poly conPoly = conPolys[p];
2354
Layer conLayer = conPoly.getLayer();
2355
if (trans != null) conPoly.transform(trans);
2356
Rectangle2D conRect = conPoly.getBounds2D();
2357
Layer.Function fun = conLayer.getFunction();
2360
addRectangle(conRect, conLayer, netID, false, false);
2361
} else if (fun.isContact())
2363
addVia(ERectangle.fromLambda(conRect), conLayer, netID, false);
2371
// cannot place contact or use existing layers, give an error
2372
String msg = "Route '" + routeName + "' at (" + TextUtils.formatDistance(pt.getX()) + "," + TextUtils.formatDistance(pt.getY()) +
2373
") from port " + pi.getPortProto().getName() + " on node " + describe(pi.getNodeInst()) + " cannot connect";
2374
if (sogp.isContactAllowedDownToAvoidedLayer() || sogp.isContactAllowedUpToAvoidedLayer())
2376
msg += " (allowed to go";
2377
if (sogp.isContactAllowedDownToAvoidedLayer())
2379
if (sogp.isContactAllowedUpToAvoidedLayer()) msg += " up/down"; else msg += " down";
2380
} else if (sogp.isContactAllowedUpToAvoidedLayer()) msg += " up";
2381
msg += " one layer)";
2384
if (whatWasChecked.size() > 0)
2386
boolean first = true;
2387
for(Integer m : whatWasChecked.keySet())
2389
if (first) msg += " because"; else msg += " and";
2391
java.awt.Point invalidColors = contactInvalidColors.get(m);
2392
if (invalidColors != null)
2394
msg += " no contact exists from metal-" + (realOffendingMetal+1) + " mask color " + invalidColors.x +
2395
" to metal-" + (m.intValue() + 1) + " mask color " + invalidColors.y;
2398
msg += " contact(s) cannot be placed:";
2399
List<PrimitiveNode> contacts = whatWasChecked.get(m);
2400
for(PrimitiveNode pNp : contacts) msg += " " + pNp.describe(false);
2405
msg += " because all connecting layers have been prevented by Routing Preferences";
2408
List<PolyBase> polyList = new ArrayList<PolyBase>();
2409
polyList.add(new PolyBase(pt.getX(), pt.getY(), 0, 0));
2410
errorLogger.logMessageWithLines(msg, polyList, null, cell, 0, true);
2415
* Method to determine the width of tapers.
2416
* Tapers are as wide as the metal at the end of the route.
2417
* @param pi the PortInst at the end of the route.
2418
* @param metalNo the metal layer (0-based) at the end of the route.
2419
* @return the taper width to use for that end of the route.
2421
private double getTaperWidth(PortInst pi, int metalNo)
2423
PortProto pp = pi.getPortProto();
2424
NodeInst ni = pi.getNodeInst();
2425
FixpTransform trans = ni.rotateOut();
2426
while (ni.isCellInstance())
2428
Export e = (Export)pp;
2429
ni = e.getOriginalPort().getNodeInst();
2430
pp = e.getOriginalPort().getPortProto();
2431
trans.concatenate(ni.rotateOut());
2433
Poly[] polys = ni.getProto().getTechnology().getShapeOfNode(ni);
2434
for(int i=0; i<polys.length; i++)
2436
Poly poly = polys[i];
2437
boolean found = false;
2438
for(int j=0; j<metalLayers[metalNo].length; j++)
2439
if (metalLayers[metalNo][j] == poly.getLayer()) { found = true; break; }
2440
if (!found) continue;
2441
poly.transform(trans);
2442
FixpRectangle rect = poly.getBounds2D();
2444
if (sogp.isForceHorVer())
2446
if (sogp.isHorizontalEven())
2448
if ((metalNo%2) == 0) hor = false;
2451
if ((metalNo%2) != 0) hor = false;
2453
if (hor) return rect.getHeight();
2454
return rect.getWidth();
2457
// choose narrowest dimension for taper width
2458
return Math.min(rect.getWidth(), rect.getHeight());
2461
return getUntaperedArcWidth(metalNo);
2464
public void makeWavefronts()
1523
2466
// make two wavefronts going in both directions
1524
Wavefront dirAtoB = new Wavefront(this, aPi, aRect, aX, aY, aZ, OFFSETENDA, bPi, bRect, bRectGridded, bX, bY, bZ, OFFSETENDB, 1, "a->b");
1525
Wavefront dirBtoA = new Wavefront(this, bPi, bRect, bX, bY, bZ, OFFSETENDB, aPi, aRect, aRectGridded, aX, aY, aZ, OFFSETENDA, -1, "b->a");
2467
dirAtoB = new Wavefront(this, aPi, aRect, aX, aY, aZ, aC, aTaperLen, BLOCKAGEENDA,
2468
bPi, bRect, bRectGridded, bX, bY, bZ, bC, bTaperLen, 1, "a->b",
2469
debuggingRouteFromA != null && debuggingRouteFromA.booleanValue());
2470
dirBtoA = new Wavefront(this, bPi, bRect, bX, bY, bZ, bC, bTaperLen, BLOCKAGEENDB,
2471
aPi, aRect, aRectGridded, aX, aY, aZ, aC, aTaperLen, -1, "b->a",
2472
debuggingRouteFromA != null && !debuggingRouteFromA.booleanValue());
1527
2474
// if (ANYPOINTONDESTINATION)
1529
2476
// // mark the blockages with the two ends of the route
1530
// growPoint(aX, aY, aZ, netID+OFFSETENDA, true);
1531
// growPoint(bX, bY, bZ, netID+OFFSETENDB, true);
2477
// growPoint(aX, aY, aZ, netID+BLOCKAGEENDA);
2478
// growPoint(bX, bY, bZ, netID+BLOCKAGEENDB);
1533
return new Wavefront[] { dirAtoB, dirBtoA };
1536
2482
public void setBatchInfo(RouteBatch batch, int routeInBatch)
1686
2717
public boolean checkEndSurround()
1688
2719
// determine "A" end surround
1689
double fromMetalSpacing = getArcWidth(aZ) / 2;
1690
double[] fromSurround = getSpacingRule(aZ, metalArcs[aZ].getDefaultLambdaBaseWidth(ep), -1);
2720
double fromMetalSpacing = getArcWidth(aZ, aX, aY, aX, aY) / 2;
2721
double[] fromSurround = getSpacingRule(aZ, maxDefArcWidth[aZ], -1);
1692
2723
// see if "A" end access is blocked
1693
2724
SOGBound block = getMetalBlockage(netID, aZ, fromMetalSpacing, fromMetalSpacing, fromSurround, aX, aY);
2725
if (block != null && !sogp.isGridForced(primaryMetalArc[aZ]))
1696
// see if gridding caused the blockage
1697
block = getMetalBlockage(netID, aZ, fromMetalSpacing, fromMetalSpacing, fromSurround, aX, aY);
2727
// ungridded center location still blocked: see if port has nonzero area and other places in it are free
2728
Rectangle2D fromRect = aPoly.getBounds2D();
2729
double stepSize = fromMetalSpacing + Math.max(fromSurround[0], fromSurround[1]);
2730
if (stepSize > 0 && (fromRect.getWidth() > 0 || fromRect.getHeight() > 0))
1700
// ungridded center location still blocked: see if port has nonzero area and other places in it are free
1701
Rectangle2D fromRect = aPoly.getBounds2D();
1702
double stepSize = fromMetalSpacing + Math.max(fromSurround[0], fromSurround[1]);
1703
if (stepSize > 0 && (fromRect.getWidth() > 0 || fromRect.getHeight() > 0))
2732
for(double x = fromRect.getMinX(); x <= fromRect.getMaxX(); x += stepSize)
1705
for(double x = fromRect.getMinX(); x <= fromRect.getMaxX(); x += stepSize)
2734
for(double y = fromRect.getMinY(); y <= fromRect.getMaxY(); y += stepSize)
1707
for(double y = fromRect.getMinY(); y <= fromRect.getMaxY(); y += stepSize)
2736
SOGBound stepBlock = getMetalBlockage(netID, aZ, fromMetalSpacing, fromMetalSpacing, fromSurround, x, y);
2737
if (stepBlock == null)
1709
SOGBound stepBlock = getMetalBlockage(netID, aZ, fromMetalSpacing, fromMetalSpacing, fromSurround, x, y);
1710
if (stepBlock == null)
1717
if (block == null) break;
1722
String errorMsg = "Cannot route from port " + aPi.getPortProto().getName()
1723
+ " of node " + describe(aPi.getNodeInst()) + " at ("
1724
+ formatDistance(aX) + "," + formatDistance(aY)
1725
+ ") because it is blocked on layer " + metalLayers[aZ].getName()
1726
+ " [needs " + formatDistance(fromMetalSpacing + Math.max(fromSurround[0], fromSurround[1]))
1727
+ " all around, blockage is "
1728
+ formatDistance(block.getBounds().getMinX()) + "<=X<="
1729
+ formatDistance(block.getBounds().getMaxX()) + " and "
1730
+ formatDistance(block.getBounds().getMinY()) + "<=Y<="
1731
+ formatDistance(block.getBounds().getMaxY())
1732
// + ", block on net " + block.getNetID() + " but this net is " + this.netID
1734
if (reroute) errorMsg = "(Retry) " + errorMsg;
1736
List<PolyBase> polyList = new ArrayList<PolyBase>();
1737
polyList.add(new PolyBase(aX, aY, (fromMetalSpacing + fromSurround[0]) * 2,
1738
(fromMetalSpacing + fromSurround[1]) * 2));
1739
polyList.add(new PolyBase(block.getBounds()));
1740
List<EPoint> lineList = new ArrayList<EPoint>();
1741
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMinY()));
1742
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMaxY()));
1743
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMaxY()));
1744
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMinY()));
1745
errorLogger.logMessageWithLines(errorMsg, polyList, lineList, cell, 0, true);
2744
if (block == null) break;
2749
String errorMsg = "Cannot route from port " + aPi.getPortProto().getName()
2750
+ " of node " + describe(aPi.getNodeInst()) + " at ("
2751
+ TextUtils.formatDistance(aX) + "," + TextUtils.formatDistance(aY)
2752
+ ") because it is blocked on layer " + describeMetal(aZ,aC)
2753
+ " [needs " + TextUtils.formatDistance(fromMetalSpacing + Math.max(fromSurround[0], fromSurround[1]))
2754
+ " all around, blockage is "
2755
+ TextUtils.formatDistance(block.getBounds().getMinX()) + "<=X<="
2756
+ TextUtils.formatDistance(block.getBounds().getMaxX()) + " and "
2757
+ TextUtils.formatDistance(block.getBounds().getMinY()) + "<=Y<="
2758
+ TextUtils.formatDistance(block.getBounds().getMaxY())
2760
if (reroute) errorMsg = "(Retry) " + errorMsg;
2762
List<PolyBase> polyList = new ArrayList<PolyBase>();
2763
polyList.add(new PolyBase(aX, aY, (fromMetalSpacing + fromSurround[0]) * 2,
2764
(fromMetalSpacing + fromSurround[1]) * 2));
2765
polyList.add(new PolyBase(block.getBounds()));
2766
List<EPoint> lineList = new ArrayList<EPoint>();
2767
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMinY()));
2768
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMaxY()));
2769
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMaxY()));
2770
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMinY()));
2771
errorLogger.logMessageWithLines(errorMsg, polyList, lineList, cell, 0, true);
1751
2776
// determine "B" end surround
1752
double toMetalSpacing = getArcWidth(bZ) / 2;
1753
double[] toSurround = getSpacingRule(bZ, metalArcs[bZ].getDefaultLambdaBaseWidth(ep), -1);
2777
double toMetalSpacing = getArcWidth(bZ, bX, bY, bX, bY) / 2;
2778
double[] toSurround = getSpacingRule(bZ, maxDefArcWidth[bZ], -1);
1755
2780
// see if "B" end access is blocked
1756
2781
block = getMetalBlockage(netID, bZ, toMetalSpacing, toMetalSpacing, toSurround, bX, bY);
2782
if (block != null && !sogp.isGridForced(primaryMetalArc[bZ]))
1759
// see if gridding caused the blockage
1760
block = getMetalBlockage(netID, bZ, toMetalSpacing, toMetalSpacing, toSurround, bX, bY);
2784
// ungridded center location still blocked: see if port has nonzero area and other places in it are free
2785
Rectangle2D toRect = bPoly.getBounds2D();
2786
double stepSize = toMetalSpacing + Math.max(toSurround[0], toSurround[1]);
2787
if (stepSize > 0 && (toRect.getWidth() > 0 || toRect.getHeight() > 0))
1763
// ungridded center location still blocked: see if port has nonzero area and other places in it are free
1764
Rectangle2D toRect = bPoly.getBounds2D();
1765
double stepSize = toMetalSpacing + Math.max(toSurround[0], toSurround[1]);
1766
if (stepSize > 0 && (toRect.getWidth() > 0 || toRect.getHeight() > 0))
2789
for(double x = toRect.getMinX(); x <= toRect.getMaxX(); x += stepSize)
1768
for(double x = toRect.getMinX(); x <= toRect.getMaxX(); x += stepSize)
2791
for(double y = toRect.getMinY(); y <= toRect.getMaxY(); y += stepSize)
1770
for(double y = toRect.getMinY(); y <= toRect.getMaxY(); y += stepSize)
2793
SOGBound stepBlock = getMetalBlockage(netID, bZ, toMetalSpacing, toMetalSpacing, toSurround, x, y);
2794
if (stepBlock == null)
1772
SOGBound stepBlock = getMetalBlockage(netID, bZ, toMetalSpacing, toMetalSpacing, toSurround, x, y);
1773
if (stepBlock == null)
1780
if (block == null) break;
1785
String errorMsg = "Cannot route to port " + bPi.getPortProto().getName()
1786
+ " of node " + describe(bPi.getNodeInst()) + " at ("
1787
+ formatDistance(bX) + "," + formatDistance(bY)
1788
+ ") because it is blocked on layer " + metalLayers[bZ].getName()
1789
+ " [needs " + formatDistance(toMetalSpacing + Math.max(toSurround[0], toSurround[1]))
1790
+ " all around, blockage is "
1791
+ formatDistance(block.getBounds().getMinX()) + "<=X<="
1792
+ formatDistance(block.getBounds().getMaxX()) + " and "
1793
+ formatDistance(block.getBounds().getMinY()) + "<=Y<="
1794
+ formatDistance(block.getBounds().getMaxY())
1795
// + ", block on net " + block.getNetID() + " but this net is " + this.netID
1797
if (reroute) errorMsg = "(Retry) " + errorMsg;
1799
List<PolyBase> polyList = new ArrayList<PolyBase>();
1800
polyList.add(new PolyBase(bX, bY, (toMetalSpacing + toSurround[0]) * 2,
1801
(toMetalSpacing + toSurround[1]) * 2));
1802
polyList.add(new PolyBase(block.getBounds()));
1803
List<EPoint> lineList = new ArrayList<EPoint>();
1804
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMinY()));
1805
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMaxY()));
1806
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMaxY()));
1807
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMinY()));
1808
errorLogger.logMessageWithLines(errorMsg, polyList, lineList, cell, 0, true);
2801
if (block == null) break;
2806
String errorMsg = "Cannot route to port " + bPi.getPortProto().getName()
2807
+ " of node " + describe(bPi.getNodeInst()) + " at ("
2808
+ TextUtils.formatDistance(bX) + "," + TextUtils.formatDistance(bY)
2809
+ ") because it is blocked on layer " + describeMetal(bZ,bC)
2810
+ " [needs " + TextUtils.formatDistance(toMetalSpacing + Math.max(toSurround[0], toSurround[1]))
2811
+ " all around, blockage is "
2812
+ TextUtils.formatDistance(block.getBounds().getMinX()) + "<=X<="
2813
+ TextUtils.formatDistance(block.getBounds().getMaxX()) + " and "
2814
+ TextUtils.formatDistance(block.getBounds().getMinY()) + "<=Y<="
2815
+ TextUtils.formatDistance(block.getBounds().getMaxY())
2817
if (reroute) errorMsg = "(Retry) " + errorMsg;
2819
List<PolyBase> polyList = new ArrayList<PolyBase>();
2820
polyList.add(new PolyBase(bX, bY, (toMetalSpacing + toSurround[0]) * 2,
2821
(toMetalSpacing + toSurround[1]) * 2));
2822
polyList.add(new PolyBase(block.getBounds()));
2823
List<EPoint> lineList = new ArrayList<EPoint>();
2824
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMinY()));
2825
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMaxY()));
2826
lineList.add(EPoint.fromLambda(block.getBounds().getMinX(), block.getBounds().getMaxY()));
2827
lineList.add(EPoint.fromLambda(block.getBounds().getMaxX(), block.getBounds().getMinY()));
2828
errorLogger.logMessageWithLines(errorMsg, polyList, lineList, cell, 0, true);
2753
3991
// compute a neighboring point
2754
3992
double dx = 0, dy = 0;
2756
MutableBoolean foundDestination = null;
2757
boolean stuck = false;
3994
boolean tooFarFromEnd = false, closeToEnd = false;
3995
StringBuffer jumpExplanation = null;
3996
if (debuggingWavefront) jumpExplanation = new StringBuffer();
2760
3999
case 0: // move -X
2761
4000
if (sogp.isForceHorVer() && ((curZ % 2) == 0) == sogp.isHorizontalEven())
2763
if (RoutingDebug.isActive()) setDebugString(i, "Cannot move in this axis");
4002
if (debuggingWavefront) setDebugString(i, "Cannot move in -X axis");
4005
if (DBMath.areEquals(curY, toY) && toRectGridded.getMinX() < toRectGridded.getMaxX() &&
4006
curX >= toRectGridded.getMinX() && curX <= toRectGridded.getMaxX()) dx = toX - curX; else
2766
4007
if (inDestGrid(toRectGridded, curX-GRAINSIZE, curY)) dx = -GRAINSIZE; else
2767
dx = nr.getLowerXGrid(curZ, curX-GRAINSIZE) - curX;
2769
double intermediate = nr.upToGrainAlways(curX + dx);
2770
if (intermediate != curX + dx) dx = intermediate - curX;
4008
dx = nr.getLowerXGrid(curZ, curX-GRAINSIZE).getCoordinate() - curX;
4010
if (nr.gridLocationsX[curZ] == null || !nr.forceGridArcs[curZ])
4012
double intermediate = nr.upToGrainAlways(curX + dx);
4013
if (intermediate != curX + dx) dx = intermediate - curX;
2774
4018
// jump as far as possible toward goal
2775
if (ANYPOINTONDESTINATION) foundDestination = new MutableBoolean(false);
2776
dx = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, foundDestination);
2777
if (dx >= 0) { dx = -1; stuck = true; }
4019
dx = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, jumpExplanation);
4020
if (dx >= 0) dx = -1;
4022
if (nr.gridLocationsX[curZ] != null && nr.forceGridArcs[curZ] && (curX+dx != toX || curY != toY || curZ != toZ))
4024
double gridX = nr.getClosestXGrid(curZ, curX+dx).getCoordinate();
4027
if (debuggingWavefront)
4029
if (jumpExplanation.length() != 0) setDebugString(i, "Blocked by " + jumpExplanation.toString()); else
4031
setDebugString(i, "Can only move to " + TextUtils.formatDistance(curX+dx) +
4032
" which is gridded right to " + TextUtils.formatDistance(gridX) + " (no movement)");
2780
4040
case 1: // move +X
2781
4041
if (sogp.isForceHorVer() && ((curZ % 2) == 0) == sogp.isHorizontalEven())
2783
if (RoutingDebug.isActive()) setDebugString(i, "Cannot move in this axis");
4043
if (debuggingWavefront) setDebugString(i, "Cannot move in +X axis");
4046
if (DBMath.areEquals(curY, toY) && toRectGridded.getMinX() < toRectGridded.getMaxX() &&
4047
curX >= toRectGridded.getMinX() && curX <= toRectGridded.getMaxX()) dx = toX - curX; else
2786
4048
if (inDestGrid(toRectGridded, curX+GRAINSIZE, curY)) dx = GRAINSIZE; else
2787
dx = nr.getUpperXGrid(curZ, curX+GRAINSIZE) - curX;
2789
intermediate = nr.downToGrainAlways(curX + dx);
2790
if (intermediate != curX + dx) dx = intermediate - curX;
4049
dx = nr.getUpperXGrid(curZ, curX+GRAINSIZE).getCoordinate() - curX;
4051
if (nr.gridLocationsX[curZ] == null || !nr.forceGridArcs[curZ])
4053
double intermediate = nr.downToGrainAlways(curX + dx);
4054
if (intermediate != curX + dx) dx = intermediate - curX;
2794
4059
// jump as far as possible toward goal
2795
if (ANYPOINTONDESTINATION) foundDestination = new MutableBoolean(false);
2796
dx = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, foundDestination);
2797
if (dx <= 0) { dx = 1; stuck = true; }
4060
dx = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, jumpExplanation);
4061
if (dx <= 0) dx = 1;
4063
if (nr.gridLocationsX[curZ] != null && nr.forceGridArcs[curZ] && (curX+dx != toX || curY != toY || curZ != toZ))
4065
double gridX = nr.getClosestXGrid(curZ, curX+dx).getCoordinate();
4068
if (debuggingWavefront)
4070
if (jumpExplanation.length() != 0) setDebugString(i, "Blocked by " + jumpExplanation.toString()); else
4072
setDebugString(i, "Can only move to " + TextUtils.formatDistance(curX+dx) +
4073
" which is gridded left to " + TextUtils.formatDistance(gridX) + " (no movement)");
2800
4081
case 2: // move -Y
2801
4082
if (sogp.isForceHorVer() && ((curZ % 2) != 0) == sogp.isHorizontalEven())
2803
if (RoutingDebug.isActive()) setDebugString(i, "Cannot move in this axis");
4084
if (debuggingWavefront) setDebugString(i, "Cannot move in -Y axis");
4087
if (DBMath.areEquals(curX, toX) && toRectGridded.getMinY() < toRectGridded.getMaxY() &&
4088
curY >= toRectGridded.getMinY() && curY <= toRectGridded.getMaxY()) dy = toY - curY; else
2806
4089
if (inDestGrid(toRectGridded, curX, curY-GRAINSIZE)) dy = -GRAINSIZE; else
2807
dy = nr.getLowerYGrid(curZ, curY-GRAINSIZE) - curY;
2809
intermediate = nr.upToGrainAlways(curY + dy);
2810
if (intermediate != curY + dy) dy = intermediate - curY;
4090
dy = nr.getLowerYGrid(curZ, curY-GRAINSIZE).getCoordinate() - curY;
4092
if (nr.gridLocationsY[curZ] == null || !nr.forceGridArcs[curZ])
4094
double intermediate = nr.upToGrainAlways(curY + dy);
4095
if (intermediate != curY + dy) dy = intermediate - curY;
2814
4100
// jump as far as possible toward goal
2815
if (ANYPOINTONDESTINATION) foundDestination = new MutableBoolean(false);
2816
dy = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, foundDestination);
2817
if (dy >= 0) { dy = -1; stuck = true; }
4101
dy = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, jumpExplanation);
4102
if (dy >= 0) dy = -1;
4104
if (nr.gridLocationsY[curZ] != null && nr.forceGridArcs[curZ] && (curX != toX || curY+dy != toY || curZ != toZ))
4106
double gridY = nr.getClosestYGrid(curZ, curY+dy).getCoordinate();
4109
if (debuggingWavefront)
4111
if (jumpExplanation.length() != 0) setDebugString(i, "Blocked by " + jumpExplanation.toString()); else
4113
setDebugString(i, "Can only move to " + TextUtils.formatDistance(curY+dy) +
4114
" which is gridded up to " + TextUtils.formatDistance(gridY) + " (no movement)");
2820
4122
case 3: // move +Y
2821
4123
if (sogp.isForceHorVer() && ((curZ % 2) != 0) == sogp.isHorizontalEven())
2823
if (RoutingDebug.isActive()) setDebugString(i, "Cannot move in this axis");
4125
if (debuggingWavefront) setDebugString(i, "Cannot move in +Y axis");
4128
if (DBMath.areEquals(curX, toX) && toRectGridded.getMinY() < toRectGridded.getMaxY() &&
4129
curY >= toRectGridded.getMinY() && curY <= toRectGridded.getMaxY()) dy = toY - curY; else
2826
4130
if (inDestGrid(toRectGridded, curX, curY+GRAINSIZE)) dy = GRAINSIZE; else
2827
dy = nr.getUpperYGrid(curZ, curY+GRAINSIZE) - curY;
2829
intermediate = nr.downToGrainAlways(curY + dy);
2830
if (intermediate != curY + dy) dy = intermediate - curY;
4131
dy = nr.getUpperYGrid(curZ, curY+GRAINSIZE).getCoordinate() - curY;
4133
if (nr.gridLocationsY[curZ] == null || !nr.forceGridArcs[curZ])
4135
double intermediate = nr.downToGrainAlways(curY + dy);
4136
if (intermediate != curY + dy) dy = intermediate - curY;
2834
4141
// jump as far as possible toward goal
2835
if (ANYPOINTONDESTINATION) foundDestination = new MutableBoolean(false);
2836
dy = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, foundDestination);
2837
if (dy <= 0) { dy = 1; stuck = true; }
4142
dy = getJumpSize(svCurrent, curX, curY, curZ, dx, dy, jumpExplanation);
4143
if (dy <= 0) dy = 1;
4145
if (nr.gridLocationsY[curZ] != null && nr.forceGridArcs[curZ] && (curX != toX || curY+dy != toY || curZ != toZ))
4147
double gridY = nr.getClosestYGrid(curZ, curY+dy).getCoordinate();
4150
if (debuggingWavefront)
4152
if (jumpExplanation.length() != 0) setDebugString(i, "Blocked by " + jumpExplanation.toString()); else
4154
setDebugString(i, "Can only move to " + TextUtils.formatDistance(curY+dy) +
4155
" which is gridded down to " + TextUtils.formatDistance(gridY) + " (no movement)");
2840
4163
case 4: // move -Z
2848
if (RoutingDebug.isActive())
4171
if (debuggingWavefront)
2852
case 0: setDebugString(i, "Move -" + TextUtils.formatDouble(Math.abs(dx))); break;
2853
case 1: setDebugString(i, "Move +" + TextUtils.formatDouble(dx)); break;
2854
case 2: setDebugString(i, "Move -" + TextUtils.formatDouble(Math.abs(dy))); break;
2855
case 3: setDebugString(i, "Move +" + TextUtils.formatDouble(dy)); break;
2856
case 4: setDebugString(i, "Move -1"); break;
2857
case 5: setDebugString(i, "Move +1"); break;
4176
setDebugString(i, "Move " + (dx < 0 ? "" : "+") + TextUtils.formatDistance(dx));
4179
setDebugString(i, "Move " + (dy < 0 ? "" : "+") + TextUtils.formatDistance(dy));
4181
case 4: setDebugString(i, "Move -1"); break;
4182
case 5: setDebugString(i, "Move +1"); break;
2860
if (stuck && STICKTOJUMPEDGES)
2862
if (RoutingDebug.isActive()) completeDebugString(i, ": Cannot Move");
2866
4186
// create the "next" step location
2867
4187
double nX = curX + dx;
2868
4188
double nY = curY + dy;
2869
4189
int nZ = curZ + dz;
4193
// limit distance if running a taper on the initial segment
4194
if (fromTaperLen >= 0 && !svCurrent.isOffInitialSegment())
4196
// compute distance from start
4197
double distX = nX - fromX;
4198
double distY = nY - fromY;
4199
double dist = Math.sqrt(distX*distX + distY*distY);
4200
if (dist > fromTaperLen)
4202
if (debuggingWavefront) completeDebugString(i, ": initial taper is " + TextUtils.formatDistance(dist)
4203
+ " from start but maximum taper is " + TextUtils.formatDistance(fromTaperLen));
4207
if (jumpExplanation != null && jumpExplanation.length() != 0)
4208
completeDebugString(i, " [Stopped by " + jumpExplanation.toString() + "]");
4211
if (nZ < 0 || nZ >= numMetalLayers)
4213
if (debuggingWavefront) completeDebugString(i, ": Out Of Bounds");
4216
if (nr.preventArc(nZ))
4218
if (debuggingWavefront) completeDebugString(i, ": Disallowed Arc");
4222
// if switching to destination layer that tapers but is too far away, mark that this cannot finish the route
4223
if (nZ == toZ && toTaperLen >= 0 && (DBMath.areEquals(nX, toX) || DBMath.areEquals(nY, toY)))
4225
// compute distance from end
4226
double closest = Math.max(Math.abs(nX - toX), Math.abs(nY - toY));
4227
if (closest > toTaperLen)
4229
if (taperOnlyArcs[nZ])
4231
if (debuggingWavefront) completeDebugString(i, ": Taper-only layer too far from destination");
4234
tooFarFromEnd = true;
4241
// if new layer has multiple masks, choose the color
4242
if (metalLayers[nZ].length == 1) nC = 0; else
4244
if (sogp.isForceHorVer())
4246
// layers are forced into tracks: get mask number from coordinate information
4247
if (((nZ % 2) == 0) == sogp.isHorizontalEven())
4249
// new layer runs vertically
4250
if (nr.gridLocationsX[nZ] == null) System.out.println("WARNING: No X grid information for Metal " + (nZ+1)); else
4252
SeaOfGatesTrack sogt = nr.getClosestXGrid(nZ, nX);
4253
nC = sogt.getMaskNum();
4256
if (nr.is2X(nZ, curX, curY, nX, nY)) nC = metalLayers[nZ].length + 1 - nC;
4259
System.out.println("WARNING: No mask color for Metal " + (nZ+1) + " at X=" + TextUtils.formatDistance(nX));
4264
// new layer runs horizontally
4265
if (nr.gridLocationsY[nZ] == null) System.out.println("WARNING: No Y grid information for Metal " + (nZ+1)); else
4267
SeaOfGatesTrack sogt = nr.getClosestYGrid(nZ, nY);
4268
nC = sogt.getMaskNum();
4271
if (nr.is2X(nZ, curX, curY, nX, nY)) nC = metalLayers[nZ].length + 1 - nC;
4274
System.out.println("WARNING: No mask color for Metal " + (nZ+1) + " at Y=" + TextUtils.formatDistance(nY));
4282
// track rules failed, figure out color from general rules
4284
// Rule 1: presume the same mask color as the previous metal
4287
// Rule 2: if switching to destination layer, presume mask color of destination
4288
if (nZ == toZ) nC = toC;
4290
// Rule 3: if over new layer, make sure to match its mask color
4291
if (tech.hasColoredMetalLayer(primaryMetalLayer[nZ]))
4293
BlockageTree bTree = rTrees.getMetalTree(primaryMetalLayer[nZ]);
4296
if (!bTree.isEmpty())
4298
// see if there is anything under this point
4299
Rectangle2D searchArea = new Rectangle2D.Double(nX, nY, 0, 0);
4300
for (Iterator<SOGBound> sea = bTree.search(searchArea); sea.hasNext(); )
4302
SOGBound sBound = sea.next();
4303
if (sBound.isSameBasicNet(nr.netID))
4304
nC = sBound.maskLayer;
2871
4315
// force next step to be inside of global routing area
2872
if (foundDestination != null && !foundDestination.booleanValue()) foundDestination = null;
2873
if (globalRoutingDelta != 0 && foundDestination == null)
4316
if (globalRoutingDelta != 0)
2875
4318
Rectangle2D limit = orderedBuckets[svCurrent.globalRoutingBucket];
2876
4319
if (nX < limit.getMinX())
2878
4321
nX = limit.getMinX();
2879
if (!inDestGrid(toRectGridded, nX, curY)) nX = nr.getUpperXGrid(curZ, nX);
4322
if (!inDestGrid(toRectGridded, nX, curY)) nX = nr.getUpperXGrid(curZ, nX).getCoordinate();
2880
4323
dx = nX - curX;
2883
if (RoutingDebug.isActive()) completeDebugString(i, ": Out Of Global Routing X Bounds");
4326
if (debuggingWavefront) completeDebugString(i, ": Out Of Global Routing X Bounds");
2887
4330
if (nX > limit.getMaxX())
2889
4332
nX = limit.getMaxX();
2890
if (!inDestGrid(toRectGridded, nX, curY)) nX = nr.getLowerXGrid(curZ, nX);
4333
if (!inDestGrid(toRectGridded, nX, curY)) nX = nr.getLowerXGrid(curZ, nX).getCoordinate();
2891
4334
dx = nX - curX;
2894
if (RoutingDebug.isActive()) completeDebugString(i, ": Out Of Global Routing X Bounds");
4337
if (debuggingWavefront) completeDebugString(i, ": Out Of Global Routing X Bounds");
2898
4341
if (nY < limit.getMinY())
2900
4343
nY = limit.getMinY();
2901
if (!inDestGrid(toRectGridded, curX, nY)) nY = nr.getUpperYGrid(curZ, nY);
4344
if (!inDestGrid(toRectGridded, curX, nY)) nY = nr.getUpperYGrid(curZ, nY).getCoordinate();
2902
4345
dy = nY - curY;
2905
if (RoutingDebug.isActive()) completeDebugString(i, ": Out Of Global Routing Y Bounds");
4348
if (debuggingWavefront) completeDebugString(i, ": Out Of Global Routing Y Bounds");
2909
4352
if (nY > limit.getMaxY())
2911
4354
nY = limit.getMaxY();
2912
if (!inDestGrid(toRectGridded, curX,nY)) nY = nr.getLowerYGrid(curZ, nY);
4355
if (!inDestGrid(toRectGridded, curX,nY)) nY = nr.getLowerYGrid(curZ, nY).getCoordinate();
2913
4356
dy = nY - curY;
2916
if (RoutingDebug.isActive()) completeDebugString(i, ": Out Of Global Routing Y Bounds");
4359
if (debuggingWavefront) completeDebugString(i, ": Out Of Global Routing Y Bounds");
3478
5004
// add this vertex into the data structures
3479
5005
setVertex(nX, nY, nZ, svNext);
3480
5006
active.add(svNext);
3481
if (RoutingDebug.isActive())
5007
if (debuggingWavefront)
3483
completeDebugString(i, ": To (" + TextUtils.formatDouble(svNext.getX()) + "," + TextUtils.formatDouble(svNext.getY()) +
3484
",M" + (svNext.getZ() + 1) + ")" + costExplanation + "]");
5009
completeDebugString(i, ": To (" + TextUtils.formatDistance(svNext.getX()) + "," + TextUtils.formatDistance(svNext.getY()) +
5010
"," + svNext.describeMetal() + ")" + costExplanation + "]");
3486
if (RoutingDebug.isActive())
5012
if (debuggingWavefront)
3487
5013
RoutingDebug.saveSVLink(svNext, i);
3489
if (RoutingDebug.isActive())
3490
RoutingDebug.saveSVDetails(svCurrent, debugString);
5015
if (debuggingWavefront)
5016
RoutingDebug.saveSVDetails(svCurrent, debugString, false);
5017
if (destinationSV != null) solution = destinationSV;
3491
5018
return destinationSV;
5022
* Method to determine extra geometry needed to ensure minimum area is met
5023
* @param svCurrent the current SearchVertex that is changing layers (or ending a route).
5024
* @param curX the X coordinate of the SearchVertex.
5025
* @param curY the Y coordinate of the SearchVertex.
5026
* @param curC the mask color of the SearchVertex.
5027
* @param curZ the metal layer of the SearchVertex.
5028
* @param mv the contact being placed at this SearchVertex (may be null).
5029
* @param conWid the width of the contact being placed.
5030
* @param conHei the height of the contact being placed.
5031
* @param error set to true if the geometry is needed but cannot be placed.
5032
* @param message set to an error message which explains the problem.
5033
* @return a SearchVertexAddon structure (null if no additional geometry is needed or there is an error).
5035
private SearchVertexAddon determineMinimumArea(SearchVertex svCurrent, double curX, double curY, int curC, int curZ, MetalVia mv, double conWid, double conHei, MutableBoolean error, StringBuffer message)
5037
if (MINAREACHECK && minimumArea[curZ] > 0)
5039
// first compute rectangle in current contact
5040
Rectangle2D conRect = getExtraGeometryForMinArea(svCurrent, mv, conWid, conHei, curX, curY, curZ);
5041
if (conRect != null)
5043
// see if it is outside of routing bounds
5044
if (routingBoundsLimit != null)
5046
if (conRect.getMinX() < routingBoundsLimit.getMinX() || conRect.getMaxX() > routingBoundsLimit.getMaxX() ||
5047
conRect.getMinY() < routingBoundsLimit.getMinY() || conRect.getMaxY() > routingBoundsLimit.getMaxY())
5049
error.setValue(true);
5050
if (debuggingWavefront)
5052
message.append("extra piece of layer " + primaryMetalLayer[curZ].getName() + " for minimum area" +
5053
" at " + TextUtils.formatDistance(conRect.getMinX()) + "<=X<=" + TextUtils.formatDistance(conRect.getMaxX()) +
5054
" and " + TextUtils.formatDistance(conRect.getMinY()) + "<=Y<=" + TextUtils.formatDistance(conRect.getMaxY()) +
5055
" is outside of routing bounds " + TextUtils.formatDistance(routingBoundsLimit.getMinX()) + "<=X<=" + TextUtils.formatDistance(routingBoundsLimit.getMaxX()) +
5056
" and " + TextUtils.formatDistance(routingBoundsLimit.getMinY()) + "<=Y<=" + TextUtils.formatDistance(routingBoundsLimit.getMaxY()));
5062
// see if it creates a design-rule violation
5063
double halfWid = conRect.getWidth() / 2;
5064
double halfHei = conRect.getHeight() / 2;
5065
SOGBound sb = getMetalBlockageAndNotch(curZ, curC, halfWid, halfHei, conRect.getCenterX(), conRect.getCenterY(), svCurrent, true);
5068
error.setValue(true);
5069
if (debuggingWavefront)
5071
message.append("extra piece of layer " + primaryMetalLayer[curZ].getName() + " for minimum area" +
5072
" at " + TextUtils.formatDistance(conRect.getMinX()) + "<=X<=" + TextUtils.formatDistance(conRect.getMaxX()) +
5073
" and " + TextUtils.formatDistance(conRect.getMinY()) + "<=Y<=" + TextUtils.formatDistance(conRect.getMaxY()) +
5074
" conflicts with " + TextUtils.formatDistance(sb.getBounds().getMinX()) + "<=X<=" + TextUtils.formatDistance(sb.getBounds().getMaxX()) +
5075
" and " + TextUtils.formatDistance(sb.getBounds().getMinY()) + "<=Y<=" + TextUtils.formatDistance(sb.getBounds().getMaxY()));
5080
// extra geometry is valid
5083
PrimitiveNode pNp = metalPureLayerNodes[curZ][c];
5084
return new SearchVertexAddon(conRect, pNp);
5091
* Method to figure out whether the minimum area has been met for a contact.
5092
* @param svCurrent the chain of SearchVertex objects leading up to this contact.
5093
* @param mv the contact that will be placed.
5094
* @param curX the X coordinate of the contact.
5095
* @param curY the Y coordinate of the contact.
5096
* @param curZ the Metal layer being considered for minimum area.
5097
* @return a Rectangle2D with extra geometry on that layer (if the minimum area has not been met).
5098
* Returns null if the minimum area has been met.
5100
private Rectangle2D getExtraGeometryForMinArea(SearchVertex svCurrent, MetalVia mv, double wid, double hei, double curX, double curY, int curZ)
5102
// look for SearchVertex with a layer change
5103
getOptimizedList(svCurrent, optimizedList);
5104
int lastInd = optimizedList.size() - 1;
5106
for (int ind = 1; ind < optimizedList.size(); ind++)
5108
SearchVertex sv = optimizedList.get(ind);
5109
SearchVertex lastSv = optimizedList.get(ind - 1);
5110
if (sv.getZ() != lastSv.getZ())
5112
prevViaMet = Math.min(sv.getZ(), lastSv.getZ());
5117
SearchVertex svLast = optimizedList.get(lastInd);
5119
// compute rectangle of metal arc on this layer
5120
double width = nr.getArcWidth(curZ, curX, curY, svLast.getX(), svLast.getY());
5121
Point2D head = new Point2D.Double(curX, curY);
5122
Point2D tail = new Point2D.Double(svLast.getX(), svLast.getY());
5124
if (head.getX() != tail.getX() || head.getY() != tail.getY())
5125
ang = GenMath.figureAngle(tail, head);
5126
Poly poly = Poly.makeEndPointPoly(head.distance(tail), width, ang, head, width / 2, tail,
5127
width / 2, Poly.Type.FILLED);
5128
Rectangle2D boundArc = poly.getBounds2D();
5130
// compute rectangle in current contact (if there is one)
5132
if (mv == null) bound = boundArc; else
5133
bound = getContactGeometry(mv, wid, hei, curX, curY, curZ);
5135
// compute rectangle in previous contact (if there is one)
5136
Rectangle2D boundPrev;
5137
if (svLast.size == null) boundPrev = boundArc; else
5139
// previous contact found: compute its bounds
5140
List<MetalVia> npsPrev = metalVias[prevViaMet].getVias();
5141
if (nr.is2X(prevViaMet, svLast.getX(), svLast.getY(), svLast.getX(), svLast.getY()) ||
5142
(prevViaMet+1 < numMetalLayers && nr.is2X(prevViaMet+1, svLast.getX(), svLast.getY(), svLast.getX(), svLast.getY())))
5144
List<MetalVia> nps2X = metalVias2X[prevViaMet].getVias();
5145
if (nps2X.size() > 0) npsPrev = nps2X;
5147
MetalVia mvPrev = npsPrev.get(svLast.getContactNo());
5148
boundPrev = getContactGeometry(mvPrev, svLast.size.getX(), svLast.size.getY(), svLast.getX(), svLast.getY(), curZ);
5151
// if any of the parts is big enough, no need to look further
5152
if (bound != null && bound.getWidth() * bound.getHeight() >= minimumArea[curZ]) return null;
5153
if (boundPrev != null && boundPrev.getWidth() * boundPrev.getHeight() >= minimumArea[curZ]) return null;
5154
if (boundArc != null && boundArc.getWidth() * boundArc.getHeight() >= minimumArea[curZ]) return null;
5156
// determine extra geometry needed to satisfy minimum area
5158
if (bound.equals(boundArc) && boundPrev.equals(boundArc))
5160
if (boundArc.getWidth() > boundArc.getHeight()) hor = Boolean.TRUE; else
5161
hor = Boolean.FALSE;
5164
if (bound.getMinX() == boundPrev.getMinX() && bound.getMinX() == boundArc.getMinX() &&
5165
bound.getMaxX() == boundPrev.getMaxX() && bound.getMaxX() == boundArc.getMaxX()) hor = Boolean.FALSE;
5166
if (bound.getMinY() == boundPrev.getMinY() && bound.getMinY() == boundArc.getMinY() &&
5167
bound.getMaxY() == boundPrev.getMaxY() && bound.getMaxY() == boundArc.getMaxY()) hor = Boolean.TRUE;
5171
// simple computation if all in a line
5172
if (!hor.booleanValue())
5174
// geometry runs vertically: easy computation of the area
5175
double lY = Math.min(bound.getMinY(), Math.min(boundPrev.getMinY(), boundArc.getMinY()));
5176
double hY = Math.max(bound.getMaxY(), Math.max(boundPrev.getMaxY(), boundArc.getMaxY()));
5177
double area = (hY - lY) * (bound.getMaxX() - bound.getMinX());
5178
if (DBMath.isLessThan(area, minimumArea[curZ]))
5180
// compute where extra geometry will go
5181
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxX() - bound.getMinX());
5182
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5183
if (bound.getCenterY() > boundPrev.getCenterY())
5184
return new Rectangle2D.Double(bound.getMinX(), hY, bound.getWidth(), extraLength);
5185
return new Rectangle2D.Double(bound.getMinX(), lY-extraLength, bound.getWidth(), extraLength);
5187
} else if (hor.booleanValue())
5189
// geometry runs horizontally: easy computation of the area
5190
double lX = Math.min(bound.getMinX(), Math.min(boundPrev.getMinX(), boundArc.getMinX()));
5191
double hX = Math.max(bound.getMaxX(), Math.max(boundPrev.getMaxX(), boundArc.getMaxX()));
5192
double area = (hX - lX) * (bound.getMaxY() - bound.getMinY());
5193
if (DBMath.isLessThan(area, minimumArea[curZ]))
5195
// compute where extra geometry will go
5196
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxY() - bound.getMinY());
5197
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5198
if (bound.getCenterX() > boundPrev.getCenterX())
5199
return new Rectangle2D.Double(hX, bound.getMinY(), extraLength, bound.getHeight());
5200
return new Rectangle2D.Double(lX-extraLength, bound.getMinY(), extraLength, bound.getHeight());
5205
// more complex area computation
5206
PolyMerge pm = new PolyMerge();
5207
Layer layer = primaryMetalLayer[curZ];
5208
pm.addPolygon(layer, new PolyBase(bound));
5209
pm.addPolygon(layer, new PolyBase(boundPrev));
5210
pm.addPolygon(layer, new PolyBase(boundArc));
5211
double area = pm.getAreaOfLayer(layer);
5212
if (DBMath.isLessThan(area, minimumArea[curZ]))
5214
if (bound.getCenterX() == boundPrev.getCenterX() && bound.getCenterY() != boundPrev.getCenterY())
5216
// geometry runs vertically
5217
double lY = Math.min(bound.getMinY(), Math.min(boundPrev.getMinY(), boundArc.getMinY()));
5218
double hY = Math.max(bound.getMaxY(), Math.max(boundPrev.getMaxY(), boundArc.getMaxY()));
5219
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxX() - bound.getMinX());
5220
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5221
if (bound.getCenterY() > boundPrev.getCenterY())
5222
return new Rectangle2D.Double(bound.getMinX(), hY, bound.getWidth(), extraLength);
5223
return new Rectangle2D.Double(bound.getMinX(), lY-extraLength, bound.getWidth(), extraLength);
5224
} else if (bound.getCenterX() != boundPrev.getCenterX() && bound.getCenterY() == boundPrev.getCenterY())
5226
// geometry runs horizontally
5227
double lX = Math.min(bound.getMinX(), Math.min(boundPrev.getMinX(), boundArc.getMinX()));
5228
double hX = Math.max(bound.getMaxX(), Math.max(boundPrev.getMaxX(), boundArc.getMaxX()));
5229
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxY() - bound.getMinY());
5230
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5231
if (bound.getCenterX() > boundPrev.getCenterX())
5232
return new Rectangle2D.Double(hX, bound.getMinY(), extraLength, bound.getHeight());
5233
return new Rectangle2D.Double(lX-extraLength, bound.getMinY(), extraLength, bound.getHeight());
5236
// contacts are not in a line, more advanced computation
5237
if (bound.getWidth() > bound.getHeight())
5239
// layer runs horizontally
5240
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxY() - bound.getMinY());
5241
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5242
if (bound.getCenterX() > boundPrev.getCenterX())
5243
return new Rectangle2D.Double(bound.getMaxX(), bound.getMinY(), extraLength, bound.getHeight());
5244
return new Rectangle2D.Double(bound.getMinX()-extraLength, bound.getMinY(), extraLength, bound.getHeight());
5247
// layer runs vertically
5248
double extraLength = (minimumArea[curZ] - area) / (bound.getMaxX() - bound.getMinX());
5249
extraLength = Math.ceil(extraLength / minResolution) * minResolution;
5250
if (bound.getCenterY() > boundPrev.getCenterY())
5251
return new Rectangle2D.Double(bound.getMinX(), bound.getMaxY(), bound.getWidth(), extraLength);
5252
return new Rectangle2D.Double(bound.getMinX(), bound.getMinY()-extraLength, bound.getWidth(), extraLength);
5261
* Method to get the geometry in a given contact and a given metal.
5262
* @param mv the contact to analyze.
5263
* @param wid the width of the contact.
5264
* @param hei the height of the contact.
5265
* @param curX the X coordinate of the contact.
5266
* @param curY the Y coordinate of the contact.
5267
* @param metNum the desired metal in the contact (0-based).
5268
* @return the rectangle of that metal in the contact.
5270
private Rectangle2D getContactGeometry(MetalVia mv, double wid, double hei, double curX, double curY, int metNum)
5272
PrimitiveNode np = mv.via;
5273
Orientation orient = Orientation.fromJava(mv.orientation * 10, false, false);
5274
NodeInst ni = NodeInst.makeDummyInstance(np, ep, EPoint.fromLambda(curX, curY), wid, hei, orient);
5275
FixpTransform trans = null;
5276
if (orient != Orientation.IDENT) trans = ni.rotateOut();
5277
Poly[] polys = np.getTechnology().getShapeOfNode(ni);
5278
for (int j = 0; j < polys.length; j++)
5280
Poly poly = polys[j];
5281
if (poly.getLayer().getFunction().getLevel() != metNum+1) continue;
5282
if (trans != null) poly.transform(trans);
5283
return poly.getBounds2D();
3494
5288
private int getNextBucket(SearchVertex svCurrent, double nX, double nY)
3496
5290
int start = orderedBase[svCurrent.globalRoutingBucket];
3797
private double getJumpSize(SearchVertex sv, double curX, double curY, int curZ, double dx, double dy, MutableBoolean foundDestination)
5690
* Method to find the X position on a horizontal line that is a given design-rule distance from a blockage point.
5691
* @param xPos an X coordinate on the horizontal line.
5692
* @param yPos the Y coordinate of the horizontal line.
5693
* @param drDist the given design-rule distance.
5694
* @param xBlock the X coordinate of the blockage point.
5695
* @param yBlock the Y coordinate of the blockage point.
5696
* @return the new X coordinate along the horizontal line that is the distance from the point.
5697
* Returns null if there is no intersection.
5699
private Double getHorizontalBlockage(double xPos, double yPos, double drDist, double xBlock, double yBlock)
5701
double dY = yBlock - yPos;
5702
if (dY >= drDist) return null;
5703
double dX = Math.sqrt(drDist*drDist - dY*dY);
5704
if (xPos > xBlock) return new Double(xBlock + dX);
5705
return new Double(xBlock - dX);
5709
* Method to find the X position on a vertical line that is a given design-rule distance from a blockage point.
5710
* @param xPos the X coordinate on the vertical line.
5711
* @param yPos a Y coordinate of the vertical line.
5712
* @param drDist the given design-rule distance.
5713
* @param xBlock the X coordinate of the blockage point.
5714
* @param yBlock the Y coordinate of the blockage point.
5715
* @return the new Y coordinate along the vertical line that is the distance from the point.
5716
* Returns null if there is no intersection.
5718
private Double getVerticalBlockage(double xPos, double yPos, double drDist, double xBlock, double yBlock)
5720
double dX = xBlock - xPos;
5721
if (dX >= drDist) return null;
5722
double dY = Math.sqrt(drDist*drDist - dX*dX);
5723
if (yPos > yBlock) return new Double(yBlock + dY);
5724
return new Double(yBlock - dY);
5727
private double getJumpSize(SearchVertex sv, double curX, double curY, int curZ, double dx, double dy,
5728
StringBuffer explanation)
3799
5730
Rectangle2D jumpBound = nr.jumpBound;
3800
double width = nr.getArcWidth(curZ);
5731
double width = nr.getArcWidth(curZ, curX, curY, curX+dx, curY+dy);
5732
double halfWidth = width / 2;
3801
5733
double[] fromSurround = nr.getSpacingRule(curZ, width, 50);
3802
double metalSpacingX = width / 2 + fromSurround[0];
3803
double metalSpacingY = width / 2 + fromSurround[1];
3804
double lX = curX - metalSpacingX, hX = curX + metalSpacingX;
3805
double lY = curY - metalSpacingY, hY = curY + metalSpacingY;
3806
if (dx > 0) hX = jumpBound.getMaxX() + metalSpacingX; else
3807
if (dx < 0) lX = jumpBound.getMinX() - metalSpacingX; else
3808
if (dy > 0) hY = jumpBound.getMaxY() + metalSpacingY; else
3809
if (dy < 0) lY = jumpBound.getMinY() - metalSpacingY;
3811
BlockageTree bTree = rTrees.getMetalTree(metalLayers[curZ]);
5734
double lX = curX - halfWidth, hX = curX + halfWidth;
5735
double lY = curY - halfWidth, hY = curY + halfWidth;
5736
if (dx > 0) hX = jumpBound.getMaxX() + halfWidth; else
5737
if (dx < 0) lX = jumpBound.getMinX() - halfWidth; else
5738
if (dy > 0) hY = jumpBound.getMaxY() + halfWidth; else
5739
if (dy < 0) lY = jumpBound.getMinY() - halfWidth;
5740
BlockageTree bTree = rTrees.getMetalTree(primaryMetalLayer[curZ]);
5741
Rectangle2D topX = null, botX = null, topY = null, botY = null;
3814
5744
if (!bTree.isEmpty())
3816
5746
// see if there is anything in that area
3817
boolean hitDestination = false;
3818
Rectangle2D searchArea = new Rectangle2D.Double(lX, lY, hX - lX, hY - lY);
3819
for (Iterator<SOGBound> sea = bTree.search(searchArea); sea.hasNext();)
5747
double lXSearch = lX - fromSurround[0], hXSearch = hX + fromSurround[0];
5748
double lYSearch = lY - fromSurround[1], hYSearch = hY + fromSurround[1];
5749
Rectangle2D searchArea = new Rectangle2D.Double(lXSearch, lYSearch, hXSearch - lXSearch, hYSearch - lYSearch);
5750
for (Iterator<SOGBound> sea = bTree.search(searchArea); sea.hasNext(); )
3821
5752
SOGBound sBound = sea.next();
3822
5753
Rectangle2D bound = sBound.getBounds();
3823
if (sBound.isSameBasicNet(nr.netID))
3825
if (foundDestination != null && sBound.hasEndBit(toBit))
3827
if (dx > 0 && bound.getCenterX() + metalSpacingX < hX) { hX = bound.getCenterX() + metalSpacingX; hitDestination = true; }
3828
if (dx < 0 && bound.getCenterX() - metalSpacingX > lX) { lX = bound.getCenterX() - metalSpacingX; hitDestination = true; }
3829
if (dy > 0 && bound.getCenterY() + metalSpacingY < hY) { hY = bound.getCenterY() + metalSpacingY; hitDestination = true; }
3830
if (dy < 0 && bound.getCenterY() - metalSpacingY > lY) { lY = bound.getCenterY() - metalSpacingY; hitDestination = true; }
3834
if (bound.getMinX() >= hX || bound.getMaxX() <= lX || bound.getMinY() >= hY || bound.getMaxY() <= lY)
3836
if (dx > 0 && bound.getMinX() < hX) { hX = bound.getMinX(); hitDestination = false; }
3837
if (dx < 0 && bound.getMaxX() > lX) { lX = bound.getMaxX(); hitDestination = false; }
3838
if (dy > 0 && bound.getMinY() < hY) { hY = bound.getMinY(); hitDestination = false; }
3839
if (dy < 0 && bound.getMaxY() > lY) { lY = bound.getMaxY(); hitDestination = false; }
5754
if (sBound.isSameBasicNet(nr.netID)) continue;
5756
// handle diagonal spacing
5757
if (lX <= bound.getMaxX() && hX >= bound.getMinX())
5759
if (lY <= bound.getMaxY() && hY >= bound.getMinY())
5761
// rectangles touch or overlap
5762
if (dx > 0 && bound.getMinX()-fromSurround[0] < hX) { hX = bound.getMinX()-fromSurround[0]; topX = bound; }
5763
if (dx < 0 && bound.getMaxX()+fromSurround[0] > lX) { lX = bound.getMaxX()+fromSurround[0]; botX = bound; }
5764
if (dy > 0 && bound.getMinY()-fromSurround[1] < hY) { hY = bound.getMinY()-fromSurround[1]; topY = bound; }
5765
if (dy < 0 && bound.getMaxY()+fromSurround[1] > lY) { lY = bound.getMaxY()+fromSurround[1]; botY = bound; }
5769
// rectangles are one above the other
5771
if ((lY+hY)/2 > (bound.getMinY()+bound.getMaxY())/2)
5772
diff = lY - bound.getMaxY(); else
5773
diff = bound.getMinY() - hY;
5774
if (DBMath.isGreaterThanOrEqualTo(diff, fromSurround[1])) continue;
5777
if (lY <= bound.getMaxY() && hY >= bound.getMinY())
5779
// rectangles are side-by-side
5781
if ((lX+hX)/2 > (bound.getMinX()+bound.getMaxX())/2)
5782
diff = lX - bound.getMaxX(); else
5783
diff = bound.getMinX() - hX;
5784
if (DBMath.isGreaterThanOrEqualTo(diff, fromSurround[0])) continue;
5787
// diagonal offset, compute Euclidean distance to corners
5788
double cut2CornerX, cut2CornerY, cut1CornerX, cut1CornerY;
5789
if ((bound.getMinX()+bound.getMaxX())/2 < (lX+hX)/2)
5791
cut2CornerX = bound.getMaxX();
5795
cut2CornerX = bound.getMinX();
5798
if ((bound.getMinY()+bound.getMaxY())/2 < (lY+hY)/2)
5800
cut2CornerY = bound.getMaxY();
5804
cut2CornerY = bound.getMinY();
5807
double dX = Math.abs(cut2CornerX - cut1CornerX);
5808
double dY = Math.abs(cut2CornerY - cut1CornerY);
5809
if (DBMath.isGreaterThanOrEqualTo(dX, fromSurround[0])) continue;
5810
if (DBMath.isGreaterThanOrEqualTo(dY, fromSurround[1])) continue;
5811
double diff = Math.sqrt(dX*dX + dY*dY);
5812
if (DBMath.isGreaterThanOrEqualTo(diff, Math.max(fromSurround[0], fromSurround[1]))) continue;
5816
// determine diagonal limit to the jump
5820
double drDist = Math.max(fromSurround[0], fromSurround[1]);
5821
double xBlock = bound.getCenterX() < curX ? bound.getMaxX() : bound.getMinX();
5822
double yBlock = bound.getCenterY() < curY ? bound.getMaxY() : bound.getMinY();
5823
Double lYintX = getHorizontalBlockage(curX, lY, drDist, xBlock, yBlock);
5824
Double hYintX = getHorizontalBlockage(curX, hY, drDist, xBlock, yBlock);
5828
if (lYintX != null && lYintX.doubleValue() > lX && lYintX.doubleValue() <= curX) { lX = lYintX.doubleValue(); botX = bound; }
5829
if (hYintX != null && hYintX.doubleValue() > lX && hYintX.doubleValue() <= curX) { lX = hYintX.doubleValue(); botX = bound; }
5833
if (lYintX != null && lYintX.doubleValue() < hX && lYintX.doubleValue() >= curX) { hX = lYintX.doubleValue(); topX = bound; }
5834
if (hYintX != null && hYintX.doubleValue() < hX && hYintX.doubleValue() >= curX) { hX = hYintX.doubleValue(); topX = bound; }
5839
double drDist = Math.max(fromSurround[0], fromSurround[1]);
5840
double xBlock = bound.getCenterX() < curX ? bound.getMaxX() : bound.getMinX();
5841
double yBlock = bound.getCenterY() < curY ? bound.getMaxY() : bound.getMinY();
5842
Double lXintY = getVerticalBlockage(lX, curY, drDist, xBlock, yBlock);
5843
Double hXintY = getVerticalBlockage(hX, curY, drDist, xBlock, yBlock);
5847
if (lXintY != null && lXintY.doubleValue() > lY && lXintY.doubleValue() <= curY) { lY = lXintY.doubleValue(); botY = bound; }
5848
if (hXintY != null && hXintY.doubleValue() > lY && hXintY.doubleValue() <= curY) { lY = hXintY.doubleValue(); botY = bound; }
5852
if (lXintY != null && lXintY.doubleValue() < hY && lXintY.doubleValue() >= curY) { hY = lXintY.doubleValue(); topY = bound; }
5853
if (hXintY != null && hXintY.doubleValue() < hY && hXintY.doubleValue() >= curY) { hY = hXintY.doubleValue(); topY = bound; }
3841
if (foundDestination != null) foundDestination.setValue(hitDestination);
3844
5859
bTree.unlock();
3848
dx = nr.downToGrain(hX - metalSpacingX) - curX;
5863
dx = nr.downToGrain(hX - halfWidth) - curX;
5864
if (fromTaperLen >= 0 && !sv.isOffInitialSegment() && dx > fromTaperLen) dx = fromTaperLen;
5865
if (curZ == toZ && curY == toY && curX < toX && curX+dx > toX) dx = toX - curX;
3849
5866
if (curX + dx > toX && curY >= toRect.getMinY() && curY <= toRect.getMaxY() && curZ == toZ) dx = toX - curX; else
3851
5868
if (!inDestGrid(toRectGridded, curX+dx, curY))
3852
dx = nr.getLowerXGrid(curZ, curX+dx) - curX;
5869
dx = nr.getLowerXGrid(curZ, curX+dx).getCoordinate() - curX;
3853
5870
if (globalRoutingDelta != 0)
3855
5872
Rectangle2D limit = orderedBuckets[sv.globalRoutingBucket];
4491
6636
private boolean initializeDesignRules()
4493
// find the metal layers, arcs, and contacts
4494
numMetalLayers = tech.getNumMetals();
4495
metalLayers = new Layer[numMetalLayers];
4496
metalArcs = new ArcProto[numMetalLayers];
6638
// find the number of metal layers
6640
for(Iterator<Layer> it = tech.getLayers(); it.hasNext(); )
6642
Layer lay = it.next();
6643
if (!lay.getFunction().isMetal()) continue;
6644
int metNum = lay.getFunction().getLevel();
6645
numMetalLayers = Math.max(metNum, numMetalLayers);
6647
for(Iterator<ArcProto> it = tech.getArcs(); it.hasNext(); )
6649
ArcProto ap = it.next();
6650
if (!ap.getFunction().isMetal()) continue;
6651
int metNum = ap.getFunction().getLevel();
6652
numMetalLayers = Math.max(metNum, numMetalLayers);
6655
// load up the metal layers
6656
metalLayers = new Layer[numMetalLayers][];
6657
primaryMetalLayer = new Layer[numMetalLayers];
6658
List<Layer>[] tempLayerList = new List[numMetalLayers];
6659
for(int i=0; i<numMetalLayers; i++) tempLayerList[i] = new ArrayList<Layer>();
6660
for(Iterator<Layer> it = tech.getLayers(); it.hasNext(); )
6662
Layer lay = it.next();
6663
if (!lay.getFunction().isMetal()) continue;
6664
int metNum = lay.getFunction().getLevel() - 1;
6665
tempLayerList[metNum].add(lay);
6667
for(int i=0; i<numMetalLayers; i++)
6669
primaryMetalLayer[i] = null;
6670
Collections.sort(tempLayerList[i], new SortLayersByMaskNumber());
6671
if (tempLayerList[i].size() > 1)
6673
// multiple layers for this metal: see if an uncolored layer is mixed with colored ones
6674
Layer first = tempLayerList[i].get(0);
6675
int colorNum = first.getFunction().getMaskColor();
6676
if (colorNum == 0) { primaryMetalLayer[i] = tempLayerList[i].get(0); tempLayerList[i].remove(0); }
6678
metalLayers[i] = new Layer[tempLayerList[i].size()];
6679
for(int c=0; c<tempLayerList[i].size(); c++) metalLayers[i][c] = tempLayerList[i].get(c);
6680
if (primaryMetalLayer[i] == null) primaryMetalLayer[i] = metalLayers[i][0];
6683
// load up the metal arcs
6684
metalArcs = new ArcProto[numMetalLayers][];
6685
metalPureLayerNodes = new PrimitiveNode[numMetalLayers][];
6686
primaryMetalArc = new ArcProto[numMetalLayers];
6687
size2X = new double[numMetalLayers];
6688
taperLength = new double[numMetalLayers];
6689
boolean hasFavorites = false;
4497
6690
favorArcs = new boolean[numMetalLayers];
4498
6691
preventArcs = new boolean[numMetalLayers];
6692
taperOnlyArcs = new boolean[numMetalLayers];
6693
for(int i=0; i<numMetalLayers; i++)
6694
favorArcs[i] = preventArcs[i] = taperOnlyArcs[i] = false;
6695
List<ArcProto>[] tempArcList = new List[numMetalLayers];
6696
for(int i=0; i<numMetalLayers; i++) tempArcList[i] = new ArrayList<ArcProto>();
6697
for(Iterator<ArcProto> it = tech.getArcs(); it.hasNext(); )
6699
ArcProto ap = it.next();
6700
if (!ap.getFunction().isMetal()) continue;
6701
int metNum = ap.getFunction().getLevel() - 1;
6702
tempArcList[metNum].add(ap);
6704
for(int i=0; i<numMetalLayers; i++)
6706
primaryMetalArc[i] = null;
6707
Collections.sort(tempArcList[i], new SortArcsByMaskNumber());
6708
if (tempArcList[i].size() > 1)
6710
// multiple layers for this metal: see if an uncolored layer is mixed with colored ones
6711
ArcProto first = tempArcList[i].get(0);
6712
int colorNum = first.getMaskLayer();
6713
if (colorNum == 0) { primaryMetalArc[i] = tempArcList[i].get(0); tempArcList[i].remove(0); }
6715
metalArcs[i] = new ArcProto[tempArcList[i].size()];
6716
metalPureLayerNodes[i] = new PrimitiveNode[tempArcList[i].size()];
6717
for(int c=0; c<tempArcList[i].size(); c++)
6719
ArcProto ap = tempArcList[i].get(c);
6720
int metNum = ap.getFunction().getLevel() - 1;
6721
metalArcs[i][c] = ap;
6722
for(Iterator<PrimitiveNode> it = tech.getNodes(); it.hasNext(); )
6724
PrimitiveNode pNp = it.next();
6725
if (pNp.getFunction() != PrimitiveNode.Function.NODE) continue;
6726
for(Iterator<Layer> lIt = pNp.getLayerIterator(); lIt.hasNext(); )
6728
Layer lay = lIt.next();
6729
if (!lay.getFunction().isMetal()) continue;
6730
if (lay.getFunction().getLevel()-1 != metNum) continue;
6731
if (lay.getFunction().getMaskColor() != ap.getMaskLayer()) continue;
6732
metalPureLayerNodes[i][c] = pNp;
6735
if (metalPureLayerNodes[i][c] != null) break;
6737
if (sogp.isFavored(ap))
6739
favorArcs[metNum] = true;
6740
hasFavorites = true;
6742
if (sogp.isPrevented(ap)) preventArcs[metNum] = true;
6743
if (sogp.isTaperOnly(ap)) taperOnlyArcs[metNum] = true;
6745
if (primaryMetalArc[i] == null) primaryMetalArc[i] = metalArcs[i][0];
6747
Double d = sogp.get2XWidth(primaryMetalArc[i]);
6748
if (d == null) size2X[i] = 0; else size2X[i] = d.doubleValue();
6749
d = sogp.getTaperLength(primaryMetalArc[i]);
6750
if (d == null) taperLength[i] = -1; else taperLength[i] = d.doubleValue();
6753
for (int i = 0; i < numMetalLayers; i++) favorArcs[i] = true;
6755
// do error checking
6756
boolean failure = false;
6757
for(int i=0; i<numMetalLayers; i++)
6759
if (metalLayers[i].length == 0)
6761
error("Cannot find layer for Metal " + (i+1) + " in technology " + tech.getTechName());
6764
if (metalArcs[i].length == 0)
6766
error("Cannot find arc for Metal " + (i+1) + " in technology " + tech.getTechName());
6769
for(int c=0; c<metalPureLayerNodes[i].length; c++)
6771
if (metalPureLayerNodes[i][c] == null)
6773
error("Cannot find pure-layer node for Metal " + (i+1) + " color " + (c+1) + " in technology " + tech.getTechName());
6777
if (metalLayers[i].length != metalArcs[i].length)
6780
for(int c=0; c<metalLayers[i].length; c++)
6782
if (layMsg.length() > 0) layMsg += ", ";
6783
layMsg += metalLayers[i][c].getName();
6786
for(int c=0; c<metalArcs[i].length; c++)
6788
if (arcMsg.length() > 0) arcMsg += ", ";
6789
arcMsg += metalArcs[i][c].getName();
6791
warn("Metal " + (i+1) + " in technology " + tech.getTechName() + " has " + metalLayers[i].length +
6792
" mask layers (" + layMsg + ") but " + metalArcs[i].length + " mask arcs (" + arcMsg + "). Making them equal length.");
6793
if (metalLayers[i].length > metalArcs[i].length)
6795
Layer[] newMetalLayers = new Layer[metalArcs[i].length];
6796
for(int c=0; c<newMetalLayers.length; c++) newMetalLayers[c] = metalLayers[i][c];
6797
metalLayers[i] = newMetalLayers;
6800
ArcProto[] newMetalArcs = new ArcProto[metalLayers[i].length];
6801
for(int c=0; c<newMetalArcs.length; c++) newMetalArcs[c] = metalArcs[i][c];
6802
metalArcs[i] = newMetalArcs;
6805
if (metalLayers[i].length == metalArcs[i].length)
6807
boolean badOrder = false;
6808
String layMsg = "", arcMsg = "";
6809
for(int c=0; c<metalLayers[i].length; c++)
6811
int layMask = metalLayers[i][c].getFunction().getMaskColor();
6812
int arcMask = metalArcs[i][c].getMaskLayer();
6813
if (layMsg.length() > 0) layMsg += ", ";
6815
if (arcMsg.length() > 0) arcMsg += ", ";
6817
if (layMask != arcMask) badOrder = true;
6821
error("Metal " + (i+1) + " in technology " + tech.getTechName() + " has layer masks " + layMsg + " but arc masks " + arcMsg);
6826
if (failure) return true;
6828
// find the layers that remove metal
6829
removeLayers = new HashMap<Layer,Layer>();
6830
for(int i=0; i<numMetalLayers; i++)
6832
for(int j=0; j<metalLayers[i].length; j++)
6834
Layer metLay = metalLayers[i][j];
6835
ArcProto metAp = metalArcs[i][j];
6836
String removeLayerName = sogp.getRemoveLayer(metAp);
6837
if (removeLayerName == null) continue;
6838
Layer removeLay = tech.findLayer(removeLayerName);
6839
if (removeLay == null) System.out.println("WARNING: Unknown removal layer: " + removeLayerName); else
6840
removeLayers.put(removeLay, metLay);
6844
// now gather the via information
4499
6845
viaLayers = new Layer[numMetalLayers - 1];
4500
6846
metalVias = new MetalVias[numMetalLayers - 1];
4501
6847
for (int i = 0; i < numMetalLayers - 1; i++)
4502
6848
metalVias[i] = new MetalVias();
4503
for (Iterator<Layer> it = tech.getLayers(); it.hasNext();)
4505
Layer lay = it.next();
4506
if (!lay.getFunction().isMetal()) continue;
4507
int layerIndex = lay.getFunction().getLevel() - 1;
4508
if (layerIndex < numMetalLayers) metalLayers[layerIndex] = lay;
4510
boolean hasFavorites = false;
4511
for (Iterator<ArcProto> it = tech.getArcs(); it.hasNext(); )
4513
ArcProto ap = it.next();
4514
for (int i = 0; i < numMetalLayers; i++)
4516
if (ap.getLayer(0) == metalLayers[i])
4519
favorArcs[i] = sogp.isFavored(ap);
4520
if (favorArcs[i]) hasFavorites = true;
4521
preventArcs[i] = sogp.isPrevented(ap);
4527
for (int i = 0; i < numMetalLayers; i++) favorArcs[i] = true;
6849
metalVias2X = new MetalVias[numMetalLayers - 1];
6850
for (int i = 0; i < numMetalLayers - 1; i++)
6851
metalVias2X[i] = new MetalVias();
4529
6853
// regular expression to discard some primitives
4530
6854
String ignorePattern = sogp.getIgnorePrimitives(); // "Z-(\\w+)"
4531
String acceptPattern = sogp.getAcceptOnlyPrimitives(); // "X-(\\w+)"
6855
String accept1XPattern = sogp.getAcceptOnly1XPrimitives(); // "X-(\\w+)"
6856
String accept2XPattern = sogp.getAcceptOnly2XPrimitives(); // "R-(\\w+)"
4532
6857
boolean contactsCanRotate = sogp.isContactsRotate();
4533
6858
Pattern ignorePat = (ignorePattern != null) ? Pattern.compile(ignorePattern) : null;
4534
Pattern acceptPat = (acceptPattern != null) ? Pattern.compile(acceptPattern) : null;
6859
Pattern acceptPat1X = (accept1XPattern != null) ? Pattern.compile(accept1XPattern) : null;
6860
Pattern acceptPat2X = (accept2XPattern != null) ? Pattern.compile(accept2XPattern) : null;
4535
6861
for (Iterator<PrimitiveNode> it = tech.getNodes(); it.hasNext();)
4537
6863
PrimitiveNode np = it.next();
4545
6871
if (matcher.find()) continue;
4548
if (acceptPat != null)
4550
// Match not found and therefore not using this primitive
4551
Matcher matcher = acceptPat.matcher(np.getName());
4552
if (!matcher.find()) continue;
4555
ArcProto[] conns = np.getPort(0).getConnections();
4556
for (int i = 0; i < numMetalLayers - 1; i++)
4558
if ((conns[0] == metalArcs[i] && conns[1] == metalArcs[i + 1]) ||
4559
(conns[1] == metalArcs[i] && conns[0] == metalArcs[i + 1]))
6874
// see if this is a 1X or 2X contact
6875
boolean is1XContact = false, is2XContact = false;
6876
if (acceptPat1X == null) is1XContact = true; else
6878
Matcher matcher = acceptPat1X.matcher(np.getName());
6879
is1XContact = matcher.find();
6881
if (acceptPat2X == null) is2XContact = true; else
6883
Matcher matcher = acceptPat2X.matcher(np.getName());
6884
is2XContact = matcher.find();
6886
if (is1XContact || is2XContact)
6888
MetalVias[] whichOnes = is1XContact ? metalVias : metalVias2X;
6889
ArcProto[] conns = np.getPort(0).getConnections();
6890
for (int i = 0; i < numMetalLayers - 1; i++)
4561
// see if the node is asymmetric and should exist in rotated states
4562
boolean square = true, offCenter = false;
4563
NodeInst dummyNi = NodeInst.makeDummyInstance(np, ep);
4564
Poly[] conPolys = tech.getShapeOfNode(dummyNi);
4565
int horMet = -1, verMet = -1;
4566
double horMetInset = 0, verMetInset = 0;
4567
for (int p = 0; p < conPolys.length; p++)
6892
if ((isOnMetalArc(i, conns[0]) && isOnMetalArc(i+1, conns[1])) ||
6893
(isOnMetalArc(i, conns[1]) && isOnMetalArc(i+1, conns[0])))
4569
Poly conPoly = conPolys[p];
4570
Layer conLayer = conPoly.getLayer();
4571
Layer.Function lFun = conLayer.getFunction();
6895
// see if the node is asymmetric and should exist in rotated states
6896
boolean square = true, offCenter = false;
6897
NodeInst dummyNi = NodeInst.makeDummyInstance(np, ep);
6898
Poly[] conPolys = tech.getShapeOfNode(dummyNi);
6899
int horMet = -1, verMet = -1;
6900
double horMetInset = 0, verMetInset = 0;
6901
int horMetColor = 0, verMetColor = 0;
6902
for (int p = 0; p < conPolys.length; p++)
4574
Rectangle2D conRect = conPoly.getBounds2D();
4575
if (conRect.getWidth() != conRect.getHeight())
6904
Poly conPoly = conPolys[p];
6905
Layer conLayer = conPoly.getLayer();
6906
Layer.Function lFun = conLayer.getFunction();
4578
if (conRect.getWidth() > conRect.getHeight())
4581
horMet = lFun.getLevel() - 1;
4582
horMetInset = dummyNi.getYSize() - conRect.getHeight();
4586
verMet = lFun.getLevel() - 1;
4587
verMetInset = dummyNi.getXSize() - conRect.getWidth();
6909
Rectangle2D conRect = conPoly.getBounds2D();
6910
if (conRect.getWidth() != conRect.getHeight())
6913
if (conRect.getWidth() > conRect.getHeight())
6916
horMet = lFun.getLevel() - 1;
6917
horMetColor = lFun.getMaskColor();
6918
horMetInset = dummyNi.getYSize() - conRect.getHeight();
6922
verMet = lFun.getLevel() - 1;
6923
verMetColor = lFun.getMaskColor();
6924
verMetInset = dummyNi.getXSize() - conRect.getWidth();
6927
if (conRect.getCenterX() != 0 || conRect.getCenterY() != 0) offCenter = true;
6928
} else if (lFun.isContact())
6930
viaLayers[i] = conLayer;
4590
if (conRect.getCenterX() != 0 || conRect.getCenterY() != 0) offCenter = true;
4591
} else if (lFun.isContact())
4593
viaLayers[i] = conLayer;
4597
if (square || offCenter) horMet = verMet = -1; else
4598
if (horMet < 0 || verMet < 0) horMet = verMet = -1;
4599
metalVias[i].addVia(np, 0, horMet, horMetInset, verMet, verMetInset);
4600
if (contactsCanRotate)
4604
// off center: test in all 4 rotations
4605
metalVias[i].addVia(np, 90, horMet, horMetInset, verMet, verMetInset);
4606
metalVias[i].addVia(np, 180, horMet, horMetInset, verMet, verMetInset);
4607
metalVias[i].addVia(np, 270, horMet, horMetInset, verMet, verMetInset);
4610
// centered but not square: test in 90-degree rotation
4611
metalVias[i].addVia(np, 90, verMet, verMetInset, horMet, horMetInset);
6934
if (square || offCenter) horMet = verMet = -1; else
6935
if (horMet < 0 || verMet < 0) horMet = verMet = -1;
6936
whichOnes[i].addVia(np, 0, horMet, horMetColor, horMetInset, verMet, verMetColor, verMetInset);
6937
if (contactsCanRotate)
6941
// off center: test in all 4 rotations
6942
whichOnes[i].addVia(np, 90, horMet, horMetColor, horMetInset, verMet, verMetColor, verMetInset);
6943
whichOnes[i].addVia(np, 180, horMet, horMetColor, horMetInset, verMet, verMetColor, verMetInset);
6944
whichOnes[i].addVia(np, 270, horMet, horMetColor, horMetInset, verMet, verMetColor, verMetInset);
6947
// centered but not square: test in 90-degree rotation
6948
whichOnes[i].addVia(np, 90, verMet, verMetColor, verMetInset, horMet, horMetColor, horMetInset);
4618
for (int i = 0; i < numMetalLayers; i++)
6956
for (int i = 0; i < numMetalLayers-1; i++)
4620
if (metalLayers[i] == null)
4622
error("Cannot find layer for Metal " + (i + 1));
4625
if (metalArcs[i] == null)
4627
error("Cannot find arc for Metal " + (i + 1));
4630
if (i < numMetalLayers - 1)
4632
boolean noContact = false;
4633
if (metalVias[i].getVias().size() == 0)
4635
warn("Cannot find contact node between Metal " + (i+1) + " and Metal " + (i+2) + " in technology " + tech.getTechName() +
4636
". Ignoring Metal layers " + (i+2) + " and higher.");
4638
} else if (viaLayers[i] == null)
4640
warn("Cannot find contact layer between Metal " + (i+1) + " and Metal " + (i+2) + " in technology " + tech.getTechName() +
4641
". Ignoring Metal layers " + (i+2) + " and higher.");
4646
for(int j=i+1; j<numMetalLayers; j++)
4647
preventArcs[j] = true;
6958
// check that the vias span all of the masks
6959
if (metalArcs[i].length > 1 || metalArcs[i+1].length > 1)
6961
boolean[][] masks = new boolean[metalArcs[i].length][metalArcs[i+1].length];
6962
for(int c1=0; c1<metalArcs[i].length; c1++)
6963
for(int c2=0; c2<metalArcs[i+1].length; c2++) masks[c1][c2] = false;
6964
List<MetalVia> allContacts = new ArrayList<MetalVia>();
6965
for(MetalVia mv : metalVias[i].getVias())
6966
allContacts.add(mv);
6967
for(MetalVia mv : metalVias2X[i].getVias())
6968
allContacts.add(mv);
6969
for(MetalVia mv : allContacts)
6971
int met1 = -1, met1c = -1, met2 = -1, met2c = -1;
6972
for(NodeLayer nl : mv.via.getNodeLayers())
6974
Layer layer = nl.getLayer();
6975
if (layer.getFunction().isMetal())
6979
met1 = layer.getFunction().getLevel();
6980
met1c = layer.getFunction().getMaskColor();
6983
met2 = layer.getFunction().getLevel();
6984
met2c = layer.getFunction().getMaskColor();
6988
if (met1 < 0 || met2 < 0) continue;
6989
if (met1 != i+1 || met2 != i+2)
6991
warn("Contact " + mv.via.getName() + " in technology " + tech.getTechName() +
6992
" bridges metals " + (i+1) + " and " + (i+2) + " but mentions different metals in its name");
6997
if (metalArcs[i].length > 1)
6998
warn("Contact " + mv.via.getName() + " in technology " + tech.getTechName() +
6999
" does not specify mask for metal " + (i+1));
7004
if (metalArcs[i+1].length > 1)
7005
warn("Contact " + mv.via.getName() + " in technology " + tech.getTechName() +
7006
" does not specify mask for metal " + (i+2));
7009
masks[met1c-1][met2c-1] = true;
7011
for(int c1=0; c1<metalArcs[i].length; c1++)
7013
for(int c2=0; c2<metalArcs[i+1].length; c2++)
7015
if (masks[c1][c2]) continue;
7016
warn("No metal-" + (i+1) + " to metal-" + (i+2) + " contact in technology " + tech.getTechName() +
7017
" that bridges metal-" + (i+1) + "/mask-" + (c1+1) + " and metal-" + (i+2) + "/mask-" + (c2+1));
7022
boolean noContact = false;
7023
if (metalVias[i].getVias().size() == 0)
7025
warn("Cannot find contact node between Metal " + (i+1) + " and Metal " + (i+2) + " in technology " + tech.getTechName() +
7026
". Ignoring Metal layers " + (i+2) + " and higher.");
7028
} else if (viaLayers[i] == null)
7030
warn("Cannot find contact layer between Metal " + (i+1) + " and Metal " + (i+2) + " in technology " + tech.getTechName() +
7031
". Ignoring Metal layers " + (i+2) + " and higher.");
7036
for(int j=i+1; j<numMetalLayers; j++)
7037
preventArcs[j] = true;
4653
7043
// compute design rule spacings
7044
DRC.DRCPreferences dp = new DRC.DRCPreferences(false);
7045
minResolution = dp.getResolution(tech).getLambda();
4654
7046
layerSurround = new Map[numMetalLayers];
4655
7047
for (int i = 0; i < numMetalLayers; i++)
4656
7048
layerSurround[i] = new HashMap<Double, Map<Double, double[]>>();
4657
metalSurround = new double[numMetalLayers];
4658
worstMetalSurround = new double[numMetalLayers];
7049
metalSurroundX = new double[numMetalLayers];
7050
metalSurroundY = new double[numMetalLayers];
7051
maxDefArcWidth = new double[numMetalLayers];
7052
minimumArea = new double[numMetalLayers];
4659
7053
MutableDouble mutableDist = new MutableDouble(0);
4660
7054
for (int i = 0; i < numMetalLayers; i++)
4662
DRCTemplate rule = DRC.getSpacingRule(metalLayers[i], null, metalLayers[i], null, false, -1, metalArcs[i].getDefaultLambdaBaseWidth(ep), 50);
4663
metalSurround[i] = 0;
4664
if (rule != null) metalSurround[i] = rule.getValue(0);
4665
if (DRC.getMaxSurround(metalLayers[i], Double.MAX_VALUE, mutableDist)) // only when found
4666
worstMetalSurround[i] = mutableDist.doubleValue();
7056
if (metalLayers[i] == null) continue;
7058
// get minimum area rule
7060
DRCTemplate minAreaRule = DRC.getMinValue(primaryMetalLayer[i], DRCTemplate.DRCRuleType.MINAREA);
7061
if (minAreaRule != null)
7062
minimumArea[i] = minAreaRule.getValue(0);
7065
metalSurroundX[i] = metalSurroundY[i] = maxDefArcWidth[i] = 0;
7066
for(int c=0; c<metalArcs[i].length; c++)
7068
maxDefArcWidth[i] = Math.max(maxDefArcWidth[i], metalArcs[i][c].getDefaultLambdaBaseWidth(ep));
7069
DRCTemplate rule = DRC.getSpacingRule(metalLayers[i][c], null, metalLayers[i][c], null, false, -1,
7070
metalArcs[i][c].getDefaultLambdaBaseWidth(ep), 50);
7073
metalSurroundX[i] = Math.max(metalSurroundX[i], rule.getValue(0));
7074
if (rule.getNumValues() > 1)
7076
metalSurroundY[i] = Math.max(metalSurroundY[i], rule.getValue(1));
7079
metalSurroundY[i] = metalSurroundX[i];
7082
if (DRC.getMaxSurround(metalLayers[i][c], Double.MAX_VALUE, mutableDist)) // only when found
7084
metalSurroundX[i] = Math.max(metalSurroundX[i], mutableDist.doubleValue());
7085
if (metalSurroundY[i] != mutableDist.doubleValue())
7086
metalSurroundY[i] = Math.max(metalSurroundY[i], mutableDist.doubleValue());
4668
7090
viaSurround = new double[numMetalLayers - 1];
7091
viaSize = new double[numMetalLayers - 1];
4669
7092
for (int i = 0; i < numMetalLayers - 1; i++)
4671
7094
Layer lay = viaLayers[i];
4672
7095
if (lay == null) continue;
4674
7097
double spacing = 2;
4675
double arcWidth = metalArcs[i].getDefaultLambdaBaseWidth(ep);
4676
DRCTemplate ruleSpacing = DRC.getSpacingRule(lay, null, lay, null, false, -1, arcWidth, 50);
7098
DRCTemplate ruleSpacing = DRC.getSpacingRule(lay, null, lay, null, false, -1, maxDefArcWidth[i], 50);
4677
7099
if (ruleSpacing != null) spacing = ruleSpacing.getValue(0);
4679
7101
// determine cut size
4901
7358
private RouteBatch[] makeListOfRoutes(Netlist netList, List<ArcInst> arcsToRoute, List<EPoint> linesInNonMahnattan)
7360
// normal condition: organize arcs by network
7361
Map<Network,List<ArcInst>> seen = new HashMap<Network,List<ArcInst>>();
7362
for (int b = 0; b < arcsToRoute.size(); b++)
7364
// get list of PortInsts that comprise this net
7365
ArcInst ai = arcsToRoute.get(b);
7366
Network net = netList.getNetwork(ai, 0);
7369
warn("Arc " + describe(ai) + " has no network!");
7372
List<ArcInst> arcsOnNet = seen.get(net);
7373
if (arcsOnNet == null) seen.put(net, arcsOnNet = new ArrayList<ArcInst>());
7375
// remove duplicates
7376
boolean exists = false;
7377
for(ArcInst oldAI : arcsOnNet)
7379
if (oldAI.getHeadPortInst().getPortProto() == ai.getHeadPortInst().getPortProto() &&
7380
oldAI.getHeadPortInst().getNodeInst() == ai.getHeadPortInst().getNodeInst() &&
7381
oldAI.getTailPortInst().getPortProto() == ai.getTailPortInst().getPortProto() &&
7382
oldAI.getTailPortInst().getNodeInst() == ai.getTailPortInst().getNodeInst()) { exists = true; break; }
7383
if (oldAI.getHeadPortInst().getPortProto() == ai.getTailPortInst().getPortProto() &&
7384
oldAI.getHeadPortInst().getNodeInst() == ai.getTailPortInst().getNodeInst() &&
7385
oldAI.getTailPortInst().getPortProto() == ai.getHeadPortInst().getPortProto() &&
7386
oldAI.getTailPortInst().getNodeInst() == ai.getHeadPortInst().getNodeInst()) { exists = true; break; }
7390
String warnMsg = "Arc from (" + TextUtils.formatDistance(ai.getHeadLocation().getX()) + "," +
7391
TextUtils.formatDistance(ai.getHeadLocation().getY()) + ") to (" + TextUtils.formatDistance(ai.getTailLocation().getX()) + "," +
7392
TextUtils.formatDistance(ai.getTailLocation().getY()) + ") is redundant";
7393
List<EPoint> linesToShow = new ArrayList<EPoint>();
7394
linesToShow.add(EPoint.fromLambda(ai.getHeadLocation().getX(), ai.getHeadLocation().getY()));
7395
linesToShow.add(EPoint.fromLambda(ai.getTailLocation().getX(), ai.getTailLocation().getY()));
7396
warn(warnMsg, netList.getCell(), linesToShow, null);
7403
// build a RoutesOnNetwork for every network
4903
7404
List<RoutesOnNetwork> allRoutes = new ArrayList<RoutesOnNetwork>();
4904
if (!DEBUGGRIDDING && RoutingDebug.isActive() && !RoutingDebug.isRewireNetworks())
7405
List<Network> allNets = new ArrayList<Network>();
7406
for(Network net : seen.keySet()) allNets.add(net);
7407
Collections.sort(allNets);
7408
for(Network net : allNets)
4906
// make a batch with just the first arc
4907
ArcInst ai = arcsToRoute.get(0);
4908
Network net = netList.getNetwork(ai, 0);
4909
7410
RoutesOnNetwork ron = new RoutesOnNetwork(net.getName());
4910
7411
allRoutes.add(ron);
4911
ron.unroutedArcs.add(ai);
4912
ron.addUnorderedPort(ai.getHeadPortInst());
4913
ron.addUnorderedPort(ai.getTailPortInst());
4914
ron.pairs.add(new SteinerTreePortPair(ai.getHeadPortInst(), ai.getTailPortInst()));
4917
// organize arcs by network
4918
Map<Network,List<ArcInst>> seen = new HashMap<Network,List<ArcInst>>();
4919
for (int b = 0; b < arcsToRoute.size(); b++)
7413
// make list of all ends in the batch
7414
List<ArcInst> arcsOnNet = seen.get(net);
7415
for (ArcInst ai : arcsOnNet)
4921
// get list of PortInsts that comprise this net
4922
ArcInst ai = arcsToRoute.get(b);
4923
Network net = netList.getNetwork(ai, 0);
4926
warn("Arc " + describe(ai) + " has no network!");
4929
List<ArcInst> arcsOnNet = seen.get(net);
4930
if (arcsOnNet == null) seen.put(net, arcsOnNet = new ArrayList<ArcInst>());
7417
ron.unroutedArcs.add(ai);
7418
if (ron.addUnorderedPort(ai.getHeadPortInst()))
7419
warn("Arc " + describe(ai) + " has an unconnectable end (on " + ai.getHeadPortInst().getNodeInst().describe(false) + ")");
7420
if (ron.addUnorderedPort(ai.getTailPortInst()))
7421
warn("Arc " + describe(ai) + " has an unconnectable end (on " + ai.getTailPortInst().getNodeInst().describe(false) + ")");
4934
// build a RoutesOnNetwork for every network
4935
List<Network> allNets = new ArrayList<Network>();
4936
for(Network net : seen.keySet()) allNets.add(net);
4937
Collections.sort(allNets);
4938
for(Network net : allNets)
7424
if (sogp.isSteinerDone())
4940
RoutesOnNetwork ron = new RoutesOnNetwork(net.getName());
4943
// make list of all ends in the batch
4944
List<ArcInst> arcsOnNet = seen.get(net);
4945
7426
for (ArcInst ai : arcsOnNet)
4947
ron.unroutedArcs.add(ai);
4948
ron.addUnorderedPort(ai.getHeadPortInst());
4949
ron.addUnorderedPort(ai.getTailPortInst());
4952
if (sogp.isSteinerDone())
4954
for (ArcInst ai : arcsOnNet)
4955
ron.pairs.add(new SteinerTreePortPair(ai.getHeadPortInst(), ai.getTailPortInst()));
7427
ron.pairs.add(new SteinerTreePortPair(ai.getHeadPortInst(), ai.getTailPortInst()));
7430
// see if this is a spine route
7431
if (prefs.enableSpineRouting && ron.setupSpineInfo())
4958
// see if this is a spine route
4959
if (prefs.enableSpineRouting && ron.setupSpineInfo())
4964
// a non-spine route
4965
List<SteinerTreePort> portList = new ArrayList<SteinerTreePort>();
4966
for(PortInst pi : ron.unorderedPorts) portList.add(new PortInstShadow(pi));
4967
SteinerTree st = new SteinerTree(portList);
4968
ron.pairs = st.getTreeBranches();
4969
if (ron.pairs == null)
7436
// a non-spine route
7437
List<SteinerTreePort> portList = new ArrayList<SteinerTreePort>();
7438
for(PortInst pi : ron.unorderedPorts) portList.add(new PortInstShadow(pi));
7439
SteinerTree st = new SteinerTree(portList);
7440
ron.pairs = st.getTreeBranches();
7441
if (ron.pairs == null)
7443
String errMsg = "Arcs in " + net.getName() + " do not make valid connection: deleted";
7445
List<EPoint> lineList = new ArrayList<EPoint>();
7446
for(ArcInst delAi : ron.unroutedArcs)
4971
String errMsg = "Arcs in " + net.getName() + " do not make valid connection: deleted";
4973
List<EPoint> lineList = new ArrayList<EPoint>();
4974
for(ArcInst delAi : ron.unroutedArcs)
4976
lineList.add(delAi.getHeadLocation());
4977
lineList.add(delAi.getTailLocation());
4979
errorLogger.logMessageWithLines(errMsg, null, lineList, cell, 0, true);
7448
lineList.add(delAi.getHeadLocation());
7449
lineList.add(delAi.getTailLocation());
7451
errorLogger.logMessageWithLines(errMsg, null, lineList, cell, 0, true);