1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

/*
 * 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/>.
 */

//! Representation of the placement problem.
//!
//! A trait based representation gives more flexibility than passing naked arguments
//! to the placement engine.

use libreda_db::prelude as db;
use std::collections::HashSet;

/// Describe the placement status of a cell instance.
#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
pub enum PlacementStatus {
    /// The instance location is fixed and must remain.
    Fixed,
    /// The instance can be put into another location by the placement engine.
    Movable,
    /// The instance should be ignored by the placement engine.
    Ignore,
}

/// Representation of the placement task.
pub trait PlacementProblem<C: db::L2NBase> {
    /// Get the base layout/netlist structure.
    fn fused_layout_netlist(&self) -> &C;

    /// Get the top cell whose content should be placed.
    fn top_cell(&self) -> C::CellId;

    /// Get a list of polygons which describe where cells are allowed to be placed.
    fn placement_region(&self) -> Vec<db::SimpleRPolygon<C::Coord>>;

    /// Get regions which should not be used for placement but can if necessary.
    /// Overlap of cells with this regions should be minimized.
    fn soft_blockages(&self) -> Vec<db::SimpleRPolygon<C::Coord>> {
        vec![]
    }

    /// Get the position of a cell instance which should be used as an initial value
    /// for the optimization.
    /// This is most likely the output of the previous placement step.
    fn initial_position(&self, cell_instance: &C::CellInstId) -> db::SimpleTransform<C::Coord>;

    /// Tell if the cell instance can be moved by the placement engine.
    fn placement_status(&self, cell_instance: &C::CellInstId) -> PlacementStatus;

    /// Get the abutment box / outline of the cell.
    fn cell_outline(&self, cell: &C::CellId) -> Option<db::Rect<C::Coord>>;

    /// Get the abutment box / outline of the cell instance.
    fn cell_instance_outline(&self, cell_instance: &C::CellInstId) -> Option<db::Rect<C::Coord>> {
        let template = self.fused_layout_netlist().template_cell(cell_instance);
        self.cell_outline(&template)
    }

    /// Get the weight of a net. Default is `1.0`.
    /// When optimizing the wire-length, the *weighted* wire-length should be used.
    /// For example a weight `0.0` means that the net should not be considered for wire-length optimization.
    fn net_weight(&self, _net: &C::NetId) -> f64 {
        1.0
    }

    /// TODO: fn arc_weight(&self, arc: &ArcId<C>) -> f64;

    /// Get the set of fixed instances.
    fn get_fixed_instances(&self) -> HashSet<C::CellInstId> {
        self.fused_layout_netlist()
            .each_cell_instance(&self.top_cell())
            .filter(|inst| self.placement_status(inst) == PlacementStatus::Fixed)
            .collect()
    }


    /// Get the set of movable cell instances.
    fn get_movable_instances(&self) -> HashSet<C::CellInstId> {
        self.fused_layout_netlist()
            .each_cell_instance(&self.top_cell())
            .filter(|inst| self.placement_status(inst) == PlacementStatus::Movable)
            .collect()
    }
}