Skip to main content

charon_lib/transform/
mod.rs

1pub mod ctx;
2pub mod typecheck_and_unify;
3pub mod utils;
4
5/// Passes that finish translation, i.e. required for the output to be a valid output.
6pub mod finish_translation {
7    pub mod filter_invisible_trait_impls;
8    pub mod insert_assign_return_unit;
9    pub mod insert_ptr_metadata;
10    pub mod insert_storage_statements;
11}
12
13/// Passes that compute extra info to be stored in the crate.
14pub mod add_missing_info {
15    pub mod add_implied_outlives;
16    pub mod add_missing_alias_clauses;
17    pub mod compute_layout_guarantees;
18    pub mod compute_short_names;
19    pub mod detect_drop_flags;
20    pub mod infer_higher_ranked_args;
21    pub mod link_specs;
22    pub mod recover_body_comments;
23    pub mod reorder_decls;
24    pub mod sccs;
25}
26
27/// Passes that effect some kind of normalization on the crate.
28pub mod normalize {
29    pub mod desugar_drops;
30    pub mod expand_associated_types;
31    pub mod normalize_trait_refs;
32    pub mod partial_monomorphization;
33    pub mod skip_trait_refs_when_known;
34    pub mod transform_dyn_trait_calls;
35}
36
37/// Passes that undo some lowering done by rustc to recover an operation closer to what the user
38/// wrote.
39pub mod resugar {
40    pub mod move_asserts_to_statements;
41    pub mod reconstruct_asserts;
42    pub mod reconstruct_box_derefs;
43    pub mod reconstruct_box_drops;
44    pub mod reconstruct_copy_for_deref;
45    pub mod reconstruct_fallible_operations;
46    pub mod reconstruct_intrinsics;
47    pub mod reconstruct_matches;
48    pub mod reconstruct_panic_calls;
49    pub mod reconstruct_static_accesses;
50    pub mod reconstruct_vec_boxes;
51    pub mod resugar_drops;
52}
53
54/// Passes that make the output simpler/easier to consume.
55pub mod simplify_output {
56    pub mod anon_const_to_call;
57    pub mod builtins_to_function_calls;
58    pub mod duplicate_defaulted_methods;
59    pub mod filter_trivial_drops;
60    pub mod hide_allocator_param;
61    pub mod index_intermediate_assigns;
62    pub mod inline_selected_functions;
63    pub mod lift_associated_item_clauses;
64    pub mod remove_adt_clauses;
65    pub mod remove_nops;
66    pub mod remove_unit_locals;
67    pub mod remove_unused_clauses;
68    pub mod remove_unused_locals;
69    pub mod simplify_constants;
70    pub mod unbind_item_vars;
71    pub mod update_block_indices;
72}
73
74/// Passes that manipulate the control flow and reconstruct its structure.
75pub mod control_flow {
76    pub mod merge_goto_chains;
77    pub mod prettify_cfg;
78    pub mod ullbc_to_llbc;
79}
80
81pub use ctx::TransformCtx;
82use ctx::{LlbcPass, TransformPass, UllbcPass};
83
84use crate::options::CliOpts;
85
86/// Shorten a pass name for display: `charon_lib::transform::foo::bar::Transform` -> `foo::bar`.
87fn short_pass_name(name: &str) -> String {
88    let name = name.strip_prefix("charon_lib::transform::").unwrap_or(name);
89    let name = name.strip_suffix("::Transform").unwrap_or(name);
90    name.to_owned()
91}
92
93/// Run transformation passes on the crate before outputting it.
94pub fn run_transformation_passes(options: &CliOpts, ctx: &mut TransformCtx) {
95    // Passes that apply to the whole crate at once, typically those that change item signatures.
96    let global = |x| Pass::NonBody(CowBox::Borrowed(x));
97    // Passes that apply to bodies but work on either kind.
98    let mixed_body = |x| Pass::NonBody(CowBox::Borrowed(x));
99
100    ctx.run_pass(Pass::NonBody(PrintCtxPass::new(
101        options.print_original_ullbc,
102        "# ULLBC after translation from MIR".to_string(),
103    )));
104
105    // Item and type cleanup passes.
106    ctx.run_passes([
107        // Link specification items and the items they specify in both directions.
108        global(&add_missing_info::link_specs::Transform),
109        // `--duplicate-defaulted-methods`: copy default method bodies into impls that use them.
110        global(&simplify_output::duplicate_defaulted_methods::Transform),
111        // Compute short names. We do it early to make pretty-printed output more legible in traces.
112        global(&add_missing_info::compute_short_names::Transform),
113        // Check that translation emitted consistent types, and unify body lifetimes (best-effort).
114        global(&typecheck_and_unify::Check::PostTranslation),
115        // Filter the trait impls that were marked invisible since we couldn't filter them out
116        // earlier.
117        global(&finish_translation::filter_invisible_trait_impls::Transform),
118        // Move clauses on associated types to be implied clauses of the trait.
119        global(&simplify_output::lift_associated_item_clauses::Transform),
120        // Infer some erased higher-ranked clause arguments.
121        global(&add_missing_info::infer_higher_ranked_args::Transform),
122        // Type aliases may use associated types without declaring the corresponding trait
123        // such missing trait clauses.
124        global(&add_missing_info::add_missing_alias_clauses::Transform),
125        // Make explicit the outlives predicates implied by type well-formedness.
126        global(&add_missing_info::add_implied_outlives::Transform),
127    ]);
128
129    // Body cleanup passes on the ullbc.
130    let pass = Pass::FusedUnstructuredBody(Box::new([
131        // Detect which locals are drop flags.
132        CowBox::Borrowed(&add_missing_info::detect_drop_flags::Transform),
133        // Elaborated MIR lowers the deallocation of a `Box` whose pointee was moved out to a
134        // direct call to `Box::drop`. We reconstruct that into a primitive operation, for
135        // borrow-checking purposes.
136        CowBox::Borrowed(&resugar::reconstruct_box_drops::Transform),
137        // Reconstruct conditional drops. Needs to be done before any pass changes the shape of the
138        // CFG.
139        CowBox::Borrowed(&resugar::resugar_drops::Transform),
140        // Compute the metadata & insert for Rvalue
141        CowBox::Borrowed(&finish_translation::insert_ptr_metadata::Transform),
142        // Add the missing assignments to the return value.
143        // When the function return type is unit, the generated MIR doesn't set the return value to
144        // `()`. This can be a concern: in the case of Aeneas, it means the return variable
145        // contains ⊥ upon returning. For this reason, when the function has return type unit, we
146        // insert an extra assignment just before returning.
147        CowBox::Borrowed(&finish_translation::insert_assign_return_unit::Transform),
148        // Insert storage markers for locals that don't have them (that's allowed in MIR).
149        CowBox::Borrowed(&finish_translation::insert_storage_statements::Transform),
150        // Transform Drops into Calls to drop_glue.
151        CowBox::Borrowed(&normalize::desugar_drops::Transform),
152        // Whenever we reference a trait method on a known type, refer to the method `FunDecl`
153        // directly instead of going via a `TraitRef`. This is done before associated-type lifting
154        // because it messes up generic args order.
155        CowBox::Borrowed(&normalize::skip_trait_refs_when_known::Transform),
156        // Transform dyn trait method calls to vtable function pointer calls.
157        // This should be early to handle the calls before other transformations.
158        CowBox::Borrowed(&normalize::transform_dyn_trait_calls::Transform),
159        // Replace promoted and inline consts with calls to their initializers.
160        simplify_output::anon_const_to_call::Transform::new(ctx),
161        // Inline promoted and inline consts, as well as dummy auto-generated panic functions.
162        simplify_output::inline_selected_functions::Transform::new(ctx),
163        // Replace calls to built-in panic functions with `Panic` terminators.
164        resugar::reconstruct_panic_calls::Transform::new(ctx),
165        // Remove drop statements that are noops.
166        CowBox::Borrowed(&simplify_output::filter_trivial_drops::Transform),
167        // Inline all asserts that correspond to dynamic checks into statements.
168        // The following pass will then merge the generated gotos as part of this substitution,
169        // and [reconstruct_fallible_operations] can then use the inlined asserts to
170        // reconstruct the fallible operations.
171        CowBox::Borrowed(&resugar::move_asserts_to_statements::Transform),
172        // Merge single-origin gotos into their parent. This drastically reduces the graph size
173        // of the CFG.
174        // This must be done early as some resugaring passes depend on it.
175        CowBox::Borrowed(&control_flow::merge_goto_chains::Transform),
176        // Undo the splitting of places at derefs done in elaborated MIR.
177        CowBox::Borrowed(&resugar::reconstruct_copy_for_deref::Transform),
178        // Remove overflow/div-by-zero/bounds checks since they are already part of the
179        // arithmetic/array operation in the semantics of (U)LLBC.
180        // **WARNING**: this pass uses the fact that the dynamic checks introduced by Rustc use a
181        // special "assert" construct. Because of this, it must happen *before* the
182        // [reconstruct_asserts] pass. See the comments in [crate::remove_dynamic_checks].
183        // **WARNING**: this pass relies on a precise structure of the MIR statements. Because of this,
184        // it must happen before passes that insert statements like [simplify_constants].
185        CowBox::Borrowed(&resugar::reconstruct_fallible_operations::Transform),
186        // Reconstruct `vec![x]` lowering to avoid unsafe operations.
187        // **WARNING**: this pass relies on a precise structure of the MIR statements. Because of
188        // this, it must happen before passes that insert statements like [simplify_constants].
189        // This must also happen after `inline_selected_functions`, and `merge_goto_chains`.
190        resugar::reconstruct_vec_boxes::Transform::new(ctx),
191        // Resugar the box derefs that got desugared in elaborated MIR.
192        CowBox::Borrowed(&resugar::reconstruct_box_derefs::Transform),
193        // Recognize calls to the `offset_of` intrinsic and replace them with the
194        // corresponding constant expression.
195        CowBox::Borrowed(&resugar::reconstruct_intrinsics::Transform),
196        // Reconstruct the asserts
197        CowBox::Borrowed(&resugar::reconstruct_asserts::Transform),
198        // Access statics directly instead of through a temporary holding their address.
199        // This must happen before [simplify_constants], which splits these temporaries.
200        CowBox::Borrowed(&resugar::reconstruct_static_accesses::Transform),
201        // Desugar the constants to other values/operands as much as possible.
202        CowBox::Borrowed(&simplify_output::simplify_constants::Transform),
203        // Introduce intermediate assignments in preparation of the [`builtins_to_function_calls`]
204        // pass.
205        CowBox::Borrowed(&simplify_output::index_intermediate_assigns::Transform),
206        // Remove locals of type `()` which show up a lot.
207        CowBox::Borrowed(&simplify_output::remove_unit_locals::Transform),
208        // Reconstruct matches on enum variants.
209        resugar::reconstruct_matches::Transform::new(ctx),
210        // Remove the locals which are never used.
211        CowBox::Borrowed(&simplify_output::remove_unused_locals::Transform),
212        // Another round.
213        CowBox::Borrowed(&control_flow::merge_goto_chains::Transform),
214        // Renumber rechable blocks to be consecutive and in topological order.
215        CowBox::Borrowed(&simplify_output::update_block_indices::Transform),
216    ]));
217    ctx.run_pass(pass);
218
219    if !options.ullbc {
220        // If we're reconstructing control-flow, print the ullbc here.
221        ctx.run_pass(Pass::NonBody(PrintCtxPass::new(
222            options.print_ullbc,
223            "# Final ULLBC before control-flow reconstruction".to_string(),
224        )));
225    }
226
227    if !options.ullbc {
228        // Go from ULLBC to LLBC (Low-Level Borrow Calculus) by reconstructing the control flow.
229        ctx.run_pass(mixed_body(&control_flow::ullbc_to_llbc::Transform));
230        // Body cleanup passes after control flow reconstruction.
231        let pass = Pass::FusedStructuredBody(Box::new([
232            // Cleanup the cfg.
233            CowBox::Borrowed(&control_flow::prettify_cfg::Transform),
234            // Replace some operations and array/slice indexing with standard library function
235            // calls.
236            simplify_output::builtins_to_function_calls::Transform::new(ctx),
237        ]));
238        ctx.run_pass(pass);
239    }
240    // Cleanup passes useful for both llbc and ullbc.
241    ctx.run_passes([
242        // Body passes may introduce fresh locals; make their storage markers explicit.
243        mixed_body(&finish_translation::insert_storage_statements::Transform),
244        // Normalize trait refs.
245        global(&normalize::normalize_trait_refs::Transform),
246        // Change trait associated types to be type parameters instead. See the module for details.
247        // This also normalizes any use of an associated type that we can resolve.
248        global(&normalize::expand_associated_types::Transform),
249        // Remove the explicit `Self: Trait` clause of methods/assoc const declaration items if
250        // they're not used. This simplifies the graph of dependencies between definitions.
251        global(&simplify_output::remove_unused_clauses::Transform),
252        // `--remove-adt-clauses`: Remove all trait clauses from type declarations.
253        global(&simplify_output::remove_adt_clauses::Transform),
254        // Remove the locals which are never used.
255        mixed_body(&simplify_output::remove_unused_locals::Transform),
256        // Remove the useless `StatementKind::Nop`s.
257        mixed_body(&simplify_output::remove_nops::Transform),
258        // Take all the comments found in the original body and assign them to statements. This must be
259        // last after all the statement-affecting passes to avoid losing comments.
260        mixed_body(&add_missing_info::recover_body_comments::Transform),
261        // Hide the `A` type parameter on standard library containers (`Box`, `Vec`, etc).
262        global(&simplify_output::hide_allocator_param::Transform),
263        // Partially monomorphize items so that no item is ever instanciated with a mutable reference
264        // or a type containing one.
265        global(&normalize::partial_monomorphization::Transform),
266        // Provide expressions describing the language-guaranteed properties of each type layout.
267        global(&add_missing_info::compute_layout_guarantees::Transform),
268        // Reorder the graph of dependencies and compute the strictly connex components to:
269        // - compute the order in which to extract the definitions
270        // - find the recursive definitions
271        // - group the mutually recursive definitions
272        // This is done last to account for the final item graph, not the initial one.
273        global(&add_missing_info::reorder_decls::Transform),
274        // Check that types are still consistent after the transformation passes.
275        global(&typecheck_and_unify::Check::PostTransformation),
276        // Use `DeBruijnVar::Free` for the variables bound in item signatures.
277        mixed_body(&simplify_output::unbind_item_vars::Check),
278    ]);
279
280    if options.ullbc {
281        // If we're not reconstructing control-flow, print the ullbc after finalizing passes.
282        ctx.run_pass(Pass::NonBody(PrintCtxPass::new(
283            options.print_ullbc,
284            "# Final ULLBC before serialization".to_string(),
285        )));
286    } else {
287        ctx.run_pass(Pass::NonBody(PrintCtxPass::new(
288            options.print_llbc,
289            "# Final LLBC before serialization".to_string(),
290        )));
291    }
292}
293
294pub enum CowBox<T: ?Sized + 'static> {
295    Borrowed(&'static T),
296    Owned(Box<T>),
297}
298
299impl<T: ?Sized + 'static> std::ops::Deref for CowBox<T> {
300    type Target = T;
301    fn deref(&self) -> &Self::Target {
302        match self {
303            CowBox::Borrowed(x) => x,
304            CowBox::Owned(x) => x.as_ref(),
305        }
306    }
307}
308
309pub enum Pass {
310    NonBody(CowBox<dyn TransformPass>),
311    FusedUnstructuredBody(Box<[CowBox<dyn UllbcPass>]>),
312    FusedStructuredBody(Box<[CowBox<dyn LlbcPass>]>),
313}
314
315impl TransformCtx {
316    pub fn run_pass(&mut self, mut pass: Pass) {
317        match &mut pass {
318            Pass::NonBody(pass) => {
319                if pass.should_run(&self.options) {
320                    trace!("# Starting pass {}", pass.name());
321                    let _guard =
322                        crate::timing::scope_lazy("transform", || short_pass_name(pass.name()));
323                    pass.transform_ctx(self)
324                }
325            }
326            Pass::FusedUnstructuredBody(passes) => {
327                // Some passes carry function bodies, which must also be transformed. This applies
328                // all the passes before pass `p` to the bodies potentially carried by pass `p`.
329                for i in 0..passes.len() {
330                    if let (first_passes, [pass, ..]) = passes.split_at_mut(i)
331                        && let CowBox::Owned(pass) = pass
332                    {
333                        pass.apply_preceding_passes(self, first_passes);
334                    }
335                }
336                self.for_each_item_mut(|ctx, mut item| {
337                    for pass in passes.iter() {
338                        if pass.should_run(&ctx.options) {
339                            trace!("# Starting pass {}", pass.name());
340                            let _guard = crate::timing::scope_lazy("transform", || {
341                                short_pass_name(pass.name())
342                            });
343                            pass.transform_item(ctx, item.reborrow());
344                        }
345                    }
346                });
347                for pass in passes.iter() {
348                    if pass.should_run(&self.options) {
349                        pass.finalize(self);
350                    }
351                }
352            }
353            Pass::FusedStructuredBody(passes) => {
354                self.for_each_fun_decl(|ctx, decl| {
355                    for pass in passes.iter() {
356                        if pass.should_run(&ctx.options) {
357                            trace!("# Starting pass {}", pass.name());
358                            let _guard = crate::timing::scope_lazy("transform", || {
359                                short_pass_name(pass.name())
360                            });
361                            pass.transform_function(ctx, decl);
362                        }
363                    }
364                });
365            }
366        };
367    }
368    pub fn run_passes(&mut self, passes: impl IntoIterator<Item = Pass>) {
369        for pass in passes {
370            self.run_pass(pass);
371        }
372    }
373}
374
375pub struct PrintCtxPass {
376    pub message: String,
377    /// Whether we're printing to stdout or only logging.
378    pub to_stdout: bool,
379}
380
381impl PrintCtxPass {
382    pub fn new(to_stdout: bool, message: String) -> CowBox<dyn TransformPass> {
383        let ret = Self { message, to_stdout };
384        CowBox::Owned(Box::new(ret))
385    }
386}
387
388impl TransformPass for PrintCtxPass {
389    fn transform_ctx(&self, ctx: &mut TransformCtx) {
390        let message = &self.message;
391        if self.to_stdout {
392            println!("{message}:\n\n{ctx}\n");
393        } else {
394            trace!("{message}:\n\n{ctx}\n");
395        }
396    }
397}