Skip to content

Commit dbc503f

Browse files
fitzgenelliottt
fitzgen
and
elliottt
authored
cranelift-frontend: Fix stack maps and liveness for loops (#9071)
* cranelift-frontend: Fix stack maps and liveness for loops Previously, we were not properly handling back edges. This manifested in values incorrectly being considered not-live inside loop bodies where they definitely were live. Consider the following example: block0: v0 = needs stack map block1: call foo(v0) call foo(v0) jump block1 We were previously considering `v0` live only for the first `call foo(v0)` but not the second, because we mistakenly concluded that `v0` would not be used again after that second `call`. While it won't be used again in *this* iteration of the loop, it will be used again in the *next* iteration of the loop. Trevor and I initially tried implementing a clever trick suggested by Chris where, if we know the minimum post-order index of all of a block's transitive predecessors, we can continue to compute liveness in a single pass over the IR. We believed we could compute the minimum predecessor post-order index via dynamic programming. It turns out, however, that approach doesn't provide correct answers out of the box for certain kinds of irreducible control flow, only nearly correct answers, and would require an additional clever fix-up pass afterwards. We deemed this cleverness on cleverness unacceptable. Instead, Trevor and I opted to implement a worklist algorithm where we process blocks to a fixed-point. This has the advantages of being obviously correct and producing more-precise results. It has the disadvantage of requiring multiple passes over the IR in the face of loops and back edges. Because this analysis is only used when needs-stack-map values are present (i.e. when the function uses GC values) and is otherwise skipped, this additional compile-time overhead is tolerable. Co-Authored-By: Trevor Elliott <telliott@fastly.com> * Add and update some comments based on review --------- Co-authored-by: Trevor Elliott <telliott@fastly.com>
1 parent c8a5acd commit dbc503f

3 files changed

Lines changed: 1128 additions & 409 deletions

File tree

‎cranelift/frontend/src/frontend.rs‎

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
//! A frontend for building Cranelift IR from other languages.
22
use crate::ssa::{SSABuilder, SideEffects};
33
use crate::variable::Variable;
4-
use alloc::collections::BTreeSet;
54
use alloc::vec::Vec;
65
use core::fmt::{self, Debug};
76
use cranelift_codegen::cursor::{Cursor, CursorPosition, FuncCursor};
@@ -34,7 +33,7 @@ pub struct FunctionBuilderContext {
3433
types: SecondaryMap<Variable, Type>,
3534
stack_map_vars: EntitySet<Variable>,
3635
stack_map_values: EntitySet<Value>,
37-
dfs: Dfs,
36+
safepoints: safepoints::SafepointSpiller,
3837
}
3938

4039
/// Temporary object used to build a single Cranelift IR [`Function`].
@@ -75,14 +74,14 @@ impl FunctionBuilderContext {
7574
types,
7675
stack_map_vars,
7776
stack_map_values,
78-
dfs,
77+
safepoints,
7978
} = self;
8079
ssa.clear();
8180
status.clear();
8281
types.clear();
8382
stack_map_values.clear();
8483
stack_map_vars.clear();
85-
dfs.clear();
84+
safepoints.clear();
8685
}
8786

8887
fn is_empty(&self) -> bool {
@@ -732,7 +731,9 @@ impl<'a> FunctionBuilder<'a> {
732731
}
733732

734733
if !self.func_ctx.stack_map_values.is_empty() {
735-
self.insert_safepoint_spills();
734+
self.func_ctx
735+
.safepoints
736+
.run(&mut self.func, &self.func_ctx.stack_map_values);
736737
}
737738

738739
// Clear the state (but preserve the allocated buffers) in preparation

0 commit comments

Comments
 (0)