Skip to main content

liil/
blocks.rs

1use crate::nnil::{Address, Nnil, NnilInstruction};
2
3#[derive(Debug, Clone, Copy)]
4pub struct BasicBlock {
5    pub addr: Address,
6    pub start_insn: usize,
7    pub end_insn: usize,
8    pub fallthrough: Option<Address>,
9    pub next_pc: u64,
10}
11
12pub fn collect_blocks(nnil: &Nnil) -> Vec<BasicBlock> {
13    let starts = nnil.instruction_starts().iter().map(|(addr, insn)| (*addr, insn.0 as usize)).collect::<Vec<_>>();
14
15    if starts.is_empty() {
16        return Vec::new();
17    }
18
19    let mut blocks = Vec::new();
20    let mut block_start_addr = starts[0].0;
21    let mut block_start_insn = starts[0].1;
22
23    for (idx, &(_, insn_start)) in starts.iter().enumerate() {
24        let next = starts.get(idx + 1).copied();
25
26        let insn_end = next.map(|(_, next_start)| next_start).unwrap_or_else(|| nnil.insns().len());
27
28        let guest_insn = &nnil.insns()[insn_start..insn_end];
29
30        let terminates = guest_insn.last().is_some_and(NnilInstruction::is_terminator);
31
32        let next_is_label = next.map(|(next_addr, _)| nnil.label_for_address(next_addr).is_some()).unwrap_or(false);
33
34        let next_pc = next.map(|(next_addr, _)| next_addr.0).unwrap_or_else(|| nnil.pc());
35
36        let should_end = terminates || next.is_none() || next_is_label;
37
38        if should_end {
39            let fallthrough = if terminates { None } else { next.map(|(next_addr, _)| next_addr) };
40
41            blocks.push(BasicBlock {
42                addr: block_start_addr,
43                start_insn: block_start_insn,
44                end_insn: insn_end,
45                fallthrough,
46                next_pc,
47            });
48
49            if let Some((next_addr, next_start)) = next {
50                block_start_addr = next_addr;
51                block_start_insn = next_start;
52            }
53        }
54    }
55
56    blocks
57}
58
59pub fn direct_successors(nnil: &Nnil) -> Vec<u64> {
60    let mut successors = Vec::new();
61
62    let Some(last) = nnil.insns().last() else {
63        return successors;
64    };
65
66    match *last {
67        NnilInstruction::Beq { ttgt, ftgt, .. }
68        | NnilInstruction::Bne { ttgt, ftgt, .. }
69        | NnilInstruction::Blt { ttgt, ftgt, .. }
70        | NnilInstruction::Bgt { ttgt, ftgt, .. } => {
71            for target in [ftgt, ttgt] {
72                if let Some(address) = nnil.label_address(target) {
73                    successors.push(address.0);
74                }
75            }
76        }
77
78        NnilInstruction::Jmp { dst } | NnilInstruction::Jr { dst } => {
79            if let NnilInstruction::Imm { imm } = nnil.insns()[dst.0 as usize]
80                && imm >= 0
81            {
82                successors.push(imm as u64);
83            }
84        }
85
86        NnilInstruction::Syscall {} | NnilInstruction::Sysbreak {} => {}
87        _ => successors.push(nnil.pc()),
88    }
89    successors
90}
91
92impl NnilInstruction {
93    pub fn is_terminator(&self) -> bool {
94        matches!(
95            self,
96            NnilInstruction::Jr { .. }
97                | NnilInstruction::Jmp { .. }
98                | NnilInstruction::Beq { .. }
99                | NnilInstruction::Bne { .. }
100                | NnilInstruction::Blt { .. }
101                | NnilInstruction::Bgt { .. }
102                | NnilInstruction::Syscall {}
103                | NnilInstruction::Sysbreak {}
104        )
105    }
106}