autostitch.java

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

		// first check for arcs that daisy-chain many nodes
		for(ArcInst ai : arcsToStitch)
		{
			soFar++;
			if (showProgress && (soFar%100) == 0)
			{
				if (job != null && job.checkAbort()) return;
				Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);
			}
			checkDaisyChain(ai, nodePortBounds, stayInside, top);
		}
		if (allRoutes.size() > 0)
		{
			// found daisy-chain elements: do them now
			System.out.println("Auto-routing detected " + allRoutes.size() + " daisy-chained arcs");
			for(Route route : allRoutes)
			{
				Router.createRouteNoJob(route, cell, false, arcsCreatedMap, nodesCreatedMap);
			}

			// reset for the rest of the analysis
			allRoutes = new ArrayList<Route>();
			top = new Topology(cell);
		}

		// now run through the nodeinsts to be checked for stitching
		for(NodeInst ni : nodesToStitch)
		{
			soFar++;
			if (showProgress && (soFar%100) == 0)
			{
				if (job != null && job.checkAbort()) return;
				Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);
			}
			checkStitching(ni, nodeBounds, nodePortBounds, arcLayers, stayInside, top, limitBound, preferredArc);
		}

		// now run through the arcinsts to be checked for stitching
		for(ArcInst ai : arcsToStitch)
		{
			soFar++;
			if (showProgress && (soFar%100) == 0)
			{
				if (job != null && job.checkAbort()) return;
				Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);
			}

			if (!ai.isLinked()) continue;

			// only interested in arcs that are wider than their nodes (and have geometry that sticks out)
			if (!arcTooWide(ai)) continue;
			checkStitching(ai, nodeBounds, nodePortBounds, arcLayers, stayInside, top, limitBound, preferredArc);
		}

		// create the routes
		makeConnections(showProgress, arcsCreatedMap, nodesCreatedMap);

		// report results
		if (forced) Router.reportRoutingResults("AUTO ROUTING", arcsCreatedMap, nodesCreatedMap);

		// check for any inline pins due to created wires
		if (showProgress)
		{
			if (job != null && job.checkAbort()) return;
			Job.getUserInterface().setProgressValue(0);
			Job.getUserInterface().setProgressNote("Cleaning up pins...");
		}
		List<CircuitChangeJobs.Reconnect> pinsToPassThrough = new ArrayList<CircuitChangeJobs.Reconnect>();
		for (NodeInst ni : possibleInlinePins)
		{
			if (ni.isInlinePin())
			{
				CircuitChangeJobs.Reconnect re = CircuitChangeJobs.Reconnect.erasePassThru(ni, false, true);
				if (re != null)
				{
					pinsToPassThrough.add(re);
				}
			}
		}
		if (pinsToPassThrough.size() > 0)
		{
			CircuitChangeJobs.CleanupChanges ccJob = new CircuitChangeJobs.CleanupChanges(cell, true, Collections.<NodeInst>emptySet(),
				pinsToPassThrough, new HashMap<NodeInst,EPoint>(), new ArrayList<NodeInst>(), new HashSet<ArcInst>(), 0, 0, 0);
			try
			{
				ccJob.doIt();
			} catch (JobException e)
			{
			}
		}
	}

	private void makeConnections(boolean showProgress, Map<ArcProto,Integer> arcsCreatedMap,
		Map<NodeProto,Integer> nodesCreatedMap)
	{
		// create the routes
		int totalToStitch = allRoutes.size();
		int soFar = 0;
		if (showProgress)
		{
			Job.getUserInterface().setProgressValue(0);
			Job.getUserInterface().setProgressNote("Creating " + totalToStitch + " wires...");
		}
		Collections.sort(allRoutes, new CompRoutes());
		for (Route route : allRoutes)
		{
			soFar++;
			if (showProgress && (soFar%100) == 0)
				Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);

			RouteElement re = route.get(0);
			Cell c = re.getCell();

			// see if the route is unnecessary because of existing connections
			RouteElementPort start = route.getStart();
			RouteElementPort end = route.getEnd();
			PortInst startPi = start.getPortInst();
			PortInst endPi = end.getPortInst();
			if (startPi != null && endPi != null)
			{
				boolean already = false;
				for(Iterator<Connection> cIt = startPi.getConnections(); cIt.hasNext(); )
				{
					Connection con = cIt.next();
					ArcInst existingAI = con.getArc();
					if (existingAI.getHead() == con)
					{
						if (existingAI.getTail().getPortInst() == endPi) { already = true;   break; }
					} else
					{
						if (existingAI.getHead().getPortInst() == endPi) { already = true;   break; }
					}
				}
				if (already) continue;
			}

			Router.createRouteNoJob(route, c, false, arcsCreatedMap, nodesCreatedMap);
		}
	}

	/****************************************** ARCS THAT DAISY-CHAIN ******************************************/

	private static class DaisyChainPoint
	{
		PortInst pi;
		EPoint location;

		DaisyChainPoint(PortInst p, Point2D loc)
		{
			pi = p;
			location = new EPoint(loc.getX(), loc.getY());
		}
	}

	/**
	 * Class to sort DaisyChainPoints.
	 */
	private static class SortDaisyPoints implements Comparator<DaisyChainPoint>
	{
		public int compare(DaisyChainPoint dcp1, DaisyChainPoint dcp2)
		{
			if (dcp1.location.getX() < dcp2.location.getX()) return 1;
			if (dcp1.location.getX() > dcp2.location.getX()) return -1;
			if (dcp1.location.getY() < dcp2.location.getY()) return 1;
			if (dcp1.location.getY() > dcp2.location.getY()) return -1;
			return 0;
		}
	}

	/**
	 * Method to see if an ArcInst daisy-chains over multiple ports.
	 * @param ai the ArcInst in question.
	 * @param nodePortBounds quad-tree bounds information for all nodes in the Cell.
	 * @param stayInside is the area in which to route (null to route arbitrarily).
	 * @param top network information for the Cell with these objects.
	 */
	private void checkDaisyChain(ArcInst ai, Map<NodeInst, ObjectQTree> nodePortBounds, PolyMerge stayInside, Topology top)
	{
		// make a list of PortInsts that are on the centerline of this arc
		Cell cell = ai.getParent();
		Network arcNet = top.getArcNetwork(ai);
		Point2D e1 = ai.getHeadLocation();
		Point2D e2 = ai.getTailLocation();
		List<DaisyChainPoint> daisyPoints = new ArrayList<DaisyChainPoint>();
		Rectangle2D searchBounds = ai.getBounds();
		for(Iterator<RTBounds> it = cell.searchIterator(searchBounds); it.hasNext(); )
		{
			Geometric geom = (Geometric)it.next();
			if (geom instanceof NodeInst)
			{
				NodeInst ni = (NodeInst)geom;
				if (USEQTREE)
				{
					// find ports on this arc
					ObjectQTree oqt = nodePortBounds.get(ni);
					Set set = oqt.find(searchBounds);
					if (set != null)
					{
						for (Object obj : set)
						{
							PortInst pi = (PortInst)obj;
							if (!pi.getPortProto().getBasePort().connectsTo(ai.getProto())) continue;
							PolyBase portPoly = pi.getPoly();
							Point2D closest = GenMath.closestPointToSegment(e1, e2, portPoly.getCenter());

							// if this port can connect, save it
							if (DBMath.pointInRect(closest, portPoly.getBounds2D()))
							{
								// ignore if they are already connected
								Network portNet = top.getPortNetwork(pi);
								if (portNet == arcNet) continue;
								daisyPoints.add(new DaisyChainPoint(pi, closest));
							}
						}
					}
				} else
				{
					// can't handle this yet
					assert false;
				}
			}
		}

		// now see if there are multiple intermediate daisy-chain points
		if (daisyPoints.size() <= 1) return;
		Collections.sort(daisyPoints, new SortDaisyPoints());

        Route route = new Route();
        route.add(RouteElementArc.deleteArc(ai));

        RouteElementPort headRE = RouteElementPort.existingPortInst(ai.getHeadPortInst(), ai.getHeadLocation());
        RouteElementPort tailRE = RouteElementPort.existingPortInst(ai.getTailPortInst(), ai.getTailLocation());
        DaisyChainPoint firstDCP = daisyPoints.get(0);
        DaisyChainPoint lastDCP = daisyPoints.get(daisyPoints.size()-1);
        if (firstDCP.location.distance(ai.getHeadLocation()) > firstDCP.location.distance(ai.getTailLocation()))
        {
        	RouteElementPort swap = headRE;   headRE = tailRE;   tailRE = swap;
        }
        if (headRE.getNodeInst().getNumConnections() == 1 && headRE.getLocation().equals(firstDCP.location))
        {
        	route.add(RouteElementPort.deleteNode(headRE.getNodeInst()));
        	headRE = null;
        }
        if (tailRE.getNodeInst().getNumConnections() == 1 && tailRE.getLocation().equals(lastDCP.location))
        {
        	route.add(RouteElementPort.deleteNode(tailRE.getNodeInst()));
        	tailRE = null;
        }
        String name = ai.getName();
        for(DaisyChainPoint dcp : daisyPoints)
        {
            RouteElementPort dcpRE = RouteElementPort.existingPortInst(dcp.pi, dcp.location);
            if (headRE != null)
            {
	        	RouteElement re = RouteElementArc.newArc(cell, ai.getProto(), ai.getLambdaBaseWidth(), headRE, dcpRE,
	        		headRE.getLocation(), dcpRE.getLocation(), name, ai.getTextDescriptor(ArcInst.ARC_NAME),
	                ai, ai.isHeadExtended(), ai.isTailExtended(), stayInside);
	            route.add(re);
            }
        	headRE = dcpRE;
        	name = null;
        }
        if (tailRE != null)
        {
	    	RouteElement re = RouteElementArc.newArc(cell, ai.getProto(), ai.getLambdaBaseWidth(), headRE, tailRE,
	    		headRE.getLocation(), tailRE.getLocation(), name, ai.getTextDescriptor(ArcInst.ARC_NAME),
	            ai, ai.isHeadExtended(), ai.isTailExtended(), stayInside);
	        route.add(re);
        }
		allRoutes.add(route);
	}

	/****************************************** NORMAL STITCHING ******************************************/

	/**
	 * Method to check an object for possible stitching to neighboring objects.
	 * @param geom the object to check for stitching.
	 * @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 top network information for the Cell with these objects.
	 * @param limitBound if not null, only consider connections that occur in this area.
	 * @param preferredArc preferred ArcProto to use.
	 */
	private void checkStitching(Geometric geom, Map<NodeInst, Rectangle2D[]> nodeBounds,
		Map<NodeInst, ObjectQTree> nodePortBounds, Map<ArcProto,Layer> arcLayers,
		PolyMerge stayInside, Topology top, Rectangle2D limitBound, ArcProto preferredArc)
	{
		Cell cell = geom.getParent();
		NodeInst ni = null;
		if (geom instanceof NodeInst) ni = (NodeInst)geom;

		// make a list of other geometrics that touch or overlap this one (copy it because the main list will change)
		List<Geometric> geomsInArea = new ArrayList<Geometric>();
		Rectangle2D geomBounds = geom.getBounds();
		double epsilon = DBMath.getEpsilon();
		Rectangle2D searchBounds = new Rectangle2D.Double(geomBounds.getMinX()-epsilon, geomBounds.getMinY()-epsilon,
			geomBounds.getWidth()+epsilon*2, geomBounds.getHeight()+epsilon*2);
		for(Iterator<RTBounds> it = cell.searchIterator(searchBounds); it.hasNext(); )
		{
			Geometric oGeom = (Geometric)it.next();
			if (oGeom != geom) geomsInArea.add(oGeom);
		}
		for(Geometric oGeom : geomsInArea)
		{
			// find another node in this area
			if (oGeom instanceof ArcInst)
			{
				// other geometric is an ArcInst
				ArcInst oAi = (ArcInst)oGeom;

				if (ni == null)
				{
					// only interested in arcs that are wider than their nodes (and have geometry that sticks out)
					if (!arcTooWide(oAi)) continue;

					// compare arc "geom" against arc "oAi"
					compareTwoArcs((ArcInst)geom, oAi, stayInside, top);
					continue;
				}

				// compare node "ni" against arc "oAi"
				if (ni.isCellInstance())
				{
					compareNodeInstWithArc(ni, oAi, stayInside, top, nodePortBounds);
				} else
				{
					compareNodePrimWithArc(ni, oAi, stayInside, top);
				}
			} else
			{
				// other geometric a NodeInst
				NodeInst oNi = (NodeInst)oGeom;
				if (!oNi.isCellInstance())
				{
					PrimitiveNode pnp = (PrimitiveNode)oNi.getProto();
					if (pnp.getTechnology() == Generic.tech()) continue;
					if (pnp.getFunction() == PrimitiveNode.Function.NODE) continue;
				}

				if (ni == null)
				{
					// compare arc "geom" against node "oNi"
					if (oNi.isCellInstance())
					{
						compareNodeInstWithArc(oNi, (ArcInst)geom, stayInside, top, nodePortBounds);
					} else
					{
						compareNodePrimWithArc(oNi, (ArcInst)geom, stayInside, top);
					}
					continue;
				}

				// compare node "ni" against node "oNi"
				compareTwoNodes(ni, oNi, nodeBounds, nodePortBounds, arcLayers, stayInside, top, limitBound, preferredArc);
			}
		}
	}

	/**
	 * Method to compare two nodes and see if they should be connected.
	 * @param ni the first NodeInst to compare.
	 * @param oNi the second NodeInst to compare.
	 * @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 top network information for the Cell with these nodes.
	 * @param limitBound if not null, only consider connections that occur in this area.
	 * @param preferredArc preferred ArcProto to use.
	 */
	private void compareTwoNodes(NodeInst ni, NodeInst oNi,
		Map<NodeInst,Rectangle2D[]> nodeBounds, Map<NodeInst,ObjectQTree> nodePortBounds,