schemtolay.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: SchemToLay.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.tool.generator.layout;

import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;

import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.network.Netlist.ShortResistors;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.prototype.PortCharacteristic;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.database.variable.Variable;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.tool.generator.layout.gates.Inv;
import com.sun.electric.tool.generator.layout.gates.Inv2i;
import com.sun.electric.tool.generator.layout.gates.Inv2iKn;
import com.sun.electric.tool.generator.layout.gates.Inv2iKp;
import com.sun.electric.tool.generator.layout.gates.InvCTLn;
import com.sun.electric.tool.generator.layout.gates.InvHT;
import com.sun.electric.tool.generator.layout.gates.InvLT;
import com.sun.electric.tool.generator.layout.gates.Inv_passgate;
import com.sun.electric.tool.generator.layout.gates.Nand2;
import com.sun.electric.tool.generator.layout.gates.Nand2HLT;
import com.sun.electric.tool.generator.layout.gates.Nand2HLT_sy;
import com.sun.electric.tool.generator.layout.gates.Nand2LT;
import com.sun.electric.tool.generator.layout.gates.Nand2LT_sy;
import com.sun.electric.tool.generator.layout.gates.Nand2PH;
import com.sun.electric.tool.generator.layout.gates.Nand2PHfk;
import com.sun.electric.tool.generator.layout.gates.Nand2_sy;
import com.sun.electric.tool.generator.layout.gates.Nand2en;
import com.sun.electric.tool.generator.layout.gates.Nand2en_sy;
import com.sun.electric.tool.generator.layout.gates.Nand3;
import com.sun.electric.tool.generator.layout.gates.Nand3LT;
import com.sun.electric.tool.generator.layout.gates.Nand3LT_sy3;
import com.sun.electric.tool.generator.layout.gates.Nand3MLT;
import com.sun.electric.tool.generator.layout.gates.Nand3_sy3;
import com.sun.electric.tool.generator.layout.gates.Nand3en_sy;
import com.sun.electric.tool.generator.layout.gates.Nand3en_sy3;
import com.sun.electric.tool.generator.layout.gates.Nms1;
import com.sun.electric.tool.generator.layout.gates.Nms2;
import com.sun.electric.tool.generator.layout.gates.Nms2_sy;
import com.sun.electric.tool.generator.layout.gates.Nms3_sy3;
import com.sun.electric.tool.generator.layout.gates.Nor2;
import com.sun.electric.tool.generator.layout.gates.Nor2LT;
import com.sun.electric.tool.generator.layout.gates.Nor2kresetV;
import com.sun.electric.tool.generator.layout.gates.Pms1;
import com.sun.electric.tool.generator.layout.gates.Pms2;
import com.sun.electric.tool.generator.layout.gates.Pms2_sy;
import com.sun.electric.tool.generator.layout.gates.TieHi;
import com.sun.electric.tool.generator.layout.gates.VertTrack;

public class SchemToLay {
    // ------------------------ private types ---------------------------------

	// A RouteSeg is a list of layout ports that should be connected
	// and a list of exports on that net.  Networks that connect to
	// both NMOS stack and PMOS stack devices need to be divided into
	// two RouteSeg's, one in the lower half of the cell and one in
	// the upper half of the cell.  Otherwise there is a one to one
	// relationship between a Network and a RouteSeg
	private static class RouteSeg {
		private static final Iterator<Export> NO_EXPORTS = new ArrayList<Export>().iterator();

		private ArrayList<PortInst> pStkPorts = new ArrayList<PortInst>();
		private ArrayList<PortInst> nStkPorts = new ArrayList<PortInst>();
		private ArrayList<PortInst> nonStkPorts = new ArrayList<PortInst>();
		private Iterator<Export> exports = NO_EXPORTS;
		private Integer exportTrack = null;

		// Has this RouteSeg been assigned a track for its exports?
		// WARNING!! Export tracks are PHYSICAL!!!!! They include blocked
		// tracks.  Everywhere else in this program we talk about
		// available tracks which exclude blocked tracks.
		private boolean hasExpTrk() {return exportTrack!=null;}
		private int getExpTrk() {return exportTrack.intValue();}
		private boolean hasPmosExpTrk() {return hasExpTrk() && getExpTrk()>0;}
		private boolean hasNmosExpTrk() {return hasExpTrk() && getExpTrk()<0;}

		private static ArrayList<PortInst> schemNetToLayPorts(Network net,
													HashMap<NodeInst,NodeInst> iconToLay) {
			ArrayList<PortInst> layPorts = new ArrayList<PortInst>();

			Iterator<PortInst> iPorts = SKIP_WIRE_PORTINSTS.filter(net.getPorts());
			while (iPorts.hasNext()) {
				PortInst iconPort = iPorts.next();
				NodeInst layInst =
					iconToLay.get(iconPort.getNodeInst());
				error(layInst==null,
					  "SchemToLay: no layout instance for Icon? "+
					  iconPort.getNodeInst());
				String portNm = iconPort.getPortProto().getName();
				PortInst layPort = layInst.findPortInst(portNm);
				error(layPort==null, "Port: "+portNm+" missing from Part: "+
					  layInst.getProto().getName());
				layPorts.add(layPort);
			}
			return layPorts;
		}
		private static Integer findExportTrack(Network net,
											   HashMap<String,Object> expTrkAsgn) {
			Integer expTrk = null;
			for (Iterator<Export> it=net.getExports(); it.hasNext();) {
				String expNm = it.next().getName();
				if (expTrkAsgn.containsKey(expNm)) {
					error(expTrk!=null,
						  "more than one track assigned to segment!");
					expTrk = (Integer)expTrkAsgn.get(expNm);
				}
			}
			return expTrk;
		}
		private boolean hasNstk() {
			return nStkPorts.size()!=0 || hasNmosExpTrk();
		}
		private boolean hasPstk() {
			return pStkPorts.size()!=0 || hasPmosExpTrk();
		}
		private Iterator<Export> removeExports() {
			exportTrack = null;
			Iterator<Export> oldExports = exports;
			exports = NO_EXPORTS;
			return oldExports;
		}
		private RouteSeg(ArrayList<PortInst> layPorts, Iterator<Export> exports, Integer expTrk) {
			this.exports = exports;
			this.exportTrack = expTrk;
			for (int i=0; i<layPorts.size(); i++) {
				PortInst p = layPorts.get(i);
				if (isNstk(p.getNodeInst())) nStkPorts.add(p);
				else if (isPstk(p.getNodeInst())) pStkPorts.add(p);
				else nonStkPorts.add(p);
			}
		}
		public RouteSeg(Network net, HashMap<NodeInst,NodeInst> iconToLay, HashMap<String,Object> expTrkAsgn) {
			this(schemNetToLayPorts(net, iconToLay), net.getExports(),
				 findExportTrack(net, expTrkAsgn));
		}
		public boolean hasExports() {return exports.hasNext();}
		public Iterator<Export> findExports() {return exports;}
		public boolean hasNonStk() {return nonStkPorts.size()!=0;}

		// A RouteSeg containing both NMOS and PMOS stacks must be divided into
		// two RouteSegs
		public RouteSeg splitOffPstkRouteSeg(ArrayList<NodeInst> vertTracks,
											 StdCellParams stdCell,
											 Cell gasp) {
			error(!hasPstk() || !hasNstk(), "can't split off anything");
			if (!hasNonStk()) {
				// There is no non-stack part on this segment.  We need to add
				// a part containing a vertical routing track so we can
				// connect the NMOS and PMOS stacks.
				NodeProto vtProt = VertTrack.makePart(stdCell);
				NodeInst vtInst =
				    LayoutLib.newNodeInst(vtProt, 0, 0, 0, 0, 0, gasp);
				vertTracks.add(vtInst);
				nonStkPorts.add(vtInst.findPortInst("in"));
			}
			// For now, old segment contains nStk and nonStk, new segment
			// contains pStk and one nonStk to bind the two segments
			// together.  Optimize this later.
			ArrayList<PortInst> pPorts = pStkPorts;
			pStkPorts = new ArrayList<PortInst>();
			pPorts.add(nonStkPorts.get(0));

			Integer pExpTrk = hasPmosExpTrk() ? new Integer(getExpTrk()) : null;
			Iterator<Export> pExports = hasPmosExpTrk() ? removeExports() : NO_EXPORTS;

			return new RouteSeg(pPorts, pExports, pExpTrk);
		}
		public ArrayList<PortInst> getAllPorts() {
			ArrayList<PortInst> ports = new ArrayList<PortInst>(pStkPorts);
			ports.addAll(nStkPorts);
			ports.addAll(nonStkPorts);
			return ports;
		}
		public double estimateLength() {
			double minX = Double.POSITIVE_INFINITY;
			double maxX = Double.NEGATIVE_INFINITY;
			ArrayList<PortInst> ports = getAllPorts();
			for (int i=0; i<ports.size(); i++) {
				double x = LayoutLib.roundCenterX(ports.get(i));
				minX = Math.min(minX, x);
				maxX = Math.max(maxX, x);
			}
			double weight = hasExports() ? 1/*.5*/ : 1;
			return weight*(maxX-minX);
		}
		public double getLoX() {
			double minX = Double.POSITIVE_INFINITY;
			ArrayList<PortInst> ports = getAllPorts();
			for (int i=0; i<ports.size(); i++) {
				double x = LayoutLib.roundCenterX(ports.get(i));
				minX = Math.min(minX, x);
			}
			return minX;
		}
		public double getHiX() {
			double maxX = Double.NEGATIVE_INFINITY;
			ArrayList<PortInst> ports = getAllPorts();
			for (int i=0; i<ports.size(); i++) {
				double x = LayoutLib.roundCenterX(ports.get(i));
				maxX = Math.max(maxX, x);
			}
			return maxX;
		}
	}

	private static class TrackAllocator {
		private static final double FULL_TRACK_XLO = -Integer.MAX_VALUE;
		private static final double FULL_TRACK_WID = 2.0 * Integer.MAX_VALUE;
		private static final boolean PMOS = true;
		private static final boolean NMOS = false;
		private final int nbNmosTracks, nbPmosTracks;
		private StdCellParams stdCell;
		private ArrayList<Rectangle2D> blockages = new ArrayList<Rectangle2D>();
		public TrackAllocator(StdCellParams stdCell) {
			this.stdCell = stdCell;
			nbNmosTracks = stdCell.nbNmosTracks();
			nbPmosTracks = stdCell.nbPmosTracks();
		}
		private boolean isBlocked(double x, double y, double w, double h) {
			for (int i=0; i<blockages.size(); i++) {
				Rectangle2D block = blockages.get(i);
				if (block.intersects(x, y, w, h)) return true;
			}
			return false;
		}

		private int findClearTrack(RouteSeg r, boolean isPmos, double wireWid) {
			// external nets block the entire track
			boolean ext = r.hasExports();
			double xLo = ext ? FULL_TRACK_XLO : (r.getLoX() - wireWid/2);
			double wid = ext ? FULL_TRACK_WID : (r.getHiX() - r.getLoX() + wireWid);

			int maxTrack = isPmos ? nbPmosTracks : nbNmosTracks;
			int dir = isPmos ? 1 : -1;
			for (int track=1; track<=maxTrack; track++) {
				double yLo = stdCell.getTrackY(dir*track) - wireWid/2;
				if (!isBlocked(xLo, yLo, wid, wireWid)) return track*dir;
			}
			return 0;
		}

		public void occupyTrack(RouteSeg r, double y, double wireWid) {
			// external nets block the entire track
			boolean ext = r.hasExports();
			double xLo = ext ? FULL_TRACK_XLO : (r.getLoX() - wireWid/2);
			double wid = ext ? FULL_TRACK_WID : (r.getHiX() - r.getLoX() + wireWid);
			double yLo = y - wireWid/2;
			Rectangle2D block = new Rectangle2D.Double(xLo, yLo, wid, wireWid);
			blockages.add(block);
		}

		public void occupyTrack(RouteSeg r, int trkNdx, double wireWid) {
			occupyTrack(r, stdCell.getTrackY(trkNdx), wireWid);
		}

		public double getTrackY(RouteSeg r, double wireWid) {
			int track;
			if (r.hasPstk()) {
				// segments with PMOS stacks must use tracks in P region
				error(r.hasNstk(), "RouteSeg requires 2 tracks");
				track = findClearTrack(r, PMOS, wireWid);
				error(track==-1, "ran out of PMOS routing tracks");
			} else if (r.hasNstk()) {
				// segments with NMOS stacks must use tracks in N region
				track = findClearTrack(r, NMOS, wireWid);
				error(track==0, "ran out of NMOS routing tracks");
			} else {
				// Segments without stacks can be routed in either region.
				int pTrack = findClearTrack(r, PMOS, wireWid);
				int nTrack = findClearTrack(r, NMOS, wireWid);
				error(pTrack==0 && nTrack==0, "ran out of routing tracks");
				if (pTrack!=0 && nTrack!=0) {
					// use the inner most track
					track = (pTrack < -nTrack) ? pTrack : nTrack;
				} else {
					// use the only track we've got
					track = (nTrack!=0) ? nTrack : pTrack;
				}
			}
			occupyTrack(r, track, wireWid);
			return stdCell.getTrackY(track);
		}
	}

	// In addition to the ordinary uninteresting schematic pieces, also
	// skip Cell wire{ic}
	private static class SkipWirePortInsts extends PortFilter.SchemPortFilter {
		@Override
		public boolean skipPort(PortInst pi) {
			// if it's a wire pin, bus pin, off page then pitch it
			if (super.skipPort(pi))  return true;
			NodeProto np = pi.getNodeInst().getProto();

			// if it's an instance of the Cell wire{ic} then pitch it
			if (np instanceof Cell && np.getName().equals("wire{ic}")) {
				return true;
			}
			if (np instanceof PrimitiveNode &&
			    np.getName().equals("Global-Signal")) {