maker.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: Maker.java
 * Silicon compiler tool (QUISC): make Electric circuitry
 * Written by Andrew R. Kostiuk, Queen's University.
 * Translated to Java by Steven M. Rubin, Sun Microsystems.
 *
 * Copyright (c) 2005 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.sc;

import com.sun.electric.database.geometry.Orientation;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.Library;
import com.sun.electric.database.prototype.PortCharacteristic;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.PrimitivePort;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Schematics;
import com.sun.electric.tool.user.User;

import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.Iterator;

/**
 * The generation part of the Silicon Compiler tool.
 */
public class Maker
{
	private static class MakerData
	{
		/** cell being layed out */			GetNetlist.SCCell	cell;
		/** list of rows */					MakerRow		rows;
		/** list of channels */				MakerChannel	channels;
		/** list of vdd ports */			MakerPower		power;
		/** list of ground ports */			MakerPower		ground;
		/** minimum x position */			double			minX;
		/** maximum x position */			double			maxX;
		/** minimum y position */			double			minY;
		/** maximum y position */			double			maxY;
	};

	private static class MakerRow
	{
		/** row number */					int				number;
		/** instances in rows */			MakerInst		members;
		/** minimum X position */			double			minX;
		/** maximum X position */			double			maxX;
		/** minimum Y position */			double			minY;
		/** maximum Y position */			double			maxY;
		/** processing bits */				int				flags;
		/** last row */						MakerRow		last;
		/** next row */						MakerRow		next;
	};

	private static class MakerInst
	{
		/** reference place */				Place.NBPlace	place;
		/** reference row */				MakerRow		row;
		/** X position */					double			xPos;
		/** Y position */					double			yPos;
		/** size in X */					double			xSize;
		/** size in Y */					double			ySize;
		/** processing flags */				int				flags;
		/** leaf instance */				NodeInst		instance;
		/** next in row */					MakerInst		next;
	};

	private static class MakerChannel
	{
		/** number of channel */			int				number;
		/** list of tracks */				MakerTrack		tracks;
		/** number of tracks */				int				numTracks;
		/** minimum Y position */			double			minY;
		/** Y size */						double			ySize;
		/** processing bits */				int				flags;
		/** last channel */					MakerChannel	last;
		/** next channel */					MakerChannel	next;
	};

	private static class MakerTrack
	{
		/** track number */					int				number;
		/** nodes in track */				MakerNode		nodes;
		/** reference track */				Route.RouteTrack	track;
		/** Y position */					double			yPos;
		/** processing bits */				int				flags;
		/** previous track */				MakerTrack		last;
		/** next track */					MakerTrack		next;
	};

	private static class MakerNode
	{
		/** list of vias */					MakerVia		vias;
		/** next node in track */			MakerNode		next;
	};

	private static final int VIASPECIAL	= 0x00000001;
	private static final int VIAEXPORT	= 0x00000002;
	private static final int VIAPOWER	= 0x00000004;

	private static class MakerVia
	{
		/** X position */					double			xPos;
		/** associated channel port */		Route.RouteChPort	chPort;
		/** associated leaf instance */		NodeInst		instance;
		/** flags for processing */			int				flags;
		/** export port */					Route.RouteExport	xPort;
		/** next via */						MakerVia		next;
	};

	private static class MakerPower
	{
		/** list of power ports */			MakerPowerPort ports;
		/** vertical position of row */		double			yPos;
		/** next in row list */				MakerPower		next;
		/** last in row list */				MakerPower		last;
	};

	private static class MakerPowerPort
	{
		/** instance */						MakerInst		inst;
		/** port on instance */				GetNetlist.SCNiPort port;
		/** resultant x position */			double			xPos;
		/** next in list */					MakerPowerPort	next;
		/** last in list */					MakerPowerPort	last;
	};

	private PrimitiveNode layer1Proto;
	private PrimitiveNode layer2Proto;
	private PrimitiveNode viaProto;
	private PrimitiveNode pWellProto;
	private PrimitiveNode nWellProto;
	private ArcProto layer1Arc;
	private ArcProto layer2Arc;

	/**
	 * Method to make Electric circuitry from the results of place-and-route.
	 *
	 *   o  Determination of final position
	 *   o  Include squeezing rows in vertical direction
	 *   o  Squeeze tracks together if nonadjacent via
	 *   o  Creating ties to power and ground
	 *   o  Routing Power and Ground buses
	 *   o  Creation in Electric's database
	 */
	public Object makeLayout(Library destLib, GetNetlist gnl)
	{
		// check if working in a cell
		if (gnl.curSCCell == null) return "No cell selected";

		// check if placement structure exists
		if (gnl.curSCCell.placement == null)
			return "No PLACEMENT structure for cell '" + gnl.curSCCell.name + "'";

		// check if route structure exists
		if (gnl.curSCCell.route == null)
			return "No ROUTE structure for cell '" + gnl.curSCCell.name + "'";

		// set up make structure
		MakerData makeData = setUp(gnl.curSCCell);

		// create actual layout
		Object result = createLayout(destLib, makeData);
		if (result instanceof String) return result;

		return result;
	}

	/**
	 * Method to create the data structures to define the precise layout of the cell.
	 * Decide exactly where cells are placed, tracks are laid, via are positioned, etc.
	 * @param cell pointer to cell to layout.
	 * @return created data.
	 */
	private MakerData setUp(GetNetlist.SCCell cell)
	{
		// create top level data structure
		MakerData data = new MakerData();
		data.cell = cell;
		data.rows = null;
		data.channels = null;
		data.power = null;
		data.ground = null;
		data.minX = Double.MAX_VALUE;
		data.maxX = Double.MIN_VALUE;
		data.minY = Double.MAX_VALUE;
		data.maxY = Double.MIN_VALUE;

		// create Maker Channel and Track data structures
		double rowToTrack = (SilComp.getViaSize() / 2) + SilComp.getMinMetalSpacing();
		double minTrackToTrack = (SilComp.getViaSize() / 2) +
			SilComp.getMinMetalSpacing() + (SilComp.getHorizArcWidth() / 2);
		double maxTrackToTrack = SilComp.getViaSize() + SilComp.getMinMetalSpacing();
		MakerChannel lastMChan = null;
		for (Route.RouteChannel chan = cell.route.channels; chan != null; chan = chan.next)
		{
			// create Maker Channel structute
			MakerChannel mChan = new MakerChannel();
			mChan.number = chan.number;
			mChan.tracks = null;
			mChan.numTracks = 0;
			mChan.ySize = 0;
			mChan.flags = 0;
			mChan.next = null;
			mChan.last = lastMChan;
			if (lastMChan != null)
			{
				lastMChan.next = mChan;
			} else
			{
				data.channels = mChan;
			}
			lastMChan = mChan;

			// create Make Track structures
			MakerTrack lastMTrack = null;
			double yPos = 0;
			for (Route.RouteTrack track = chan.tracks; track != null; track = track.next)
			{
				MakerTrack mTrack = new MakerTrack();
				mTrack.number = track.number;
				mTrack.nodes = null;
				mTrack.track = track;
				mTrack.flags = 0;
				mTrack.next = null;
				mTrack.last = lastMTrack;
				if (lastMTrack != null)
				{
					lastMTrack.next = mTrack;
				} else
				{
					mChan.tracks = mTrack;
				}
				lastMTrack = mTrack;
				mChan.numTracks++;
				if (mTrack.number == 0)
				{
					yPos += rowToTrack;
					mTrack.yPos = yPos;
				} else
				{
					// determine if min or max track to track spacing is used
					double deltaY = minTrackToTrack;
					Route.RouteTrackMem tr1Mem = track.nodes;
					Route.RouteTrackMem tr2Mem = track.last.nodes;
					Route.RouteChPort tr1Port = tr1Mem.node.firstPort;
					Route.RouteChPort tr2Port = tr2Mem.node.firstPort;
					while (tr1Port != null && tr2Port != null)
					{
						if (Math.abs(tr1Port.xPos - tr2Port.xPos) < maxTrackToTrack)
						{
							deltaY = maxTrackToTrack;
							break;
						}
						if (tr1Port.xPos < tr2Port.xPos)
						{
							tr1Port = tr1Port.next;
							if (tr1Port == null)
							{
								tr1Mem = tr1Mem.next;
								if (tr1Mem != null)
									tr1Port = tr1Mem.node.firstPort;
							}
						} else
						{
							tr2Port = tr2Port.next;
							if (tr2Port == null)
							{
								tr2Mem = tr2Mem.next;
								if (tr2Mem != null)
									tr2Port = tr2Mem.node.firstPort;
							}
						}
					}
					yPos += deltaY;
					mTrack.yPos = yPos;
				}
				if (track.next == null)
					yPos += rowToTrack;
			}
			mChan.ySize = yPos;
		}

		// create Maker Rows and Instances data structures
		MakerChannel mChan = data.channels;
		mChan.minY = 0;
		double yPos = mChan.ySize;
		MakerRow lastMRow = null;
		for(Place.RowList row : cell.placement.theRows)
		{
			// create maker row data structure
			MakerRow mRow = new MakerRow();
			mRow.number = row.rowNum;
			mRow.members = null;
			mRow.minX = Double.MAX_VALUE;
			mRow.maxX = Double.MIN_VALUE;
			mRow.minY = Double.MAX_VALUE;
			mRow.maxY = Double.MIN_VALUE;
			mRow.flags = 0;
			mRow.next = null;
			mRow.last = lastMRow;
			if (lastMRow != null)
			{
				lastMRow.next = mRow;
			} else
			{
				data.rows = mRow;
			}
			lastMRow = mRow;

			// determine permissible top and bottom overlap
			double tOffset = Double.MIN_VALUE;
			double bOffset = Double.MAX_VALUE;
			for (Place.NBPlace place = row.start; place != null; place = place.next)
			{
				if (place.cell.type != GetNetlist.LEAFCELL) continue;
				GetNetlist.SCCellNums cNums = GetNetlist.getLeafCellNums((Cell)place.cell.np);
				tOffset = Math.max(tOffset, SilComp.leafCellYSize((Cell)place.cell.np) - cNums.topActive);
				bOffset = Math.min(bOffset, cNums.bottomActive);
			}
			yPos -= bOffset;

			// create maker instance structure for each member in the row
			MakerInst lastMInst = null;
			for (Place.NBPlace place = row.start; place != null; place = place.next)
			{
				if (place.cell.type != GetNetlist.LEAFCELL &&
					place.cell.type != GetNetlist.FEEDCELL &&
					place.cell.type != GetNetlist.LATERALFEED) continue;
				MakerInst mInst = new MakerInst();
				mInst.place = place;
				mInst.row = mRow;
				mInst.xPos = place.xPos;
				mInst.yPos = yPos;
				mInst.xSize = place.cell.size;
				if (place.cell.type == GetNetlist.LEAFCELL)
				{
					mInst.ySize = SilComp.leafCellYSize((Cell)place.cell.np);

					// add power ports
					for (GetNetlist.SCNiPort iport = place.cell.power; iport != null; iport = iport.next)
					{
						MakerPowerPort powerPort = new MakerPowerPort();
						powerPort.inst = mInst;
						powerPort.port = iport;
						if ((mRow.number % 2) != 0)
						{
							powerPort.xPos = mInst.xPos + mInst.xSize - iport.xPos;
						} else
						{
							powerPort.xPos = mInst.xPos + iport.xPos;
						}
						powerPort.next = null;
						powerPort.last = null;
						double portYPos = mInst.yPos + SilComp.leafPortYPos((Export)iport.port);
						MakerPower pList;
						for (pList = data.power; pList != null; pList = pList.next)
						{
							if (pList.yPos == portYPos) break;
						}
						if (pList == null)
						{
							pList = new MakerPower();
							pList.ports = null;
							pList.yPos = portYPos;
							MakerPower lastPList = null;
							MakerPower nextPList;
							for (nextPList = data.power; nextPList != null; nextPList = nextPList.next)
							{
								if (portYPos < nextPList.yPos) break;
								lastPList = nextPList;
							}
							pList.next = nextPList;
							pList.last = lastPList;
							if (lastPList != null)
							{
								lastPList.next = pList;
							} else
							{
								data.power = pList;
							}
							if (nextPList != null)
							{
								nextPList.last = pList;
							}
						}
						MakerPowerPort lastPort = null;
						MakerPowerPort nextPort;
						for (nextPort = pList.ports; nextPort != null; nextPort = nextPort.next)
						{
							if (powerPort.xPos < nextPort.xPos) break;
							lastPort = nextPort;
						}
						powerPort.next = nextPort;
						powerPort.last = lastPort;
						if (lastPort != null)
						{
							lastPort.next = powerPort;