//! Data structures for control flow emission. //! //! As of the current implementation, Winch doesn't offer support for the //! multi-value proposal, which in the context of control flow constructs it //! means that blocks don't take any params and produce 0 or 1 return. The //! intention is to implement support for multi-value across the compiler, when //! that time comes, here are some general changes that will be needed for //! control flow: //! //! * Consider having a copy of the block params on the side, and push them when //! encountering an else or duplicate the block params upfront. If no else is //! present, clean the extra copies from the stack. //! //! * Eagerly load the block params. Params can flow "downward" as the block //! results in the case of an empty then or else block: //! (module //! (func (export "params") (param i32) (result i32) //! (i32.const 2) //! (if (param i32) (result i32) (local.get 0) //! (then)) //! (i32.const 3) //! (i32.add) //! ) //! //! As a future optimization, we could perform a look ahead to the next //! instruction when reaching any of the comparison instructions. If the next //! instruction is a control instruction, we could avoid emitting //! a [`crate::masm::MacroAssembler::cmp_with_set`] and instead emit //! a conditional jump inline when emitting the control flow instruction. use super::{CodeGenContext, MacroAssembler, OperandSize}; use crate::{ abi::{ABIResult, ABI}, masm::CmpKind, CallingConvention, }; use cranelift_codegen::MachLabel; use wasmtime_environ::WasmType; /// Holds the necessary metdata to support the emission /// of control flow instructions. #[derive(Debug)] pub(crate) enum ControlStackFrame { If { /// The if continuation label. cont: MachLabel, /// The exit label of the block. exit: MachLabel, /// The return values of the block. result: ABIResult, /// The size of the value stack at the beginning of the If. original_stack_len: usize, /// The stack pointer offset at the beginning of the If. original_sp_offset: u32, /// Local reachability state when entering the block. reachable: bool, }, Else { /// The exit label of the block. exit: MachLabel, /// The return values of the block. result: ABIResult, /// The size of the value stack at the beginning of the Else. original_stack_len: usize, /// The stack pointer offset at the beginning of the Else. original_sp_offset: u32, /// Local reachability state when entering the block. reachable: bool, }, Block { /// The block exit label. exit: MachLabel, /// The size of the value stack at the beginning of the block. original_stack_len: usize, /// The return values of the block. result: ABIResult, /// The stack pointer offset at the beginning of the Block. original_sp_offset: u32, /// Exit state of the block. /// /// This flag is used to dertermine if a block is a branch /// target. By default, this is false, and it's updated when /// emitting a `br` or `br_if`. is_branch_target: bool, }, Loop { /// The start of the loop. head: MachLabel, /// The size of the value stack at the beginning of the block. original_stack_len: usize, /// The stack pointer offset at the beginning of the Block. original_sp_offset: u32, /// The return values of the block. result: ABIResult, }, } impl ControlStackFrame { /// Returns [`ControlStackFrame`] for an if. pub fn if_( returns: &[WasmType], masm: &mut M, context: &mut CodeGenContext, ) -> Self { let result = ::result(&returns, &CallingConvention::Default); let mut control = Self::If { cont: masm.get_label(), exit: masm.get_label(), result, reachable: context.reachable, original_stack_len: 0, original_sp_offset: 0, }; control.emit(masm, context); control } /// Creates a block that represents the base /// block for the function body. pub fn function_body_block( result: ABIResult, masm: &mut M, context: &mut CodeGenContext, ) -> Self { Self::Block { original_stack_len: context.stack.len(), result, is_branch_target: false, exit: masm.get_label(), original_sp_offset: masm.sp_offset(), } } /// Returns [`ControlStackFrame`] for a block. pub fn block( returns: &[WasmType], masm: &mut M, context: &mut CodeGenContext, ) -> Self { let result = ::result(&returns, &CallingConvention::Default); let mut control = Self::Block { original_stack_len: 0, result, is_branch_target: false, exit: masm.get_label(), original_sp_offset: 0, }; control.emit(masm, context); control } /// Returns [`ControlStackFrame`] for a loop. pub fn loop_( returns: &[WasmType], masm: &mut M, context: &mut CodeGenContext, ) -> Self { let result = ::result(&returns, &CallingConvention::Default); let mut control = Self::Loop { original_stack_len: 0, result, head: masm.get_label(), original_sp_offset: 0, }; control.emit(masm, context); control } fn emit(&mut self, masm: &mut M, context: &mut CodeGenContext) { use ControlStackFrame::*; // Do not perform any emissions if we are in an unreachable state. if !context.reachable { return; } match self { If { cont, original_stack_len, original_sp_offset, .. } => { // Pop the condition value. let top = context.pop_to_reg(masm, None, OperandSize::S32); // Unconditionall spill before emitting control flow. context.spill(masm); *original_stack_len = context.stack.len(); *original_sp_offset = masm.sp_offset(); masm.branch(CmpKind::Eq, top.into(), top.into(), *cont, OperandSize::S32); context.free_gpr(top); } Block { original_stack_len, original_sp_offset, .. } => { // Unconditional spill before entering the block. // We assume that there are no live registers when // exiting the block. context.spill(masm); *original_stack_len = context.stack.len(); *original_sp_offset = masm.sp_offset(); } Loop { original_stack_len, original_sp_offset, head, .. } => { // Unconditional spill before entering the loop block. context.spill(masm); *original_stack_len = context.stack.len(); *original_sp_offset = masm.sp_offset(); masm.bind(*head); } _ => unreachable!(), } } /// Handles the else branch if the current control stack frame is /// [`ControlStackFrame::If`]. pub fn emit_else(&mut self, masm: &mut M, context: &mut CodeGenContext) { use ControlStackFrame::*; match self { If { result, original_stack_len, exit, .. } => { assert!((*original_stack_len + result.len()) == context.stack.len()); // Before emitting an unconditional jump to the exit branch, // we handle the result of the if-then block. context.pop_abi_results(&result, masm); // Before binding the else branch, we emit the jump to the end // label. masm.jmp(*exit); // Bind the else branch. self.bind_else(masm, context.reachable); } _ => unreachable!(), } } /// Binds the else branch label and converts `self` to /// [`ControlStackFrame::Else`]. pub fn bind_else(&mut self, masm: &mut M, reachable: bool) { use ControlStackFrame::*; match self { If { cont, result, original_stack_len, original_sp_offset, exit, .. } => { // Bind the else branch. masm.bind(*cont); // Update the stack control frame with an else control frame. *self = ControlStackFrame::Else { exit: *exit, original_stack_len: *original_stack_len, result: *result, reachable, original_sp_offset: *original_sp_offset, }; } _ => unreachable!(), } } /// Handles the end of a control stack frame. pub fn emit_end(&mut self, masm: &mut M, context: &mut CodeGenContext) { use ControlStackFrame::*; match self { If { result, original_stack_len, .. } | Else { result, original_stack_len, .. } => { assert!((*original_stack_len + result.len()) == context.stack.len()); // Before binding the exit label, we handle the block results. context.pop_abi_results(&result, masm); self.bind_end(masm, context); } Block { original_stack_len, result, .. } => { assert!((*original_stack_len + result.len()) == context.stack.len()); context.pop_abi_results(&result, masm); self.bind_end(masm, context); } Loop { result, original_stack_len, .. } => { assert!((*original_stack_len + result.len()) == context.stack.len()); } } } /// Binds the exit label of the current control stack frame and pushes the /// ABI results to the value stack. pub fn bind_end(&self, masm: &mut M, context: &mut CodeGenContext) { // Push the results to the value stack. context.push_abi_results(self.result(), masm); self.bind_exit_label(masm); } /// Binds the exit label of the control stack frame. pub fn bind_exit_label(&self, masm: &mut M) { use ControlStackFrame::*; match self { // We use an explicit label to track the exit of an if block. In case there's no // else, we bind the if's continuation block to make sure that any jumps from the if // condition are reachable and we bind the explicit exit label as well to ensure that any // branching instructions are able to correctly reach the block's end. If { cont, .. } => masm.bind(*cont), _ => {} } if let Some(label) = self.exit_label() { masm.bind(*label); } } /// Returns the continuation label of the current control stack frame. pub fn label(&self) -> &MachLabel { use ControlStackFrame::*; match self { If { exit, .. } | Else { exit, .. } | Block { exit, .. } => exit, Loop { head, .. } => head, } } /// Returns the exit label of the current control stack frame. Note that /// this is similar to [`ControlStackFrame::label`], with the only difference that it /// returns `None` for `Loop` since its label doesn't represent an exit. pub fn exit_label(&self) -> Option<&MachLabel> { use ControlStackFrame::*; match self { If { exit, .. } | Else { exit, .. } | Block { exit, .. } => Some(exit), Loop { .. } => None, } } /// Set the current control stack frame as a branch target. pub fn set_as_target(&mut self) { match self { ControlStackFrame::Block { is_branch_target, .. } => { *is_branch_target = true; } _ => {} } } /// Returns [`crate::abi::ABIResult`] of the control stack frame /// block. pub fn result(&self) -> &ABIResult { use ControlStackFrame::*; match self { If { result, .. } | Else { result, .. } | Block { result, .. } | Loop { result, .. } => result, } } /// This function is used at the end of unreachable code handling /// to determine if the reachability status should be updated. pub fn is_next_sequence_reachable(&self) -> bool { use ControlStackFrame::*; match self { // For if/else, the reachability of the next sequence is determined // by the reachability state at the start of the block. An else // block will be reachable if the if block is also reachable at // entry. If { reachable, .. } | Else { reachable, .. } => *reachable, // For blocks, the reachability of the next sequence is determined // if they're a branch target. Block { is_branch_target, .. } => *is_branch_target, // Loops are not used for reachability analysis, // given that they don't have exit branches. Loop { .. } => false, } } // TODO document. pub fn original_stack_len_and_sp_offset(&self) -> (usize, u32) { use ControlStackFrame::*; match self { If { original_stack_len, original_sp_offset, .. } | Else { original_stack_len, original_sp_offset, .. } | Block { original_stack_len, original_sp_offset, .. } | Loop { original_stack_len, original_sp_offset, .. } => (*original_stack_len, *original_sp_offset), } } }