neyuki 0.1.1

A small Lua-like scripting language implemented in Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

// Liveness analysis on Control Flow Graph using backward dataflow equations.

use std::collections::{HashMap, HashSet};

use crate::compiler::ir::block::ControlFlowGraph;
use crate::compiler::ir::types::{IrLabel, IrVar};

#[derive(Debug, Clone)]
pub struct BlockLiveness {
    pub use_vars: HashSet<IrVar>,
    pub def_vars: HashSet<IrVar>,
    pub live_in: HashSet<IrVar>,
    pub live_out: HashSet<IrVar>,
}

#[derive(Debug, Clone)]
pub struct LivenessInfo {
    pub blocks: HashMap<IrLabel, BlockLiveness>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LiveInterval {
    pub var: IrVar,
    pub start: usize,
    pub end: usize,
}

impl LivenessInfo {
    pub fn compute(cfg: &ControlFlowGraph) -> Self {
        let mut blocks = HashMap::new();

        // 1. Calculate local use and def sets for each basic block
        for block in &cfg.blocks {
            let mut block_use = HashSet::new();
            let mut block_def = HashSet::new();

            for inst in &block.instructions {
                for u in inst.use_vars() {
                    if !block_def.contains(&u) {
                        block_use.insert(u);
                    }
                }
                for d in inst.def_vars() {
                    block_def.insert(d);
                }
            }

            blocks.insert(
                block.label,
                BlockLiveness {
                    use_vars: block_use,
                    def_vars: block_def,
                    live_in: HashSet::new(),
                    live_out: HashSet::new(),
                },
            );
        }

        // 2. Iterative backward dataflow analysis
        // out[B] = Union_{S in succ[B]} in[S]
        // in[B] = use[B] Union (out[B] \ def[B])
        let mut changed = true;
        let mut iterations = 0;
        const MAX_ITERATIONS: usize = 1000;

        while changed && iterations < MAX_ITERATIONS {
            changed = false;
            iterations += 1;

            for block in cfg.blocks.iter().rev() {
                let lbl = block.label;

                // Compute out[B]
                let mut new_out = HashSet::new();
                for succ in &block.successors {
                    if let Some(succ_info) = blocks.get(succ) {
                        for v in &succ_info.live_in {
                            new_out.insert(*v);
                        }
                    }
                }

                // Compute in[B] = use[B] Union (out[B] \ def[B])
                let (use_vars, def_vars) = {
                    let b = &blocks[&lbl];
                    (b.use_vars.clone(), b.def_vars.clone())
                };

                let mut new_in = use_vars;
                for v in &new_out {
                    if !def_vars.contains(v) {
                        new_in.insert(*v);
                    }
                }

                let cur = blocks.get_mut(&lbl).expect("block exists");
                if cur.live_out != new_out || cur.live_in != new_in {
                    cur.live_out = new_out;
                    cur.live_in = new_in;
                    changed = true;
                }
            }
        }

        Self { blocks }
    }

    pub fn is_live_in(&self, label: IrLabel, var: IrVar) -> bool {
        self.blocks
            .get(&label)
            .is_some_and(|b| b.live_in.contains(&var))
    }

    pub fn is_live_out(&self, label: IrLabel, var: IrVar) -> bool {
        self.blocks
            .get(&label)
            .is_some_and(|b| b.live_out.contains(&var))
    }

    pub fn compute_live_intervals(&self, cfg: &ControlFlowGraph) -> HashMap<IrVar, LiveInterval> {
        let mut intervals: HashMap<IrVar, (usize, usize)> = HashMap::new();
        let mut pc = 0usize;

        for block in &cfg.blocks {
            // Variables live at block entry start at or before pc
            if let Some(info) = self.blocks.get(&block.label) {
                for &v in &info.live_in {
                    intervals
                        .entry(v)
                        .and_modify(|(_, end)| *end = (*end).max(pc))
                        .or_insert((pc, pc));
                }
            }

            for inst in &block.instructions {
                for u in inst.use_vars() {
                    intervals
                        .entry(u)
                        .and_modify(|(_, end)| *end = (*end).max(pc))
                        .or_insert((pc, pc));
                }

                for d in inst.def_vars() {
                    intervals
                        .entry(d)
                        .and_modify(|(_, end)| *end = (*end).max(pc))
                        .or_insert((pc, pc));
                }

                pc += 1;
            }

            // Variables live out of the block extend to the end of the block
            if let Some(info) = self.blocks.get(&block.label) {
                for &v in &info.live_out {
                    intervals
                        .entry(v)
                        .and_modify(|(_, end)| *end = (*end).max(pc))
                        .or_insert((pc, pc));
                }
            }
        }

        intervals
            .into_iter()
            .map(|(var, (start, end))| (var, LiveInterval { var, start, end }))
            .collect()
    }
}