weir/
fixed_point_execution_plan_cache.rs

1//! Cache for fixed-point execution plans.
2//!
3//! This module owns plan reuse only. It does not upload graph resources,
4//! dispatch kernels, or mutate fixed-point scratch.
5
6use crate::fixed_point_execution_plan::{plan_prepared_graph, FixedPointExecutionPlan};
7use crate::fixed_point_graph::{FixedPointAnalysisKind, FixedPointForwardGraph};
8use crate::fixed_point_scratch::{FrontierDensityTelemetry, FrontierExecutionMode};
9use crate::resident_cache_lru::ResidentCacheLru;
10use std::collections::HashMap;
11
12/// Runtime counters for [`FixedPointExecutionPlanCache`].
13#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
14pub struct FixedPointExecutionPlanCacheStats {
15    /// Successful lookups that reused a prior graph/backend/density-bucket plan.
16    pub hits: u64,
17    /// Lookups that had to build a new plan entry.
18    pub misses: u64,
19    /// Least-recently-used entries evicted to enforce the cache bound.
20    pub evictions: u64,
21    /// Current cached plan entries.
22    pub entries: usize,
23}
24
25/// Execution-plan cache keyed by backend identity, analysis family, graph
26/// layout, and frontier-density family.
27#[derive(Clone, Debug, PartialEq)]
28pub struct FixedPointExecutionPlanCache {
29    entries: HashMap<FixedPointExecutionPlanCacheKey, FixedPointExecutionPlanCacheEntry>,
30    lru: ResidentCacheLru<FixedPointExecutionPlanCacheKey>,
31    max_entries: usize,
32    clock: u64,
33    hits: u64,
34    misses: u64,
35    evictions: u64,
36}
37
38#[derive(Clone, Debug, Eq, Hash, PartialEq)]
39struct FixedPointExecutionPlanCacheKey {
40    backend_id: &'static str,
41    backend_version: &'static str,
42    supported_ops_fingerprint: u64,
43    kind: FixedPointAnalysisKind,
44    layout_hash: u64,
45    node_count: u32,
46    edge_count: u32,
47    density_mode: FrontierExecutionMode,
48}
49
50#[derive(Clone, Debug, PartialEq)]
51struct FixedPointExecutionPlanCacheEntry {
52    last_seen: u64,
53    plan: FixedPointExecutionPlan,
54}
55
56impl Default for FixedPointExecutionPlanCache {
57    fn default() -> Self {
58        Self {
59            entries: HashMap::new(),
60            lru: ResidentCacheLru::default(),
61            max_entries: 1024,
62            clock: 0,
63            hits: 0,
64            misses: 0,
65            evictions: 0,
66        }
67    }
68}
69
70impl FixedPointExecutionPlanCache {
71    /// Create an empty execution-plan cache.
72    #[must_use]
73    pub fn new() -> Self {
74        Self::default()
75    }
76
77    /// Create an empty execution-plan cache with an explicit entry bound.
78    #[must_use]
79    pub fn with_max_entries(max_entries: usize) -> Self {
80        Self {
81            max_entries: max_entries.max(1),
82            ..Self::default()
83        }
84    }
85
86    /// Return a plan for this backend, graph, analysis kind, and density bucket.
87    pub fn get_or_plan(
88        &mut self,
89        backend: &dyn vyre::VyreBackend,
90        kind: FixedPointAnalysisKind,
91        graph: &FixedPointForwardGraph,
92        frontier_density: FrontierDensityTelemetry,
93    ) -> Result<FixedPointExecutionPlan, String> {
94        graph.require_kind(kind, "FixedPointExecutionPlanCache::get_or_plan")?;
95        let supported_ops_fingerprint = self.backend_supported_ops_fingerprint(backend)?;
96        let key = FixedPointExecutionPlanCacheKey {
97            backend_id: backend.id(),
98            backend_version: backend.version(),
99            supported_ops_fingerprint,
100            kind,
101            layout_hash: graph.stable_layout_hash(),
102            node_count: graph.node_count(),
103            edge_count: graph.edge_count(),
104            density_mode: frontier_density.recommended_execution_mode(),
105        };
106        if let Some(entry) = self.entries.get_mut(&key) {
107            self.hits = self.hits.checked_add(1).ok_or_else(|| {
108                "weir fixed-point execution-plan cache hit counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
109                    .to_string()
110            })?;
111            self.clock = self.clock.checked_add(1).ok_or_else(|| {
112                "weir fixed-point execution-plan cache logical clock overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
113                    .to_string()
114            })?;
115            let last_seen = self.clock;
116            entry.last_seen = last_seen;
117            let plan = entry.plan;
118            self.record_lru(key, last_seen)?;
119            return Ok(FixedPointExecutionPlan {
120                frontier_density,
121                ..plan
122            });
123        }
124        self.misses = self.misses.checked_add(1).ok_or_else(|| {
125            "weir fixed-point execution-plan cache miss counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
126                .to_string()
127        })?;
128        self.evict_until_room()?;
129        self.reserve_entry_slot()?;
130        let plan = plan_prepared_graph(graph, frontier_density)?;
131        let last_seen = self.next_cache_tick()?;
132        self.entries.insert(
133            key.clone(),
134            FixedPointExecutionPlanCacheEntry { last_seen, plan },
135        );
136        self.record_lru(key, last_seen)?;
137        Ok(plan)
138    }
139
140    /// Return point-in-time plan-cache counters.
141    #[must_use]
142    pub fn stats(&self) -> FixedPointExecutionPlanCacheStats {
143        FixedPointExecutionPlanCacheStats {
144            hits: self.hits,
145            misses: self.misses,
146            evictions: self.evictions,
147            entries: self.entries.len(),
148        }
149    }
150
151    /// Remove all cached execution plans.
152    pub fn clear(&mut self) {
153        self.entries.clear();
154        self.lru.clear();
155    }
156
157    fn backend_supported_ops_fingerprint(
158        &self,
159        backend: &dyn vyre::VyreBackend,
160    ) -> Result<u64, String> {
161        supported_ops_fingerprint(backend.supported_ops())
162    }
163
164    fn evict_until_room(&mut self) -> Result<(), String> {
165        while self.entries.len() >= self.max_entries {
166            let Some(key) = self.pop_lru_key() else {
167                return Ok(());
168            };
169            self.entries.remove(&key);
170            self.evictions = self.evictions.checked_add(1).ok_or_else(|| {
171                "weir fixed-point execution-plan cache eviction counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
172                    .to_string()
173            })?;
174        }
175        Ok(())
176    }
177
178    fn pop_lru_key(&mut self) -> Option<FixedPointExecutionPlanCacheKey> {
179        self.lru.pop_valid(
180            |key| self.entries.get(key).map(|entry| entry.last_seen),
181            || self.entries.keys().next().cloned(),
182        )
183    }
184
185    fn record_lru(
186        &mut self,
187        key: FixedPointExecutionPlanCacheKey,
188        last_seen: u64,
189    ) -> Result<(), String> {
190        self.lru.record(
191            key,
192            last_seen,
193            self.entries
194                .iter()
195                .map(|(key, entry)| (key.clone(), entry.last_seen)),
196            "weir fixed-point execution-plan cache",
197        )
198    }
199
200    fn next_cache_tick(&mut self) -> Result<u64, String> {
201        self.clock = self.clock.checked_add(1).ok_or_else(|| {
202            "weir fixed-point execution-plan cache logical clock overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
203                .to_string()
204        })?;
205        Ok(self.clock)
206    }
207
208    fn reserve_entry_slot(&mut self) -> Result<(), String> {
209        let needed = self.entries.len().checked_add(1).ok_or_else(|| {
210            "weir fixed-point execution-plan cache entry count overflowed usize. Fix: lower the cache bound or recreate the cache before continuing an unbounded planning stream."
211                .to_string()
212        })?;
213        if self.entries.capacity() >= needed {
214            return Ok(());
215        }
216        self.entries.try_reserve(needed - self.entries.capacity()).map_err(|error| {
217            format!(
218                "weir fixed-point execution-plan cache could not reserve {needed} plan entry slot(s): {error}. Fix: lower the cache bound or recreate the cache before continuing an unbounded planning stream."
219            )
220        })
221    }
222}
223
224fn supported_ops_fingerprint(
225    supported_ops: &std::collections::HashSet<vyre::ir::OpId>,
226) -> Result<u64, String> {
227    const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
228
229    let count = u64::try_from(supported_ops.len()).map_err(|source| {
230        format!(
231            "weir fixed-point execution-plan supported-op count cannot fit u64: {source}. Fix: shard backend capability sets before fingerprinting."
232        )
233    });
234    let mut sum = 0u64;
235    let mut xor = 0u64;
236    let mut product = FNV_OFFSET;
237    let mut hash = FNV_OFFSET;
238    let count = count?;
239    for op in supported_ops {
240        let op_hash = stable_op_hash(op.as_ref())?;
241        sum = sum.wrapping_add(op_hash);
242        xor ^= op_hash.rotate_left((op_hash & 63) as u32);
243        product = product.wrapping_mul(op_hash | 1);
244    }
245    mix_u64(&mut hash, count);
246    mix_u64(&mut hash, sum);
247    mix_u64(&mut hash, xor);
248    mix_u64(&mut hash, product);
249    Ok(hash)
250}
251
252fn stable_op_hash(op: &str) -> Result<u64, String> {
253    const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
254    const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
255
256    let mut hash = FNV_OFFSET;
257    for byte in op.as_bytes() {
258        hash ^= u64::from(*byte);
259        hash = hash.wrapping_mul(FNV_PRIME);
260    }
261    let len = u64::try_from(op.len()).map_err(|source| {
262        format!(
263            "weir fixed-point execution-plan op name length cannot fit u64: {source}. Fix: reject oversized backend op identifiers before fingerprinting."
264        )
265    })?;
266    Ok(hash ^ len)
267}
268
269fn mix_u64(hash: &mut u64, value: u64) {
270    const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
271
272    for byte in value.to_le_bytes() {
273        *hash ^= u64::from(byte);
274        *hash = hash.wrapping_mul(FNV_PRIME);
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use super::*;
281    use std::collections::HashSet;
282    use vyre::backend::{private, BackendError, DispatchConfig, Resource};
283
284    struct FakeBackend {
285        version: &'static str,
286        supported_ops: HashSet<vyre::ir::OpId>,
287    }
288
289    impl private::Sealed for FakeBackend {}
290
291    impl vyre::VyreBackend for FakeBackend {
292        fn id(&self) -> &'static str {
293            "weir_test_fixed_point_execution_plan_cache"
294        }
295
296        fn version(&self) -> &'static str {
297            self.version
298        }
299
300        fn supported_ops(&self) -> &HashSet<vyre::ir::OpId> {
301            &self.supported_ops
302        }
303
304        fn dispatch(
305            &self,
306            _: &vyre::ir::Program,
307            _: &[Vec<u8>],
308            _: &DispatchConfig,
309        ) -> Result<Vec<Vec<u8>>, BackendError> {
310            unreachable!("plan cache tests never dispatch")
311        }
312
313        fn allocate_resident(&self, _: usize) -> Result<Resource, BackendError> {
314            unreachable!("plan cache tests never allocate")
315        }
316
317        fn upload_resident(&self, _: &Resource, _: &[u8]) -> Result<(), BackendError> {
318            unreachable!("plan cache tests never upload")
319        }
320
321        fn upload_resident_many(&self, _: &[(&Resource, &[u8])]) -> Result<(), BackendError> {
322            unreachable!("plan cache tests never upload")
323        }
324
325        fn free_resident(&self, _: Resource) -> Result<(), BackendError> {
326            unreachable!("plan cache tests never free")
327        }
328    }
329
330    fn graph_for_kind(kind: FixedPointAnalysisKind) -> FixedPointForwardGraph {
331        FixedPointForwardGraph::new_for_kind(
332            kind,
333            "fixed_point_execution_plan_cache_test",
334            4096,
335            &[0; 4097],
336            &[],
337            &[],
338        )
339        .expect("empty graph fixture must pack")
340    }
341
342    fn graph() -> FixedPointForwardGraph {
343        graph_for_kind(FixedPointAnalysisKind::Reaching)
344    }
345
346    fn density(active_bits_total: u64) -> FrontierDensityTelemetry {
347        FrontierDensityTelemetry {
348            domain_bits: 4096,
349            samples: 2,
350            iterations: 1,
351            active_bits_total,
352            delta_bits_total: 1,
353            last_active_bits: active_bits_total / 2,
354            last_delta_bits: 1,
355            peak_active_bits: active_bits_total / 2,
356            peak_delta_bits: 1,
357            truncated_frontier_samples: 0,
358            domain_overflow_events: 0,
359            arithmetic_overflow_events: 0,
360        }
361    }
362
363    fn backend(version: &'static str, ops: &[&str]) -> FakeBackend {
364        FakeBackend {
365            version,
366            supported_ops: ops.iter().map(|op| vyre::ir::OpId::from(*op)).collect(),
367        }
368    }
369
370    #[test]
371    fn execution_plan_cache_reuses_equivalent_backend_graph_and_density_bucket() {
372        let backend = backend("v1", &["weir.reaching"]);
373        let graph = graph();
374        let mut cache = FixedPointExecutionPlanCache::new();
375
376        let first = cache
377            .get_or_plan(
378                &backend,
379                FixedPointAnalysisKind::Reaching,
380                &graph,
381                density(8),
382            )
383            .expect("first plan-cache lookup must build a plan");
384        let second = cache
385            .get_or_plan(
386                &backend,
387                FixedPointAnalysisKind::Reaching,
388                &graph,
389                density(10),
390            )
391            .expect("equivalent density bucket must reuse a plan");
392
393        assert_eq!(first.layout_hash, second.layout_hash);
394        assert_eq!(cache.stats().misses, 1);
395        assert_eq!(cache.stats().hits, 1);
396        assert_eq!(cache.stats().entries, 1);
397    }
398
399    #[test]
400    fn execution_plan_cache_separates_backend_versions_and_analysis_families() {
401        let backend_v1 = backend("v1", &["weir.reaching"]);
402        let backend_v2 = backend("v2", &["weir.reaching"]);
403        let reaching_graph = graph();
404        let live_graph = graph_for_kind(FixedPointAnalysisKind::Live);
405        let mut cache = FixedPointExecutionPlanCache::new();
406
407        let _ = cache
408            .get_or_plan(
409                &backend_v1,
410                FixedPointAnalysisKind::Reaching,
411                &reaching_graph,
412                density(8),
413            )
414            .expect("backend v1 reaching plan must build");
415        let _ = cache
416            .get_or_plan(
417                &backend_v2,
418                FixedPointAnalysisKind::Reaching,
419                &reaching_graph,
420                density(8),
421            )
422            .expect("backend v2 reaching plan must build separately");
423        let _ = cache
424            .get_or_plan(
425                &backend_v1,
426                FixedPointAnalysisKind::Live,
427                &live_graph,
428                density(8),
429            )
430            .expect("live plan must build separately from reaching");
431
432        assert_eq!(cache.stats().misses, 3);
433        assert_eq!(cache.stats().hits, 0);
434        assert_eq!(cache.stats().entries, 3);
435    }
436
437    #[test]
438    fn execution_plan_cache_rejects_mismatched_graph_family_before_cache_mutation() {
439        let backend = backend("v1", &["weir.reaching"]);
440        let graph = FixedPointForwardGraph::new_for_kind(
441            FixedPointAnalysisKind::Live,
442            "fixed_point_execution_plan_cache_wrong_family",
443            2,
444            &[0, 1, 1],
445            &[1],
446            &[vyre_primitives::predicate::edge_kind::CONTROL],
447        )
448        .expect("typed live graph must pack");
449        let mut cache = FixedPointExecutionPlanCache::new();
450
451        let error = cache
452            .get_or_plan(
453                &backend,
454                FixedPointAnalysisKind::Reaching,
455                &graph,
456                density(8),
457            )
458            .expect_err("plan cache must reject mismatched analysis family");
459
460        assert!(
461            error.contains("expected Reaching"),
462            "unexpected diagnostic: {error}"
463        );
464        assert_eq!(cache.stats(), FixedPointExecutionPlanCacheStats::default());
465    }
466
467    #[test]
468    fn execution_plan_cache_separates_supported_op_feature_sets() {
469        let backend_control_only = backend("v1", &["weir.reaching"]);
470        let backend_control_and_live = backend("v1", &["weir.live", "weir.reaching"]);
471        let graph = graph();
472        let mut cache = FixedPointExecutionPlanCache::new();
473
474        let _ = cache
475            .get_or_plan(
476                &backend_control_only,
477                FixedPointAnalysisKind::Reaching,
478                &graph,
479                density(8),
480            )
481            .expect("first supported-op feature-set plan must build");
482        let _ = cache
483            .get_or_plan(
484                &backend_control_and_live,
485                FixedPointAnalysisKind::Reaching,
486                &graph,
487                density(8),
488            )
489            .expect("changed supported-op feature-set plan must build separately");
490
491        assert_eq!(cache.stats().misses, 2);
492        assert_eq!(cache.stats().hits, 0);
493        assert_eq!(cache.stats().entries, 2);
494    }
495
496    #[test]
497    fn supported_ops_fingerprint_is_order_independent_without_sorted_scratch() {
498        let first = ["weir.reaching", "weir.live", "weir.slice"]
499            .into_iter()
500            .map(vyre::ir::OpId::from)
501            .collect::<HashSet<_>>();
502        let second = ["weir.slice", "weir.reaching", "weir.live"]
503            .into_iter()
504            .map(vyre::ir::OpId::from)
505            .collect::<HashSet<_>>();
506        let third = ["weir.reaching", "weir.live", "weir.points_to_subset"]
507            .into_iter()
508            .map(vyre::ir::OpId::from)
509            .collect::<HashSet<_>>();
510
511        assert_eq!(
512            supported_ops_fingerprint(&first).expect("first fingerprint must fit"),
513            supported_ops_fingerprint(&second).expect("second fingerprint must fit")
514        );
515        assert_ne!(
516            supported_ops_fingerprint(&first).expect("first fingerprint must fit"),
517            supported_ops_fingerprint(&third).expect("third fingerprint must fit")
518        );
519    }
520
521    #[test]
522    fn execution_plan_cache_evicts_least_recently_used_entry_at_bound() {
523        let backend_a = backend("v1", &["weir.a"]);
524        let backend_b = backend("v1", &["weir.b"]);
525        let backend_c = backend("v1", &["weir.c"]);
526        let graph = graph();
527        let mut cache = FixedPointExecutionPlanCache::with_max_entries(2);
528
529        let _ = cache
530            .get_or_plan(
531                &backend_a,
532                FixedPointAnalysisKind::Reaching,
533                &graph,
534                density(8),
535            )
536            .expect("backend a plan must build");
537        let _ = cache
538            .get_or_plan(
539                &backend_b,
540                FixedPointAnalysisKind::Reaching,
541                &graph,
542                density(8),
543            )
544            .expect("backend b plan must build");
545        let _ = cache
546            .get_or_plan(
547                &backend_a,
548                FixedPointAnalysisKind::Reaching,
549                &graph,
550                density(8),
551            )
552            .expect("backend a plan must hit");
553        let _ = cache
554            .get_or_plan(
555                &backend_c,
556                FixedPointAnalysisKind::Reaching,
557                &graph,
558                density(8),
559            )
560            .expect("backend c plan must evict least-recently-used entry");
561
562        assert_eq!(cache.stats().entries, 2);
563        assert_eq!(cache.stats().evictions, 1);
564        assert_eq!(cache.stats().hits, 1);
565        assert_eq!(cache.stats().misses, 3);
566
567        let _ = cache
568            .get_or_plan(
569                &backend_b,
570                FixedPointAnalysisKind::Reaching,
571                &graph,
572                density(8),
573            )
574            .expect("evicted backend b plan must rebuild");
575        assert_eq!(
576            cache.stats().misses,
577            4,
578            "Fix: the least-recently-used backend_b entry should have been evicted, not the recently-hit backend_a entry."
579        );
580    }
581
582    #[test]
583    fn execution_plan_cache_lru_heap_stays_capacity_scale() {
584        let graph = graph();
585        let mut cache = FixedPointExecutionPlanCache::with_max_entries(4);
586
587        for idx in 0..96u32 {
588            let op = format!("weir.op.{idx}");
589            let backend = backend("v1", &[op.as_str()]);
590            let _ = cache
591                .get_or_plan(
592                    &backend,
593                    FixedPointAnalysisKind::Reaching,
594                    &graph,
595                    density(u64::from(idx.saturating_add(1))),
596                )
597                .expect("plan cache lookup must build or reuse");
598            let _ = cache
599                .get_or_plan(
600                    &backend,
601                    FixedPointAnalysisKind::Reaching,
602                    &graph,
603                    density(u64::from(idx.saturating_add(1))),
604                )
605                .expect("plan cache hit must update recency");
606        }
607
608        assert_eq!(cache.stats().entries, 4);
609        assert!(
610            cache.lru.len() <= cache.entries.len().saturating_mul(4).max(8),
611            "Fix: execution-plan cache LRU heap must compact stale touches to cache-capacity scale"
612        );
613    }
614
615    #[test]
616    fn execution_plan_cache_source_has_no_release_path_panic_or_unwrap() {
617        let source = include_str!("fixed_point_execution_plan_cache.rs");
618
619        for forbidden in [
620            concat!("panic", "!("),
621            concat!(".unwrap_or_else", "(|source|"),
622            concat!(".", "unwrap()"),
623        ] {
624            assert!(
625                !source.contains(forbidden),
626                "Fix: fixed-point execution-plan cache must return errors instead of panicking or unwrapping in release-path planning/fingerprinting: {forbidden}"
627            );
628        }
629        assert!(
630            source.contains("fn reserve_entry_slot(&mut self)")
631                && source.contains("self.reserve_entry_slot()?")
632                && source.contains("ResidentCacheLru")
633                && source.contains("self.lru.record("),
634            "Fix: fixed-point execution-plan cache allocation and recency policy must stay modular and share the fallible LRU helper instead of reimplementing a local heap."
635        );
636    }
637}
weir/fixed_point_execution_plan_cache.rs

weir/
fixed_point_execution_plan_cache.rs
