connectivity.java

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

		for (Layer layer : layers)
		{
			// compute the possible via nodes that this layer could become
			List<PossibleVia> possibleVias = findPossibleVias(layer);

			// make a list of all necessary layers
			Set<Layer> layersToExamine = new HashSet<Layer>();
			for(PossibleVia pv : possibleVias)
			{
				for(int i=0; i<pv.layers.length; i++)
					layersToExamine.add(pv.layers[i]);
			}

			// get all of the geometry on the cut/via layer
			List<PolyBase> cutList = allCutLayers.get(layer);

			RTNode root = null;
			if (Extract.isApproximateCuts())
			{
				root = RTNode.makeTopLevel();
				for(PolyBase cut : cutList)
					root = RTNode.linkGeom(null, root, new CutBound(cut));
			}

			// the new way to extract vias
			List<PolyBase> cutsNotExtracted = new ArrayList<PolyBase>();
			while (cutList.size() > 0)
			{
				PolyBase cut = cutList.get(0);

				soFar++;
				if ((soFar % 100) == 0) Job.getUserInterface().setProgressValue(soFar * 100 / totalCuts);

				// figure out which of the layers is present at this cut point
				Rectangle2D cutBox = cut.getBox();
				if (cutBox == null)
				{
					cutBox = cut.getBounds2D();
                    double centerX = cutBox.getCenterX()/SCALEFACTOR;
                    double centerY = cutBox.getCenterY()/SCALEFACTOR;
                    String msg = "Cannot extract nonManhattan contact cut at (" + (centerX) + "," + (centerY) + ")";
                    addErrorLog(newCell, msg, new EPoint(centerX, centerY));
                    cutList.remove(cut);
					cutsNotExtracted.add(cut);
					continue;
				}
				Point2D ctr = new Point2D.Double(cutBox.getCenterX(), cutBox.getCenterY());
				Set<Layer> layersPresent = new HashSet<Layer>();
				for(Layer l : layersToExamine)
				{
					boolean layerAtPoint = originalMerge.contains(l, ctr);
					if (layerAtPoint) layersPresent.add(geometricLayer(l));
				}
				boolean ignorePWell = false, ignoreNWell = false;
				if (pWellProcess)
				{
					// P-Well process (P-well is presumed where there is no N-Well)
					boolean foundNWell = false;
					for(Layer l : layersPresent)
					{
						if (l.getFunction() == Layer.Function.WELLN) { foundNWell = true;   break; }
					}
					if (!foundNWell) ignorePWell = true;
				}
				if (nWellProcess)
				{
					// N-Well process (N-well is presumed where there is no P-Well)
					boolean foundPWell = false;
					for(Layer l : layersPresent)
					{
						if (l.getFunction() == Layer.Function.WELLP) { foundPWell = true;   break; }
					}
					if (!foundPWell) ignoreNWell = true;
				}

				boolean foundCut = false;
				String reason = null;
				for(PossibleVia pv : possibleVias)
				{
					// quick test to see if this via could possibly exist
					boolean someLayersMissing = false;
					for(int i=0; i<pv.layers.length; i++)
					{
						if (!layersPresent.contains(pv.layers[i]))
						{
							if (ignorePWell && pv.layers[i].getFunction() == Layer.Function.WELLP) continue;
							if (ignoreNWell && pv.layers[i].getFunction() == Layer.Function.WELLN) continue;
							someLayersMissing = true;
							break;
						}
					}
					if (someLayersMissing) continue;

					// if selected, look for larger collection of cuts and place larger multi-cut contact
					double trueWidth = pv.minWidth;
					double trueHeight = pv.minHeight;
					if (pv.rotation == 90 || pv.rotation == 270)
					{
						trueWidth = pv.minHeight;
						trueHeight = pv.minWidth;
					}

					// see if this is an active/poly layer (in which case, there can be no poly/active in the area)
					boolean activeCut = false;
					boolean polyCut = false;
					NodeLayer [] primLayers = pv.pNp.getLayers();
					for(int i=0; i<primLayers.length; i++)
					{
						if (primLayers[i].getLayer().getFunction().isDiff()) activeCut = true;
						if (primLayers[i].getLayer().getFunction().isPoly()) polyCut = true;
					}
					if (activeCut && polyCut) activeCut = polyCut = false;

					Layer badLayer = null;
                    // Try AppriximateCuts first
                    if (Extract.isApproximateCuts() && pv.cutNodeLayer.getRepresentation() == Technology.NodeLayer.MULTICUTBOX)
					{
						// look for other cuts in the vicinity
						Set<PolyBase> cutsInArea = new HashSet<PolyBase>();
						cutsInArea.add(cut);
						Rectangle2D multiCutArea = new Rectangle2D.Double(cutBox.getCenterX(), cutBox.getCenterY(), 0, 0);
						double cutLimit = Math.ceil(Math.max(pv.cutNodeLayer.getMulticutSep1D(), pv.cutNodeLayer.getMulticutSep2D()) +
							Math.max(pv.cutNodeLayer.getMulticutSizeX(), pv.cutNodeLayer.getMulticutSizeX()) + 2);
						cutLimit *= SCALEFACTOR;
						boolean foundMore = true;
						while (foundMore)
						{
							foundMore = false;
							Rectangle2D searchArea = new Rectangle2D.Double(multiCutArea.getMinX()-cutLimit, multiCutArea.getMinY()-cutLimit,
								multiCutArea.getWidth() + cutLimit*2, multiCutArea.getHeight() + cutLimit*2);
							for(RTNode.Search sea = new RTNode.Search(searchArea, root, true); sea.hasNext(); )
							{
								CutBound cBound = (CutBound)sea.next();
								if (cutsInArea.contains(cBound.cut)) continue;
								Rectangle2D bound = cBound.getBounds();
								if (searchArea.contains(bound.getCenterX(), bound.getCenterY()))
								{
									cutsInArea.add(cBound.cut);
									double lX = Math.min(multiCutArea.getMinX(), bound.getCenterX());
									double hX = Math.max(multiCutArea.getMaxX(), bound.getCenterX());
									double lY = Math.min(multiCutArea.getMinY(), bound.getCenterY());
									double hY = Math.max(multiCutArea.getMaxY(), bound.getCenterY());
									multiCutArea.setRect(lX, lY, hX-lX, hY-lY);
									foundMore = true;
								}
							}
						}

						// see if a multi-cut contact fits
						double lX = multiCutArea.getCenterX() - trueWidth/2;
						double hX = multiCutArea.getCenterX() + trueWidth/2;
						double lY = multiCutArea.getCenterY() - trueHeight/2;
						double hY = multiCutArea.getCenterY() + trueHeight/2;
						multiCutArea.setRect(lX, lY, hX-lX, hY-lY);
						badLayer = doesNodeFit(pv, multiCutArea, originalMerge, ignorePWell, ignoreNWell);
						if (badLayer == null)
						{
							// it fits: create it
							double mw = multiCutArea.getWidth();
							double mh = multiCutArea.getHeight();
							if (pv.rotation == 90 || pv.rotation == 270)
							{
								mw = multiCutArea.getHeight();
								mh = multiCutArea.getWidth();
							}
							realizeBiggestContact(pv.pNp, multiCutArea.getCenterX(), multiCutArea.getCenterY(), mw, mh,
								pv.rotation*10, originalMerge, newCell, contactNodes, activeCut, polyCut);
							for(PolyBase cutsFound : cutsInArea)
								cutList.remove(cutsFound);
							soFar += cutsInArea.size() - 1;
							foundCut = true;
							break;
						}
					}
                    // if no approximateCuts is available,
                    //else
					{
						// exact cut placement required: see if a single-cut contact fits
						Rectangle2D contactLoc = new Rectangle2D.Double(cutBox.getCenterX() - trueWidth/2,
							cutBox.getCenterY() - trueHeight/2, trueWidth, trueHeight);
						badLayer = doesNodeFit(pv, contactLoc, originalMerge, ignorePWell, ignoreNWell);
						if (badLayer == null)
						{
							// it fits: create it
							realizeNode(pv.pNp, contactLoc.getCenterX(), contactLoc.getCenterY(), pv.minWidth, pv.minHeight,
								pv.rotation*10, null, originalMerge, newCell, contactNodes);
//							realizeBiggestContact(pv.pNp, contactLoc.getCenterX(), contactLoc.getCenterY(), pv.minWidth, pv.minHeight,
//								pv.rotation*10, originalMerge, newCell, contactNodes, activeCut, polyCut);
							cutList.remove(cut);
							foundCut = true;
							break;
						}
					}

					reason = "node " + pv.pNp.describe(false) + ", layer " + badLayer.getName() + " does not fit";
					if (pv.rotation != 0) reason += " (when rotated " + pv.rotation + ")";
				}
				if (!foundCut)
				{
                    double centerX = cutBox.getCenterX()/SCALEFACTOR;
                    double centerY = cutBox.getCenterY()/SCALEFACTOR;
                    String msg = "Did not extract contact " + cut.getLayer().getName() + " cut at (" +
						(centerX) + "," + (centerY) + ") in '" + newCell.getName() + "'";
					if (reason != null) msg += " because " + reason;
                    addErrorLog(newCell, msg, new EPoint(centerX, centerY));
					cutList.remove(cut);
					cutsNotExtracted.add(cut);
				}
			}
			if (cutsNotExtracted.size() > 0)
				allCutLayers.put(layer, cutsNotExtracted);
		}

		// now remove all created contacts from the original merge
		if (!startSection("Finish extracting " + contactNodes.size() + " vias..."))
             return false; // aborted

        // build an R-Tree of all created nodes
		RTNode root = RTNode.makeTopLevel();
		for(NodeInst ni : contactNodes)
			root = RTNode.linkGeom(null, root, ni);

		// recursively scan the R-Tree, merging geometry on created nodes and removing them from the main merge
		PolyMerge subtractMerge = new PolyMerge();
		extractContactNodes(root, merge, subtractMerge, 0, contactNodes.size());
		merge.subtractMerge(subtractMerge);
        return true;
    }

	/**
	 * Method to create the biggest contact node in a given location.
	 * @param pNp the type of node to create.
	 * @param x the center X coordinate of the node.
	 * @param y the center Y coordinate of the node.
	 * @param sX the initial width of the node.
	 * @param sY the initial height of the node.
	 * @param rot the rotation of the node.
	 * @param merge the merge in which this node must reside.
	 * @param newCell the Cell in which the node will be created.
	 * @param contactNodes a list of nodes that were created.
	 * @param activeCut true if this is an active cut and must not have poly in the area.
	 * @param polyCut true if this is an poly cut and must not have active in the area.
	 */
	private void realizeBiggestContact(PrimitiveNode pNp, double x, double y, double sX, double sY, int rot,
		PolyMerge merge, Cell newCell, List<NodeInst> contactNodes, boolean activeCut, boolean polyCut)
	{
		Orientation orient = Orientation.fromAngle(rot);
		EPoint ctr = new EPoint(x / SCALEFACTOR, y / SCALEFACTOR);

		// first find an X size that does not fit
		double lowXInc = 0;
		double highXInc = SCALEFACTOR*2;
		for(;;)
		{
			NodeInst ni = NodeInst.makeDummyInstance(pNp, ctr, (sX+highXInc) / SCALEFACTOR, sY / SCALEFACTOR, orient);
			if (ni == null) return;
			Poly error = dummyNodeFits(ni, merge, activeCut, polyCut);
			if (error != null) break;
			lowXInc = highXInc;
			highXInc *= 2;
		}

		// now iterate to find the precise node X size
		for(;;)
		{
			if (highXInc - lowXInc <= 1) break;
			double medInc = (lowXInc + highXInc) / 2;
			NodeInst ni = NodeInst.makeDummyInstance(pNp, ctr, (sX+medInc) / SCALEFACTOR, sY / SCALEFACTOR, orient);
			if (ni == null) return;
			Poly error = dummyNodeFits(ni, merge, activeCut, polyCut);
			if (error == null) lowXInc = medInc; else
				highXInc = medInc;
		}

		// first find an Y size that does not fit
		double lowYInc = 0;
		double highYInc = SCALEFACTOR*2;
		for(;;)
		{
			NodeInst ni = NodeInst.makeDummyInstance(pNp, ctr, sX / SCALEFACTOR, (sY+highYInc) / SCALEFACTOR, orient);
			if (ni == null) return;
			Poly error = dummyNodeFits(ni, merge, activeCut, polyCut);
			if (error != null) break;
			lowYInc = highYInc;
			highYInc *= 2;
		}

		// now iterate to find the precise node Y size
		for(;;)
		{
			if (highYInc - lowYInc <= 1) break;
			double medInc = (lowYInc + highYInc) / 2;
			NodeInst ni = NodeInst.makeDummyInstance(pNp, ctr, sX / SCALEFACTOR, (sY+medInc) / SCALEFACTOR, orient);
			if (ni == null) return;
			Poly error = dummyNodeFits(ni, merge, activeCut, polyCut);
			if (error == null) lowYInc = medInc; else
				highYInc = medInc;
		}
		sX += lowXInc;
		sY += lowYInc;

		realizeNode(pNp, x, y, sX, sY, rot, null, merge, newCell, contactNodes);
	}

	private Poly dummyNodeFits(NodeInst ni, PolyMerge merge, boolean activeCut, boolean polyCut)
	{
		AffineTransform trans = ni.rotateOut();
		Technology tech = ni.getProto().getTechnology();
		Poly [] polys = tech.getShapeOfNode(ni);
		double biggestArea = 0;
		Poly biggestPoly = null;
		for(Poly poly : polys)
		{
			Layer l = poly.getLayer();
			if (l == null) continue;
			l = geometricLayer(l);
			poly.setLayer(l);
			if (l.getFunction().isSubstrate()) continue;
			if (l.getFunction().isContact()) continue;
			poly.transform(trans);
			double area = poly.getArea();
			if (area > biggestArea)
			{
				biggestArea = area;
				biggestPoly = poly;
			}
			Point2D[] points = poly.getPoints();
			for(int i=0; i<points.length; i++)
				poly.setPoint(i, scaleUp(points[i].getX()), scaleUp(points[i].getY()));
			if (!merge.contains(l, poly))
			{
				return poly;
			}
		}

		// contact fits, now check for active or poly problems
		if (activeCut && biggestPoly != null)
		{
			// disallow poly in the contact area
			if (merge.intersects(polyLayer, biggestPoly)) return biggestPoly;
		}
		if (polyCut && biggestPoly != null)
		{
			// disallow active in the contact area
			if (pActiveLayer != null && merge.intersects(pActiveLayer, biggestPoly)) return biggestPoly;
			if (nActiveLayer != null && nActiveLayer != pActiveLayer && merge.intersects(nActiveLayer, biggestPoly)) return biggestPoly;
		}
		return null;
	}

	/**
	 * Class to