ASIC place & route framework. This crate contains interface definitions of the core parts of the place & route flow.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

164 lines
7.0 KiB

/*
* Copyright (c) 2020-2021 Thomas Kramer.
*
* This file is part of LibrEDA
* (see https://codeberg.org/libreda).
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program 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 Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//! 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.
for (inst, tf) in legal_positions {
if movable_instances.contains(&inst) {
chip.set_transform(&inst, tf);
} else {
// Don't move fixed instances.
}
}
}
/// 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
}
}