quick.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: Quick.java
 *
 * 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.drc;

import com.sun.electric.database.geometry.*;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.HierarchyEnumerator;
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.prototype.NodeProto;
import com.sun.electric.database.prototype.PortOriginal;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.text.TextUtils;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.Geometric;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.topology.RTBounds;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.database.variable.Variable;
import com.sun.electric.technology.*;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.user.ErrorLogger;

import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.*;

/**
 * This is the "quick" DRC which does full hierarchical examination of the circuit.
 * <P>
 * The "quick" DRC works as follows:
 *    It first examines every primitive node and arc in the cell
 *        For each layer on these objects, it examines everything surrounding it, even in subcells
 *            R-trees are used to limit search.
 *            Where cell instances are found, the contents are examined recursively
 *    It next examines every cell instance in the cell
 *        All other instances within the surrounding area are considered
 *            When another instance is found, the two instances are examined for interaction
 *                A cache is kept of instance pairs in specified configurations to speed-up arrays
 *            All objects in the other instance that are inside the bounds of the first are considered
 *                The other instance is hierarchically examined to locate primitives in the area of consideration
 *            For each layer on each primitive object found in the other instance,
 *                Examine the contents of the first instance for interactions about that layer
 * <P>
 * Since Electric understands connectivity, it uses this information to determine whether two layers
 * are connected or not.  However, if such global connectivity is propagated in the standard Electric
 * way (placing numbers on exports, descending into the cell, and pulling the numbers onto local networks)
 * then it is not possible to decompose the DRC for multiple processors, since two different processors
 * may want to write global network information on the same local networks at once.
 * <P>
 * To solve this problem, the "quick" DRC determines how many instances of each cell exist.  For every
 * network in every cell, an array is built that is as large as the number of instances of that cell.
 * This array contains the global network number for that each instance of the cell.  The algorithm for
 * building these arrays is quick (1 second for a million-transistor chip) and the memory requirement
 * is not excessive (8 megabytes for a million-transistor chip).  It uses the CheckInst and CheckProto
 * objects.
 * @author  Steve Rubin, Gilda Garreton
 */

public class Quick
{
	private HashMap<NodeInst,CheckInst> checkInsts = null;
    private HashMap<Cell,CheckProto> checkProtos = null;
	private HashMap<Network,Integer[]> networkLists = null;
	private HashMap<Layer,DRCTemplate> minAreaLayerMap = new HashMap<Layer,DRCTemplate>();    // For minimum area checking
	private HashMap<Layer,DRCTemplate> enclosedAreaLayerMap = new HashMap<Layer,DRCTemplate>();    // For enclosed area checking
    private HashMap<Layer,DRCTemplate> spacingLayerMap = new HashMap<Layer,DRCTemplate>();    // to detect holes using the area function
    private HashMap<Layer,DRCTemplate> slotSizeLayerMap = new HashMap<Layer,DRCTemplate>();    // For max length checking
    private DRC.CheckDRCJob job; // Reference to running job
	private HashMap<Cell,Cell> cellsMap = new HashMap<Cell,Cell>(); // for cell caching
    private HashMap<Geometric,Geometric> nodesMap = new HashMap<Geometric,Geometric>(); // for node caching
    private GeometryHandler.GHMode mergeMode = GeometryHandler.GHMode.ALGO_SWEEP; // .ALGO_QTREE;
    private Map<Layer,NodeInst> od2Layers = new HashMap<Layer,NodeInst>(3);  /** to control OD2 combination in the same die according to foundries */

	public Quick(DRC.CheckDRCJob j, GeometryHandler.GHMode mode)
	{
		this.job = j;
        this.mergeMode = mode;
	}

    private List<InstanceInter> instanceInteractionList = new ArrayList<InstanceInter>();

	/** a NodeInst that is too tiny for its connection. */		private NodeInst tinyNodeInst;
	/** the other Geometric in "tiny" errors. */				private Geometric tinyGeometric;
	/** for tracking the time of good DRC. */					private HashSet<Cell> goodSpacingDRCDate = new HashSet<Cell>();
	/** for tracking cells that need to clean good DRC vars */	private HashSet<Cell> cleanSpacingDRCDate = new HashSet<Cell>();
	/** for tracking the time of good DRC. */					private HashSet<Cell> goodAreaDRCDate = new HashSet<Cell>();
	/** for tracking cells that need to clean good DRC vars */	private HashSet<Cell> cleanAreaDRCDate = new HashSet<Cell>();
	/** Top cell for DRC */                                     private Cell topCell;
    /** Miscellanous data for DRC */                            private DRC.ReportInfo reportInfo;

//    /* for figuring out which layers are valid for DRC */
    // To speed up the layer process
    private ValidationLayers validLayers;

    public static ErrorLogger checkDesignRules(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,
                                               Rectangle2D bounds)
    {
        if (errorLog == null) errorLog = DRC.getDRCErrorLogger(true, false, null);
        return checkDesignRules(errorLog, cell, geomsToCheck, validity, bounds, null,
                GeometryHandler.GHMode.ALGO_SWEEP, false);
    }

    /**
	 * This is the entry point for DRC.
	 *
	 * Method to do a hierarchical DRC check on cell "cell".
	 * If "count" is zero, check the entire cell.
	 * If "count" is nonzero, only check that many instances (in "nodesToCheck") and set the
	 * entry in "validity" TRUE if it is DRC clean.
	 * @param bounds if null, check entire cell. If not null, only check area in bounds.
     * @param drcJob
	 * @param onlyArea
     * @return ErrorLogger containing the information
	 */
	public static ErrorLogger checkDesignRules(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,
                                               Rectangle2D bounds, DRC.CheckDRCJob drcJob, GeometryHandler.GHMode mode, boolean onlyArea)
	{
		Quick q = new Quick(drcJob, mode);
        return q.doCheck(errorLog, cell, geomsToCheck, validity, bounds, onlyArea);
	}

    // returns the number of errors found
	private ErrorLogger doCheck(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,
                                Rectangle2D bounds, boolean onlyArea)
	{
		// Check if there are DRC rules for particular tech
        Technology tech = cell.getTechnology();
		DRCRules rules = DRC.getRules(tech);

        // if checking specific instances, adjust options and processor count
        int count = (geomsToCheck != null) ? geomsToCheck.length : 0;

        reportInfo = new DRC.ReportInfo(errorLog, tech, (count > 0));
        ErrorLogger errorLogger = errorLog;

        // caching bits
        System.out.println("Running DRC with " + DRC.explainBits(reportInfo.activeSpacingBits));

		// Nothing to check for this particular technology
		if (rules == null || rules.getNumberOfRules() == 0) return errorLogger;

	    topCell = cell; /* Especially important for minArea checking */

		// cache valid layers for this technology
        validLayers = new ValidationLayers(reportInfo.errorLogger, topCell, rules);

		// clean out the cache of instances
	    instanceInteractionList.clear();

		// determine maximum DRC interaction distance
//		worstInteractionDistance = DRC.getWorstSpacingDistance(tech, -1);

	    // determine if min area must be checked (if any layer got valid data)
	    minAreaLayerMap.clear();
	    enclosedAreaLayerMap.clear();
        spacingLayerMap.clear();
        slotSizeLayerMap.clear();
	    cellsMap.clear();
	    nodesMap.clear();

	    // No incremental neither per Cell
	    if (!DRC.isIgnoreAreaChecking() && reportInfo.errorTypeSearch != DRC.DRCCheckMode.ERROR_CHECK_CELL)
	    {
		    for(Iterator<Layer> it = tech.getLayers(); it.hasNext(); )
			{
				Layer layer = it.next();

				// Storing min areas
				DRCTemplate minAreaRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.MINAREA);
				if (minAreaRule != null)
					minAreaLayerMap.put(layer, minAreaRule);

				// Storing enclosed areas
				DRCTemplate enclosedAreaRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.MINENCLOSEDAREA);
				if (enclosedAreaRule != null)
					enclosedAreaLayerMap.put(layer, enclosedAreaRule);

                // Storing spacing rules
                DRCTemplate spaceRule = DRC.getSpacingRule(layer, null, layer, null, true, -1, -1.0, -1.0); // UCONSPA, CONSPA or SPACING
                if (spaceRule != null)
                    spacingLayerMap.put(layer, spaceRule);

                // Storing slot sizes
				DRCTemplate slotRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.SLOTSIZE);
				if (slotRule != null)
					slotSizeLayerMap.put(layer, slotRule);
			}
            if (onlyArea)
            {
                int numErrors = checkMinAreaSlow(cell);
                if (numErrors == 0)
                    goodAreaDRCDate.add(cell);
                else
                    cleanAreaDRCDate.add(cell);
                System.out.println("Missing update in dates");
                return errorLogger;
            }
        }

		// initialize all cells for hierarchical network numbering
		checkProtos = new HashMap<Cell,CheckProto>();
		checkInsts = new HashMap<NodeInst,CheckInst>();

		// initialize cells in tree for hierarchical network numbering
		Netlist netlist = cell.getNetlist();
		CheckProto cp = checkEnumerateProtos(cell, netlist);

		// now recursively examine, setting information on all instances
		cp.hierInstanceCount = 1;
		reportInfo.checkTimeStamp = 0;
		checkEnumerateInstances(cell);

		// now allocate space for hierarchical network arrays
		//int totalNetworks = 0;
		networkLists = new HashMap<Network,Integer[]>();
        for (Map.Entry<Cell,CheckProto> e : checkProtos.entrySet())
		{
			Cell libCell = e.getKey();
			CheckProto subCP = e.getValue();
			if (subCP.hierInstanceCount > 0)
			{
				// allocate net number lists for every net in the cell
				for(Iterator<Network> nIt = subCP.netlist.getNetworks(); nIt.hasNext(); )
				{
					Network net = nIt.next();
					Integer [] netNumbers = new Integer[subCP.hierInstanceCount];
					for(int i=0; i<subCP.hierInstanceCount; i++) netNumbers[i] = new Integer(0);
					networkLists.put(net, netNumbers);
					//totalNetworks += subCP.hierInstanceCount;
				}
			}
			for(Iterator<NodeInst> nIt = libCell.getNodes(); nIt.hasNext(); )
			{
				NodeInst ni = nIt.next();
				NodeProto np = ni.getProto();
				if (!ni.isCellInstance()) continue;

				// ignore documentation icons
				if (ni.isIconOfParent()) continue;

				CheckInst ci = checkInsts.get(ni);
				CheckProto ocp = getCheckProto((Cell)np);
				ci.offset = ocp.totalPerCell;
			}
			reportInfo.checkTimeStamp++;
			for(Iterator<NodeInst> nIt = libCell.getNodes(); nIt.hasNext(); )
			{
				NodeInst ni = nIt.next();
				NodeProto np = ni.getProto();
				if (!ni.isCellInstance()) continue;

				// ignore documentation icons
				if (ni.isIconOfParent()) continue;

				CheckProto ocp = getCheckProto((Cell)np);
				if (ocp.timeStamp != reportInfo.checkTimeStamp)
				{
					CheckInst ci = checkInsts.get(ni);
					ocp.timeStamp = reportInfo.checkTimeStamp;
					ocp.totalPerCell += subCP.hierInstanceCount * ci.multiplier;
				}
			}
		}

		// now fill in the hierarchical network arrays
		reportInfo.checkTimeStamp = 0;
		int checkNetNumber = 1;

		HashMap<Network,Integer> enumeratedNets = new HashMap<Network,Integer>();
		for(Iterator<Network> nIt = cp.netlist.getNetworks(); nIt.hasNext(); )
		{
			Network net = nIt.next();
			enumeratedNets.put(net, new Integer(checkNetNumber));
			checkNetNumber++;
		}
		checkEnumerateNetworks(cell, cp, 0, enumeratedNets);

		if (count <= 0)
			System.out.println("Found " + checkNetNumber + " networks");

		// now search for DRC exclusion areas
        reportInfo.exclusionMap.clear();
		accumulateExclusion(cell);

		// now do the DRC
        int logsFound = 0;
//        int totalErrors = 0;

		if (count == 0)
		{