Struct midenc_hir_transform::RewriteSpills

pub struct RewriteSpills;

This pass rewrites a function annotated by the InsertSpills pass, by means of the spill and reload pseudo-instructions, such that the resulting function is semantically equivalent to the original function, but with the additional property that the function will keep the operand stack depth <= 16 at all times.

This rewrite consists of the following main objectives:

• Match all uses of spilled values with the nearest dominating definition, modifying the IR as required to ensure that all uses are strictly dominated by their definitions.
• Allocate sufficient procedure locals to store concurrently-active spills
• Rewrite all spill instructions to primitive local.store instructions
• Rewrite used reload instructions to primitive local.load instructions
• Remove unused reload instructions as dead code

NOTE: This pass is intended to be combined with the InsertSpills pass. If run on its own, it is effectively a no-op, so it is safe to do, but nonsensical. In a normal compilation pipeline, this pass is run immediately after InsertSpills. It is not safe to run other passes between InsertSpills and RewriteSpills, unless that pass specifically is designed to preserve the results of the SpillAnalysis computed and used by InsertSpills to place spills and reloads. Conversely, you can’t just run InsertSpills without this pass, or the resulting IR will fail to codegen.

Design

See SpillAnalysis and InsertSpills for more context and details.

The primary purpose of this pass is twofold: reconstruct SSA form after insertion of spills and reloads by InsertSpills, and lowering of the spill and reload pseudo-instructions to primitive stores and loads from procedure-local variables. It is the final, and most important phase of the spills transformation.

Unlike InsertSpills, which mainly just materializes the results of the SpillAnalysis, this pass must do a tricky combo of dataflow analysis and rewrite in a single postorder traversal of the CFG (i.e. bottom-up):

• We need to find uses of spilled values as we encounter them, and keep track of them until we find an appropriate definition for each use.
• We need to propagate uses up the dominance tree until all uses are matched with definitions
• We need to rewrite uses when we find a definition
• We need to identify whether a block we are about to leave (on our way up the CFG), is in the iterated dominance frontier for the set of spilled values we’ve found uses for. If it is, we must append a new block parameter, rewrite the terminator of any predecessor blocks, and rewrite all uses found so far by using the new block parameter as the dominating definition.

Technically, this pass could be generalized a step further, such that it fixes up invalid def-use relationships in general, rather than just the narrow case of spills/reloads - but it is more efficient to keep it specialized for now, we can always generalize later.

This pass guarantees that:

1. No spill or reload instructions remain in the IR
2. The semantics of the original IR on which InsertSpills was run, will be preserved, if:

• The original IR was valid
• No modification to the IR was made between InsertSpills and RewriteSpills

3. The resulting function, once compiled to Miden Assembly, will keep the operand stack depth <= 16 elements, so long as the schedule produced by the backend preserves the scheduling semantics. For example, spills/reloads are computed based on an implied scheduling of operations, given by following the control flow graph, and visiting instructions in a block top-down. If the backend reschedules operations for more optimal placement of operands on the operand stack, it is possible that this rescheduling could result in the operand stack depth exceeding 16 elements. However, at this point, it is not expected that this will be a practical issue, even if it does occur, since the introduction of spills and reloads, not only place greater constraints on backend scheduling, but also ensure that more live ranges are split, and thus operands will spend less time on the operand stack overall. Time will tell whether this holds true or not.

Trait Implementations

impl Default for RewriteSpills

fn default() -> RewriteSpills

Returns the “default value” for a type.

impl RewritePass for RewriteSpills

type Entity = Function

The entity type to which this rewrite applies

fn apply( &mut self, function: &mut Self::Entity, analyses: &mut AnalysisManager, session: &Session, ) -> RewriteResult

Apply this rewrite to entity

fn should_apply(&self, _entity: &Self::Entity, _session: &Session) -> bool

Returns true if this rewrite should be applied to entity

fn chain<R>(self, next: R) -> RewriteSet<Self::Entity>

where Self: Sized + 'static, R: RewritePass<Entity = Self::Entity> + 'static,

Apply this rewrite, then next as a pipeline of rewrites