charon_lib/ast/bodies/
unstructured.rs

1//! Bodies with unstructured control-flow, i.e. with a control-flow graph and GOTOs.
2//!
3//! In effect, this is a cleaned up version of MIR.
4use derive_generic_visitor::{Drive, DriveMut, DriveTwo};
5use macros::{EnumAsGetters, EnumIsA, VariantName};
6use rustc_hash::FxHashMap as HashMap;
7use serde_state::{DeserializeState, SerializeState};
8use smallvec::{SmallVec, smallvec};
9use std::mem;
10use std::ops::{Index, IndexMut};
11
12use crate::ast::*;
13
14// Block identifier. Similar to rust's `BasicBlock`.
15generate_index_type!(BlockId, "Block");
16
17// The entry block of a function is always the block with id 0
18pub static START_BLOCK_ID: BlockId = BlockId::ZERO;
19
20#[cfg_attr(feature = "charon_on_charon", charon::rename("Blocks"))]
21pub type BodyContents = IndexVec<BlockId, BlockData>;
22pub type ExprBody = GExprBody<BodyContents>;
23
24/// A "basic block", which contains a linear sequence of statements, followed by a terminator, which
25/// is where non-linear control-flow happens.
26#[derive(Debug, Clone, PartialEq, Eq)]
27#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
28#[cfg_attr(feature = "charon_on_charon", charon::rename("Block"))]
29pub struct BlockData {
30    pub statements: Vec<Statement>,
31    pub terminator: Terminator,
32    pub kind: UnwindKind,
33}
34
35/// Where a block runs relative to unwinding.
36#[derive(Debug, Copy, Clone, PartialEq, Eq)]
37#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
38pub enum UnwindKind {
39    /// A non-unwind block; it may start unwinding.
40    Regular,
41    /// An unwind block that may continue unwinding.
42    Cleanup,
43    /// An unwind block that may only terminate the execution; used for double-unwinds or unwinding
44    /// across incompatible ABI boundaries.
45    Terminate,
46}
47
48/// A statement.
49#[derive(Debug, Clone, PartialEq, Eq)]
50#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
51pub struct Statement {
52    pub span: Span,
53    pub kind: StatementKind,
54    /// Comments that precede this statement.
55    // This is filled in a late pass after all the control-flow manipulation.
56    pub comments_before: Vec<String>,
57}
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60#[derive(EnumIsA, EnumAsGetters, VariantName)]
61#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
62pub enum StatementKind {
63    Assign(Place, Rvalue),
64    /// A call. For now, we don't support dynamic calls (i.e. to a function pointer in memory).
65    SetDiscriminant(Place, VariantId),
66    /// Indicates that this local should be allocated; if it is already allocated, this frees
67    /// the local and re-allocates it. The arguments do not receive a `StorageLive`. We ensure in
68    /// the micro-pass `insert_storage_statements` that all other locals have a `StorageLive`
69    /// associated with them.
70    StorageLive(LocalId),
71    /// Deallocates the given local; if it is already deallocated, this is
72    /// a no-op. Not all local deallocations are explicit: if a non-return local is still live at
73    /// function end (return or unwind), it is implicitly deallocated.
74    /// If `--deallocate-all-locals` is set, all local deallocations are made explicit.
75    StorageDead(LocalId),
76    /// A place is mentioned, but not accessed. The place itself must still be valid though, so
77    /// this statement is not a no-op: it can trigger UB if the place's projections are not valid
78    /// (e.g. because they go out of bounds).
79    PlaceMention(Place),
80    /// Statements that only affect borrow-checking.
81    Borrowck(BorrowckStatement),
82    /// A non-diverging runtime check for a condition. This can be either:
83    /// - Emitted for inlined "assumes" (which cause UB on failure)
84    /// - Reconstructed from `if b { panic() }` if `--reconstruct-asserts` is set.
85    ///
86    /// This statement comes with the effect that happens when the check fails
87    /// (rather than representing it as an unwinding edge).
88    Assert {
89        assert: Assert,
90        on_failure: AbortKind,
91    },
92    /// Does nothing. Useful for passes.
93    Nop,
94}
95
96#[derive(Debug, Clone, PartialEq, Eq)]
97#[derive(EnumIsA, EnumAsGetters)]
98#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
99pub enum TerminatorKind {
100    Goto {
101        target: BlockId,
102    },
103    Switch {
104        data: SwitchData,
105        branches: IndexVec<BranchId, BlockId>,
106    },
107    Call {
108        call: Call,
109        target: BlockId,
110        on_unwind: BlockId,
111    },
112    /// Drop the value at the given place.
113    ///
114    /// Depending on `DropKind`, this may be a real call to `drop_glue`, or a conditional call
115    /// that should only happen if the place has not been moved out of. See the docs of `DropKind`
116    /// for more details; to get precise drops use `--precise-drops`.
117    Drop {
118        kind: DropKind,
119        place: Place,
120        /// Reference to the `drop_glue` code to call on drop.
121        fn_ptr: FnPtr,
122        target: BlockId,
123        on_unwind: BlockId,
124    },
125    /// An inline assembly block.
126    InlineAsm {
127        asm: InlineAsm,
128        /// Next block if the control-flow continues without jumping. Absent for `naked_asm!` and `noreturn`.
129        fallthrough: Option<BlockId>,
130        /// Targets of [`AsmOperand::Label`] operands.
131        labels: IndexVec<BranchId, BlockId>,
132        /// Action to be taken if the inline assembly unwinds.
133        on_unwind: BlockId,
134    },
135
136    /// Assert that the given condition holds, and if not, unwind to the given block. This is used for
137    /// bounds checks, overflow checks, etc.
138    #[cfg_attr(feature = "charon_on_charon", charon::rename("TAssert"))]
139    Assert {
140        assert: Assert,
141        target: BlockId,
142        on_unwind: BlockId,
143    },
144    /// Call to a built-in panicking function. Only if `--reconstruct-panic-calls` is passed.
145    Panic {
146        /// The name of the function that was called.
147        name: Name,
148        on_unwind: BlockId,
149    },
150    /// Unwinding must stop for ABI reasons or because cleanup code panicked again.
151    UnwindTerminate,
152    /// Unwind out of the current function into its caller.
153    UnwindResume,
154
155    Return,
156    /// Reaching this point is undefined behavior in the Rust abstract machine.
157    UndefinedBehavior,
158}
159
160/// A terminator: instruction to execute at the end of a block, which may jump to other blocks.
161#[derive(Debug, Clone, PartialEq, Eq)]
162#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
163pub struct Terminator {
164    pub span: Span,
165    pub kind: TerminatorKind,
166    /// Comments that precede this terminator.
167    // This is filled in a late pass after all the control-flow manipulation.
168    pub comments_before: Vec<String>,
169}
170
171impl ExprBody {
172    /// Returns a map from blocks in this body to their abort kind, if they correspond to an abort
173    /// block (ie. a block with only bookkeeping statements and an unconditional error terminator).
174    pub fn as_abort_map(&self) -> HashMap<BlockId, AbortKind> {
175        self.body
176            .iter_enumerated()
177            .filter_map(|(bid, block)| block.as_abort().map(|abort| (bid, abort)))
178            .collect()
179    }
180
181    pub fn transform_sequences_fwd<F>(&mut self, mut f: F)
182    where
183        F: FnMut(BlockId, &mut Locals, &mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
184    {
185        for (id, block) in &mut self.body.iter_mut_enumerated() {
186            block.transform_sequences_fwd(|seq| f(id, &mut self.locals, seq));
187        }
188    }
189
190    pub fn transform_sequences_bwd<F>(&mut self, mut f: F)
191    where
192        F: FnMut(&mut Locals, &mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
193    {
194        for block in &mut self.body {
195            block.transform_sequences_bwd(|seq| f(&mut self.locals, seq));
196        }
197    }
198
199    /// Apply a function to all the block ids in this body, i.e. the targets of its terminators.
200    pub fn visit_block_ids_mut<F: FnMut(&mut BlockId)>(&mut self, mut f: F) {
201        for block in &mut self.body {
202            block.terminator.targets_mut().into_iter().for_each(&mut f);
203        }
204    }
205
206    /// Apply a function to all the statements, in a bottom-up manner.
207    pub fn visit_statements<F: FnMut(&mut Statement)>(&mut self, mut f: F) {
208        for block in self.body.iter_mut().rev() {
209            for st in block.statements.iter_mut().rev() {
210                f(st);
211            }
212        }
213    }
214}
215
216impl BlockData {
217    /// Build a block that's just a goto terminator.
218    pub fn new_goto(span: Span, target: BlockId, kind: UnwindKind) -> Self {
219        BlockData {
220            statements: vec![],
221            terminator: Terminator::goto(span, target),
222            kind,
223        }
224    }
225    pub fn as_goto(&self) -> Option<BlockId> {
226        if let TerminatorKind::Goto { target } = self.terminator.kind {
227            Some(target)
228        } else {
229            None
230        }
231    }
232    pub fn as_trivial_goto(&self) -> Option<BlockId> {
233        self.as_goto().filter(|_| {
234            self.statements
235                .iter()
236                .all(|st| matches!(st.kind, StatementKind::Nop))
237        })
238    }
239
240    pub fn as_abort(&self) -> Option<AbortKind> {
241        if self.statements.iter().all(|st| {
242            matches!(
243                st.kind,
244                StatementKind::Nop | StatementKind::StorageLive(_) | StatementKind::StorageDead(_)
245            )
246        }) {
247            match &self.terminator.kind {
248                TerminatorKind::Panic { name, .. } => Some(AbortKind::Panic(Some(name.clone()))),
249                TerminatorKind::UndefinedBehavior => Some(AbortKind::UndefinedBehavior),
250                TerminatorKind::UnwindTerminate => Some(AbortKind::UnwindTerminate),
251                _ => None,
252            }
253        } else {
254            None
255        }
256    }
257
258    /// Build a block that's UB to reach.
259    pub fn new_unreachable(kind: UnwindKind) -> Self {
260        Terminator::new(Span::dummy(), TerminatorKind::UndefinedBehavior).into_block(kind)
261    }
262    /// Replace this block with a dummy block.
263    pub fn take(&mut self) -> Self {
264        mem::replace(self, BlockData::new_unreachable(self.kind))
265    }
266
267    pub fn targets(&self) -> SmallVec<[BlockId; 2]> {
268        self.terminator.targets()
269    }
270    pub fn targets_ignoring_unwind(&self) -> SmallVec<[BlockId; 2]> {
271        self.terminator.targets_ignoring_unwind()
272    }
273
274    /// Apply a transformer to all the statements.
275    ///
276    /// The transformer should:
277    /// - mutate the current statement in place
278    /// - return the sequence of statements to introduce before the current statement
279    pub fn transform<F: FnMut(&mut Statement) -> Vec<Statement>>(&mut self, mut f: F) {
280        self.transform_sequences_fwd(|slice| {
281            let new_statements = f(&mut slice[0]);
282            if new_statements.is_empty() {
283                vec![]
284            } else {
285                vec![(0, new_statements)]
286            }
287        });
288    }
289
290    /// Helper, see `transform_sequences_fwd` and `transform_sequences_bwd`.
291    fn transform_sequences<F>(&mut self, mut f: F, forward: bool)
292    where
293        F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
294    {
295        let mut to_insert = vec![];
296        let mut final_len = self.statements.len();
297        if forward {
298            for i in 0..self.statements.len() {
299                let new_to_insert = f(&mut self.statements[i..]);
300                to_insert.extend(new_to_insert.into_iter().map(|(j, stmts)| {
301                    final_len += stmts.len();
302                    (i + j, stmts)
303                }));
304            }
305        } else {
306            for i in (0..self.statements.len()).rev() {
307                let new_to_insert = f(&mut self.statements[i..]);
308                to_insert.extend(new_to_insert.into_iter().map(|(j, stmts)| {
309                    final_len += stmts.len();
310                    (i + j, stmts)
311                }));
312            }
313        }
314        if !to_insert.is_empty() {
315            to_insert.sort_by_key(|(i, _)| *i);
316            // Make it so the first element is always at the end so we can pop it.
317            to_insert.reverse();
318            // Construct the merged list of statements.
319            let old_statements = mem::replace(&mut self.statements, Vec::with_capacity(final_len));
320            for (i, stmt) in old_statements.into_iter().enumerate() {
321                while let Some((j, _)) = to_insert.last()
322                    && *j == i
323                {
324                    let (_, mut stmts) = to_insert.pop().unwrap();
325                    self.statements.append(&mut stmts);
326                }
327                self.statements.push(stmt);
328            }
329        }
330    }
331
332    /// Apply a transformer to all the statements.
333    ///
334    /// The transformer should:
335    /// - mutate the current statements in place
336    /// - return a list of `(i, statements)` where `statements` will be inserted before index `i`.
337    pub fn transform_sequences_fwd<F>(&mut self, f: F)
338    where
339        F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
340    {
341        self.transform_sequences(f, true);
342    }
343
344    /// Apply a transformer to all the statements.
345    ///
346    /// The transformer should:
347    /// - mutate the current statements in place
348    /// - return a list of `(i, statements)` where `statements` will be inserted before index `i`.
349    pub fn transform_sequences_bwd<F>(&mut self, f: F)
350    where
351        F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
352    {
353        self.transform_sequences(f, false);
354    }
355}
356
357impl UnwindKind {
358    /// The kind of a block reached by unwinding from this one.
359    pub fn further_unwind_kind(self) -> Self {
360        match self {
361            Self::Regular => Self::Cleanup,
362            // Unwinding from an unwind block is not allowed to continue unwinding up the stack.
363            Self::Cleanup | Self::Terminate => Self::Terminate,
364        }
365    }
366}
367
368impl Statement {
369    pub fn new(span: Span, kind: StatementKind) -> Self {
370        Statement {
371            span,
372            kind,
373            comments_before: vec![],
374        }
375    }
376}
377
378impl Terminator {
379    pub fn new(span: Span, kind: TerminatorKind) -> Self {
380        Terminator {
381            span,
382            kind,
383            comments_before: vec![],
384        }
385    }
386    pub fn goto(span: Span, target: BlockId) -> Self {
387        Self::new(span, TerminatorKind::Goto { target })
388    }
389    /// Whether this terminator is an unconditional error (panic, UB, or abort).
390    pub fn is_error(&self) -> bool {
391        use TerminatorKind::*;
392        match &self.kind {
393            Panic { .. } | UndefinedBehavior | UnwindTerminate => true,
394            Goto { .. }
395            | Switch { .. }
396            | InlineAsm { .. }
397            | Return
398            | Call { .. }
399            | Drop { .. }
400            | UnwindResume
401            | Assert { .. } => false,
402        }
403    }
404
405    pub fn into_block(self, kind: UnwindKind) -> BlockData {
406        BlockData {
407            statements: vec![],
408            terminator: self,
409            kind,
410        }
411    }
412
413    pub fn targets(&self) -> SmallVec<[BlockId; 2]> {
414        match &self.kind {
415            TerminatorKind::Goto { target } => {
416                smallvec![*target]
417            }
418            TerminatorKind::Switch { branches, .. } => branches.iter().copied().collect(),
419            TerminatorKind::InlineAsm {
420                fallthrough,
421                labels,
422                on_unwind,
423                ..
424            } => fallthrough
425                .iter()
426                .copied()
427                .chain(labels.iter().copied())
428                .chain([*on_unwind])
429                .collect(),
430            TerminatorKind::Call {
431                target, on_unwind, ..
432            }
433            | TerminatorKind::Drop {
434                target, on_unwind, ..
435            }
436            | TerminatorKind::Assert {
437                target, on_unwind, ..
438            } => smallvec![*target, *on_unwind],
439            TerminatorKind::Panic { on_unwind, .. } => smallvec![*on_unwind],
440            TerminatorKind::UndefinedBehavior
441            | TerminatorKind::UnwindTerminate
442            | TerminatorKind::Return
443            | TerminatorKind::UnwindResume => {
444                smallvec![]
445            }
446        }
447    }
448    pub fn targets_mut(&mut self) -> SmallVec<[&mut BlockId; 2]> {
449        match &mut self.kind {
450            TerminatorKind::Goto { target } => {
451                smallvec![target]
452            }
453            TerminatorKind::Switch { branches, .. } => branches.iter_mut().collect(),
454            TerminatorKind::InlineAsm {
455                fallthrough,
456                labels,
457                on_unwind,
458                ..
459            } => fallthrough
460                .iter_mut()
461                .chain(labels.iter_mut())
462                .chain([on_unwind])
463                .collect(),
464            TerminatorKind::Call {
465                target, on_unwind, ..
466            }
467            | TerminatorKind::Drop {
468                target, on_unwind, ..
469            }
470            | TerminatorKind::Assert {
471                target, on_unwind, ..
472            } => smallvec![target, on_unwind],
473            TerminatorKind::Panic { on_unwind, .. } => smallvec![on_unwind],
474            TerminatorKind::UndefinedBehavior
475            | TerminatorKind::UnwindTerminate
476            | TerminatorKind::Return
477            | TerminatorKind::UnwindResume => {
478                smallvec![]
479            }
480        }
481    }
482
483    pub fn targets_ignoring_unwind(&self) -> SmallVec<[BlockId; 2]> {
484        match &self.kind {
485            TerminatorKind::Goto { target } => {
486                smallvec![*target]
487            }
488            TerminatorKind::Switch { branches, .. } => branches.iter().copied().collect(),
489            TerminatorKind::InlineAsm {
490                fallthrough,
491                labels,
492                ..
493            } => fallthrough
494                .iter()
495                .copied()
496                .chain(labels.iter().copied())
497                .collect(),
498            TerminatorKind::Call { target, .. }
499            | TerminatorKind::Drop { target, .. }
500            | TerminatorKind::Assert { target, .. } => {
501                smallvec![*target]
502            }
503            TerminatorKind::Panic { .. }
504            | TerminatorKind::UndefinedBehavior
505            | TerminatorKind::UnwindTerminate
506            | TerminatorKind::Return
507            | TerminatorKind::UnwindResume => {
508                smallvec![]
509            }
510        }
511    }
512}
513
514impl TerminatorKind {
515    /// Replace this terminator with a dummy.
516    pub fn take(&mut self) -> Self {
517        std::mem::replace(self, TerminatorKind::UndefinedBehavior)
518    }
519}
520
521/// A statement location within a body.
522#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
523pub struct StmtLoc {
524    pub block: BlockId,
525    pub statement: usize,
526}
527
528impl StmtLoc {
529    pub fn new(block: BlockId, statement: usize) -> Self {
530        StmtLoc { block, statement }
531    }
532
533    pub fn block_start(block: BlockId) -> Self {
534        StmtLoc {
535            block,
536            statement: 0,
537        }
538    }
539
540    pub fn after(self) -> Self {
541        StmtLoc {
542            block: self.block,
543            statement: self.statement + 1,
544        }
545    }
546}
547
548impl Index<StmtLoc> for ExprBody {
549    type Output = Statement;
550    fn index(&self, loc: StmtLoc) -> &Self::Output {
551        &self.body[loc.block].statements[loc.statement]
552    }
553}
554
555impl IndexMut<StmtLoc> for ExprBody {
556    fn index_mut(&mut self, loc: StmtLoc) -> &mut Self::Output {
557        &mut self.body[loc.block].statements[loc.statement]
558    }
559}
560
561/// Helper to construct a small ullbc body.
562pub struct BodyBuilder {
563    /// The span to use for everything.
564    pub span: Span,
565    /// Body under construction.
566    pub body: ExprBody,
567    /// Block onto which we're adding statements. Its terminator is always `Return`.
568    pub current_block: BlockId,
569    /// Block to unwind to; created on demand.
570    pub unwind_block: Option<BlockId>,
571}
572
573fn mk_block(span: Span, term: TerminatorKind, kind: UnwindKind) -> BlockData {
574    BlockData {
575        statements: vec![],
576        terminator: Terminator::new(span, term),
577        kind,
578    }
579}
580
581impl BodyBuilder {
582    pub fn new(span: Span, arg_count: usize) -> Self {
583        let mut body: ExprBody = GExprBody {
584            span,
585            locals: Locals::new(arg_count),
586            bound_body_regions: 0,
587            body: IndexVec::new(),
588            comments: vec![],
589        };
590        let current_block = body.body.push(BlockData {
591            statements: Default::default(),
592            terminator: Terminator::new(span, TerminatorKind::Return),
593            kind: UnwindKind::Regular,
594        });
595        Self {
596            span,
597            body,
598            current_block,
599            unwind_block: None,
600        }
601    }
602
603    /// Finalize the builder by returning the built body.
604    pub fn build(mut self) -> ExprBody {
605        // Replace erased regions with fresh ones.
606        let mut freshener: IndexMap<RegionId, ()> = IndexMap::new();
607        self.body.dyn_visit_mut(|r: &mut Region| {
608            if r.is_erased() || r.is_body() {
609                *r = Region::Body(freshener.push(()));
610            }
611        });
612        self.body.bound_body_regions = freshener.slot_count();
613        // Return the built body.
614        self.body
615    }
616
617    /// Create a new local. Adds a `StorageLive` statement if the local is not one of the special
618    /// ones (return or function argument).
619    pub fn new_var(&mut self, name: Option<String>, ty: Ty) -> Place {
620        let place = self.body.locals.new_var(name, ty);
621        let local_id = place.as_local().unwrap();
622        if !self.body.locals.is_return_or_arg(local_id) {
623            self.push_statement(StatementKind::StorageLive(local_id));
624        }
625        place
626    }
627
628    /// Helper.
629    fn current_block(&mut self) -> &mut BlockData {
630        &mut self.body.body[self.current_block]
631    }
632
633    pub fn push_statement(&mut self, kind: StatementKind) {
634        let st = Statement::new(self.span, kind);
635        self.current_block().statements.push(st);
636    }
637
638    fn unwind_block(&mut self) -> BlockId {
639        *self.unwind_block.get_or_insert_with(|| {
640            self.body.body.push(mk_block(
641                self.span,
642                TerminatorKind::UnwindResume,
643                UnwindKind::Cleanup,
644            ))
645        })
646    }
647
648    pub fn call(&mut self, call: Call) {
649        let next_block = self.body.body.push(mk_block(
650            self.span,
651            TerminatorKind::Return,
652            UnwindKind::Regular,
653        ));
654        let term = TerminatorKind::Call {
655            target: next_block,
656            call,
657            on_unwind: self.unwind_block(),
658        };
659        self.current_block().terminator.kind = term;
660        self.current_block = next_block;
661    }
662
663    pub fn insert_drop(&mut self, place: Place, fn_ptr: FnPtr) {
664        let next_block = self.body.body.push(mk_block(
665            self.span,
666            TerminatorKind::Return,
667            UnwindKind::Regular,
668        ));
669        let term = TerminatorKind::Drop {
670            kind: DropKind::Precise,
671            place,
672            fn_ptr,
673            target: next_block,
674            on_unwind: self.unwind_block(),
675        };
676        self.current_block().terminator.kind = term;
677        self.current_block = next_block;
678    }
679}
charon_lib/ast/bodies/unstructured.rs

charon_lib/ast/bodies/
unstructured.rs
