compaction.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: Compaction.java
 * Originally written by: Nora Ryan, Schlumberger Palo Alto Research
 * Rewritten and translated by: Steven M. Rubin, Sun Microsystems.
 *
 * Copyright (c) 2004 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.compaction;

import com.sun.electric.database.constraint.Layout;
import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.geometry.GenMath;
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.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.text.Pref;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.Connection;
import com.sun.electric.database.topology.Geometric;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.variable.UserInterface;
import com.sun.electric.technology.DRCTemplate;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.SizeOffset;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.JobException;
import com.sun.electric.tool.Tool;
import com.sun.electric.tool.drc.DRC;

import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

/**
 * This is the Compaction tool.
 *
 * When compacting cell instances, the system only examines polygons
 * within a protection frame of the cell border.  This frame is the largest
 * design rule distance in the technology.  If the cell border is irregular,
 * there may be objects that are not seen, causing the cell to overlap
 * more than it should.
 */
public class Compaction extends Tool
{
	/** the Compaction tool. */		private static Compaction tool = new Compaction();

	/****************************** TOOL INTERFACE ******************************/

	/**
	 * The constructor sets up the Compaction tool.
	 */
	private Compaction()
	{
		super("compaction");
	}

	/**
	 * Method to initialize the Compaction tool.
	 */
	public void init() {}

    /**
     * Method to retrieve the singleton associated with the Compaction tool.
     * @return the Compaction tool.
     */
    public static Compaction getCompactionTool() { return tool; }

	/****************************** COMPACTION CONTROL ******************************/

	/**
	 * Method to compact the current cell.
	 */
	public static void compactNow()
	{
		UserInterface ui = Job.getUserInterface();
		Cell cell = ui.getCurrentCell();
		if (cell == null) return;
		compactNow(cell);
	}

	/**
	 * Method to compact the requested cell.
	 */
	public static void compactNow(Cell cell)
	{
		// do the compaction in a job
		CompactCellJob job = new CompactCellJob(cell, true, CompactCell.Axis.HORIZONTAL);
        job.startJob();
	}

private static int limitLoops = 10;
	/**
	 * Class to compact a cell in a Job.
	 */
	private static class CompactCellJob extends Job
	{
		private Cell cell;
		private boolean lastTime;
		private CompactCell.Axis curAxis;

		private CompactCellJob(Cell cell, boolean lastTime, CompactCell.Axis curAxis)
		{
			super("Compact " + cell, tool, Job.Type.CHANGE, null, null, Job.Priority.USER);
			this.cell = cell;
			this.lastTime = lastTime;
			this.curAxis = curAxis;
		}

		public boolean doIt() throws JobException
		{
			// make the compaction object for the cell
			CompactCell cc = new CompactCell(cell);

			// alternate vertical then horizontal compaction
			boolean change = cc.compactOneDirection(curAxis);
if (--limitLoops <= 0) change = false;
			if (lastTime || change)
			{
				curAxis = (curAxis == CompactCell.Axis.HORIZONTAL) ? CompactCell.Axis.VERTICAL : CompactCell.Axis.HORIZONTAL;
				CompactCellJob job = new CompactCellJob(cell, change, curAxis);
                job.startJobOnMyResult();
			} else
			{
				System.out.println("Compaction complete");
			}
			return true;
		}
	}

	/****************************** OPTIONS ******************************/

	private static Pref cacheAllowSpreading = Pref.makeBooleanPref("AllowSpreading", tool.prefs, false);
	/**
	 * Method to tell whether the compactor can spread circuitry apart, or just compact it.
	 * The default is "false" (may only compact).
	 * @return true if the compactor can spread circuitry apart; false to just compact it.
	 */
	public static boolean isAllowsSpreading() { return cacheAllowSpreading.getBoolean(); }
	/**
	 * Method to set whether the compactor can spread circuitry apart, or just compact it.
	 * @param on true if the compactor can spread circuitry apart; false to just compact it.
	 */
	public static void setAllowsSpreading(boolean on) { cacheAllowSpreading.setBoolean(on); }
	/**
	 * Method to tell whether the factory default for the compactor is to spread circuitry apart, or just compact it.
	 * @return true if the compactor can spread circuitry apart in factory default.
	 */
	public static boolean isFactoryAllowsSpreading() { return cacheAllowSpreading.getBooleanFactoryValue(); }

	/****************************** COMPACTION ******************************/

	/**
	 * Class to compact a cell.
	 */
	private static class CompactCell
	{
		private static final double DEFAULT_VAL = -99999999;

		private static enum Axis { HORIZONTAL, VERTICAL };

		private static class PolyList
		{
			private Poly       poly;
			private Technology tech;
			private int        networkNum;
			private PolyList   nextPolyList;
		};

		private static class GeomObj
		{
			private Geometric inst;
			private PolyList  firstPolyList;
			private double    lowx, highx, lowy, highy;
			private double    outerLowx, outerHighx, outerLowy, outerHighy;
			private GeomObj   nextObject;
		};

		private static class Line
		{
			private double   val;
			private double   low, high;
			private GeomObj  firstObject;
			private Line     nextLine;
			private Line     prevLine;
		};

		/** protection frame max size for technology */			private double  maxBoundary;
		/** lowest edge of current line */						private double  lowBound;
		/** counter for unique network numbers */				private int     flatIndex;
		/** current axis of compaction */						private Axis    curAxis;
		/** cell being compacted */								private Cell    cell;

		private CompactCell(Cell cell)
		{
			this.cell = cell;
		}

		/**
		 * Method to do vertical compaction (if "axis" is VERTICAL) or horizontal
		 * compaction (if "axis" is HORIZONTAL) to cell "np".  Displays state if
		 * "verbose" is nonzero.  Returns true if a change was made.
		 */
		private boolean compactOneDirection(Axis curAxis)
		{
			this.curAxis = curAxis;

			// determine maximum drc surround for entire technology
			maxBoundary = DRC.getWorstSpacingDistance(Technology.getCurrent(), -1);

			if (curAxis == Axis.HORIZONTAL) System.out.println("Compacting horizontally"); else
				System.out.println("Compacting vertically");

			// number ports of cell "cell"
			HashMap<PortProto,Integer> portIndices = new HashMap<PortProto,Integer>();
			flatIndex = 1;
			Netlist nl = cell.acquireUserNetlist();
			if (nl == null)
			{
				System.out.println("Sorry, a deadlock aborted compaction (network information unavailable).  Please try again");
				return false;
			}
			for(Iterator<PortProto> it = cell.getPorts(); it.hasNext(); )
			{
				Export pp = (Export)it.next();
				Network net = nl.getNetwork(pp, 0);

				// see if this port is on the same net as previously examined one
				Export found = null;
				for(Iterator<PortProto> oIt = cell.getPorts(); oIt.hasNext(); )
				{
					Export oPp = (Export)oIt.next();
					if (oPp == pp) break;
					Network oNet = nl.getNetwork(oPp, 0);
					if (net == oNet) { found = oPp;   break; }
				}
				if (found != null)
				{
					Integer oIndex = portIndices.get(found);
					portIndices.put(pp, oIndex);
				} else portIndices.put(pp, new Integer(flatIndex++));
			}

			// copy port numbering onto arcs
			HashMap<ArcInst,Integer> arcIndices = subCellSmash(cell, portIndices);

			// clear "seen" information on every node
			HashSet<NodeInst> nodesSeen = new HashSet<NodeInst>();

			// clear object information
			Line lineComp = null;
			List<GeomObj> otherObjectList = new ArrayList<GeomObj>();

			// now check every object
			for(Iterator<NodeInst> it = cell.getNodes(); it.hasNext(); )
			{
				NodeInst ni = it.next();
				if (ni.getProto() == Generic.tech().cellCenterNode ||
					ni.getProto() == Generic.tech().essentialBoundsNode) continue;

				// clear "thisObject" before calling createobject
				List<GeomObj> thisObjectList = new ArrayList<GeomObj>();
				createObjects(ni, thisObjectList, otherObjectList, nodesSeen, arcIndices, portIndices);

				// create object of layout
				if (thisObjectList.size() != 0)
					lineComp = makeObjectLine(lineComp, thisObjectList);
			}

			// create list of perpendicular line which need to be set stretchable
			Line lineStretch = null;
			if (otherObjectList.size() != 0)
				lineStretch = makeObjectLine(null, otherObjectList);

			// compute bounds for each line
			for(Line curLine = lineComp; curLine != null; curLine = curLine.nextLine)
				computeLineHiAndLow(curLine);

			// sort the compacting line of objects
			lineComp = sortLines(lineComp);

			// do the compaction
			lowBound = findLeastLow(lineComp);
//			boolean change = lineupFirstRow(lineComp, lineStretch, lowBound);
			boolean change = false;
			change = compactLine(lineComp, lineStretch, change, cell);

			return change;
		}

//		private boolean lineupFirstRow(Line line, Line lineStretch, double lowestBound)
//		{
//			boolean change = false;
//			double i = line.low - lowestBound;
//			if (i > DBMath.getEpsilon())
//			{
//				// initialize arcs: disable stretching line from sliding; make moving line rigid
//				HashSet<ArcInst> clearedArcs = ensureSlidability(lineStretch);
//				setupTemporaryRigidity(line, lineStretch);
//
//				if (curAxis == Axis.HORIZONTAL) change = moveLine(line, i, 0, change); else
//					change = moveLine(line, 0, i, change);
//
//				// restore slidability on stretching lines
//				restoreSlidability(clearedArcs);
//			}
//			return change;
//		}

		private boolean compactLine(Line line, Line lineStretch, boolean change, Cell cell)
		{
//            System.out.println("Compacting line:");
//            for (Line curLine = line; curLine != null; curLine = curLine.nextLine) {
//                System.out.print("\t");
//                for (GeomObj obj = curLine.firstObject; obj != null; obj = obj.nextObject)
//                    System.out.print(" " + obj.inst);
//                System.out.println();
//            }
//            System.out.println("Stretch line:");
//            for (Line curLine = lineStretch; curLine != null; curLine = curLine.nextLine) {
//                System.out.print("\t");
//                for (GeomObj obj = curLine.firstObject; obj != null; obj = obj.nextObject)
//                    System.out.print(" " + obj.inst);
//                System.out.println();
//            }
           
			boolean spread = isAllowsSpreading();

			// loop through all lines that may compact
			for(Line curLine = line.nextLine; curLine != null; curLine = curLine.nextLine)
			{
				if (curLine.low <= line.low) continue;
				double bestMotion = DEFAULT_VAL;

				// look at all previous lines
				for(Line prevLine = curLine.prevLine; prevLine != null; prevLine = prevLine.prevLine)
				{
					// look at every object in the line that may compact
					for(GeomObj curObject = curLine.firstObject; curObject != null; curObject = curObject.nextObject)
					{
						// no need to test this line if it is farther than best motion
						if (bestMotion != DEFAULT_VAL &&
							curLine.low - prevLine.high > bestMotion) continue;

						// simple object compaction
						double thisMotion = checkInst(curObject, prevLine, cell);
						if (thisMotion == DEFAULT_VAL) continue;
						if (bestMotion == DEFAULT_VAL || thisMotion < bestMotion)
						{
							bestMotion = thisMotion;
						}
					}
				}

				if (bestMotion == DEFAULT_VAL)
				{
					// no constraints: allow overlap
					bestMotion = curLine.low - lowBound;
				}
				if (bestMotion > DBMath.getEpsilon() || (spread && bestMotion < -DBMath.getEpsilon()))
				{
					// initialize arcs: disable stretching line from sliding; make moving line rigid
					HashSet<ArcInst> clearedArcs = ensureSlidability(lineStretch);
					setupTemporaryRigidity(line, lineStretch);

					if (curAxis == Axis.HORIZONTAL)
						change = moveLine(curLine, bestMotion, 0, change); else
							change = moveLine(curLine, 0, bestMotion, change);

					// restore slidability on stretching lines
					restoreSlidability(clearedArcs);
				}
			}
			return change;
		}

		private double checkInst(GeomObj object, Line line, Cell cell)
		{
			double bestMotion = DEFAULT_VAL;
			for(PolyList polys = object.firstPolyList; polys != null; polys = polys.nextPolyList)
			{
				// translate any pseudo layers for this node
				Poly poly = polys.poly;
				Layer layer = poly.getLayer().getNonPseudoLayer();

				// find distance line can move toward this poly
				double thisMotion = minSeparate(object, layer, polys, line, cell);
				if (thisMotion == DEFAULT_VAL) continue;
				if (bestMotion == DEFAULT_VAL || thisMotion < bestMotion)
				{
					bestMotion = thisMotion;
				}
			}
			return bestMotion;
		}