libreda-pnr 0.0.4

// Copyright (c) 2020-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Tools for inserting tie-cells to drive constant nets.


use crate::db;
use db::traits::*;
use db::{Direction, CoordinateType, TerminalId};

use num_traits::{PrimInt, NumCast};

/// Insert tie cells and connect unconnected LOW and HIGH nets.
///
/// Tie-cells are placed such that the maximal manhattan distance
/// to the sinks is kept below `max_distance`.
#[derive(Debug, Clone)]
pub struct SimpleTieCellInsertionEngine {

    /// Name of the tie-low cell to be used for buffering constant LOW nets.
    pub tie_cell_low: String,
    /// Name of the tie-high cell to be used for buffering constant HIGH nets.
    pub tie_cell_high: String,
    /// Maximal number of cells that should be driven by a tie-cell cell.
    /// Must be larger than `1`.
    pub max_fanout: u32,
    /// Maximal manhattan distance from the tie-cell to the attached sink.
    pub max_distance: db::Coord,
}


impl SimpleTieCellInsertionEngine {

    /// Insert tie cells to drive the sinks which are attached to this net.
    /// The net must be either the constant LOW or HIGH net.
    ///
    /// A tie cell is usually used to drive a cluster of many inputs. The way the
    /// clusters are formed depends on the locations of the inputs such that the wiring
    /// can be minimized from tie-cells to inputs but also the additional space required by tie-cells
    /// is reasonable (instead of placing a tie-cell for every input).
    pub fn insert_tie_cells_on_net<LN: NetlistEdit + LayoutEdit>(
        &self,
        chip: &mut LN,
        net: &LN::NetId,
    ) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
        where LN::Coord: PrimInt {
        // Check if the net is a special net (LOW or HIGH).
        if !chip.is_constant_net(&net) {
            let parent_name = chip.cell_name(&chip.parent_cell_of_net(&net));
            log::warn!("Net '{:?}' in '{}' is neither a constant LOW nor HIGH net.", &net, parent_name);
        }

        // Find the sinks of the net.
        let mut sinks = vec![];

        for t in chip.each_terminal_of_net(&net) {
            // A pin of the parent cell is considered to be a source when it's direction is 'INPUT',
            // however a pin instance that connects to a child instance is considered a sink when it's direction is 'INPUT'.
            match &t {
                TerminalId::PinId(p) => {
                    match chip.pin_direction(p) {
                        Direction::Output => sinks.push(t),
                        d => {
                            let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&p));
                            let pin_name = chip.pin_name(p);
                            panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an output)", pin_name, cell_name, d)
                        }
                    }
                }
                TerminalId::PinInstId(p) => {
                    match chip.pin_direction(&chip.template_pin(p)) {
                        Direction::Input => sinks.push(t),
                        d => {
                            let pin = chip.template_pin(p);
                            let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&pin));
                            let pin_name = chip.pin_name(&pin);
                            panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an input)", pin_name, cell_name, d)
                        }
                    }
                }
            }
        }

        log::debug!("Number of sinks: {}", sinks.len());

        self.insert_tie_cells(chip, &sinks)
    }

    /// All terminals must be in the same parent cell.
    /// Returns a vector of all added tie-cell instances and all added nets.
    fn insert_tie_cells<LN: NetlistEdit + LayoutEdit>(
        &self,
        chip: &mut LN,
        signal_sinks: &Vec<TerminalId<LN>>,
    ) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
        where LN::Coord: PrimInt {
        log::debug!("Insert tie-cells for {} sinks.", signal_sinks.len());

        // Store all nets and cells that are added in this step and return them later.
        let mut added_tie_cells = vec![];
        let mut added_nets = vec![];

        if signal_sinks.is_empty() {
            return Ok((added_tie_cells, added_nets));
        }


        let parent_cell = match &signal_sinks[0] {
            TerminalId::PinId(p) => chip.parent_cell_of_pin(p),
            TerminalId::PinInstId(p) => chip.parent_cell(&chip.parent_of_pin_instance(p))
        };


        // Sanity check: The source and all sinks must be connected to the same net.
        let source_net = chip.net_of_terminal(&signal_sinks[0]);
        if source_net.is_none() {
            log::error!("Sink terminal is not connected to any net.");
            // TODO: Pass a `Result::Err` instead o panicking?
            panic!("Source terminal is not connected to any net.");
        }

        {
            let is_connected_to_correct_nets = signal_sinks.iter()
                .all(|sink| chip.net_of_terminal(sink) == source_net);
            if !is_connected_to_correct_nets {
                log::error!("Sinks are not all connected to the same net as the source.");
                panic!("Sinks are not all connected to the same net as the source.");
            }
        }

        let source_net = source_net.unwrap();
        assert!(chip.is_constant_net(&source_net), "Net must be either constant LOW or HIGH for tie-cell insertion.");

        let net_value = source_net == chip.net_one(&parent_cell);
        let tie_cell_name = if net_value {
            &self.tie_cell_high
        } else {
            &self.tie_cell_low
        };
        // Find tie-cell cell to be used.
        log::info!("Use tie-cell '{}'.", &tie_cell_name);
        let tie_cell = chip.cell_by_name(tie_cell_name)
            .expect("Tie-cell not found.");


        // Detect inputs and the outputs of the tie-cell cell.
        let inputs: Vec<_> = chip.each_pin(&tie_cell)
            .filter(|pin| chip.pin_direction(&pin).is_input())
            .collect();
        assert_eq!(inputs.len(), 0, "Tie-cell must have no input pins.");

        let outputs: Vec<_> = chip.each_pin(&tie_cell)
            .filter(|pin| chip.pin_direction(&pin).is_output())
            .collect();
        assert_eq!(outputs.len(), 1, "Tie-cell must have exactly one output pin.");

        let tie_cell_output = outputs[0].clone();

        // Find locations of terminals.
        let terminal_location = |t: &TerminalId<LN>| {
            match t {
                TerminalId::PinId(_t) => {
                    // TODO: Find the location of the pin shape.
                    db::Point::zero()
                }
                TerminalId::PinInstId(t) => {
                    let inst = chip.parent_of_pin_instance(t);
                    let tf = chip.get_transform(&inst);
                    // Assume that the physical pin is close to the origin of the cell.
                    // This is good enough only for small standard-cells, not for big macro blocks.
                    let location = tf.transform_point(db::Point::zero());
                    location
                }
            }
        };

        // Build clusters that are driven by the same tie-cell.
        let clusters = {
            // Find sink locations.
            let sink_locations: Vec<_> = signal_sinks.iter()
                .map(terminal_location)
                .collect();

            // Find clusters.
            let (cluster_ids, num_clusters) = find_clusters(
                &sink_locations,
                self.max_fanout,
                NumCast::from(self.max_distance).unwrap());

            // Create a nested list of terminals for each cluster.
            let mut clusters = vec![vec![]; num_clusters as usize];
            for (i, cluster_id) in cluster_ids.iter().enumerate() {
                clusters[*cluster_id as usize].push((signal_sinks[i].clone(), sink_locations[i]));
            }
            clusters
        };

        // Create a tie-cell for each cluster.
        let mut name_counter = 0; // Counter for unique names of tie-cell instances.
        for cluster in clusters {
            let (sinks, positions): (Vec<_>, Vec<_>) = cluster.into_iter().unzip();
            let center = center_of_mass(&positions);

            // Create name for the tie-cell instance.
            let instance_name = loop {
                let name = format!("_tie_cell_{}", name_counter);
                name_counter += 1;
                if chip.cell_instance_by_name(&parent_cell, &name).is_none() {
                    break name;
                }
            };

            let tie_cell_inst = chip.create_cell_instance(&parent_cell, &tie_cell, Some(instance_name.into()));
            // Create output net.
            let new_net = chip.create_net(&parent_cell, None);

            // Connect output of the tie-cell to the buffered net.
            let tie_cell_output_pin = chip.pin_instance(&tie_cell_inst, &tie_cell_output);
            chip.connect_pin_instance(&tie_cell_output_pin, Some(new_net.clone()));

            // Set the location of the tie-cell.
            chip.set_transform(&tie_cell_inst, db::SimpleTransform::translate(center));

            // Connect the sinks to the tie_cell output.
            for sink in &sinks {
                let old_net = chip.connect_terminal(sink, Some(new_net.clone()));
                debug_assert_eq!(old_net.as_ref(), Some(&source_net), "Sink is expected to be connected to the source net.");
            }

            added_tie_cells.push(tie_cell_inst);
            added_nets.push(new_net);

        }
        Ok((added_tie_cells, added_nets))
    }
}


/// Group points together to clusters and return a vector with the cluster ID for each point and the number of clusters.
/// The clusters are formed as follows:
/// 1) Sort the points by (x, y).
/// 2) As long as there's an unassigned point: take the next unassigned point `p` and put it into the new cluster `c`.
/// 3) Take the closest point to the center of the bounding-box around `c`. If adding `p` to `c` does not enlarge the bounding box
/// around `c` beyond `max_cluster_span` then add `p` to `c` and repeat 3) otherwise go to 2).
///
/// * `max_cluster_size`: Maximal number of points in cluster.
/// * `max_cluster_span`: Maximal width and height of the bounding box around the cluster.
fn find_clusters<C: CoordinateType + PrimInt>(points: &Vec<db::Point<C>>,
                                              max_cluster_size: u32,
                                              max_cluster_span: C) -> (Vec<u32>, u32) {
    // For each point store the original index and the cluster ID.
    // The index used to map back to the original points after sorting.
    let mut points_with_cluster_id: Vec<(db::Point<_>, usize, u32)> = points.iter()
        .enumerate()
        .map(|(idx, p)| (*p, idx, 0))
        .collect();
    // Sort by locations.
    points_with_cluster_id.sort_by_key(|(p, _, _)| (p.x, p.y));

    let mut cluster_id = 0u32;
    // While there is a point that does not belong to a cluster
    // take the first one (sorted by x and y) and use it as a start
    // of the cluster.

    let mut current_cluster_points = vec![];

    // Find the first point without assigned cluster.
    while let Some((first_point_idx, _)) = points_with_cluster_id.iter()
        .enumerate()
        .find(|(_pos, (_, _, cluster))| *cluster == 0) {
        cluster_id += 1;

        // Assign the cluster ID.
        points_with_cluster_id[first_point_idx].2 = cluster_id;

        let start = points_with_cluster_id[first_point_idx].0;

        let mut bbox = db::Rect::new(start, start);

        current_cluster_points.clear();
        current_cluster_points.push(start);
        // Find closest neighbour.
        for _ in 1..max_cluster_size {

            // Compute center of mass of the cluster.
            let center = center_of_mass(&current_cluster_points);

            let closest = points_with_cluster_id.iter()
                .enumerate()
                .filter(|(_, (_, _, cluster))| *cluster == 0) // Take only unassigned sinks.
                .filter(|(_, (p, _, _))| {
                    let new_bbox = bbox.add_point(*p);
                    new_bbox.height() < max_cluster_span && new_bbox.width() < max_cluster_span
                })
                .min_by_key(|(_, (pos, _, _))| (center - *pos).norm1())
                .map(|(idx, _)| idx);

            if let Some(closest) = closest {
                points_with_cluster_id[closest].2 = cluster_id;
                let p = points_with_cluster_id[closest].0;
                current_cluster_points.push(p);
                // Update the cluster bounding box.
                bbox = bbox.add_point(p);
            } else {
                // No unassigned node found.
                break;
            }
        }
    }

    let num_clusters = cluster_id;

    let mut result = vec![0u32; points_with_cluster_id.len()];
    for (_p, index, cluster_id) in points_with_cluster_id {
        result[index] = cluster_id - 1; // `0` meant 'no cluster'
    }

    (result, num_clusters)
}

/// Compute the center of mass of a list of points.
fn center_of_mass<C: PrimInt>(points: &Vec<db::Point<C>>) -> db::Point<C> {
    // Sum up all points and divide by number of points.
    points.iter()
        .fold(db::Point::zero(), |a, b| a + b)
        / NumCast::from(points.len()).unwrap()
}