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

//! Legalization (or detail-placement) of globally placed standard cells.
//! Legalization involves snapping the standard-cells to the rows in an overlap-free manner.

use libreda_db::prelude as db;
use std::collections::{HashMap, HashSet};

use log::{debug, info, warn};
use db::{L2NEdit, NetlistBase};

/// Find legal positions and move the cells to those.
///
/// * `legalizer`: Legalization engine that finds the legal positions of the movable cells.
/// * `top_cell`: The cell whose content should be legalized.
/// * `core_area`: The region to be used for the placement.
/// * `cell_outlines`: Abutment boxes of the standard-cells.
/// * `fixed_instances`: Cell instanced that can be moved.
pub fn legalize<L, LN>(legalizer: &L,
                       chip: &mut LN,
                       top_cell: &LN::CellId,
                       core_area: &db::SimplePolygon<LN::Coord>,
                       cell_outlines: &HashMap<LN::CellId, db::Rect<LN::Coord>>,
                       movable_instances: &HashSet<LN::CellInstId>)
    where L: SimpleStdCellLegalizer<LN>,
          LN: L2NEdit<Coord=db::Coord>,
{

    // Extract initial positions from the layout.
    // Convert transformations to simple displacements.
    let initial_positions = chip.each_cell_instance(top_cell)
        .map(|inst| {
            let tf = chip.get_transform(&inst);
            let point = tf.transform_point(db::Point::zero());
            (inst, point)
        })
        .collect();

    // Compute legal positions.
    let legal_positions = legalizer.find_legal_positions(
        chip,
        top_cell,
        core_area,
        cell_outlines,
        &initial_positions,
        movable_instances,
    );

    // Apply legal positions.
    let mut fixed_instance_moves = 0; // Count how many fixed instance the legalizer tries to move.
    for (inst, tf) in legal_positions {
        if movable_instances.contains(&inst) {
            chip.set_transform(&inst, tf);
        } else {
            // Don't move fixed instances.
            fixed_instance_moves += 1;
        }
    }

    if fixed_instance_moves > 0 {
        log::warn!("Legalizer tried to move fixed instances: {}", fixed_instance_moves);
    }
}

/// Trait for a legalizer that is able to put globally placed standard-cells
/// into legal positions. A legal position must for instance be overlap free, snapped to a standard-cell row
/// and rotated or flipped correctly such that the power rails and wells are properly oriented.
pub trait SimpleStdCellLegalizer<N: NetlistBase> {
    /// Find legal positions and rotations for the cells based on a global placement.
    ///
    /// # Parameters
    /// * `netlist`: The netlist containing the circuit to be placed.
    /// * `circuit`: The circuit netlist which is being placed.
    /// * `core_area`: The region which shall be used for the placement.
    /// * `cell_outlines`: Outlines (abutment boxes) of the standard cells.
    /// * `global_positions`: Result of the global placement: a location for each circuit instance.
    /// * `movable_instances`: Circuit instances that can be moved.
    fn find_legal_positions_impl(&self,
                                 netlist: &N,
                                 circuit: &N::CellId,
                                 core_area: &db::SimplePolygon<db::SInt>,
                                 cell_outlines: &HashMap<N::CellId, db::Rect<db::SInt>>,
                                 global_positions: &HashMap<N::CellInstId, db::Point<db::SInt>>,
                                 movable_instances: &HashSet<N::CellInstId>,
    ) -> HashMap<N::CellInstId, db::SimpleTransform<db::SInt>>;

    /// Wrapper around `legalize_impl(). Does additional logging and sanity checks.
    ///
    /// # Parameters
    /// * `netlist`: The netlist containing the circuit to be placed.
    /// * `circuit`: The circuit netlist which is being placed.
    /// * `core_area`: The region which shall be used for the placement.
    /// * `cell_outlines`: Outlines (abutment boxes) of the standard cells.
    /// * `global_positions`: Result of the global placement: a location for each circuit instance.
    /// * `movable_instances`: Circuit instances that can be moved.
    fn find_legal_positions(&self,
                            netlist: &N,
                            circuit: &N::CellId,
                            core_area: &db::SimplePolygon<db::SInt>,
                            cell_outlines: &HashMap<N::CellId, db::Rect<db::SInt>>,
                            global_positions: &HashMap<N::CellInstId, db::Point<db::SInt>>,
                            movable_instances: &HashSet<N::CellInstId>,
    ) -> HashMap<N::CellInstId, db::SimpleTransform<db::SInt>> {
        info!("Run legalization of the standard-cells.");

        // Check that all circuit instances have a global position.
        debug!("Check that all circuit instances have a global position.");
        let without_position: Vec<_> = netlist.each_cell_instance(circuit)
            .filter(|c| !global_positions.contains_key(c))
            .collect();
        // Print debug information if there are instances without global position.
        if without_position.len() > 0 {
            warn!("{} circuit instances have no global position.", without_position.len());
            debug!("Circuit instances without global position: {:?}",
                   without_position.iter()
                       .map(|c| netlist.cell_instance_name(c)
                           .map(|n| n.into())
                           .unwrap_or(format!("ID={:?}", c))
                       ).collect::<Vec<_>>()
            )
        }

        // Check that the shapes are defined for all used cells.
        // Print a warning if the shapes are not known for some cells.
        let mut unknown_shapes: Vec<_> = netlist.each_cell_dependency(circuit)
            .filter(|c| !cell_outlines.contains_key(c))
            .map(|c| netlist.cell_name(&c))
            .collect();
        unknown_shapes.sort();
        let unknown_shapes = unknown_shapes;
        if !unknown_shapes.is_empty() {
            warn!("Number of cells without known shape: {}", unknown_shapes.len());
            warn!("Cells without known shape: {}", unknown_shapes.join(", "))
        }

        // Call the legalizer.
        debug!("Call legalize_impl().");
        let result = self.find_legal_positions_impl(
            netlist,
            circuit,
            core_area,
            cell_outlines,
            global_positions,
            movable_instances);

        // TODO: Check that the found positions are actually legal.

        info!("Legalization finished.");

        result
    }
}