connectivity.java

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

					{
						cutsOnLayer = new ArrayList<PolyBase>();
						allCutLayers.put(layer, cutsOnLayer);
					}
					cutsOnLayer.add(poly);
				} else
				{
					Rectangle2D box = poly.getBox();
					if (box != null) merge.addRectangle(layer, box); else
						merge.addPolygon(layer, poly);
				}
			}

			// save exports on pure-layer nodes for restoration later
			for(Iterator<Export> it = ni.getExports(); it.hasNext(); )
			{
				Export e = it.next();
				exportsToRestore.add(e);
			}
		}

		// throw all arcs into the new cell, too
		for(Iterator<ArcInst> aIt = oldCell.getArcs(); aIt.hasNext(); )
		{
			ArcInst ai = aIt.next();
			NodeInst end1 = newNodes.get(ai.getHeadPortInst().getNodeInst());
			NodeInst end2 = newNodes.get(ai.getTailPortInst().getNodeInst());
			if (end1 == null || end2 == null) continue;
			PortInst pi1 = end1.findPortInstFromProto(ai.getHeadPortInst().getPortProto());
			PortInst pi2 = end2.findPortInstFromProto(ai.getTailPortInst().getPortProto());
			Point2D headLocation = new Point2D.Double(0, 0);
			Point2D tailLocation = new Point2D.Double(0, 0);
			prevTrans.transform(ai.getHeadLocation(), headLocation);
			prevTrans.transform(ai.getTailLocation(), tailLocation);
			ArcInst.makeInstanceBase(ai.getProto(), ai.getLambdaBaseWidth(), pi1, pi2,
				headLocation, tailLocation, ai.getName());
		}
	}

	/**
	 * Method to determine if this is a "p-well" or "n-well" process.
	 * Examines the merge to see which well layers are found.
	 * @param merge the merged geometry.
	 */
	private void findMissingWells(PolyMerge merge)
	{
		boolean hasPWell = false, hasNWell = false, hasWell = false;

		for (Layer layer : merge.getKeySet())
		{
			Layer.Function fun = layer.getFunction();
			if (fun == Layer.Function.WELL) hasWell = true;
			if (fun == Layer.Function.WELLP) hasPWell = true;
			if (fun == Layer.Function.WELLN) hasNWell = true;
		}
		if (!hasPWell)
		{
			pWellProcess = true;
			System.out.println("Presuming a P-well process");
			return;
		}
		if (!hasNWell && !hasWell)
		{
			nWellProcess = true;
			System.out.println("Presuming an N-well process");
		}
	}

	/********************************************** WIRE EXTRACTION **********************************************/

	/**
	 * Method to extract wires from the merge.
	 * @param merge the merged geometry that remains (after contacts and transistors are extracted).
	 * @param originalMerge the original merge with all geometry.
	 * @param newCell the new Cell in which wires are placed.
	 * @return true on error.
	 */
	private boolean makeWires(PolyMerge merge, PolyMerge originalMerge, Cell newCell)
	{
		// make a list of polygons that could be turned into wires
		int totPolys = 0;
		Map<Layer,List<PolyBase>> geomToWire = new HashMap<Layer,List<PolyBase>>();
		for (Layer layer : merge.getKeySet())
		{
			Layer.Function fun = layer.getFunction();
			if (fun.isDiff() || fun.isPoly() || fun.isMetal())
			{
				List<PolyBase> polyList = getMergePolys(merge, layer);
				totPolys += polyList.size();
				geomToWire.put(layer, polyList);
			}
		}

		// examine each wire layer, looking for a skeletal structure that approximates it
		int soFar = 0;
		Set<Layer> allLayers = geomToWire.keySet();
		for (Layer layer : allLayers)
		{
			// examine the geometry on the layer
			List<PolyBase> polyList = geomToWire.get(layer);
			for(PolyBase poly : polyList)
			{
				Job.getUserInterface().setProgressValue(soFar * 100 / totPolys);
				soFar++;

				// figure out which arcproto to use here
				ArcProto ap = findArcProtoForPoly(layer, poly, originalMerge);
				if (ap == null) continue;

				// reduce the geometry to a skeleton of centerlines
				double minWidth = 1;
				if (ENFORCEMINIMUMSIZE) minWidth = scaleUp(ap.getDefaultLambdaBaseWidth());
				List<Centerline> lines = findCenterlines(poly, layer, minWidth, merge, originalMerge);

				// now realize the wires
				for(Centerline cl : lines)
				{
					Point2D loc1Unscaled = new Point2D.Double();
					PortInst pi1 = locatePortOnCenterline(cl, loc1Unscaled, layer, ap, true, newCell);
					Point2D loc2Unscaled = new Point2D.Double();
					PortInst pi2 = locatePortOnCenterline(cl, loc2Unscaled, layer, ap, false, newCell);
					Point2D loc1 = new Point2D.Double(scaleUp(loc1Unscaled.getX()), scaleUp(loc1Unscaled.getY()));
					Point2D loc2 = new Point2D.Double(scaleUp(loc2Unscaled.getX()), scaleUp(loc2Unscaled.getY()));

					// make sure the wire fits
					MutableBoolean headExtend = new MutableBoolean(true), tailExtend = new MutableBoolean(true);
					boolean fits = originalMerge.arcPolyFits(layer, loc1, loc2, cl.width, headExtend, tailExtend);
					if (DEBUGCENTERLINES) System.out.println("FIT="+fits+" "+cl);
					if (!fits)
					{
						// arc does not fit, try reducing width
						double wid = cl.width / SCALEFACTOR;
						Dimension2D alignment = Job.getUserInterface().getGridAlignment();
						long x = Math.round(wid / alignment.getWidth());
						double gridWid = x * alignment.getWidth();
						if (gridWid < wid)
						{
							// grid-aligning the width results in a smaller value...try it
							cl.width = scaleUp(gridWid);
							fits = originalMerge.arcPolyFits(layer, loc1, loc2, cl.width, headExtend, tailExtend);
							if (DEBUGCENTERLINES) System.out.println("   WID="+(cl.width/SCALEFACTOR)+" FIT="+fits);
						} else
						{
							// see if width can be reduced by a small amount and still fit
							cl.width--;
							fits = originalMerge.arcPolyFits(layer, loc1, loc2, cl.width, headExtend, tailExtend);
							if (DEBUGCENTERLINES) System.out.println("   WID="+(cl.width/SCALEFACTOR)+" FIT="+fits);
						}
					}
					if (!fits)
					{
						cl.width = 0;
						fits = originalMerge.arcPolyFits(layer, loc1, loc2, cl.width, headExtend, tailExtend);
						if (DEBUGCENTERLINES) System.out.println("   WID=0 FIT="+fits);
					}
					if (!fits) continue;

                    // create the wire
					ArcInst ai = realizeArc(ap, pi1, pi2, loc1Unscaled, loc2Unscaled, cl.width / SCALEFACTOR,
						!headExtend.booleanValue(), !tailExtend.booleanValue(), merge);
					if (ai == null)
					{
                        String msg = "  Failed to run arc " + ap.getName() + " from (" + loc1Unscaled.getX() + "," +
							loc1Unscaled.getY() + ") on node " + pi1.getNodeInst().describe(false) + " to (" +
							loc2Unscaled.getX() + "," + loc2Unscaled.getY() + ") on node " + pi2.getNodeInst().describe(false);
//                        System.out.println(msg);
//                        List<EPoint> pointList = new ArrayList<EPoint>();
//                        pointList.add(new EPoint(loc1Unscaled.getX(), loc1Unscaled.getY()));
//                        pointList.add(new EPoint(loc2Unscaled.getX(), loc2Unscaled.getY()));
//                        errorLogger.logError(msg, null, null, null, pointList, null, newCell, -1);
                        addErrorLog(newCell, msg, new EPoint(loc1Unscaled.getX(), loc1Unscaled.getY()),
                            new EPoint(loc2Unscaled.getX(), loc2Unscaled.getY()));
                        return true;
					}
				}
			}
		}

		// examine each wire layer, looking for a simple rectangle that covers it
		for(Layer layer : allLayers)
		{
			// examine the geometry on the layer
			List<PolyBase> polyList = getMergePolys(merge, layer);
			for(PolyBase poly : polyList)
			{
				Rectangle2D bounds = poly.getBounds2D();
				Poly rectPoly = new Poly(bounds);
				if (!originalMerge.contains(layer, rectPoly)) continue;

				// figure out which arc proto to use for the layer
				ArcProto ap = findArcProtoForPoly(layer, poly, originalMerge);
				if (ap == null) continue;

				// determine the endpoints of the arc
				Point2D loc1, loc2;
				double width = Math.min(bounds.getWidth(), bounds.getHeight());
				if (bounds.getWidth() > bounds.getHeight())
				{
					loc1 = new Point2D.Double((bounds.getMinX() + width/2) / SCALEFACTOR, bounds.getCenterY() / SCALEFACTOR);
					loc2 = new Point2D.Double((bounds.getMaxX() - width/2) / SCALEFACTOR, bounds.getCenterY() / SCALEFACTOR);
				} else
				{
					loc1 = new Point2D.Double(bounds.getCenterX() / SCALEFACTOR, (bounds.getMinY() + width/2) / SCALEFACTOR);
					loc2 = new Point2D.Double(bounds.getCenterX() / SCALEFACTOR, (bounds.getMaxY() - width/2) / SCALEFACTOR);
				}
				PortInst pi1 = wantConnectingNodeAt(loc1, ap, width / SCALEFACTOR, newCell);
				PortInst pi2 = wantConnectingNodeAt(loc2, ap, width / SCALEFACTOR, newCell);
				realizeArc(ap, pi1, pi2, loc1, loc2, width / SCALEFACTOR, false, false, merge);
			}
		}
		return false;
	}

	/**
	 * Method to figure out which ArcProto to use for a polygon on a layer.
	 * In the case of Active layers, it examines the well and select layers to figure out
	 * which arctive arc to use.
	 * @param layer the layer of the polygon.
	 * @param poly the polygon
	 * @param originalMerge the merged data for the cell
	 * @return the ArcProto to use (null if none can be found).
	 */
	private ArcProto findArcProtoForPoly(Layer layer, PolyBase poly, PolyMerge originalMerge)
	{
		Layer.Function fun = layer.getFunction();
		if (fun.isPoly() || fun.isMetal()) return arcsForLayer.get(layer);
		if (!fun.isDiff()) return null;

		// must further differentiate the active arcs...find implants
		Layer wellP = null, wellN = null, selectP = null, selectN = null;
		for(Layer l : originalMerge.getKeySet())
		{
			if (l.getFunction() == Layer.Function.WELLP) wellP = l;
			if (l.getFunction() == Layer.Function.WELLN) wellN = l;
			if (l.getFunction() == Layer.Function.IMPLANTP) selectP = l;
			if (l.getFunction() == Layer.Function.IMPLANTN) selectN = l;
		}

		ArcProto.Function neededFunction = null;
		if (originalMerge.intersects(selectP, poly))
		{
			// Active in P-Select could either be a P-Active arc or a P-Well arc
			neededFunction = ArcProto.Function.DIFFP;
			if (wellP == null)
			{
				// a P-Well process: just look for the absense of N-Well surround
				if (!originalMerge.intersects(wellN, poly)) neededFunction = ArcProto.Function.DIFFS;
			} else
			{
				if (originalMerge.intersects(wellP, poly)) neededFunction = ArcProto.Function.DIFFS;
			}
		} else if (originalMerge.intersects(selectN, poly))
		{
			// Active in N-Select could either be a N-Active arc or a N-Well arc
			neededFunction = ArcProto.Function.DIFFN;
			if (wellN == null)
			{
				// a N-Well process: just look for the absense of P-Well surround
				if (!originalMerge.intersects(wellP, poly)) neededFunction = ArcProto.Function.DIFFW;
			} else
			{
				if (originalMerge.intersects(wellN, poly)) neededFunction = ArcProto.Function.DIFFW;
			}
		}

		// now find the arc with the desired function
		for(Iterator<ArcProto> aIt = tech.getArcs(); aIt.hasNext(); )
		{
			ArcProto ap = aIt.next();
			if (ap.getFunction() == neededFunction) return ap;
		}
		return null;
	}

	/**
	 * Method to locate a port on a node at a specific point with a specific connectivity.
	 * @param pt the center location of the desired node.
	 * @param ap the type of the arc that must connect.
	 * @param size the size of the node (if it must be created).
	 * @param newCell the cell in which to locate or place the node.
	 * @return the port on the node that is at the proper point.
	 * If there is none there, a node is created.
	 */
	private PortInst wantConnectingNodeAt(Point2D pt, ArcProto ap, double size, Cell newCell)
	{
		Rectangle2D bounds = new Rectangle2D.Double(pt.getX(), pt.getY(), 0, 0);
		for(Iterator<RTBounds> it = newCell.searchIterator(bounds); it.hasNext(); )
		{
			RTBounds geom = it.next();
			if (!(geom instanceof NodeInst)) continue;
			NodeInst ni = (NodeInst)geom;
			for(Iterator<PortInst> pIt = ni.getPortInsts(); pIt.hasNext(); )
			{
				PortInst pi = pIt.next();
				PortProto pp = pi.getPortProto();
				if (!pp.connectsTo(ap)) continue;
				Poly poly = pi.getPoly();
				if (poly.contains(pt)) return pi;
			}
		}
		NodeInst ni = createNode(ap.findPinProto(), pt, size, size, null, newCell);
		return ni.getOnlyPortInst();
	}

	/**
	 * Method to locate a node at a specific point with a specific type.
	 * @param pt the center location of the desired node.
	 * @param pin the type of the desired node.
	 * @param size the size of the node (if it must be created).
	 * @param newCell the cell in which to locate or place the node.
	 * @return a node of that type at that location.
	 * If there is none there, it is created.
	 */
	private NodeInst wantNodeAt(Point2D pt, NodeProto pin, double size, Cell newCell)
	{
		Rectangle2D bounds = new Rectangle2D.Double(pt.getX(), pt.getY(), 0, 0);
		for(Iterator<RTBounds> it = newCell.searchIterator(bounds); it.hasNext(); )
		{
			RTBounds geom = it.next();
			if (!(geom instanceof NodeInst)) continue;
			NodeInst ni = (NodeInst)geom;
			if (ni.getProto() != pin) continue;
			if (ni.getAnchorCenter().equals(pt)) return ni;
		}
		NodeInst ni = createNode(pin, pt, size, size, null, newCell);
		return ni;
	}

	/**
	 * Method to find the PortInst on a NodeInst that connects to a given PortProto and is closest to a given point.
	 * Because some primitive nodes (transistors) may have multiple ports that connect to each other
	 * (the poly ports) and because the system returns only one of those ports when describing the topology of
	 * a piece of geometry, it is necessary to find the closest port.
	 * @param ni the primitive NodeInst being examined.
	 * @param pp the primitive port on that node which defines the connection to the node.
	 * @param pt a point close to the desired port.
	 * @return the PortInst on the node that is electrically connected to the given primitive port, and closest to the point.
	 */
	private PortInst findPortInstClosestToPoly(NodeInst ni, PrimitivePort pp, Point2D pt)
	{
		PortInst touchingPi = ni.findPortInstFromProto(pp);
		PrimitiveNode pnp = (PrimitiveNode)ni.getProto();
		Poly touchingPoly = touchingPi.getPoly();
		double bestDist = pt.distance(new Point2D.Double(touchingPoly.getCenterX(), touchingPoly.getCenterY()));
		for(Iterator<PortProto> pIt = pnp.getPorts(); pIt.hasNext(); )
		{
			PrimitivePort prP = (PrimitivePort)pIt.next();
			if (prP.getTopology() == pp.getTopology())
			{
				PortInst testPi = ni.findPortInstFromProto(prP);
				Poly testPoly = testPi.getPoly();
				double dist = pt.distance(new Point2D.Double(testPoly.getCenterX(), testPoly.getCenterY()));
				if (dist < bestDist)
				{
					bestDist = dist;
					touchingPi = testPi;