Method gen_cfg_skeleton

src/debug_utils/generic_function/arbitrary.rs:225–314

Generates a function skeleton with a randomly generated CFG. These blocks do not contain any instructions yet.

(&mut self)

    ///
    /// These blocks do not contain any instructions yet.
    fn gen_cfg_skeleton(&mut self) -> Result<()> {
        // To avoid critical edges, we need to ensure that blocks with multiple
        // successors only jump to blocks with a single predecessors, and that
        // blocks with multiple predecessors are only jumped to from blocks with
        // a single successor.
        let mut can_add_succ = vec![];
        let mut can_add_pred = vec![];

        // Create the entry points.
        let num_entries = self
            .u
            .int_in_range(self.config.entry_points.clone())?
            .max(1);
        for _ in 0..num_entries {
            let entry_frequency = self.block_frequency()?;
            let entry = self.func.blocks.push(BlockData {
                insts: InstRange::new(Inst::new(0), Inst::new(0)),
                preds: vec![],
                succs: vec![],
                block_params_in: vec![],
                block_params_out: vec![],
                immediate_dominator: None.into(),
                frequency: entry_frequency,
                is_critical_edge: false,
            });
            self.func.entry_points.push(entry);
            can_add_succ.push(entry);
        }

        // Repeatedly add edges to the CFG, either to a new block, or to an
        // existing block.
        for _ in 0..self.u.int_in_range(self.config.cfg_edges.clone())? {
            if can_add_succ.is_empty() {
                break;
            }

            let from = *self.u.choose(&can_add_succ)?;
            let mut to = None;

            // If the chosen block has no successors, try linking it to an
            // existing block that accepts predecessors.
            if !can_add_pred.is_empty()
                && self.func.blocks[from].succs.is_empty()
                && self.u.arbitrary()?
            {
                to = Some(*self.u.choose(&can_add_pred)?);
            }

            if let Some(to) = to {
                // Create an edge to an existing block.
                self.func.blocks[from].succs.push(to);
                self.func.blocks[to].preds.push(from);

                // If the `to` block now has multiple predecessors, prevent
                // adding new successors to them.
                if self.func.blocks[to].preds.len() > 1 {
                    can_add_succ.retain(|b| !self.func.blocks[to].preds.contains(b));
                }