Method build_search_tree

cranelift/frontend/src/switch.rs:103–151

Binary search for the right `ContiguousCaseRange`.

(
        bx: &mut FunctionBuilder,
        val: Value,
        otherwise: Block,
        contiguous_case_ranges: &'a [ContiguousCaseRange],
    )

    /// Binary search for the right `ContiguousCaseRange`.
    fn build_search_tree<'a>(
        bx: &mut FunctionBuilder,
        val: Value,
        otherwise: Block,
        contiguous_case_ranges: &'a [ContiguousCaseRange],
    ) {
        // If no switch cases were added to begin with, we can just emit `jump otherwise`.
        if contiguous_case_ranges.is_empty() {
            bx.ins().jump(otherwise, &[]);
            return;
        }

        // Avoid allocation in the common case
        if contiguous_case_ranges.len() <= 3 {
            Self::build_search_branches(bx, val, otherwise, contiguous_case_ranges);
            return;
        }

        let mut stack = Vec::new();
        stack.push((None, contiguous_case_ranges));

        while let Some((block, contiguous_case_ranges)) = stack.pop() {
            if let Some(block) = block {
                bx.switch_to_block(block);
            }

            if contiguous_case_ranges.len() <= 3 {
                Self::build_search_branches(bx, val, otherwise, contiguous_case_ranges);
            } else {
                let split_point = contiguous_case_ranges.len() / 2;
                let (left, right) = contiguous_case_ranges.split_at(split_point);

                let left_block = bx.create_block();
                let right_block = bx.create_block();

                let first_index = right[0].first_index;
                let should_take_right_side =
                    icmp_imm_u128(bx, IntCC::UnsignedGreaterThanOrEqual, val, first_index);
                bx.ins()
                    .brif(should_take_right_side, right_block, &[], left_block, &[]);

                bx.seal_block(left_block);
                bx.seal_block(right_block);

                stack.push((Some(left_block), left));
                stack.push((Some(right_block), right));
            }
        }
    }

    /// Linear search for the right `ContiguousCaseRange`.
    fn build_search_branches<'a>(