celox_analysis/
memory_ssa.rs

1//! IR- and alias-domain-independent access-based MemorySSA.
2//!
3//! This module owns only the sparse `LiveOnEntry`/`MemoryDef`/`MemoryPhi`
4//! graph, program-point coordinates into that graph, and the generic clobber
5//! walk.  Definition effects, byte ranges, read queries, value numbers, and
6//! lowering certificates belong to client adapters.
7//!
8//! Graph construction uses `O(B + E + C + D + F)` storage, where `B/E`
9//! describe the CFG, `C` is the number of captured program points, `D` is the
10//! number of memory definitions, and `F` is the number of MemoryPhi inputs. A
11//! clobber query is linear in the visited graph in the worst case and reuses
12//! one `O(D + F)` scratch allocation across all of that query's start points.
13
14use std::collections::{BTreeMap, BTreeSet};
15use std::fmt;
16
17use crate::ssa::{self, Event, SsaCfg, Version};
18
19#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
20pub struct MemoryAccessId(usize);
21
22/// One ordered program event.  An event with a definition creates one
23/// `MemoryDef`; an event without one only records a queryable program point.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub struct MemoryAccessEvent<D, P> {
26    pub point: P,
27    pub definition: Option<D>,
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
31pub struct MemoryPointAccess {
32    pub before: MemoryAccessId,
33    pub after: MemoryAccessId,
34}
35
36/// Coordinate conversion produced while building a graph.
37///
38/// This is intentionally separate from `MemoryAccessGraph`: clients that
39/// retain their own instruction-to-access mapping can discard it without
40/// changing the graph or the clobber walker.
41#[derive(Debug)]
42pub struct MemoryPointMap<P> {
43    events: BTreeMap<P, MemoryPointAccess>,
44    block_entries: Vec<MemoryAccessId>,
45    block_exits: Vec<MemoryAccessId>,
46}
47
48impl<P: Copy + Ord> MemoryPointMap<P> {
49    #[must_use]
50    pub fn event(&self, point: P) -> Option<MemoryPointAccess> {
51        self.events.get(&point).copied()
52    }
53
54    #[must_use]
55    pub fn block_entry(&self, block: usize) -> Option<MemoryAccessId> {
56        self.block_entries.get(block).copied()
57    }
58
59    #[must_use]
60    pub fn block_exit(&self, block: usize) -> Option<MemoryAccessId> {
61        self.block_exits.get(block).copied()
62    }
63}
64
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66pub enum MemoryAccess<'a, D> {
67    LiveOnEntry,
68    Definition {
69        definition: &'a D,
70        previous: MemoryAccessId,
71    },
72    Phi {
73        block: usize,
74        inputs: &'a [(usize, MemoryAccessId)],
75    },
76}
77
78#[derive(Debug)]
79enum MemoryAccessNode<D> {
80    LiveOnEntry,
81    Definition {
82        definition: D,
83        previous: MemoryAccessId,
84    },
85    Phi {
86        block: usize,
87        /// `(predecessor block, reaching memory state)` in CFG predecessor
88        /// order.  Keeping the edge identity lets clients build structural
89        /// certificates instead of treating every phi in one block as equal.
90        inputs: Vec<(usize, MemoryAccessId)>,
91    },
92}
93
94/// Sparse memory-state graph.  It contains no alias information and no read
95/// query results.
96#[derive(Debug)]
97pub struct MemoryAccessGraph<D> {
98    nodes: Vec<MemoryAccessNode<D>>,
99    definition_count: usize,
100    phi_count: usize,
101}
102
103impl<D> MemoryAccessGraph<D> {
104    #[must_use]
105    pub fn access(&self, access: MemoryAccessId) -> Option<MemoryAccess<'_, D>> {
106        match self.nodes.get(access.0)? {
107            MemoryAccessNode::LiveOnEntry => Some(MemoryAccess::LiveOnEntry),
108            MemoryAccessNode::Definition {
109                definition,
110                previous,
111            } => Some(MemoryAccess::Definition {
112                definition,
113                previous: *previous,
114            }),
115            MemoryAccessNode::Phi { block, inputs } => Some(MemoryAccess::Phi {
116                block: *block,
117                inputs,
118            }),
119        }
120    }
121
122    #[must_use]
123    pub fn access_count(&self) -> usize {
124        self.nodes.len()
125    }
126
127    #[must_use]
128    pub fn definition_count(&self) -> usize {
129        self.definition_count
130    }
131
132    #[must_use]
133    pub fn phi_count(&self) -> usize {
134        self.phi_count
135    }
136}
137
138/// Alias policy supplied by a client.  The definition identity is the graph
139/// payload; effects and query representation remain outside MemorySSA.
140pub trait AliasOracle<D, Q> {
141    fn may_alias(&self, definition: &D, query: &Q) -> bool;
142}
143
144impl<D, Q, F> AliasOracle<D, Q> for F
145where
146    F: Fn(&D, &Q) -> bool,
147{
148    fn may_alias(&self, definition: &D, query: &Q) -> bool {
149        self(definition, query)
150    }
151}
152
153/// Result of a clobber walk.  `Access` is a stable identity within the graph
154/// and can therefore be embedded in a client-specific snapshot certificate.
155#[derive(Debug, Clone, Copy, PartialEq, Eq)]
156pub enum MemoryClobber {
157    Access(MemoryAccessId),
158    /// A closed cycle without a resolvable MemoryPhi.  Graphs built from a
159    /// normal reachable CFG should not produce this result.
160    Indeterminate,
161}
162
163#[derive(Debug, Clone, Copy, PartialEq, Eq)]
164enum ClobberResolution {
165    Access(usize),
166    Cycle,
167}
168
169#[derive(Debug)]
170enum ResolveFrame {
171    Enter(usize),
172    FinishDefinition(usize),
173    FinishPhi { access: usize, inputs: usize },
174}
175
176/// Reusable, query-local state for clobber walking.  It owns no graph and no
177/// alias-domain data.
178#[derive(Debug, Default)]
179pub struct ClobberWalker {
180    epochs: Vec<u32>,
181    states: Vec<u8>,
182    results: Vec<Option<ClobberResolution>>,
183    epoch: u32,
184    frames: Vec<ResolveFrame>,
185    values: Vec<ClobberResolution>,
186}
187
188impl ClobberWalker {
189    #[must_use]
190    pub fn new() -> Self {
191        Self::default()
192    }
193
194    /// Find the nearest definition that may alias `query`.  Diverging
195    /// incoming clobbers resolve to their nearest `MemoryPhi`.
196    pub fn clobber<D, Q>(
197        &mut self,
198        graph: &MemoryAccessGraph<D>,
199        start: MemoryAccessId,
200        query: &Q,
201        alias_oracle: &impl AliasOracle<D, Q>,
202    ) -> Option<MemoryClobber> {
203        self.query(graph, query, alias_oracle).clobber(start)
204    }
205
206    /// Start one alias query which may resolve several program points. Results
207    /// are memoized only for the lifetime of this session and are discarded
208    /// before a different alias query begins.
209    pub fn query<'a, D, Q, A>(
210        &'a mut self,
211        graph: &'a MemoryAccessGraph<D>,
212        query: &'a Q,
213        alias_oracle: &'a A,
214    ) -> ClobberQuery<'a, D, Q, A>
215    where
216        A: AliasOracle<D, Q>,
217    {
218        self.epochs.resize(graph.nodes.len(), 0);
219        self.states.resize(graph.nodes.len(), 0);
220        self.results.resize(graph.nodes.len(), None);
221        self.epoch = self.epoch.wrapping_add(1);
222        if self.epoch == 0 {
223            self.epochs.fill(0);
224            self.epoch = 1;
225        }
226        ClobberQuery {
227            walker: self,
228            graph,
229            query,
230            alias_oracle,
231        }
232    }
233
234    fn find_clobber<D, Q>(
235        &mut self,
236        nodes: &[MemoryAccessNode<D>],
237        start: usize,
238        query: &Q,
239        alias_oracle: &impl AliasOracle<D, Q>,
240    ) -> MemoryClobber {
241        let current_epoch = self.epoch;
242        self.frames.clear();
243        self.values.clear();
244        self.frames.push(ResolveFrame::Enter(start));
245
246        while let Some(frame) = self.frames.pop() {
247            match frame {
248                ResolveFrame::Enter(access) => {
249                    if self.epochs[access] == current_epoch && self.states[access] != 0 {
250                        match self.states[access] {
251                            1 => self.values.push(ClobberResolution::Cycle),
252                            2 => self.values.push(
253                                self.results[access]
254                                    .expect("a resolved clobber node retains its result"),
255                            ),
256                            _ => unreachable!("current-epoch clobber state is valid"),
257                        }
258                        continue;
259                    }
260                    self.epochs[access] = current_epoch;
261                    self.states[access] = 1;
262                    self.results[access] = None;
263                    match &nodes[access] {
264                        MemoryAccessNode::LiveOnEntry => {
265                            let result = ClobberResolution::Access(access);
266                            self.states[access] = 2;
267                            self.results[access] = Some(result);
268                            self.values.push(result);
269                        }
270                        MemoryAccessNode::Definition {
271                            definition,
272                            previous,
273                        } => {
274                            if alias_oracle.may_alias(definition, query) {
275                                let result = ClobberResolution::Access(access);
276                                self.states[access] = 2;
277                                self.results[access] = Some(result);
278                                self.values.push(result);
279                            } else {
280                                self.frames.push(ResolveFrame::FinishDefinition(access));
281                                self.frames.push(ResolveFrame::Enter(previous.0));
282                            }
283                        }
284                        MemoryAccessNode::Phi { inputs, .. } => {
285                            self.frames.push(ResolveFrame::FinishPhi {
286                                access,
287                                inputs: inputs.len(),
288                            });
289                            self.frames.extend(
290                                inputs
291                                    .iter()
292                                    .rev()
293                                    .map(|(_, input)| ResolveFrame::Enter(input.0)),
294                            );
295                        }
296                    }
297                }
298                ResolveFrame::FinishDefinition(access) => {
299                    let result = self
300                        .values
301                        .pop()
302                        .expect("a MemoryDef predecessor produces one clobber result");
303                    if result == ClobberResolution::Cycle {
304                        // A disjoint definition on a loop backedge cannot be
305                        // resolved independently of the active MemoryPhi.
306                        self.states[access] = 0;
307                        self.results[access] = None;
308                    } else {
309                        self.states[access] = 2;
310                        self.results[access] = Some(result);
311                    }
312                    self.values.push(result);
313                }
314                ResolveFrame::FinishPhi { access, inputs } => {
315                    let first = self
316                        .values
317                        .len()
318                        .checked_sub(inputs)
319                        .expect("every MemoryPhi input produces one clobber result");
320                    let mut common = None::<ClobberResolution>;
321                    let mut diverged = false;
322                    for result in self.values.drain(first..) {
323                        if result == ClobberResolution::Cycle {
324                            continue;
325                        }
326                        match common {
327                            Some(previous) if previous != result => diverged = true,
328                            Some(_) => {}
329                            None => common = Some(result),
330                        }
331                    }
332                    let result = if diverged {
333                        ClobberResolution::Access(access)
334                    } else {
335                        common.unwrap_or(ClobberResolution::Access(access))
336                    };
337                    self.states[access] = 2;
338                    self.results[access] = Some(result);
339                    self.values.push(result);
340                }
341            }
342        }
343
344        let resolution = self
345            .values
346            .pop()
347            .expect("one clobber query produces one result");
348        debug_assert!(self.values.is_empty());
349        match resolution {
350            ClobberResolution::Access(access) => MemoryClobber::Access(MemoryAccessId(access)),
351            ClobberResolution::Cycle => MemoryClobber::Indeterminate,
352        }
353    }
354}
355
356/// Multi-point clobber query for one immutable alias query. Resolving a phi
357/// root and then its incoming states therefore visits each access at most once
358/// instead of restarting a whole-graph walk per edge.
359pub struct ClobberQuery<'a, D, Q, A> {
360    walker: &'a mut ClobberWalker,
361    graph: &'a MemoryAccessGraph<D>,
362    query: &'a Q,
363    alias_oracle: &'a A,
364}
365
366impl<D, Q, A> ClobberQuery<'_, D, Q, A>
367where
368    A: AliasOracle<D, Q>,
369{
370    pub fn clobber(&mut self, start: MemoryAccessId) -> Option<MemoryClobber> {
371        (start.0 < self.graph.nodes.len()).then(|| {
372            self.walker
373                .find_clobber(&self.graph.nodes, start.0, self.query, self.alias_oracle)
374        })
375    }
376}
377
378#[derive(Debug, Clone, PartialEq, Eq)]
379pub struct MemorySsaError {
380    pub rule: &'static str,
381    pub block: Option<usize>,
382    pub message: String,
383}
384
385impl MemorySsaError {
386    fn new(rule: &'static str, block: Option<usize>, message: impl Into<String>) -> Self {
387        Self {
388            rule,
389            block,
390            message: message.into(),
391        }
392    }
393}
394
395impl fmt::Display for MemorySsaError {
396    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
397        write!(formatter, "{}", self.rule)?;
398        if let Some(block) = self.block {
399            write!(formatter, " at block {block}")?;
400        }
401        write!(formatter, ": {}", self.message)
402    }
403}
404
405impl std::error::Error for MemorySsaError {}
406
407impl From<ssa::SsaError> for MemorySsaError {
408    fn from(error: ssa::SsaError) -> Self {
409        Self {
410            rule: error.rule,
411            block: error.block,
412            message: error.message,
413        }
414    }
415}
416
417#[derive(Debug)]
418struct PendingPoint<D, P> {
419    point: P,
420    before_usage: usize,
421    definition: Option<D>,
422}
423
424#[derive(Debug)]
425struct PendingDefinition<D> {
426    definition: D,
427    predecessor_usage: usize,
428}
429
430/// Build a standard access-based MemorySSA graph and a separate coordinate
431/// map.  The caller decides which events are memory definitions; no effect or
432/// alias representation crosses this interface.
433pub fn build<D, P>(
434    cfg: &impl SsaCfg,
435    memory_events: &[Vec<MemoryAccessEvent<D, P>>],
436) -> Result<(MemoryAccessGraph<D>, MemoryPointMap<P>), MemorySsaError>
437where
438    D: Copy + Ord,
439    P: Copy + Ord,
440{
441    if memory_events.len() != cfg.successors().len() {
442        return Err(MemorySsaError::new(
443            "MEMORY_SSA.MODEL_SHAPE",
444            None,
445            "memory-event and CFG block tables have different lengths",
446        ));
447    }
448
449    // A single SSA variable represents abstract memory state.  Uses at event
450    // and block boundaries exist solely to build the separately returned
451    // coordinate map.
452    let mut events = vec![Vec::<Event<(), D, usize>>::new(); memory_events.len()];
453    let mut pending_points = Vec::<PendingPoint<D, P>>::new();
454    let mut pending_definitions = Vec::<PendingDefinition<D>>::new();
455    let mut block_entry_usages = Vec::with_capacity(memory_events.len());
456    let mut block_exit_usages = Vec::with_capacity(memory_events.len());
457    let mut point_ids = BTreeSet::<P>::new();
458    let mut next_usage = 0usize;
459
460    for (block, block_events) in memory_events.iter().enumerate() {
461        let entry_usage = allocate_usage(&mut next_usage)?;
462        events[block].push(Event::Use {
463            variable: (),
464            usage: entry_usage,
465        });
466        block_entry_usages.push(entry_usage);
467
468        for event in block_events {
469            if !point_ids.insert(event.point) {
470                return Err(MemorySsaError::new(
471                    "MEMORY_SSA.POINT_IDENTITY",
472                    Some(block),
473                    "one memory program-point identity occurs more than once",
474                ));
475            }
476            let before_usage = allocate_usage(&mut next_usage)?;
477            events[block].push(Event::Use {
478                variable: (),
479                usage: before_usage,
480            });
481            pending_points.push(PendingPoint {
482                point: event.point,
483                before_usage,
484                definition: event.definition,
485            });
486            if let Some(definition) = event.definition {
487                events[block].push(Event::Definition {
488                    variable: (),
489                    definition,
490                });
491                pending_definitions.push(PendingDefinition {
492                    definition,
493                    predecessor_usage: before_usage,
494                });
495            }
496        }
497
498        let exit_usage = allocate_usage(&mut next_usage)?;
499        events[block].push(Event::Use {
500            variable: (),
501            usage: exit_usage,
502        });
503        block_exit_usages.push(exit_usage);
504    }
505
506    let ssa = ssa::build(cfg, &events)?;
507    let mut definition_accesses = BTreeMap::<D, MemoryAccessId>::new();
508    for (definition_index, definition) in pending_definitions.iter().enumerate() {
509        let access = MemoryAccessId(definition_index + 1);
510        if definition_accesses
511            .insert(definition.definition, access)
512            .is_some()
513        {
514            return Err(MemorySsaError::new(
515                "MEMORY_SSA.DEFINITION_IDENTITY",
516                None,
517                "one definition identity has multiple MemoryDefs",
518            ));
519        }
520    }
521
522    let mut phi_accesses = BTreeMap::<usize, MemoryAccessId>::new();
523    let phi_start = pending_definitions.len() + 1;
524    for (phi_index, phi) in ssa.phis.iter().enumerate() {
525        let access = MemoryAccessId(phi_start + phi_index);
526        if phi_accesses.insert(phi.block, access).is_some() {
527            return Err(MemorySsaError::new(
528                "MEMORY_SSA.PHI_IDENTITY",
529                Some(phi.block),
530                "one block has multiple phis for the single memory state",
531            ));
532        }
533    }
534
535    let mut nodes = Vec::with_capacity(1 + pending_definitions.len() + ssa.phis.len());
536    nodes.push(MemoryAccessNode::LiveOnEntry);
537    for definition in &pending_definitions {
538        let access = definition_accesses[&definition.definition];
539        let previous = ssa
540            .uses
541            .get(&definition.predecessor_usage)
542            .copied()
543            .ok_or_else(|| {
544                MemorySsaError::new(
545                    "MEMORY_SSA.DEFINITION_PREDECESSOR",
546                    None,
547                    "MemoryDef has no reaching memory state",
548                )
549            })?;
550        let previous = access_for_version(previous, &definition_accesses, &phi_accesses)?;
551        debug_assert_eq!(nodes.len(), access.0);
552        nodes.push(MemoryAccessNode::Definition {
553            definition: definition.definition,
554            previous,
555        });
556    }
557    for phi in &ssa.phis {
558        let access = phi_accesses[&phi.block];
559        let inputs = phi
560            .inputs
561            .iter()
562            .map(|&(predecessor, version)| {
563                access_for_version(version, &definition_accesses, &phi_accesses)
564                    .map(|access| (predecessor, access))
565            })
566            .collect::<Result<Vec<_>, _>>()?;
567        debug_assert_eq!(nodes.len(), access.0);
568        nodes.push(MemoryAccessNode::Phi {
569            block: phi.block,
570            inputs,
571        });
572    }
573
574    let usage_access = |usage| {
575        let version = ssa.uses.get(&usage).copied().ok_or_else(|| {
576            MemorySsaError::new(
577                "MEMORY_SSA.POINT_VERSION",
578                None,
579                "memory program point has no reaching memory state",
580            )
581        })?;
582        access_for_version(version, &definition_accesses, &phi_accesses)
583    };
584    let mut point_accesses = BTreeMap::<P, MemoryPointAccess>::new();
585    for point in pending_points {
586        let before = usage_access(point.before_usage)?;
587        let after = point
588            .definition
589            .map_or(before, |definition| definition_accesses[&definition]);
590        if point_accesses
591            .insert(point.point, MemoryPointAccess { before, after })
592            .is_some()
593        {
594            return Err(MemorySsaError::new(
595                "MEMORY_SSA.POINT_ACCESS_IDENTITY",
596                None,
597                "one program point has multiple MemorySSA coordinate records",
598            ));
599        }
600    }
601    let block_entries = block_entry_usages
602        .into_iter()
603        .map(usage_access)
604        .collect::<Result<Vec<_>, _>>()?;
605    let block_exits = block_exit_usages
606        .into_iter()
607        .map(usage_access)
608        .collect::<Result<Vec<_>, _>>()?;
609
610    Ok((
611        MemoryAccessGraph {
612            nodes,
613            definition_count: pending_definitions.len(),
614            phi_count: ssa.phis.len(),
615        },
616        MemoryPointMap {
617            events: point_accesses,
618            block_entries,
619            block_exits,
620        },
621    ))
622}
623
624fn allocate_usage(next_usage: &mut usize) -> Result<usize, MemorySsaError> {
625    let usage = *next_usage;
626    *next_usage = next_usage.checked_add(1).ok_or_else(|| {
627        MemorySsaError::new(
628            "MEMORY_SSA.USE_ID_RANGE",
629            None,
630            "memory use count exceeds usize",
631        )
632    })?;
633    Ok(usage)
634}
635
636fn access_for_version<D: Copy + Ord>(
637    version: Version<(), D>,
638    definitions: &BTreeMap<D, MemoryAccessId>,
639    phis: &BTreeMap<usize, MemoryAccessId>,
640) -> Result<MemoryAccessId, MemorySsaError> {
641    match version {
642        Version::Entry(()) => Ok(MemoryAccessId(0)),
643        Version::Definition { definition, .. } => {
644            definitions.get(&definition).copied().ok_or_else(|| {
645                MemorySsaError::new(
646                    "MEMORY_SSA.DEFINITION_ACCESS",
647                    None,
648                    "SSA definition has no MemoryDef",
649                )
650            })
651        }
652        Version::Phi { block, .. } => phis.get(&block).copied().ok_or_else(|| {
653            MemorySsaError::new(
654                "MEMORY_SSA.PHI_ACCESS",
655                Some(block),
656                "SSA phi has no MemoryPhi",
657            )
658        }),
659    }
660}
661
662#[cfg(test)]
663mod tests {
664    use super::*;
665    use crate::cfg::ControlFlowGraph;
666    use crate::memory::{MemoryEffect, MemoryLocation, effects_may_alias};
667
668    type Object = u8;
669    type Instruction = (usize, usize);
670
671    #[derive(Debug)]
672    struct EffectEvent {
673        instruction: Instruction,
674        reads: Vec<MemoryEffect<Object>>,
675        writes: Vec<MemoryEffect<Object>>,
676    }
677
678    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
679    enum TestClobber {
680        LiveOnEntry,
681        Definition(Instruction),
682        Phi(usize),
683        Indeterminate,
684    }
685
686    struct Analysis {
687        graph: MemoryAccessGraph<Instruction>,
688        points: MemoryPointMap<Instruction>,
689        writes: BTreeMap<Instruction, Vec<MemoryEffect<Object>>>,
690        reads: Vec<(Instruction, usize, MemoryEffect<Object>)>,
691    }
692
693    impl Analysis {
694        fn clobber(&self, instruction: Instruction, query: MemoryEffect<Object>) -> TestClobber {
695            let start = self.points.event(instruction).unwrap().before;
696            let oracle = |definition: &Instruction, query: &MemoryEffect<Object>| {
697                self.writes[definition]
698                    .iter()
699                    .copied()
700                    .any(|write| effects_may_alias(write, *query))
701            };
702            let mut walker = ClobberWalker::new();
703            match walker.clobber(&self.graph, start, &query, &oracle).unwrap() {
704                MemoryClobber::Indeterminate => TestClobber::Indeterminate,
705                MemoryClobber::Access(access) => match self.graph.access(access).unwrap() {
706                    MemoryAccess::LiveOnEntry => TestClobber::LiveOnEntry,
707                    MemoryAccess::Definition { definition, .. } => {
708                        TestClobber::Definition(*definition)
709                    }
710                    MemoryAccess::Phi { block, .. } => TestClobber::Phi(block),
711                },
712            }
713        }
714
715        fn only_clobber(&self) -> TestClobber {
716            assert_eq!(self.reads.len(), 1);
717            let (instruction, _, query) = self.reads[0];
718            self.clobber(instruction, query)
719        }
720    }
721
722    fn exact(object: Object, offset: i64, byte_len: usize) -> MemoryEffect<Object> {
723        MemoryEffect::Exact(MemoryLocation {
724            object,
725            offset,
726            byte_len,
727        })
728    }
729
730    fn event(
731        instruction: Instruction,
732        reads: Vec<MemoryEffect<Object>>,
733        writes: Vec<MemoryEffect<Object>>,
734    ) -> EffectEvent {
735        EffectEvent {
736            instruction,
737            reads,
738            writes,
739        }
740    }
741
742    fn analyze(cfg: &ControlFlowGraph, events: &[Vec<EffectEvent>]) -> Analysis {
743        let mut access_events = vec![Vec::new(); events.len()];
744        let mut writes = BTreeMap::new();
745        let mut reads = Vec::new();
746        for (block, block_events) in events.iter().enumerate() {
747            for event in block_events {
748                for (read_index, &read) in event.reads.iter().enumerate() {
749                    reads.push((event.instruction, read_index, read));
750                }
751                if !event.writes.is_empty() {
752                    writes.insert(event.instruction, event.writes.clone());
753                }
754                access_events[block].push(MemoryAccessEvent {
755                    point: event.instruction,
756                    definition: (!event.writes.is_empty()).then_some(event.instruction),
757                });
758            }
759        }
760        let (graph, points) = build(cfg, &access_events).unwrap();
761        Analysis {
762            graph,
763            points,
764            writes,
765            reads,
766        }
767    }
768
769    #[test]
770    fn exact_store_reaches_later_load() {
771        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
772        let analysis = analyze(
773            &cfg,
774            &[vec![
775                event((0, 0), vec![], vec![exact(1, 8, 4)]),
776                event((0, 1), vec![exact(1, 8, 4)], vec![]),
777            ]],
778        );
779
780        assert_eq!(analysis.only_clobber(), TestClobber::Definition((0, 0)));
781        assert_eq!(analysis.graph.definition_count(), 1);
782        assert_eq!(analysis.graph.phi_count(), 0);
783        assert_eq!(analysis.graph.access_count(), 2);
784    }
785
786    #[test]
787    fn point_map_supports_lowering_coordinates_without_owning_queries() {
788        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
789        let analysis = analyze(&cfg, &[vec![event((0, 0), vec![], vec![exact(1, 8, 8)])]]);
790        let event = analysis.points.event((0, 0)).unwrap();
791
792        assert_eq!(
793            analysis.clobber((0, 0), exact(1, 8, 8)),
794            TestClobber::LiveOnEntry
795        );
796        let oracle = |definition: &Instruction, query: &MemoryEffect<Object>| {
797            analysis.writes[definition]
798                .iter()
799                .copied()
800                .any(|write| effects_may_alias(write, *query))
801        };
802        let mut walker = ClobberWalker::new();
803        let after = walker
804            .clobber(&analysis.graph, event.after, &exact(1, 8, 8), &oracle)
805            .unwrap();
806        let MemoryClobber::Access(after) = after else {
807            panic!("a store's post-state has a concrete clobber")
808        };
809        assert!(matches!(
810            analysis.graph.access(after),
811            Some(MemoryAccess::Definition {
812                definition: &(0, 0),
813                ..
814            })
815        ));
816        assert_eq!(analysis.points.block_entry(0), Some(event.before));
817        assert_eq!(analysis.points.block_exit(0), Some(event.after));
818    }
819
820    #[test]
821    fn disjoint_store_is_skipped_by_the_external_alias_oracle() {
822        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
823        let analysis = analyze(
824            &cfg,
825            &[vec![
826                event((0, 0), vec![], vec![exact(1, 0, 8)]),
827                event((0, 1), vec![exact(1, 16, 8)], vec![]),
828            ]],
829        );
830
831        assert_eq!(analysis.only_clobber(), TestClobber::LiveOnEntry);
832    }
833
834    #[test]
835    fn partial_overlap_and_unknown_object_are_clobbers() {
836        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
837        let overlap = analyze(
838            &cfg,
839            &[vec![
840                event((0, 0), vec![], vec![exact(1, 4, 8)]),
841                event((0, 1), vec![exact(1, 8, 8)], vec![]),
842            ]],
843        );
844        assert_eq!(overlap.only_clobber(), TestClobber::Definition((0, 0)));
845
846        let unknown = analyze(
847            &cfg,
848            &[vec![
849                event((0, 0), vec![], vec![MemoryEffect::UnknownObject(1)]),
850                event((0, 1), vec![exact(1, 8, 8)], vec![]),
851            ]],
852        );
853        assert_eq!(unknown.only_clobber(), TestClobber::Definition((0, 0)));
854    }
855
856    #[test]
857    fn one_arm_store_resolves_to_the_join_phi() {
858        let cfg = ControlFlowGraph::analyze(vec![vec![1, 2], vec![3], vec![3], vec![]], 0).unwrap();
859        let analysis = analyze(
860            &cfg,
861            &[
862                vec![],
863                vec![event((1, 0), vec![], vec![exact(1, 8, 8)])],
864                vec![],
865                vec![event((3, 0), vec![exact(1, 8, 8)], vec![])],
866            ],
867        );
868
869        assert_eq!(analysis.only_clobber(), TestClobber::Phi(3));
870        assert_eq!(analysis.graph.phi_count(), 1);
871    }
872
873    #[test]
874    fn one_query_session_reuses_phi_input_clobbers() {
875        let cfg = ControlFlowGraph::analyze(vec![vec![1, 2], vec![3], vec![3], vec![]], 0).unwrap();
876        let analysis = analyze(
877            &cfg,
878            &[
879                vec![],
880                vec![event((1, 0), vec![], vec![exact(1, 8, 8)])],
881                vec![],
882                vec![event((3, 0), vec![exact(1, 8, 8)], vec![])],
883            ],
884        );
885        let calls = std::cell::Cell::new(0usize);
886        let oracle = |definition: &Instruction, query: &MemoryEffect<Object>| {
887            calls.set(calls.get() + 1);
888            analysis.writes[definition]
889                .iter()
890                .copied()
891                .any(|write| effects_may_alias(write, *query))
892        };
893        let query = exact(1, 8, 8);
894        let mut walker = ClobberWalker::new();
895        let mut session = walker.query(&analysis.graph, &query, &oracle);
896        let join = analysis.points.event((3, 0)).unwrap().before;
897        assert!(matches!(
898            session.clobber(join),
899            Some(MemoryClobber::Access(_))
900        ));
901        let calls_after_join = calls.get();
902        let left_exit = analysis.points.block_exit(1).unwrap();
903        assert!(matches!(
904            session.clobber(left_exit),
905            Some(MemoryClobber::Access(_))
906        ));
907        assert_eq!(calls.get(), calls_after_join);
908    }
909
910    #[test]
911    fn same_dominating_store_is_found_through_a_join() {
912        let cfg = ControlFlowGraph::analyze(vec![vec![1, 2], vec![3], vec![3], vec![]], 0).unwrap();
913        let analysis = analyze(
914            &cfg,
915            &[
916                vec![event((0, 0), vec![], vec![exact(1, 8, 8)])],
917                vec![],
918                vec![],
919                vec![event((3, 0), vec![exact(1, 8, 8)], vec![])],
920            ],
921        );
922
923        assert_eq!(analysis.only_clobber(), TestClobber::Definition((0, 0)));
924    }
925
926    #[test]
927    fn disjoint_loop_definition_does_not_hide_dominating_store() {
928        let cfg = ControlFlowGraph::analyze(vec![vec![1], vec![1, 2], vec![]], 0).unwrap();
929        let analysis = analyze(
930            &cfg,
931            &[
932                vec![event((0, 0), vec![], vec![exact(1, 8, 8)])],
933                vec![
934                    event((1, 0), vec![], vec![exact(1, 64, 8)]),
935                    event((1, 1), vec![exact(1, 8, 8)], vec![]),
936                ],
937                vec![],
938            ],
939        );
940
941        assert_eq!(analysis.only_clobber(), TestClobber::Definition((0, 0)));
942        assert_eq!(analysis.graph.phi_count(), 1);
943    }
944
945    #[test]
946    fn aliasing_loop_definition_resolves_to_the_header_phi() {
947        let cfg = ControlFlowGraph::analyze(vec![vec![1], vec![1, 2], vec![]], 0).unwrap();
948        let analysis = analyze(
949            &cfg,
950            &[
951                vec![event((0, 0), vec![], vec![exact(1, 8, 8)])],
952                vec![event((1, 0), vec![], vec![exact(1, 8, 1)])],
953                vec![],
954            ],
955        );
956
957        let exit = analysis.points.block_exit(1).unwrap();
958        let entry = analysis.points.block_entry(1).unwrap();
959        let oracle = |definition: &Instruction, query: &MemoryEffect<Object>| {
960            analysis.writes[definition]
961                .iter()
962                .copied()
963                .any(|write| effects_may_alias(write, *query))
964        };
965        let classify = |clobber| match clobber {
966            MemoryClobber::Indeterminate => TestClobber::Indeterminate,
967            MemoryClobber::Access(access) => match analysis.graph.access(access).unwrap() {
968                MemoryAccess::LiveOnEntry => TestClobber::LiveOnEntry,
969                MemoryAccess::Definition { definition, .. } => TestClobber::Definition(*definition),
970                MemoryAccess::Phi { block, .. } => TestClobber::Phi(block),
971            },
972        };
973        let mut walker = ClobberWalker::new();
974        assert_eq!(
975            classify(
976                walker
977                    .clobber(&analysis.graph, exit, &exact(1, 8, 8), &oracle)
978                    .unwrap()
979            ),
980            TestClobber::Definition((1, 0))
981        );
982        assert_eq!(
983            classify(
984                walker
985                    .clobber(&analysis.graph, entry, &exact(1, 8, 8), &oracle)
986                    .unwrap()
987            ),
988            TestClobber::Phi(1)
989        );
990    }
991
992    #[test]
993    fn graph_size_is_independent_of_effect_range_length() {
994        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
995        let analysis = analyze(
996            &cfg,
997            &[vec![
998                event((0, 0), vec![], vec![exact(1, 1_000_000, 16 * 1024 * 1024)]),
999                event((0, 1), vec![exact(1, 2_000_000, 8)], vec![]),
1000            ]],
1001        );
1002
1003        assert_eq!(analysis.only_clobber(), TestClobber::Definition((0, 0)));
1004        assert_eq!(analysis.graph.definition_count(), 1);
1005        assert_eq!(analysis.graph.access_count(), 2);
1006    }
1007
1008    #[test]
1009    fn custom_alias_domain_needs_no_memory_effect_types() {
1010        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
1011        let (graph, points) = build(
1012            &cfg,
1013            &[vec![
1014                MemoryAccessEvent {
1015                    point: 0u8,
1016                    definition: Some(10u8),
1017                },
1018                MemoryAccessEvent {
1019                    point: 1u8,
1020                    definition: None,
1021                },
1022            ]],
1023        )
1024        .unwrap();
1025        let oracle = |definition: &u8, query: &u8| definition % 10 == *query;
1026        let mut walker = ClobberWalker::new();
1027        let clobber = walker
1028            .clobber(&graph, points.event(1).unwrap().before, &0, &oracle)
1029            .unwrap();
1030        let MemoryClobber::Access(access) = clobber else {
1031            panic!("the custom oracle finds one definition")
1032        };
1033        assert!(matches!(
1034            graph.access(access),
1035            Some(MemoryAccess::Definition { definition: 10, .. })
1036        ));
1037    }
1038}
celox_analysis/memory_ssa.rs

celox_analysis/
memory_ssa.rs
