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}