autostitch.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

		Map<ArcProto,Layer> arcLayers, PolyMerge stayInside,
		Topology top, Rectangle2D limitBound, ArcProto preferredArc)
	{
		// if both nodes are being checked, examine them only once
		if (nodeMark.contains(oNi) && oNi.getNodeIndex() <= ni.getNodeIndex()) return;

		// now look at every layer in this node
		Rectangle2D oBounds = oNi.getBounds();
		if (ni.isCellInstance())
		{
			// complex node instance: look at all ports
			if (USEQTREE)
			{
				// find ports near this bound
				ObjectQTree oqt = nodePortBounds.get(ni);
				Rectangle2D biggerBounds = new Rectangle2D.Double(oBounds.getMinX()-1, oBounds.getMinY()-1, oBounds.getWidth()+2, oBounds.getHeight()+2);
				Set set = oqt.find(biggerBounds);
				if (set != null)
				{
					for (Object obj : set)
					{
						PortInst pi = (PortInst)obj;
						PortProto pp = pi.getPortProto();

						// find the primitive node at the bottom of this port
						AffineTransform trans = ni.rotateOut();
						NodeInst rNi = ni;
						PortProto rPp = pp;
						while (rNi.isCellInstance())
						{
							AffineTransform temp = rNi.translateOut();
							temp.preConcatenate(trans);
							Export e = (Export)rPp;
							rNi = e.getOriginalPort().getNodeInst();
							rPp = e.getOriginalPort().getPortProto();

							trans = rNi.rotateOut();
							trans.preConcatenate(temp);
						}

						// determine the smallest layer for all possible arcs
						ArcProto [] connections = pp.getBasePort().getConnections();
						for(int i=0; i<connections.length; i++)
						{
							findSmallestLayer(connections[i], arcLayers);
						}

						// look at all polygons on this nodeinst
						boolean usePortPoly = false;
						Poly [] nodePolys = shapeOfNode(rNi);
						int tot = nodePolys.length;
						if (tot == 0 || rNi.getProto() == Generic.tech().simProbeNode)
						{
							usePortPoly = true;
							tot = 1;
						}
						Netlist subNetlist = rNi.getParent().getUserNetlist();
						for(int j=0; j<tot; j++)
						{
							Layer layer = null;
							Poly poly = null;
							if (usePortPoly)
							{
								poly = ni.getShapeOfPort(pp);
								layer = poly.getLayer();
							} else
							{
								poly = nodePolys[j];

								// only want electrically connected polygons
								if (poly.getPort() == null) continue;

								// only want polygons on correct part of this nodeinst
								if (!subNetlist.portsConnected(rNi, rPp, poly.getPort())) continue;

								// transformed polygon
								poly.transform(trans);

								// if the polygon layer is pseudo, substitute real layer
								layer = poly.getLayer();
								if (layer != null) layer = layer.getNonPseudoLayer();
							}

							// see which arc can make the connection
							boolean connected = false;
							for(int pass=0; pass<2; pass++)
							{
								for(int i=0; i<connections.length; i++)
								{
									ArcProto ap = connections[i];
									if (pass == 0)
									{
										if (ap != preferredArc) continue;
									} else
									{
										if (ap == preferredArc) continue;

										// arc must be in the same technology
										if (ap.getTechnology() != rNi.getProto().getTechnology()) continue;
									}

									// this polygon must be the smallest arc layer
									if (!usePortPoly)
									{
										Layer oLayer = arcLayers.get(ap);
										if (!layer.getTechnology().sameLayer(oLayer, layer)) continue;
									}

									// pass it on to the next test
									connected = testPoly(ni, pp, ap, poly, oNi, top, nodeBounds, nodePortBounds, arcLayers, stayInside, limitBound);
									if (connected) break;
								}
								if (connected) break;
							}
							if (connected) break;
						}
					}
				}
			} else
			{
				Rectangle2D [] boundArray = nodeBounds.get(ni);
				int bbp = 0;
				for(Iterator<PortProto> pIt = ni.getProto().getPorts(); pIt.hasNext(); )
				{
					PortProto pp = pIt.next();

					// first do a bounding box check
					if (boundArray != null)
					{
						Rectangle2D bounds = boundArray[bbp++];
						if (bounds.getMinX() > oBounds.getMaxX() || bounds.getMaxX() < oBounds.getMinX() ||
							bounds.getMinY() > oBounds.getMaxY() || bounds.getMaxY() < oBounds.getMinY()) continue;
					}

					// find the primitive node at the bottom of this port
					AffineTransform trans = ni.rotateOut();
					NodeInst rNi = ni;
					PortProto rPp = pp;
					while (rNi.isCellInstance())
					{
						AffineTransform temp = rNi.translateOut();
						temp.preConcatenate(trans);
						Export e = (Export)rPp;
						rNi = e.getOriginalPort().getNodeInst();
						rPp = e.getOriginalPort().getPortProto();

						trans = rNi.rotateOut();
						trans.preConcatenate(temp);
					}

					// determine the smallest layer for all possible arcs
					ArcProto [] connections = pp.getBasePort().getConnections();
					for(int i=0; i<connections.length; i++)
					{
						findSmallestLayer(connections[i], arcLayers);
					}

					// look at all polygons on this nodeinst
					boolean usePortPoly = false;
					Poly [] nodePolys = shapeOfNode(rNi);
					int tot = nodePolys.length;
					if (tot == 0 || rNi.getProto() == Generic.tech().simProbeNode)
					{
						usePortPoly = true;
						tot = 1;
					}
					Netlist subNetlist = rNi.getParent().getUserNetlist();
					for(int j=0; j<tot; j++)
					{
						Layer layer = null;
						Poly poly = null;
						if (usePortPoly)
						{
							poly = ni.getShapeOfPort(pp);
							layer = poly.getLayer();
						} else
						{
							poly = nodePolys[j];

							// only want electrically connected polygons
							if (poly.getPort() == null) continue;

							// only want polygons on correct part of this nodeinst
							if (!subNetlist.portsConnected(rNi, rPp, poly.getPort())) continue;

							// transformed polygon
							poly.transform(trans);

							// if the polygon layer is pseudo, substitute real layer
							layer = poly.getLayer();
							if (layer != null) layer = layer.getNonPseudoLayer();
						}

						// see which arc can make the connection
						boolean connected = false;
						for(int pass=0; pass<2; pass++)
						{
							for(int i=0; i<connections.length; i++)
							{
								ArcProto ap = connections[i];
								if (pass == 0)
								{
									if (ap != preferredArc) continue;
								} else
								{
									if (ap == preferredArc) continue;

									// arc must be in the same technology
									if (ap.getTechnology() != rNi.getProto().getTechnology()) continue;
								}

								// this polygon must be the smallest arc layer
								if (!usePortPoly)
								{
									Layer oLayer = arcLayers.get(ap);
									if (!layer.getTechnology().sameLayer(oLayer, layer)) continue;
								}

								// pass it on to the next test
								connected = testPoly(ni, pp, ap, poly, oNi, top, nodeBounds, nodePortBounds, arcLayers, stayInside, limitBound);
								if (connected) break;
							}
							if (connected) break;
						}
						if (connected) break;
					}
				}
			}
		} else
		{
			// primitive node: check its layers
			AffineTransform trans = ni.rotateOut();

			// save information about the other node
			double oX = oNi.getAnchorCenterX();
			double oY = oNi.getAnchorCenterY();

			// look at all polygons on this nodeinst
			boolean usePortPoly = false;
			Poly [] polys = shapeOfNode(ni);
			int tot = polys.length;
			if (tot == 0 || ni.getProto() == Generic.tech().simProbeNode)
			{
				usePortPoly = true;
				tot = 1;
			}
			for(int j=0; j<tot; j++)
			{
				PortProto rPp = null;
				Poly polyPtr = null;
				if (usePortPoly)
				{
					// search all ports for the closest
					PortProto bestPp = null;
					double bestDist = 0;
					for(Iterator<PortProto> pIt = ni.getProto().getPorts(); pIt.hasNext(); )
					{
						PortProto tPp = pIt.next();

						// compute best distance to the other node
						Poly portPoly = ni.getShapeOfPort(tPp);
						double x = portPoly.getCenterX();
						double y = portPoly.getCenterY();
						double dist = Math.abs(x-oX) + Math.abs(y-oY);
						if (bestPp == null)
						{
							bestDist = dist;
							bestPp = tPp;
						}
						if (dist > bestDist) continue;
						bestPp = tPp;   bestDist = dist;
					}
					if (bestPp == null) continue;
					rPp = bestPp;
					polyPtr = ni.getShapeOfPort(rPp);
				} else
				{
					polyPtr = polys[j];

					// only want electrically connected polygons
					if (polyPtr.getPort() == null) continue;

					// search all ports for the closest connected to this layer
					PortProto bestPp = null;
					double bestDist = 0;
					for(Iterator<PortProto> pIt = ni.getProto().getPorts(); pIt.hasNext(); )
					{
						PortProto tPp = pIt.next();
						if (!top.portsConnected(ni, tPp, polyPtr.getPort())) continue;

						// compute best distance to the other node
						Poly portPoly = ni.getShapeOfPort(tPp);
						double x = portPoly.getCenterX();
						double y = portPoly.getCenterY();
						double dist = Math.abs(x-oX) + Math.abs(y-oY);
						if (bestPp == null) bestDist = dist;
						if (dist > bestDist) continue;
						bestPp = tPp;   bestDist = dist;
					}
					if (bestPp == null) continue;
					rPp = bestPp;

					// transformed the polygon
					polyPtr.transform(trans);
				}

				// if the polygon layer is pseudo, substitute real layer
				Layer layer = polyPtr.getLayer();
				if (layer != null) layer = layer.getNonPseudoLayer();

				// stop now if already an arc on this port to other node
				boolean found = false;
				for(Iterator<Connection> cIt = ni.getConnections(); cIt.hasNext(); )
				{
					Connection con = cIt.next();
					PortInst pi = con.getPortInst();
					if (!top.portsConnected(ni, rPp, pi.getPortProto())) continue;
					if (con.getArc().getHeadPortInst().getNodeInst() == oNi ||
						con.getArc().getTailPortInst().getNodeInst() == oNi) { found = true;   break; }
				}
				if (found) continue;

				// see if an arc is possible
				boolean connected = false;
				ArcProto [] connections = rPp.getBasePort().getConnections();
				for(int pass=0; pass<2; pass++)
				{
					for(int i=0; i<connections.length; i++)
					{
						ArcProto ap = connections[i];
						if (pass == 0)
						{
							if (ap != preferredArc) continue;
						} else
						{
							if (ap == preferredArc) continue;
						}

						// arc must be in the same technology
						if (ap.getTechnology() != ni.getProto().getTechnology()) break;

						// this polygon must be the smallest arc layer
						findSmallestLayer(ap, arcLayers);
						if (!usePortPoly)
						{
							Layer oLayer = arcLayers.get(ap);
							if (!ap.getTechnology().sameLayer(oLayer, layer)) continue;
						}

						// pass it on to the next test
						connected = testPoly(ni, rPp, ap, polyPtr, oNi, top, nodeBounds, nodePortBounds, arcLayers, stayInside, limitBound);
						if (connected) break;
					}
					if (connected) break;
				}
				if (connected) break;
			}
		}
	}

	/**
	 * Method to compare two arcs and see if they should be connected.
	 * @param ai1 the first ArcInst to compare.
	 * @param ai2 the second ArcInst to compare.
	 * @param stayInside is the area in which to route (null to route arbitrarily).
	 * @param top the Netlist information for the Cell with the arcs.
	 */
	private void compareTwoArcs(ArcInst ai1, ArcInst ai2, PolyMerge stayInside, Topology top)
	{
		// if connected, stop now
		if (ai1.getProto() != ai2.getProto()) return;
		Network net1 = top.getArcNetwork(ai1);
		Network net2 = top.getArcNetwork(ai2);
		if (net1 == net2) return;