problemreductions/rules/
minimumcodegenerationunlimitedregisters_ilp.rs

1//! Rank dependencies and copy indicators for two-address operations.
2use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
3use crate::models::misc::MinimumCodeGenerationUnlimitedRegisters;
4use crate::rules::ilp_helpers::ranks_to_positions;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6
7#[derive(Debug, Clone)]
8pub struct ReductionMinimumCodeGenerationUnlimitedRegistersToILP {
9    target: ILP<i64, i64, Bounded>,
10    num_operations: usize,
11}
12impl ReductionResult for ReductionMinimumCodeGenerationUnlimitedRegistersToILP {
13    type Source = MinimumCodeGenerationUnlimitedRegisters;
14    type Target = ILP<i64, i64, Bounded>;
15    fn target_problem(&self) -> &Self::Target {
16        &self.target
17    }
18    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
19        crate::rules::traits::validate_target_witness(
20            &self.target,
21            solution,
22            |value| value.value.is_some(),
23            "target ILP assignment is infeasible",
24        )?;
25        Ok(ranks_to_positions(&solution[..self.num_operations]))
26    }
27}
28#[crate::reduction(transform = upper_bound {
29    num_vars = "2 * num_vertices + 1",
30    num_constraints = "num_vertices * num_vertices + num_vertices",
31    num_nonzeros = "3 * num_vertices * num_vertices + num_vertices",
32    max_constraint_magnitude_bits = "num_vertices + 1",
33})]
34impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumCodeGenerationUnlimitedRegisters {
35    type Result = ReductionMinimumCodeGenerationUnlimitedRegistersToILP;
36    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
37        // Every internal vertex has exactly one left operand.
38        let mut operations = self.left_arcs().to_vec();
39        operations.sort_unstable();
40        let k = operations.len();
41        let count = k
42            .checked_mul(2)
43            .and_then(|v| v.checked_add(1))
44            .ok_or_else(|| {
45                crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
46                    "counting code-generation variables",
47                )
48            })?;
49        let bound = Self::exact_i64(k, "bounding operation ranks")?;
50        Self::exact_i64(count, "bounding the instruction count")?;
51        let mut variables = Vec::with_capacity(count);
52        for _ in 0..k {
53            variables.push(
54                IntegerVariable::new(Some(0), Some(bound - 1))
55                    .map_err(Self::target_construction)?,
56            );
57        }
58        variables.extend(std::iter::repeat_n(IntegerVariable::binary(), k));
59        variables.push(IntegerVariable::new(Some(1), Some(1)).map_err(Self::target_construction)?);
60        let mut index = vec![None; self.num_vertices()];
61        let mut users = vec![Vec::new(); self.num_vertices()];
62        for (i, &(v, _)) in operations.iter().enumerate() {
63            index[v] = Some(i);
64        }
65        let mut rows = Vec::new();
66        for &(v, child) in self.left_arcs().iter().chain(self.right_arcs()) {
67            let parent = index[v].expect("every operation has a left operand");
68            users[child].push(parent);
69            if let Some(child) = index[child] {
70                rows.push(LinearConstraint::ge(vec![(parent, 1), (child, -1)], 1));
71            }
72        }
73        for users in &mut users {
74            users.sort_unstable();
75            users.dedup();
76        }
77        for (v, &(_, left)) in operations.iter().enumerate() {
78            for &u in &users[left] {
79                if u != v {
80                    rows.push(LinearConstraint::ge(
81                        vec![(v, 1), (u, -1), (k + v, bound)],
82                        1,
83                    ));
84                }
85            }
86        }
87        let mut objective: Vec<_> = (k..2 * k).map(|i| (i, 1)).collect();
88        objective.push((2 * k, bound));
89        let target = ILP::with_variables(variables, rows, objective, ObjectiveSense::Minimize)
90            .map_err(Self::target_construction)?;
91        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
92        Ok(Self::Result {
93            target,
94            num_operations: k,
95        })
96    }
97}
98#[cfg(feature = "example-db")]
99pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
100    vec![crate::example_db::specs::RuleExampleSpec {
101        id: "minimumcodegenerationunlimitedregisters_to_ilp",
102        build: || {
103            crate::example_db::specs::rule_example_via_bounded_ilp(
104                MinimumCodeGenerationUnlimitedRegisters::new(
105                    5,
106                    vec![(1, 3), (2, 3), (0, 1)],
107                    vec![(1, 4), (2, 4), (0, 2)],
108                ),
109            )
110        },
111    }]
112}
113#[cfg(test)]
114#[path = "../unit_tests/rules/minimumcodegenerationunlimitedregisters_ilp.rs"]
115mod tests;
problemreductions/rules/minimumcodegenerationunlimitedregisters_ilp.rs

problemreductions/rules/
minimumcodegenerationunlimitedregisters_ilp.rs
