logiclib/

builder.rs

//! The builder implementation.

use libertyparse::{ Liberty, Cell, Pin, PinDirection, SequentialDef };
use ulib::UVec;
use compact_str::CompactString;
use indexmap::{ IndexMap, IndexSet };
use super::{ LogicVal, LogicLib, LogicCell, LogicOutputPin };
use super::{ combinational, sequential };
use sequential::SequentialInterface;

impl LogicLib {
    /// Build the logic library from a parsed liberty library.
    pub fn from(liberty: &Liberty) -> LogicLib {
        // deduplicate same logic cell in different library.
        let cell_refs: IndexMap<&CompactString, &Cell> = liberty.libs.iter()
            .map(|(_, lib)| lib.cells.iter().map(|(n, p)| (n, p)))
            .flatten().collect();
        
        let mut logic_cells = cell_refs.into_iter().map(|(name, cell)| {
            let (logic_cell, seq) = LogicCell::build_pin_sizes(cell);
            (name.clone(), (cell, logic_cell, seq))
        }).collect::<Vec<_>>();

        // calculate the flattened truth table size and offset
        let mut truthtable_size = 0;
        for (_, (_, lc, _)) in &mut logic_cells {
            for (_, pin) in &mut lc.output_pins {
                if let Ok(pin) = pin {
                    pin.table_start = truthtable_size;
                    truthtable_size += pin.table_size;
                }
            }
        }

        // compute and put the truth table entries
        let mut truthtable = UVec::new_zeroed(truthtable_size,
                                              ulib::Device::CPU);
        let tt_ref = truthtable.as_mut();
        for (_, (c, lc, seq)) in &logic_cells {
            lc.build_pin_table(c, seq.as_ref(), tt_ref);
        }

        // completed.
        LogicLib {
            logic_cells: logic_cells.into_iter()
                .map(|(name, (_, lc, _))| (name, lc)).collect(),
            truthtable
        }
    }
}

impl LogicCell {
    // Build the basic pin structure, and compute the truth table size.
    fn build_pin_sizes(
        cell: &Cell
    ) -> (LogicCell, Option<SequentialInterface>) {
        let inputs = cell.pins.iter().filter_map(|(n, p)| {
            match p.direction {
                PinDirection::I => Some(n),
                _ => None
            }
        }).collect();
        let seq = match &cell.sequential_def {
            None => None,
            Some(seq) => Some(SequentialInterface::from(seq))
        };
        (LogicCell {
            output_pins: cell.pins.iter().filter_map(|(n, p)| {
                match p.direction {
                    PinDirection::I => None,
                    PinDirection::O => Some((
                        n.clone(),
                        LogicOutputPin::build_size(
                            &inputs, seq.as_ref(), p)
                    )),
                    _ => Some((
                        n.clone(),
                        Err("unknown pin direction in liberty def")
                    ))
                }
            }).collect()
        },
        seq)
    }
    
    // Fill in the table items.
    fn build_pin_table(
        &self,
        cell: &Cell,
        seq: Option<&SequentialInterface>,
        tab: &mut [LogicVal]
    ) {
        for (n, pin) in &cell.pins {
            if let Some(Ok(lp)) = self.output_pins.get(n) {
                lp.build_table(
                    pin,
                    cell.sequential_def.as_ref(),
                    seq,
                    &mut tab[
                        lp.table_start..
                            lp.table_start + lp.table_size]);
            }
        }
    }
}

impl LogicOutputPin {
    fn build_size(
        all_cell_inputs: &IndexSet<&CompactString>,
        seq_int: Option<&SequentialInterface>,
        pin: &Pin
    ) -> Result<LogicOutputPin, &'static str> {
        let expr = match &pin.function {
            Some(expr) => expr,
            None => return Err("No function field in liberty")
        };
        let mut related_inputs = IndexMap::new();
        let mut has_internal = false;
        for name in combinational::all_idents(expr) {
            if all_cell_inputs.contains(name) {
                related_inputs.insert(name.clone(), false);
                continue;
            }
            if let Some(seq_int) = seq_int {
                if seq_int.internals.contains(name) {
                    has_internal = true;
                    continue;
                }
            }
            clilog::error!(
                LOGICLIB_FUNC_BADREF,
                "Parsing logiclib: bad reference {}",
                name);
            return Err("Bad function reference")
        }
        let num_internals = if has_internal {
            let seq_int = seq_int.unwrap();
            for (name, rf_sens) in &seq_int.inputs {
                related_inputs.insert((*name).clone(), *rf_sens);
            }
            seq_int.internals.len()
        }
        else { 0 };
        // sort inputs by alphabetical order for simplicity
        related_inputs.sort_keys();
        
        let table_size = related_inputs.iter()
            .map(|(_, rf_s)| match rf_s { true => 7, false => 5 })
            .product::<usize>()
            * 4usize.pow(num_internals as u32) * (num_internals + 1);
        Ok(LogicOutputPin {
            related_inputs,
            num_internals: num_internals.try_into().unwrap(),
            table_size,
            table_start: usize::MAX
        })
    }

    fn build_table(
        &self,
        pin: &Pin,
        seq: Option<&SequentialDef>,
        seq_int: Option<&SequentialInterface>,
        tab: &mut [LogicVal]
    ) {
        use LogicVal::*;
        // two stages.
        // includes very heavy constant index calculations,
        // 4, 6; 5, 7; ...
        // modify them with care.

        // map rf sensitivity to non-u base
        fn map_rf_nu_base(rf: bool) -> usize {
            match rf { true => 6, false => 4 }
        }
        // map rf to base with u
        fn map_rf_u_base(rf: bool) -> usize {
            match rf { true => 7, false => 5 }
        }
        // map non-u base to logic value
        fn map_nu_val(v: usize) -> LogicVal {
            match v {
                0 => L, 1 => H, 2 => X, 3 => Z,
                4 => R, 5 => F,
                _ => unreachable!()
            }
        }
        // map u base to logic value.
        // guaranteed to be a trivial one.
        fn map_u_val(v: usize) -> LogicVal {
            (v as u8).try_into().unwrap()
        }
        // map logic value to u base.
        // guaranteed to be a trivial one.
        fn map_val_u(lv: LogicVal) -> usize {
            lv as u8 as usize
        }
        
        // stage 1: calculate all non-U table items
        // note our little-endian encoding. the related inputs
        // reside in the lower part of encoding.
        assert_eq!(tab.len(), self.table_size);
        let internals_mul = 4usize.pow(self.num_internals as u32);
        let set_size = self.related_inputs.iter()
            .map(|(_, rf_s)| map_rf_nu_base(*rf_s))
            .product::<usize>() * internals_mul;
        let n_inputs = self.related_inputs.len();
        let n_internals = self.num_internals as usize;
        let mut b = vec![U; n_inputs + n_internals];
        // `s` is a simplified encoding that does not have U's.
        for s in 0..set_size {
            // dump s (set index) into bits (b)
            let mut t = s;
            for (i, (_, rf)) in self.related_inputs.iter().enumerate() {
                let base = map_rf_nu_base(*rf);
                b[i] = map_nu_val(t % base);
                t /= base;
            }
            for i in 0..n_internals {
                b[n_inputs + i] = map_nu_val(t % 4);
                t /= 4;
            }
            assert_eq!(t, 0);
            // load b into t (table index)
            // note the reversed index: important for our
            // little-endian encoding.
            for i in (0..n_internals).rev() {
                t = t * 4 + map_val_u(b[n_inputs + i]);
            }
            for (i, (_, rf)) in self.related_inputs.iter().enumerate().rev() {
                t = t * map_rf_u_base(*rf) + map_val_u(b[i]);
            }
            let t = t; // table index computed.
            // compute expr, with seq or not
            match (seq, seq_int) {
                (None, None) => {
                    // directly evaluate a pure combinational
                    // logic expression.
                    tab[t] = combinational::eval(
                        pin.function.as_ref().unwrap(),
                        &|name| {
                            b[self.related_inputs
                              .get_index_of(name).unwrap()]
                        },
                        false
                    );
                }
                (Some(seq), Some(seq_int)) => {
                    let tab_start = t * (n_internals + 1);
                    // evaluate sequential element to get
                    // new internals.
                    // (the sequential evaluation might call
                    // other combinational evaluations inside.)
                    sequential::eval(
                        seq,
                        seq_int,
                        &|name| {
                            b[match self.related_inputs
                              .get_index_of(name) {
                                Some(i) => i,
                                None => n_inputs + seq_int.internals
                                      .get_index_of(name).unwrap()
                            }]
                        },
                        &mut tab[tab_start + 1..tab_start + n_internals + 1]
                    );
                    // evaluate pin function given inputs
                    // and the determined new internals.
                    tab[tab_start] = combinational::eval(
                        pin.function.as_ref().unwrap(),
                        &|name| {
                            match self.related_inputs
                                .get_index_of(name)
                            {
                                Some(i) => b[i],
                                // use new internals.
                                None => tab[
                                    tab_start + 1 + seq_int.internals
                                        .get_index_of(name)
                                        .unwrap()]
                            }
                        },
                        false
                    );
                }
                _ => panic!()
            }
        }
        
        // stage 2: use a bitmask DP to calculate U's.
        // s_u: masked (undetermined) positions
        for s_u in 1..(1 << n_inputs) {
            let first_u = (0..n_inputs)
                .filter(|i| (s_u >> i & 1) != 0)
                .next().unwrap();
            let set_size = self.related_inputs.iter()
                .enumerate()
                .map(|(i, (_, rf_s))| {
                    if (s_u >> i & 1) != 0 { 1 }
                    else { map_rf_nu_base(*rf_s) }
                })
                .product::<usize>() * internals_mul;
            let first_u_base = map_rf_u_base(
                *self.related_inputs
                    .get_index(first_u).unwrap().1
            );
            let first_u_skip = self.related_inputs.iter()
                .enumerate()
                .take_while(|(i, _)| *i < first_u)
                .map(|(_, (_, rf_s))| map_rf_u_base(*rf_s))
                .product::<usize>();
            
            for s in 0..set_size {
                // transfrom s into a bit representation s_bit.
                // non-first-u are U's.
                // first-u is 0.
                // others are assigned with their proper value.
                let mut t = s;
                // initialize with all internals.
                // the orders do not matter.
                let mut s_bit = t % internals_mul;
                t /= internals_mul;
                for (i, (_, rf_s)) in self.related_inputs
                    .iter().enumerate().rev()
                {
                    let s_bit_base = map_rf_u_base(*rf_s);
                    let s_base = map_rf_nu_base(*rf_s);
                    s_bit *= s_bit_base;
                    if i == first_u {
                        // do nothing
                    }
                    else if (s_u >> i & 1) != 0 {
                        s_bit += map_val_u(U);
                    }
                    else {
                        s_bit += map_val_u(map_nu_val(t % s_base));
                        t /= s_base;
                    }
                }
                assert_eq!(t, 0);
                
                // check if all assignments are equal to
                // the L assignment (0).
                // if yes, we propagate the L assigns (can be Us).
                // if no, we give up and fill in Us.
                let mut all_eq = true;
                let gslice = |s_bit: usize| -> std::ops::Range<usize> {
                    s_bit * (n_internals + 1)..
                        (s_bit + 1) * (n_internals + 1)
                };
                for first_to in 1..first_u_base {
                    if map_u_val(first_to) == U { continue }
                    let s_bit_first_to = s_bit +
                        first_to * first_u_skip;
                    if tab[gslice(s_bit)] != tab[gslice(s_bit_first_to)] {
                        all_eq = false;
                        break;
                    }
                }
                let s_bit_first_u = s_bit + map_val_u(U) * first_u_skip;
                if all_eq {
                    tab.copy_within(gslice(s_bit), gslice(s_bit_first_u).start);
                }
                else {
                    tab[gslice(s_bit_first_u)].fill(U);
                }
            }
        }
    }
}