libreda_sta/liberty_library/
mod.rs

1// SPDX-FileCopyrightText: 2021-2024 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! Interface definitions for cell delay look-up as it is provided for example by Liberty libraries.
6//! Imports liberty data using the `liberty-io` crate.
7
8mod import;
9mod import_timing_table;
10mod propagation_pattern;
11
12use fnv::FnvHashMap;
13use smallvec::SmallVec;
14use uom::si::{
15    capacitance::farad,
16    f64::{Capacitance, Time},
17    time::second,
18};
19
20use self::propagation_pattern::{PropagationPattern, PropagationPatterns};
21
22use super::liberty_util::*;
23use crate::{
24    traits::{
25        cell_constraint_model::CellConstraintArc,
26        cell_logic_model::{OutputFunction, Unateness},
27        timing_library::{RiseFall, TimingLibrary},
28    },
29    CellDelayArc, ConstraintArcArg, DelayArcArg, SetupHold,
30};
31use itertools::Itertools;
32use liberty_io::{
33    boolean::{parse_boolean_function, BooleanExpr},
34    CapacitiveLoadUnit, Group, TimeUnit,
35};
36use std::{collections::HashMap, hash::Hash, str::FromStr};
37
38/// Lookup table which maps a `(capacitance, time)`-pair to a time.
39type SlewLut = Interp<Time, Capacitance, Time>;
40/// Lookup table which maps a `(capacitance, time)`-pair to a time.
41type DelayLut = Interp<Time, Capacitance, Time>;
42/// Lookup table which maps the slew of the constrained and related signal
43/// to a constraint (e.g. setup or hold time).
44type ConstraintLut = Interp<Time, Time, Time>;
45
46/// Delay tables.
47#[derive(Default, Clone, Debug)]
48pub struct DelayArc {
49    /// Timing sense/unateness of the arc.
50    pub timing_sense: Unateness,
51    /// Type of the timing arc.
52    pub timing_type: TimingType,
53    /// Lookup-table for rise transition times.
54    rise_transition: Option<SlewLut>,
55    /// Lookup-table for fall transition times.
56    fall_transition: Option<SlewLut>,
57    /// Lookup-table for rise times.
58    cell_rise: Option<DelayLut>,
59    /// Lookup-table for fall times.
60    cell_fall: Option<DelayLut>,
61}
62
63/// Constraint tables.
64#[derive(Default, Clone, Debug)]
65pub struct ConstraintArc {
66    /// Type of the timing arc.
67    pub timing_type: TimingType,
68    /// Constraint for rising edges of the constrained signal.
69    pub rise_constraint: Option<ConstraintLut>,
70    /// Constraint for falling edges of the constrained signal.
71    pub fall_constraint: Option<ConstraintLut>,
72}
73
74/// Liberty timing type.
75// TODO: Use TimingType of liberty-io crate.
76#[allow(missing_docs)]
77#[derive(Copy, Clone, Debug, Hash, Default)]
78pub enum TimingType {
79    #[default]
80    Combinational,
81    CombinationalRise,
82    CombinationalFall,
83    ThreeStateDisable,
84    ThreeStateEnable,
85    ThreeStateDisableRise,
86    ThreeStateDisableFall,
87    ThreeStateEnableRise,
88    ThreeStateEnableFall,
89
90    // // Sequential:
91    /// Output pin is sensitive to rising edge of related signal.
92    RisingEdge,
93    /// Output pin is sensitive to falling edge of related signal.
94    FallingEdge,
95    /// Asynchronous set.
96    Preset,
97    /// Asynchronous clear/reset.
98    Clear,
99    /// Hold arc which is sensitive to rising edge at related pin.
100    HoldRising,
101    /// Hold arc which is sensitive to falling edge at related pin.
102    HoldFalling,
103    /// Setup arc which is sensitive to rising edge at related pin.
104    SetupRising,
105    /// Setup arc which is sensitive to falling edge at related pin.
106    SetupFalling,
107    RecoveryRising,
108    RecoveryFalling,
109    // SkewRising,
110    // SkewFalling,
111    RemovalRising,
112    RemovalFalling,
113}
114
115impl DelayArc {
116    /// Get the lookup table for transition times (slews).
117    pub fn transition(&self, output_edge: RiseFall) -> Option<&SlewLut> {
118        self.debug_sanity_check();
119        match output_edge {
120            RiseFall::Rise => self.rise_transition.as_ref(),
121            RiseFall::Fall => self.fall_transition.as_ref(),
122        }
123    }
124    /// Get the lookup table for delays.
125    pub fn delay(&self, output_edge: RiseFall) -> Option<&DelayLut> {
126        self.debug_sanity_check();
127        match output_edge {
128            RiseFall::Rise => self.cell_rise.as_ref(),
129            RiseFall::Fall => self.cell_fall.as_ref(),
130        }
131    }
132
133    /// Check that fields have consistent values.
134    /// TODO: Enforce consisten values by structure.
135    fn debug_sanity_check(&self) {
136        // debug_assert_eq!(self.rising_edge, self.rise_transition.is_some());
137        // debug_assert_eq!(self.falling_edge, self.fall_transition.is_some());
138        // debug_assert_eq!(self.rising_edge, self.cell_rise.is_some());
139        // debug_assert_eq!(self.falling_edge, self.cell_fall.is_some());
140        // debug_assert_eq!(self.cell_fall.is_some(), self.fall_transition.is_some());
141        // debug_assert_eq!(self.cell_rise.is_some(), self.rise_transition.is_some());
142    }
143}
144
145/// Timing library based on a 'liberty' library.
146#[derive(Clone, Debug)]
147pub struct LibertyTimingLibrary<CellId, PinId> {
148    table_templates: HashMap<String, LuTableTemplate>,
149    time_unit: Time,
150    capacitive_load_unit: Capacitance,
151    /// Mapping from `(cell_name, pin_name, related_pin_name)` to the delay arc structure.
152    pub(crate) cells: HashMap<CellId, Cell<PinId>>,
153}
154
155/// Timing model of a cell.
156#[derive(Clone, Debug)]
157pub(crate) struct Cell<PinId> {
158    flip_flops: Vec<FlipFlop<PinId>>,
159    latches: Vec<Latch<PinId>>,
160    /// Timing information of pins.
161    pub(crate) pins: FnvHashMap<PinId, Pin<PinId>>,
162    cell_name: String,
163    /// All possible delay arcs in this cell.
164    /// This information is used to build the cell-internal edges in the timing graph.
165    pub(super) delay_arcs: SmallVec<[CellDelayArc<PinId>; 4]>,
166}
167
168impl<PinId> Cell<PinId>
169where
170    PinId: Clone,
171{
172    /// Do precomputations for speeding-up the construction of the timing graph.
173    pub(super) fn run_precomputations(&mut self) {
174        self.precompute_delay_arcs()
175    }
176
177    fn precompute_delay_arcs(&mut self) {
178        self.delay_arcs = self
179            .pins
180            .iter()
181            .flat_map(move |(output_pin, pin)| {
182                pin.timing
183                    .delay_arcs
184                    .iter()
185                    .flat_map(move |(related_pin, delay_arc)| {
186                        // Get the possible propagation patterns.
187                        let prop_patterns =
188                            PropagationPatterns::new(delay_arc.timing_type, delay_arc.timing_sense);
189                        let related_edge = related_pin.1;
190
191                        // Get the possible output edge types for the given input edge type.
192                        let output_edges = [RiseFall::Rise, RiseFall::Fall].into_iter().filter(
193                            move |&output_edge| {
194                                let current_edge =
195                                    PropagationPattern::from_risefall(related_edge, output_edge);
196                                prop_patterns.contains(&current_edge)
197                            },
198                        );
199
200                        // Assemble delay arc specification.
201                        output_edges.map(|output_edge| CellDelayArc {
202                            output_pin: (output_pin.clone(), output_edge),
203                            input_pin: related_pin.clone(),
204                        })
205                    })
206            })
207            .collect()
208    }
209}
210
211/// Define a cell-internal edge-triggered flip-flop.
212/// Contains data extracted from a `ff` group of the liberty library.
213#[derive(Clone, Debug)]
214pub(crate) struct FlipFlop<PinId> {
215    /// Name of non-inverted output.
216    state_variable: String,
217    /// Name of inverted output.
218    state_variable_inv: String,
219    next_state: BooleanExpr<PinId>,
220    /// Flip-Flop samples the date when this boolean expression transitions from `false` to `true`.
221    clocked_on: BooleanExpr<PinId>,
222    /// Optional second clock condition for 'master-slave' flip-flops.
223    clocked_on_also: Option<BooleanExpr<PinId>>,
224    /// Number of storage bits.
225    /// For normal flip-flops this is 1.
226    /// For flip-flop banks this can be any number.
227    num_bits: usize,
228}
229
230/// Define a cell-internal edge-triggered latch.
231/// Contains data extracted from a `latch` group of the liberty library.
232#[derive(Clone, Debug)]
233pub(crate) struct Latch<PinId> {
234    /// Name of the state variable of the latch.
235    state_variable: String,
236    /// Name of inverted output.
237    state_variable_inv: String,
238    /// Data which get sampled into the latch.
239    data_in: BooleanExpr<PinId>,
240    /// Condition for the latch to be transparent.
241    enable: BooleanExpr<PinId>,
242}
243
244/// Timing information of an output pin.
245#[derive(Default, Debug, Clone)]
246pub struct Pin<PinId> {
247    pin_name: String,
248    /// Abstract logic function of output pins.
249    pub(crate) output_function: OutputFunction<PinId>,
250    /// Input capacitance of the pin (regardless of input transition).
251    pub(crate) capacitance: Capacitance,
252    pub(crate) capacitance_rise: Capacitance,
253    pub(crate) capacitance_fall: Capacitance,
254    /// Timing tables for this Pin.
255    pub(crate) timing: PinTiming<PinId>,
256}
257
258/// Timing information of an output pin.
259#[derive(Debug, Clone)]
260pub struct PinTiming<PinId> {
261    /// Mapping from input pin to the delay/slew values.
262    delay_arcs: FnvHashMap<(PinId, RiseFall), DelayArc>,
263    /// Mapping from related pin (and edge type) to hold arcs.
264    pub(crate) hold_arcs: FnvHashMap<(PinId, RiseFall), ConstraintArc>,
265    /// Mapping from related pin (and edge type) to setup arcs.
266    pub(crate) setup_arcs: FnvHashMap<(PinId, RiseFall), ConstraintArc>,
267}
268
269impl<PinId> PinTiming<PinId>
270where
271    PinId: Hash + Eq,
272{
273    /// Find a delay arc by the related pin and the related edge type.
274    pub fn get_delay_lut(&self, input_pin: &(PinId, RiseFall)) -> Option<&DelayArc> {
275        self.delay_arcs.get(input_pin)
276    }
277
278    /// Find a constraint arc by the constraint type (setup/hold), the constrained edge type and the related pin.
279    pub fn get_constraint_lut(
280        &self,
281        constraint_type: SetupHold,
282        constrained_edge: RiseFall,
283        related_pin: &(PinId, RiseFall),
284    ) -> Option<&ConstraintLut> {
285        use SetupHold::*;
286
287        let arcs = match constraint_type {
288            Hold => &self.hold_arcs,
289            Setup => &self.setup_arcs,
290        };
291
292        arcs.get(related_pin)
293            .and_then(|constraint_arc| match constrained_edge {
294                RiseFall::Rise => constraint_arc.rise_constraint.as_ref(),
295                RiseFall::Fall => constraint_arc.fall_constraint.as_ref(),
296            })
297    }
298}
299
300impl<PinId> Default for PinTiming<PinId> {
301    fn default() -> Self {
302        Self {
303            delay_arcs: Default::default(),
304            hold_arcs: Default::default(),
305            setup_arcs: Default::default(),
306        }
307    }
308}
309
310/// Template for lookup-tables.
311#[derive(Clone, Debug)]
312struct LuTableTemplate {
313    /// Name of the first variable.
314    var1: String,
315    /// Name of the second variable (if defined).
316    var2: Option<String>,
317    /// Dimension of the table.
318    size: (usize, usize),
319}
320
321/// Context information used during import of a liberty library.
322struct LibraryImportContext<'a, CellId, PinId> {
323    cell_by_name: &'a dyn Fn(&str) -> Option<CellId>,
324    pin_by_name: &'a dyn Fn(&CellId, &str) -> Option<PinId>,
325}
326
327/// Context information used during import of a cell from a liberty library.
328struct CellImportContext<'a, CellId, PinId> {
329    library_context: &'a LibraryImportContext<'a, CellId, PinId>,
330    cell_id: &'a CellId,
331    cell_name: &'a str,
332}
333
334/// Context information used during import of a pin from a liberty library.
335struct PinImportContext<'a, CellId, PinId> {
336    cell_context: &'a CellImportContext<'a, CellId, PinId>,
337    pin_id: &'a PinId,
338    pin_name: &'a str,
339}
340
341impl<CellId, PinId> LibertyTimingLibrary<CellId, PinId>
342where
343    CellId: Hash + Eq + Clone,
344    PinId: Hash + Eq + Clone,
345{
346    /// Create a new timing library based on a liberty structure.
347    pub fn new(
348        lib: &Group,
349        cell_by_name: impl Fn(&str) -> Option<CellId>,
350        pin_by_name: impl Fn(&CellId, &str) -> Option<PinId>,
351    ) -> Result<Self, LibertyErr> {
352        let library_import_context = LibraryImportContext {
353            cell_by_name: &cell_by_name,
354            pin_by_name: &pin_by_name,
355        };
356
357        // Check that `lib` is really a `library` group.
358        if lib.name != "library" {
359            Err(LibertyErr::Other(format!(
360                "Group must be a `library` group but it is `{}`",
361                lib.name
362            )))?;
363        }
364
365        // Create empty data structure.
366        let mut l = Self {
367            table_templates: Default::default(),
368            cells: Default::default(),
369            time_unit: Default::default(),
370            capacitive_load_unit: Default::default(),
371        };
372
373        l.init_units(lib)?;
374
375        Self::check_delay_model(lib)?;
376
377        // Read table templates.
378        l.table_templates = import::read_template_tables(lib)?;
379
380        // Import cells from the liberty library.
381        l.read_cells(lib, library_import_context)?;
382
383        Ok(l)
384    }
385
386    /// Check that the specified delay model is supported.
387    /// At the moment only "table_lookup" is supported.
388    fn check_delay_model(lib: &Group) -> Result<(), LibertyErr> {
389        let delay_model = lib
390            .get_simple_attribute("delay_model")
391            .and_then(|v| v.as_str());
392
393        if delay_model != Some("table_lookup") {
394            log::error!(
395                "Delay model is not supported. Must be `table_lookup`. delay_model = {:?}",
396                delay_model
397            );
398            Err(LibertyErr::UnsupportedDelayModel(
399                delay_model.unwrap_or("<unknown>").to_string(),
400            ))?;
401        }
402
403        Ok(())
404    }
405
406    /// Load units from the liberty data structure.
407    fn init_units(&mut self, lib: &Group) -> Result<(), LibertyErr> {
408        // Get time unit.
409        {
410            let time_unit_str = lib
411                .get_simple_attribute("time_unit")
412                .ok_or(LibertyErr::UnitNotDefined("time_unit"))?
413                .as_str()
414                .ok_or(LibertyErr::UnitNotDefined("time_unit is not a string"))?;
415
416            let time_unit_sec = TimeUnit::from_str(time_unit_str)
417                .map_err(|_| LibertyErr::UnitNotDefined("Failed to parse time_unit."))?;
418
419            self.time_unit = Time::new::<second>(time_unit_sec.as_seconds());
420        }
421
422        // Get capacitance unit.
423        {
424            let cap_unit = lib
425                .get_complex_attribute("capacitive_load_unit")
426                .ok_or(LibertyErr::UnitNotDefined("capacitive_load_unit"))?;
427
428            let c = CapacitiveLoadUnit::try_from(cap_unit.as_slice())
429                .map_err(|_| LibertyErr::UnitNotDefined("capacitive_load_unit is malformed"))?;
430
431            self.capacitive_load_unit = Capacitance::new::<farad>(c.as_farad());
432        }
433
434        Ok(())
435    }
436}
437
438impl<CellId, PinId> LibertyTimingLibrary<CellId, PinId>
439where
440    CellId: Hash + Eq,
441    PinId: Hash + Eq + Clone,
442{
443    /// Find a pin by the name of the cell and the name of the pin.
444    pub fn get_pin(&self, cell: &CellId, output_pin: &PinId) -> Option<&Pin<PinId>> {
445        self.cells.get(cell).and_then(|c| c.pins.get(output_pin))
446    }
447
448    pub(crate) fn get_delay_arc(&self, arc: DelayArcArg<CellId, PinId>) -> Option<&DelayArc> {
449        self.get_pin(arc.cell, &arc.arc.output_pin.0)
450            .and_then(|p| p.timing.get_delay_lut(&arc.arc.input_pin))
451    }
452
453    pub(crate) fn get_hold_lut(
454        &self,
455        cell: &CellId,
456        arc: &CellConstraintArc<PinId>,
457    ) -> Option<&ConstraintLut> {
458        self.get_pin(cell, &arc.constrained_pin.0).and_then(|p| {
459            p.timing
460                .get_constraint_lut(SetupHold::Hold, arc.constrained_pin.1, &arc.related_pin)
461        })
462    }
463
464    pub(crate) fn get_setup_lut(
465        &self,
466        cell: &CellId,
467        arc: &CellConstraintArc<PinId>,
468    ) -> Option<&ConstraintLut> {
469        self.get_pin(cell, &arc.constrained_pin.0).and_then(|p| {
470            p.timing
471                .get_constraint_lut(SetupHold::Setup, arc.constrained_pin.1, &arc.related_pin)
472        })
473    }
474}
475
476fn get_cell_name(cell_group: &Group) -> Result<&str, LibertyErr> {
477    let cell_name = cell_group
478        .arguments
479        .first()
480        .and_then(|v| v.as_str())
481        .ok_or_else(|| {
482            let msg = "Cell group has no name argument.";
483            log::error!("{}", msg);
484
485            LibertyErr::Other(msg.to_string())
486        })?;
487    Ok(cell_name)
488}
489
490impl<CellId, PinId> TimingLibrary for LibertyTimingLibrary<CellId, PinId>
491where
492    CellId: Hash + Eq,
493    PinId: Hash + Eq + Clone,
494{
495    type CellId = CellId;
496
497    type PinId = PinId;
498
499    fn get_slew(
500        &self,
501        arc: DelayArcArg<CellId, PinId>,
502        input_slew: Time,
503        output_capacitance: Capacitance,
504    ) -> Option<Time> {
505        let edge_polarity = arc.arc.output_pin.1;
506        self.get_delay_arc(arc)
507            .and_then(|d| d.transition(edge_polarity))
508            .map(|f| {
509                // println!("?_transition({}, {}) = {}", output_capacitance, input_slew, f.eval2d((input_slew, output_capacitance)));
510                f.eval2d((output_capacitance, input_slew))
511            })
512    }
513
514    fn get_cell_delay(
515        &self,
516        arc: DelayArcArg<CellId, PinId>,
517        input_slew: Time,
518        output_capacitance: Capacitance,
519    ) -> Option<Time> {
520        let edge_polarity = arc.arc.output_pin.1;
521        self.get_delay_arc(arc)
522            .and_then(|d| d.delay(edge_polarity))
523            .map(|f| f.eval2d((output_capacitance, input_slew)))
524    }
525
526    fn get_hold_constraint(
527        &self,
528        arc: ConstraintArcArg<CellId, PinId>,
529        related_pin_transition: Time,
530        constrained_pin_transition: Time,
531        output_load: Capacitance,
532    ) -> Option<Time> {
533        self.get_hold_lut(arc.cell, arc.arc)
534            .map(|f| f.eval2d((related_pin_transition, constrained_pin_transition)))
535    }
536
537    fn get_setup_constraint(
538        &self,
539        arc: ConstraintArcArg<CellId, PinId>,
540        related_pin_transition: Time,
541        constrained_pin_transition: Time,
542        output_load: Capacitance,
543    ) -> Option<Time> {
544        self.get_setup_lut(arc.cell, arc.arc)
545            .map(|f| f.eval2d((related_pin_transition, constrained_pin_transition)))
546    }
547}
548
549#[test]
550fn test_load_timing_library_freepdk45() {
551    use std::fs::File;
552    use std::io::BufReader;
553
554    // Parse the liberty file.
555    let f = File::open("./tests/data/freepdk45/gscl45nm.lib").unwrap();
556    let mut buf = BufReader::new(f);
557    let result = liberty_io::read_liberty_bytes(&mut buf);
558    let library = result.unwrap();
559    assert_eq!(library.name.to_string(), "library");
560    assert_eq!(library.arguments[0].to_string(), "gscl45nm");
561
562    // Use strings as IDs for cells and pins.
563    let cell_by_name = |name: &str| -> Option<String> { Some(name.into()) };
564    let pin_by_name = |cell_id: &String, name: &str| -> Option<(String, String)> {
565        Some((cell_id.clone(), name.into()))
566    };
567
568    // Load the timing library structure.
569    let timing_library = LibertyTimingLibrary::new(&library, cell_by_name, pin_by_name).unwrap();
570}
571
572#[test]
573fn test_lut_variable_ordering() {
574    use crate::traits::CellDelayArc;
575
576    // Parse the liberty file.
577
578    let data = r#"
579    library() {
580
581      time_unit: "1ns" ;
582      capacitive_load_unit (1, pf);
583    
584      delay_model: table_lookup;
585      lu_table_template(delay_template_2x3) {
586        variable_1 : total_output_net_capacitance;
587        variable_2 : input_net_transition;
588        index_1 ("1000.0, 1001.0");
589        index_2 ("1000.0, 1001.0, 1002.0");
590      }
591      lu_table_template(delay_template_2x3_swapped_vars) {
592        variable_1 : input_net_transition;
593        variable_2 : total_output_net_capacitance;
594        index_1 ("1000.0, 1001.0, 1002.0");
595        index_2 ("1000.0, 1001.0");
596      }
597      cell(INVX1) {
598        pin(Y) {
599            timing() {
600                related_pin: "A";
601                cell_rise(delay_template_2x3) {
602                    index_1: "1.0, 2.0";
603                    index_2: "1.0, 2.0, 3.0";
604                    values (
605                        "1.0, 1.1, 1.2", \
606                        "1.1, 1.3, 1.5"
607                    );
608                }
609                cell_fall(delay_template_2x3_swapped_vars) { // Use other variable ordering!
610                    index_1: "1.0, 2.0, 3.0";
611                    index_2: "1.0, 2.0";
612                    values (
613                        "1.0, 1.1", \
614                        "1.1, 1.3", \
615                        "1.2, 1.5"
616                    );
617                }
618            }
619        }
620      }
621    }
622    "#;
623
624    let result = liberty_io::read_liberty_chars(data.chars());
625    let library = result.unwrap();
626
627    // Load the timing library structure.
628
629    // Use strings as IDs for cells and pins.
630    // Normally, this would be resolved by the netlist.
631    let cell_by_name = |name: &str| -> Option<String> { Some(name.into()) };
632    let pin_by_name = |cell_id: &String, name: &str| -> Option<(String, String)> {
633        Some((cell_id.clone(), name.into()))
634    };
635
636    let timing_library = LibertyTimingLibrary::new(&library, cell_by_name, pin_by_name).unwrap();
637
638    let invx1 = cell_by_name("INVX1").unwrap();
639    dbg!(&timing_library);
640    let arc_a_y = timing_library
641        .get_delay_arc(DelayArcArg {
642            cell: &invx1,
643            arc: &CellDelayArc {
644                input_pin: (pin_by_name(&invx1, "A").unwrap(), RiseFall::Rise),
645                output_pin: (pin_by_name(&invx1, "Y").unwrap(), RiseFall::Fall),
646            },
647        })
648        .unwrap();
649
650    let cell_rise = arc_a_y.cell_rise.as_ref().unwrap();
651    let cell_fall = arc_a_y.cell_fall.as_ref().unwrap();
652
653    use uom::si::{capacitance::picofarad, time::nanosecond};
654    let ns = Time::new::<nanosecond>;
655    let pf = Capacitance::new::<picofarad>;
656
657    assert!((cell_rise.eval2d((pf(2.0), ns(3.0))) - ns(1.5)).abs() < ns(1e-6));
658    assert!((cell_rise.eval2d((pf(3.0), ns(2.0))) - ns(1.5)).abs() < ns(1e-6)); // Swapped variables
659}
libreda_sta/liberty_library/mod.rs

libreda_sta/liberty_library/
mod.rs
