autostitch.java

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

		// look at all polygons on the first arcinst
		Poly [] polys1 = ai1.getProto().getTechnology().getShapeOfArc(ai1);
		int tot1 = polys1.length;
		Poly [] polys2 = ai2.getProto().getTechnology().getShapeOfArc(ai2);
		int tot2 = polys2.length;
		for(int i1=0; i1<tot1; i1++)
		{
			Poly poly1 = polys1[i1];
			Layer layer1 = poly1.getLayer();
			Layer.Function fun = layer1.getFunction();
			if (!fun.isMetal() && !fun.isDiff() && !fun.isPoly()) continue;
			Rectangle2D bounds1 = poly1.getBounds2D();

			// compare them against all of the polygons in the second arcinst
			for(int i2=0; i2<tot2; i2++)
			{
				Poly poly2 = polys2[i2];
				if (layer1 != poly2.getLayer()) continue;

				// two polygons on the same layer...are they even near each other?
				Rectangle2D bounds2 = poly2.getBounds2D();
				if (!bounds1.intersects(bounds2)) continue;

				// do precise test for touching

				// connect their closest ends
				Rectangle2D intersection = new Rectangle2D.Double();
				Rectangle2D.intersect(bounds1, bounds2, intersection);
				double x = intersection.getCenterX();
				double y = intersection.getCenterY();

				// run the wire
				connectObjects(ai1, net1, ai2, net2, ai1.getParent(), new Point2D.Double(x,y), stayInside, top);
				return;
			}
		}
	}

	/**
	 * Method to compare a node instance and an arc to see if they touch and should be connected.
	 * @param ni the NodeInst to compare.
	 * @param ai the 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 node and arc.
	 * @param nodePortBounds quad-tree bounds information for all nodes in the Cell.
	 */
	private void compareNodeInstWithArc(NodeInst ni, ArcInst ai, PolyMerge stayInside, Topology top,
		Map<NodeInst,ObjectQTree> nodePortBounds)
	{
		// sorry, this method demands the USEQTREE be set
		if (!USEQTREE) return;

		Network arcNet = top.getArcNetwork(ai);

		// find all ports on the instance that are near the arc
		ObjectQTree oqt = nodePortBounds.get(ni);
		Rectangle2D aBounds = ai.getBounds();
		Rectangle2D biggerBounds = new Rectangle2D.Double(aBounds.getMinX()-1, aBounds.getMinY()-1, aBounds.getWidth()+2, aBounds.getHeight()+2);
		Set set = oqt.find(biggerBounds);
		if (set == null || set.size() == 0) return;

		// look at all polygons on the arcinst
		Poly [] arcPolys = ai.getProto().getTechnology().getShapeOfArc(ai);
		int aTot = arcPolys.length;
		for(int i=0; i<aTot; i++)
		{
			Poly arcPoly = arcPolys[i];
			Layer arcLayer = arcPoly.getLayer();
			Layer.Function arcLayerFun = arcLayer.getFunction();
			if (!arcLayerFun.isMetal() && !arcLayerFun.isDiff() && !arcLayerFun.isPoly()) continue;

			// find ports near the arc
			for (Object obj : set)
			{
				PortInst pi = (PortInst)obj;

				// ignore if already connected
				Network portNet = top.getPortNetwork(pi);
				if (portNet == arcNet) continue;

				// find the primitive node at the bottom of the port
				AffineTransform trans = ni.rotateOut();
				NodeInst rNi = ni;
				PortProto rPp = pi.getPortProto();
				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);
				}

				// see if anything on the base node touches the arc
				Poly [] polys = shapeOfNode(rNi);
				int tot = polys.length;
				for(int j=0; j<tot; j++)
				{
					Poly baseNodePoly = polys[j];
					Layer nodeLayer = baseNodePoly.getLayer();
					if (nodeLayer == null) continue;
					nodeLayer = nodeLayer.getNonPseudoLayer();
					if (nodeLayer.getFunction() != arcLayerFun) continue;
					baseNodePoly.transform(trans);
					double polyDist = arcPoly.separation(baseNodePoly);
					if (polyDist >= DBMath.getEpsilon()) continue;

					// arc touches the port: connect them
					Poly portPoly = pi.getPoly();
					double portCX = portPoly.getCenterX();
					double portCY = portPoly.getCenterY();

					Rectangle2D arcBounds = arcPoly.getBounds2D();
					double aCX = arcBounds.getCenterX();
					double aCY = arcBounds.getCenterY();
					Point2D bend1 = new Point2D.Double(portCX, aCY);
					Point2D bend2 = new Point2D.Double(aCX, portCY);
					if (stayInside != null)
					{
						if (!stayInside.contains(arcLayer, bend1)) bend1 = bend2;
					} else
					{
						if (!arcPoly.contains(bend1)) bend1 = bend2;
					}
					connectObjects(ai, arcNet, pi, portNet, ai.getParent(), bend1, stayInside, top);
					return;
				}
			}
		}
	}

	/**
	 * Method to compare a primitive node and an arc to see if they touch and should be connected.
	 * @param ni the NodeInst to compare.
	 * @param ai the 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 node and arc.
	 */
	private void compareNodePrimWithArc(NodeInst ni, ArcInst ai, PolyMerge stayInside, Topology top)
	{
		Network arcNet = top.getArcNetwork(ai);

		// gather information about the node
		Poly [] nodePolys = shapeOfNode(ni);
		int nTot = nodePolys.length;
		AffineTransform trans = ni.rotateOut();

		// look at all polygons on the arcinst
		Poly [] arcPolys = ai.getProto().getTechnology().getShapeOfArc(ai);
		int aTot = arcPolys.length;
		for(int i=0; i<aTot; i++)
		{
			Poly arcPoly = arcPolys[i];
			Layer arcLayer = arcPoly.getLayer();
			Layer.Function arcLayerFun = arcLayer.getFunction();
			if (!arcLayerFun.isMetal() && !arcLayerFun.isDiff() && !arcLayerFun.isPoly()) continue;
			Rectangle2D arcBounds = arcPoly.getBounds2D();
			double aCX = arcBounds.getCenterX();
			double aCY = arcBounds.getCenterY();

			// compare them against all of the polygons in the node
			for(int j=0; j<nTot; j++)
			{
				Poly nodePoly = nodePolys[j];
				nodePoly.transform(trans);

				// they must be on the same layer and touch
				Layer nodeLayer = nodePoly.getLayer();
				if (nodeLayer != null) nodeLayer = nodeLayer.getNonPseudoLayer();
				if (nodeLayer.getFunction() != arcLayerFun) continue;
				double polyDist = arcPoly.separation(nodePoly);
				if (polyDist >= DBMath.getEpsilon()) continue;

				// only want electrically connected polygons
				if (nodePoly.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, nodePoly.getPort())) continue;

					// compute best distance to the other node
					Poly portPoly = ni.getShapeOfPort(tPp);
					double portCX = portPoly.getCenterX();
					double portCY = portPoly.getCenterY();
					double dist = Math.abs(portCX-aCX) + Math.abs(portCY-aCY);
					if (bestPp == null) bestDist = dist;
					if (dist > bestDist) continue;
					bestPp = tPp;   bestDist = dist;
				}
				if (bestPp == null) continue;

				// run the wire
				PortInst pi = ni.findPortInstFromProto(bestPp);
				Poly portPoly = ni.getShapeOfPort(bestPp);
				double portCX = portPoly.getCenterX();
				double portCY = portPoly.getCenterY();
				Network nodeNet = top.getPortNetwork(pi);
				if (arcNet == nodeNet) continue;
				Point2D bend1 = new Point2D.Double(portCX, aCY);
				Point2D bend2 = new Point2D.Double(aCX, portCY);
				if (stayInside != null)
				{
					if (!stayInside.contains(arcLayer, bend1)) bend1 = bend2;
				} else
				{
					if (!arcPoly.contains(bend1)) bend1 = bend2;
				}
				connectObjects(ai, arcNet, pi, nodeNet, ai.getParent(), bend1, stayInside, top);
				return;
			}
		}
	}

	/**
	 * Method to connect two nodes if they touch.
	 * @param ni the first node to test.
	 * @param pp the port on the first node to test.
	 * @param ap the arcproto to use when connecting the nodes.
	 * @param poly the polygon on the first node to test.
	 * @param oNi the second node to test.
	 * @param top network information for the cell with the nodes.
	 * @param nodeBounds bounds information for all nodes in the Cell (when not using quad-trees).
	 * @param nodePortBounds quad-tree bounds information for all nodes in the Cell.
	 * @param arcLayers a map from ArcProtos to Layers.
	 * @param stayInside is the area in which to route (null to route arbitrarily).
	 * @param limitBound if not null, only consider connections that occur in this area.
	 * @return the number of connections made (0 if none).
	 */
	private boolean testPoly(NodeInst ni, PortProto pp, ArcProto ap, Poly poly, NodeInst oNi, Topology top,
		Map<NodeInst, Rectangle2D[]> nodeBounds, Map<NodeInst, ObjectQTree> nodePortBounds,
		Map<ArcProto,Layer> arcLayers, PolyMerge stayInside, Rectangle2D limitBound)
	{
		// get network associated with the node/port
		PortInst pi = ni.findPortInstFromProto(pp);
		Network net = top.getNodeNetwork(ni, pp);

		// now look at every layer in this node
		if (oNi.isCellInstance())
		{
			// complex cell: look at all exports
			Rectangle2D bounds = poly.getBounds2D();

			if (USEQTREE)
			{
				// find ports near this bound
				ObjectQTree oqt = nodePortBounds.get(oNi);
				Rectangle2D biggerBounds = new Rectangle2D.Double(bounds.getMinX()-1, bounds.getMinY()-1, bounds.getWidth()+2, bounds.getHeight()+2);
				Set set = oqt.find(biggerBounds);
				if (set != null)
				{
					for (Object obj : set)
					{
						PortInst oPi = (PortInst)obj;
						PortProto mPp = oPi.getPortProto();

						// port must be able to connect to the arc
						if (!mPp.getBasePort().connectsTo(ap)) continue;

						// do not stitch where there is already an electrical connection
						Network oNet = top.getPortNetwork(oNi.findPortInstFromProto(mPp));
						if (net != null && oNet == net) continue;

						// do not stitch if there is already an arc connecting these two ports
						boolean ignore = false;
						for (Iterator<Connection> piit = oPi.getConnections(); piit.hasNext(); )
						{
							Connection conn = piit.next();
							ArcInst ai = conn.getArc();
							if (ai.getHeadPortInst() == pi) ignore = true;
							if (ai.getTailPortInst() == pi) ignore = true;
						}
						if (ignore) continue;

						// find the primitive node at the bottom of this port
						AffineTransform trans = oNi.rotateOut();
						NodeInst rNi = oNi;
						PortProto rPp = mPp;
						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);
						}

						// see how much geometry is on this node
						Poly [] polys = shapeOfNode(rNi);
						int tot = polys.length;
						if (tot == 0)
						{
							// not a geometric primitive: look for ports that touch
							Poly oPoly = oNi.getShapeOfPort(mPp);
							if (comparePoly(oNi, mPp, oPoly, oNet, ni, pp, poly, net, ap, stayInside, top, limitBound))
								return true;
						} else
						{
							// a geometric primitive: look for ports on layers that touch
							Netlist subNetlist = rNi.getParent().getUserNetlist();
							for(int j=0; j<tot; j++)
							{
								Poly oPoly = polys[j];

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

								// only want polygons connected to correct part of nodeinst
								if (!subNetlist.portsConnected(rNi, rPp, oPoly.getPort())) continue;

								// if the polygon layer is pseudo, substitute real layer
								if (ni.getProto() != Generic.tech().simProbeNode)
								{
									Layer oLayer = oPoly.getLayer();
									if (oLayer != null) oLayer = oLayer.getNonPseudoLayer();
									Layer apLayer = arcLayers.get(ap);
									if (!oLayer.getTechnology().sameLayer(oLayer, apLayer)) continue;
								}

								// transform the polygon and pass it on to the next test
								oPoly.transform(trans);
								if (comparePoly(oNi, mPp, oPoly, oNet, ni, pp, poly, net, ap, stayInside, top, limitBound))
									return true;
							}
						}
					}
				}
			} else
			{
				// NOT USING QTREE
				Rectangle2D [] boundArray = nodeBounds.get(oNi);
				int bbp = 0;
				for(Iterator<PortProto> it = oNi.getProto().getPorts(); it.hasNext(); )
				{
					PortProto mPp = it.next();

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

					// port must be able to connect to the arc
					if (!mPp.getBasePort().connectsTo(ap)) continue;

					// do not stitch where there is already an electrical connection
					Network oNet = top.getPortNetwork(oNi.findPortInstFromProto(mPp));
					if (net != null && oNet == net) continue;

					// do not stitch if there is already an arc connecting these two ports
					PortInst oPi = oNi.findPortInstFromProto(mPp);
					boolean ignore = false;
					for (Iterator<Connection> piit = oPi.getConnections(); piit.hasNext(); )
					{
						Connection conn = piit.next();
						ArcInst ai = conn.getArc();
						if (ai.getHeadPortInst() == pi) ignore = true;
						if (ai.getTailPortInst() == pi) ignore = true;
					}
					if (ignore) continue;

					// find the primitive node at the bottom of this port
					AffineTransform trans = oNi.rotateOut();
					NodeInst rNi = oNi;