route.java

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

				for (RouteNode node2 = node.sameLast; node2 != null; node2 = node2.sameLast)
				{
					if (node2.firstPort != null)
					{
						portsBelow = true;
						break;
					}
				}

				// if none found below, any ports in this row only going down
				if (!portsBelow && node.firstPort != node.lastPort)
				{
					for (RoutePort port = node.firstPort; port != null; port = port.next)
					{
						int direct = GetNetlist.getLeafPortDirection((PortProto)port.port.port);
						if ((direct & GetNetlist.PORTDIRDOWN) != 0 && (direct & GetNetlist.PORTDIRUP) == 0)
						{
							portsBelow = true;
							break;
						}
					}
				}

				// do not add if only one port unless an export
				if (!portsAbove && !portsBelow)
				{
					if (node.firstPort == node.lastPort)
					{
						GetNetlist.SCPort xPort;
						for (xPort = cell.ports; xPort != null; xPort = xPort.next)
						{
							if (xPort.node.ports.extNode == node.extNode)
								break;
						}
						if (xPort == null) continue;

						// if top row, put in above channel
						if (row.number != 0 && row.next == null)
							portsAbove = true;
					}
				}

				// assign ports to channel
				for (RoutePort port = node.firstPort; port != null; port = port.next)
				{
					if ((port.flags & ROUTESEEN) != 0) continue;

					// check how ports can be connected to
					int direct = GetNetlist.getLeafPortDirection((PortProto)port.port.port);

					// for ports both up and down
					if ((direct & GetNetlist.PORTDIRUP) != 0 && (direct & GetNetlist.PORTDIRDOWN) != 0)
					{
						if (!portsAbove)
						{
							// add to channel below
							addPortToChannel(port, node.extNode, channels, row.number);
						} else
						{
							if (portsBelow)
							{
								// add to channel where closest
								int offset = 0;
								if (nearestPort(port, node, row.number, cell) > 0)
								{
									offset = 1;
								}
								addPortToChannel(port, node.extNode, channels, row.number + offset);
							} else
							{
								// add to channel above
								addPortToChannel(port, node.extNode, channels, row.number + 1);
							}
						}
						port.flags |= ROUTESEEN;
					}

					// for ports only up
					else if ((direct & GetNetlist.PORTDIRUP) != 0)
					{
						// add to channel above
						addPortToChannel(port, node.extNode, channels, row.number + 1);
						port.flags |= ROUTESEEN;
					}

					// for ports only down
					else if ((direct & GetNetlist.PORTDIRDOWN) != 0)
					{
						// add to channel below
						addPortToChannel(port, node.extNode, channels, row.number);
						port.flags |= ROUTESEEN;
					}

					// ports left
					else if ((direct & GetNetlist.PORTDIRLEFT) != 0)
					{
						addLateralFeed(port, channels, portsAbove, portsBelow, cell);
					}

					// ports right
					else if ((direct & GetNetlist.PORTDIRRIGHT) != 0)
					{
						addLateralFeed(port, channels, portsAbove, portsBelow, cell);
					} else
					{
						System.out.println("ERROR - no direction for " + port.place.cell.name + " port " +
							((PortProto)port.port.port).getName());
						port.flags |= ROUTESEEN;
					}
				}
			}
		}
	}

	/**
	 * Method to return the offset to the row which has the closest port to the indicated port.
	 * The offset is +1 for every row above, -1 for every row below.
	 * @param port pointer to current port.
	 * @param node pointer to reference node.
	 * @param rowNum row number of port.
	 * @param cell pointer to parent cell.
	 * @return offset of row of closest port.
	 */
	private double nearestPort(RoutePort port, RouteNode node, int rowNum, GetNetlist.SCCell cell)
	{
		double minDist = Double.MAX_VALUE;
		double whichRow = 0;
		double xPos1;
		if ((rowNum % 2) != 0)
		{
			xPos1 = port.place.xPos + port.place.cell.size -
				port.port.xPos;
		} else
		{
			xPos1 = port.place.xPos + port.port.xPos;
		}

		// find closest above
		double offset = 0;
		for (RouteNode nNode = node.sameNext; nNode != null; nNode = nNode.sameNext)
		{
			offset++;
			for (RoutePort nPort = nNode.firstPort; nPort != null; nPort = nPort.next)
			{
				double dist = Math.abs(offset) * cell.placement.avgHeight * 2;
				double xPos2;
				if (((rowNum + offset) % 2) != 0)
				{
					xPos2 = nPort.place.xPos + nPort.place.cell.size - nPort.port.xPos;
				} else
				{
					xPos2 = nPort.place.xPos + nPort.port.xPos;
				}
				dist += Math.abs(xPos2 - xPos1);
				if (dist < minDist)
				{
					minDist = dist;
					whichRow = offset;
				}
			}
		}

		// check below
		offset = 0;
		for (RouteNode nNode = node.sameLast; nNode != null; nNode = nNode.sameLast)
		{
			offset--;
			for (RoutePort nPort = nNode.firstPort; nPort != null; nPort = nPort.next)
			{
				double dist = Math.abs(offset) * cell.placement.avgHeight * 2;
				double xPos2;
				if (((rowNum + offset) % 2) != 0)
				{
					xPos2 = nPort.place.xPos + nPort.place.cell.size - nPort.port.xPos;
				} else
				{
					xPos2 = nPort.place.xPos + nPort.port.xPos;
				}
				dist += Math.abs(xPos2 - xPos1);
				if (dist < minDist)
				{
					minDist = dist;
					whichRow = offset;
				}
			}
		}

		return whichRow;
	}

	/**
	 * Method to add the indicated port to the indicated channel.
	 * Create node for that channel if it doesn't already exist.
	 * @param port pointer to route port.
	 * @param extNode value of reference extracted node.
	 * @param channels start of channel list.
	 * @param chanNum number of wanted channel.
	 */
	private void addPortToChannel(RoutePort port, GetNetlist.ExtNode extNode, RouteChannel channels, int chanNum)
	{
		// get correct channel
		RouteChannel channel = channels;
		for (int i = 0; i < chanNum; i++)
			channel = channel.next;

		// check if node already exists for this channel
		RouteChNode node;
		for (node = channel.nodes; node != null; node = node.next)
		{
			if (node.extNode == extNode) break;
		}
		if (node == null)
		{
			node = new RouteChNode();
			node.extNode = extNode;
			node.number = 0;
			node.firstPort = null;
			node.lastPort = null;
			node.channel = channel;
			node.flags = ROUTESEEN;
			node.sameNext = null;
			node.sameLast = null;
			node.next = channel.nodes;
			channel.nodes = node;

			// resolve any references to other channels
			// check previous channels
			for (RouteChannel nchan = channel.last; nchan != null; nchan = nchan.last)
			{
				RouteChNode nNode;
				for (nNode = nchan.nodes; nNode != null; nNode = nNode.next)
				{
					if (nNode.extNode == extNode)
					{
						nNode.sameNext = node;
						node.sameLast = nNode;
						break;
					}
				}
				if (nNode != null) break;
			}

			// check later channels
			for (RouteChannel nchan = channel.next; nchan != null; nchan = nchan.next)
			{
				RouteChNode nNode;
				for (nNode = nchan.nodes; nNode != null; nNode = nNode.next)
				{
					if (nNode.extNode == extNode)
					{
						nNode.sameLast = node;
						node.sameNext = nNode;
						break;
					}
				}
				if (nNode != null) break;
			}
		}

		// add port to node
		RouteChPort nPort = new RouteChPort();
		nPort.port = port;
		nPort.node = node;
		nPort.xPos = 0;
		nPort.flags = 0;
		nPort.next = null;
		nPort.last = node.lastPort;
		if (node.lastPort != null)
		{
			node.lastPort.next = nPort;
		} else
		{
			node.firstPort = nPort;
		}
		node.lastPort = nPort;
	}

	/**
	 * Method to add a lateral feed for the port indicated.
	 * Add a "stitch" if port of same type adjecent, else add full lateral feed.
	 * Add to appropriate channel(s) if full feed.
	 * @param port pointer to port in question.
	 * @param channels list of channels.
	 * @param portsAbove true if ports above.
	 * @param portsBelow true if ports below.
	 * @param cell pointer to parent cell.
	 */
	private void addLateralFeed(RoutePort port, RouteChannel channels,
		boolean portsAbove, boolean portsBelow, GetNetlist.SCCell cell)
	{
		int direct = GetNetlist.getLeafPortDirection((PortProto)port.port.port);

		// determine if stitch
		Place.NBPlace nPlace = null;
		int sDirect = 0;
		if ((direct & GetNetlist.PORTDIRLEFT) != 0)
		{
			if ((port.node.row.number % 2) != 0)
			{
				// odd row
				for (nPlace = port.place.next; nPlace != null; nPlace = nPlace.next)
				{
					if (nPlace.cell.type == GetNetlist.LEAFCELL) break;
				}
			} else
			{
				// even row
				for (nPlace = port.place.last; nPlace != null; nPlace = nPlace.last)
				{
					if (nPlace.cell.type == GetNetlist.LEAFCELL) break;
				}
			}
			sDirect = GetNetlist.PORTDIRRIGHT;
		} else
		{
			if ((port.node.row.number % 2) != 0)
			{
				// odd row
				for (nPlace = port.place.last; nPlace != null; nPlace = nPlace.last)
				{
					if (nPlace.cell.type == GetNetlist.LEAFCELL) break;
				}
			} else
			{
				// even row
				for (nPlace = port.place.next; nPlace != null; nPlace = nPlace.next)
				{
					if (nPlace.cell.type == GetNetlist.LEAFCELL) break;
				}
			}
			sDirect = GetNetlist.PORTDIRLEFT;
		}
		if (nPlace != null)
		{
			// search for same port with correct direction
			RoutePort port2;
			for (port2 = port.next; port2 != null; port2 = port2.next)
			{
				if (port2.place == nPlace &&
					GetNetlist.getLeafPortDirection((PortProto)port2.port.port) == sDirect)
						break;
			}
			if (port2 != null)
			{
				// stitch feed
				port.flags |= ROUTESEEN;
				port2.flags |= ROUTESEEN;
				Place.NBPlace sPlace = new Place.NBPlace();
				sPlace.cell = null;
				GetNetlist.SCNiTree sInst = new GetNetlist.SCNiTree("Stitch", GetNetlist.STITCH);
				sPlace.cell = sInst;

				// save two ports
				GetNetlist.SCNiPort sPort = new GetNetlist.SCNiPort(sInst);
				sPort.port = port;
				GetNetlist.SCNiPort sPort2 = new GetNetlist.SCNiPort(sInst);
				sPort2.port = port2;

				// insert in place
				if ((direct & GetNetlist.PORTDIRLEFT) != 0)
				{
					if ((port.node.row.number % 2) != 0)
					{
						sPlace.last = port.place;
						sPlace.next = port.place.next;
						if (sPlace.last != null) sPlace.last.next = sPlace;
						if (sPlace.next != null) sPlace.next.last = sPlace;
					} else
					{
						sPlace.last = port.place.last;
						sPlace.next = port.place;
						if (sPlace.last != null) sPlace.last.next = sPlace;
						if (sPlace.next != null) sPlace.next.last = sPlace;
					}
				} else
				{
					if ((port.node.row.number % 2) != 0)
					{
						sPlace.last = port.place.last;
						sPlace.next = port.place;
						if (sPlace.last != null) sPlace.last.next = sPlace;
						if (sPlace.next != null) sPlace.next.last = sPlace;
					} else
					{
						sPlace.last = port.place;
						sPlace.next = port.place.next;
						if (sPlace.last != null) sPlace.last.next = sPlace;
						if (sPlace.next != null) sPlace.next.last = sPlace;
					}
				}
				return;
			}
		}

		// full lateral feed
		port.flags |= ROUTESEEN;
		Place.NBPlace sPlace = new Place.NBPlace();
		sPlace.cell = null;
		GetNetlist.SCNiTree sInst = new GetNetlist.SCNiTree("Lateral Feed", GetNetlist.LATERALFEED);
		sInst.size = SilComp.getFeedThruSize();
		sPlace.cell = sInst;

		// save port
		GetNetlist.SCNiPort sPort = new GetNetlist.SCNiPort(sInst);
		sPort.xPos = SilComp.getFeedThruSize() / 2;

		// create new route port
		RoutePort nPort = new RoutePort();
		nPort.place = port.place;
		nPort.port = port.port;
		nPort.node = port.node;
		nPort.flags = 0;
		nPort.last = null;
		nPort.next = null;
		sPort.port = nPort;

		// insert in place
		if ((direct & GetNetlist.PORTDIRLEFT) != 0)
		{
			if ((port.node.row.number % 2) != 0)
			{
				sPlace.last = port.place;
				sPlace.next = port.place.next;
			} else
			{
				sPlace.last = port.place.last;
				sPlace.next = port.place;
			}
		} else
		{
			if ((port.node.row.number % 2) != 0)
			{
				sPlace.last = port.place.last;
				sPlace.next = port.place;
			} else
			{
				sPlace.last = port.place;
				sPlace.next = port.place.next;
			}
		}
		if (sPlace.last != null)
		{
			sPlace.last.next = sPlace;
		} else
		{
			port.node.row.row.start = sPlace;
		}
		if (sPlace.next != null)
		{
			sPlace.next.last = sPlace;
		} else
		{
			port.node.row.row.end = sPlace;
		}
		resolveNewXPos(sPlace, port.node.row.row);

		// change route port to lateral feed
		port.place = sPlace;
		port.port = sPort;

		// channel assignment of lateral feed
		if (!portsAbove)
		{
			// add to channel below
			addPortToChannel(port, port.node.extNode, channels, port.node.row.number);
		} else
		{
			if (portsBelow)
			{
				// add to channel where closest
				int offset = 0;
				if (nearestPort(port, port.node, port.node.row.number, cell) > 0)
				{
					offset = 1;