Skip to main content

rapx/analysis/dataflow/
pointer_offset.rs

1//! Infer pointer offset direction from a callee's MIR.
2
3use std::collections::HashSet;
4
5use rustc_hir::def_id::DefId;
6use rustc_middle::{
7    mir::{BinOp, Body, Local, Operand, Rvalue, StatementKind, TerminatorKind},
8    ty::{TyCtxt, TypingEnv},
9};
10
11use crate::{
12    def_ids::{intrinsic_api, other_api},
13    util::mir_utils,
14};
15
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub(crate) enum PointerOffsetDirection {
18    Forward,
19    Backward,
20}
21
22#[derive(Clone, Copy, PartialEq, Eq)]
23struct PointerOffset {
24    base: usize,
25    count: Option<usize>,
26    direction: PointerOffsetDirection,
27}
28
29/// Infer the direction of a pointer offset from optimized MIR, including
30/// wrappers around `Offset` and the `arith_offset` intrinsic.
31pub(crate) fn pointer_offset_direction(
32    tcx: TyCtxt<'_>,
33    callee: DefId,
34) -> Option<PointerOffsetDirection> {
35    let offset = pointer_offset(tcx, callee, 6)?;
36    (offset.base == 0 && offset.count == Some(1)).then_some(offset.direction)
37}
38
39fn pointer_offset(tcx: TyCtxt<'_>, callee: DefId, depth: usize) -> Option<PointerOffset> {
40    if depth == 0 || !tcx.is_mir_available(callee) {
41        return None;
42    }
43    let body = tcx.optimized_mir(callee);
44    let pointee = body
45        .local_decls
46        .get(Local::from_usize(1))
47        .and_then(|decl| mir_utils::pointee_ty(decl.ty));
48    let mut zst_switches = Vec::new();
49    let mut ub_switches = Vec::new();
50    let only_zst_or_ub_switches = body.basic_blocks.iter_enumerated().all(|(bb, block)| {
51        let TerminatorKind::SwitchInt { discr, .. } = &block.terminator().kind else {
52            return true;
53        };
54        if zst_property_operand(tcx, body, discr, pointee) {
55            zst_switches.push(bb);
56            true
57        } else if ub_check_result_operand(tcx, body, discr) {
58            ub_switches.push(bb);
59            true
60        } else {
61            false
62        }
63    });
64    let ub_checks_precede_zst = if ub_switches.is_empty() {
65        true
66    } else if let [zst_bb] = zst_switches.as_slice() {
67        let dominators = body.basic_blocks.dominators();
68        ub_switches
69            .iter()
70            .all(|&bb| dominators.dominates(bb, *zst_bb))
71            && body
72                .basic_blocks
73                .iter_enumerated()
74                .filter(|(_, block)| matches!(block.terminator().kind, TerminatorKind::Return))
75                .all(|(bb, _)| dominators.dominates(*zst_bb, bb))
76    } else {
77        false
78    };
79    let zst_branch = !zst_switches.is_empty() && only_zst_or_ub_switches && ub_checks_precede_zst;
80    trace_pointer_offset(
81        tcx,
82        body,
83        rustc_middle::mir::RETURN_PLACE,
84        depth,
85        zst_branch,
86        &mut HashSet::new(),
87    )
88}
89
90/// A debug UB check may branch before the ZST switch without changing the result.
91fn ub_check_result_operand(tcx: TyCtxt<'_>, body: &Body<'_>, discr: &Operand<'_>) -> bool {
92    let Some(place) = mir_utils::operand_mir_place(discr) else {
93        return false;
94    };
95    if !place.projection.is_empty() {
96        return false;
97    }
98    let mut callee = None;
99    for block in body.basic_blocks.iter() {
100        if block.statements.iter().any(|stmt| {
101            matches!(&stmt.kind,
102            StatementKind::Assign(assign) if assign.0.local == place.local)
103        }) {
104            return false;
105        }
106        if let TerminatorKind::Call {
107            func, destination, ..
108        } = &block.terminator().kind
109            && destination.local == place.local
110        {
111            if !destination.projection.is_empty() || callee.is_some() {
112                return false;
113            }
114            let Some(did) = mir_utils::dep_callee_def_id(func) else {
115                return false;
116            };
117            callee = Some(did);
118        }
119    }
120    callee.is_some_and(|did| other_api::is_ub_check(tcx, did))
121}
122
123fn trace_pointer_offset<'tcx>(
124    tcx: TyCtxt<'tcx>,
125    body: &Body<'tcx>,
126    local: Local,
127    depth: usize,
128    zst_branch: bool,
129    seen: &mut HashSet<Local>,
130) -> Option<PointerOffset> {
131    if !seen.insert(local) {
132        return None;
133    }
134    let index = local.as_usize();
135    if index > 0 && index <= body.arg_count {
136        return Some(PointerOffset {
137            base: index - 1,
138            count: None,
139            direction: PointerOffsetDirection::Forward,
140        });
141    }
142    let mut result = None;
143    for block in body.basic_blocks.iter() {
144        for stmt in &block.statements {
145            let StatementKind::Assign(assign) = &stmt.kind else {
146                continue;
147            };
148            let (dest, rvalue) = &**assign;
149            if dest.local != local || !dest.projection.is_empty() {
150                continue;
151            }
152            let candidate = match rvalue {
153                Rvalue::Use(op, _) | Rvalue::Cast(_, op, _) => {
154                    let source = mir_utils::operand_mir_place(op)?;
155                    trace_pointer_offset(
156                        tcx,
157                        body,
158                        source.local,
159                        depth,
160                        zst_branch,
161                        &mut seen.clone(),
162                    )?
163                }
164                Rvalue::BinaryOp(BinOp::Offset, operands) => {
165                    let base = mir_utils::operand_mir_place(&operands.0)?;
166                    let base = trace_pointer_offset(
167                        tcx,
168                        body,
169                        base.local,
170                        depth,
171                        zst_branch,
172                        &mut seen.clone(),
173                    )?;
174                    if base.count.is_some() {
175                        return None;
176                    }
177                    let (count, backward) =
178                        trace_offset_count(tcx, body, &operands.1, &mut HashSet::new())?;
179                    PointerOffset {
180                        base: base.base,
181                        count: Some(count),
182                        direction: if backward {
183                            PointerOffsetDirection::Backward
184                        } else {
185                            PointerOffsetDirection::Forward
186                        },
187                    }
188                }
189                Rvalue::Aggregate(kind, operands)
190                    if operands.len() == 1
191                        || matches!(&**kind, rustc_middle::mir::AggregateKind::RawPtr(..)) =>
192                {
193                    let source = mir_utils::operand_mir_place(operands.iter().next()?)?;
194                    trace_pointer_offset(
195                        tcx,
196                        body,
197                        source.local,
198                        depth,
199                        zst_branch,
200                        &mut seen.clone(),
201                    )?
202                }
203                _ => return None,
204            };
205            result = Some(merge_pointer_offsets(result, candidate, zst_branch)?);
206        }
207        let TerminatorKind::Call {
208            func,
209            args,
210            destination,
211            ..
212        } = &block.terminator().kind
213        else {
214            continue;
215        };
216        if destination.local != local || !destination.projection.is_empty() {
217            continue;
218        }
219        let callee = mir_utils::dep_callee_def_id(func)?;
220        let intrinsic = intrinsic_api::intrinsic_name(tcx, Some(callee))
221            .is_some_and(|name| name.as_str() == "arith_offset");
222        let nested = if intrinsic {
223            PointerOffset {
224                base: 0,
225                count: Some(1),
226                direction: PointerOffsetDirection::Forward,
227            }
228        } else {
229            pointer_offset(tcx, callee, depth - 1)?
230        };
231        let base_arg = args.get(nested.base)?;
232        let base_place = mir_utils::operand_mir_place(&base_arg.node)?;
233        let base = trace_pointer_offset(
234            tcx,
235            body,
236            base_place.local,
237            depth,
238            zst_branch,
239            &mut seen.clone(),
240        )?;
241        if base.count.is_some() {
242            return None;
243        }
244        let candidate = if let Some(count_index) = nested.count {
245            let (count, negative) =
246                trace_offset_count(tcx, body, &args.get(count_index)?.node, &mut HashSet::new())?;
247            PointerOffset {
248                base: base.base,
249                count: Some(count),
250                direction: if negative == (nested.direction == PointerOffsetDirection::Backward) {
251                    PointerOffsetDirection::Forward
252                } else {
253                    PointerOffsetDirection::Backward
254                },
255            }
256        } else {
257            base
258        };
259        result = Some(merge_pointer_offsets(result, candidate, zst_branch)?);
260    }
261    result
262}
263
264fn zst_property_operand<'tcx>(
265    tcx: TyCtxt<'tcx>,
266    body: &Body<'tcx>,
267    operand: &Operand<'tcx>,
268    pointee: Option<rustc_middle::ty::Ty<'tcx>>,
269) -> bool {
270    let Some(pointee) = pointee else {
271        return false;
272    };
273    let constant = match operand {
274        Operand::Constant(constant) => Some(constant),
275        Operand::Copy(place) | Operand::Move(place) => {
276            let mut found = None;
277            for stmt in body.basic_blocks.iter().flat_map(|block| &block.statements) {
278                let StatementKind::Assign(assign) = &stmt.kind else {
279                    continue;
280                };
281                if assign.0.local != place.local {
282                    continue;
283                }
284                let Rvalue::Use(Operand::Constant(value), _) = &assign.1 else {
285                    return false;
286                };
287                if found.replace(value).is_some() {
288                    return false;
289                }
290            }
291            found
292        }
293        Operand::RuntimeChecks(_) => None,
294    };
295    let Some(constant) = constant else {
296        return false;
297    };
298    let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_ else {
299        return false;
300    };
301    mir_utils::is_sized_type_property(tcx, uneval.def, "IS_ZST")
302        && uneval.args.types().next() == Some(pointee)
303}
304
305fn merge_pointer_offsets(
306    current: Option<PointerOffset>,
307    next: PointerOffset,
308    zst_branch: bool,
309) -> Option<PointerOffset> {
310    match current {
311        None => Some(next),
312        Some(old) if old == next => Some(old),
313        Some(old) if zst_branch && old.base == next.base && old.count.is_none() => Some(next),
314        Some(old) if zst_branch && old.base == next.base && next.count.is_none() => Some(old),
315        _ => None,
316    }
317}
318
319fn trace_offset_count<'tcx>(
320    tcx: TyCtxt<'tcx>,
321    body: &Body<'tcx>,
322    operand: &Operand<'tcx>,
323    seen: &mut HashSet<Local>,
324) -> Option<(usize, bool)> {
325    let place = mir_utils::operand_mir_place(operand)?;
326    let local = place.local;
327    if !seen.insert(local) {
328        return None;
329    }
330    let index = local.as_usize();
331    if index > 0 && index <= body.arg_count {
332        return Some((index - 1, false));
333    }
334    let mut result = None;
335    for block in body.basic_blocks.iter() {
336        for stmt in &block.statements {
337            let StatementKind::Assign(assign) = &stmt.kind else {
338                continue;
339            };
340            if assign.0.local != local || !assign.0.projection.is_empty() {
341                continue;
342            }
343            let candidate = match &assign.1 {
344                Rvalue::Use(op, _) | Rvalue::Cast(_, op, _) => {
345                    trace_offset_count(tcx, body, op, &mut seen.clone())?
346                }
347                Rvalue::BinaryOp(BinOp::Sub | BinOp::SubUnchecked, operands)
348                    if is_zero_constant(tcx, &operands.0) =>
349                {
350                    let (arg, neg) = trace_offset_count(tcx, body, &operands.1, &mut seen.clone())?;
351                    (arg, !neg)
352                }
353                _ => return None,
354            };
355            if result.is_some_and(|old| old != candidate) {
356                return None;
357            }
358            result = Some(candidate);
359        }
360    }
361    result
362}
363
364fn is_zero_constant<'tcx>(tcx: TyCtxt<'tcx>, operand: &Operand<'tcx>) -> bool {
365    let Operand::Constant(c) = operand else {
366        return false;
367    };
368    c.const_
369        .eval(tcx, TypingEnv::fully_monomorphized(), rustc_span::DUMMY_SP)
370        .ok()
371        .and_then(|value| value.try_to_scalar_int())
372        .is_some_and(|scalar| scalar.to_bits(scalar.size()) == 0)
373}