cranelift_codegen/egraph/
cost.rs

1//! Cost functions for egraph representation.
2
3use crate::ir::Opcode;
4
5/// A cost of computing some value in the program.
6///
7/// Costs are measured in an arbitrary union that we represent in a
8/// `u32`. The ordering is meant to be meaningful, but the value of a
9/// single unit is arbitrary (and "not to scale"). We use a collection
10/// of heuristics to try to make this approximation at least usable.
11///
12/// We start by defining costs for each opcode (see `pure_op_cost`
13/// below). The cost of computing some value, initially, is the cost
14/// of its opcode, plus the cost of computing its inputs.
15///
16/// We then adjust the cost according to loop nests: for each
17/// loop-nest level, we multiply by 1024. Because we only have 32
18/// bits, we limit this scaling to a loop-level of two (i.e., multiply
19/// by 2^20 ~= 1M).
20///
21/// Arithmetic on costs is always saturating: we don't want to wrap
22/// around and return to a tiny cost when adding the costs of two very
23/// expensive operations. It is better to approximate and lose some
24/// precision than to lose the ordering by wrapping.
25///
26/// Finally, we reserve the highest value, `u32::MAX`, as a sentinel
27/// that means "infinite". This is separate from the finite costs and
28/// not reachable by doing arithmetic on them (even when overflowing)
29/// -- we saturate just *below* infinity. (This is done by the
30/// `finite()` method.) An infinite cost is used to represent a value
31/// that cannot be computed, or otherwise serve as a sentinel when
32/// performing search for the lowest-cost representation of a value.
33#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
34pub(crate) struct Cost(u32);
35impl Cost {
36    pub(crate) fn at_level(&self, loop_level: usize) -> Cost {
37        let loop_level = std::cmp::min(2, loop_level);
38        let multiplier = 1u32 << ((10 * loop_level) as u32);
39        Cost(self.0.saturating_mul(multiplier)).finite()
40    }
41
42    pub(crate) fn infinity() -> Cost {
43        // 2^32 - 1 is, uh, pretty close to infinite... (we use `Cost`
44        // only for heuristics and always saturate so this suffices!)
45        Cost(u32::MAX)
46    }
47
48    pub(crate) fn zero() -> Cost {
49        Cost(0)
50    }
51
52    /// Clamp this cost at a "finite" value. Can be used in
53    /// conjunction with saturating ops to avoid saturating into
54    /// `infinity()`.
55    fn finite(self) -> Cost {
56        Cost(std::cmp::min(u32::MAX - 1, self.0))
57    }
58}
59
60impl std::default::Default for Cost {
61    fn default() -> Cost {
62        Cost::zero()
63    }
64}
65
66impl std::ops::Add<Cost> for Cost {
67    type Output = Cost;
68    fn add(self, other: Cost) -> Cost {
69        Cost(self.0.saturating_add(other.0)).finite()
70    }
71}
72
73/// Return the cost of a *pure* opcode. Caller is responsible for
74/// checking that the opcode came from an instruction that satisfies
75/// `inst_predicates::is_pure_for_egraph()`.
76pub(crate) fn pure_op_cost(op: Opcode) -> Cost {
77    match op {
78        // Constants.
79        Opcode::Iconst | Opcode::F32const | Opcode::F64const => Cost(0),
80        // Extends/reduces.
81        Opcode::Uextend | Opcode::Sextend | Opcode::Ireduce | Opcode::Iconcat | Opcode::Isplit => {
82            Cost(1)
83        }
84        // "Simple" arithmetic.
85        Opcode::Iadd
86        | Opcode::Isub
87        | Opcode::Band
88        | Opcode::Bor
89        | Opcode::Bxor
90        | Opcode::Bnot
91        | Opcode::Ishl
92        | Opcode::Ushr
93        | Opcode::Sshr => Cost(2),
94        // Everything else (pure.)
95        _ => Cost(3),
96    }
97}
cranelift_codegen/egraph/cost.rs

cranelift_codegen/egraph/
cost.rs
