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

// Dead Code Elimination (DCE) and unreachable code removal pass on IR.

use std::collections::HashSet;

use crate::compiler::ir::block::{ControlFlowGraph, IrModule};
use crate::compiler::ir::inst::IrInst;
use crate::compiler::ir::liveness::LivenessInfo;
use crate::compiler::ir::types::IrVar;

pub fn is_pure_instruction(inst: &IrInst) -> bool {
    matches!(
        inst,
        IrInst::LoadConst { .. }
            | IrInst::LoadNil { .. }
            | IrInst::Move { .. }
            | IrInst::BinOp { .. }
            | IrInst::UnOp { .. }
            | IrInst::NewTable { .. }
            | IrInst::Phi { .. }
    )
}

// CFG-aware Dead Code Elimination using backward dataflow liveness analysis
pub fn dead_code_elimination_cfg(cfg: &mut ControlFlowGraph) -> bool {
    let captured = super::captured_vars(cfg);
    let mut any_changed = false;
    let mut changed = true;
    let mut iterations = 0;
    const MAX_PASSES: usize = 20;

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

        let liveness = LivenessInfo::compute(cfg);

        for block in &mut cfg.blocks {
            let mut live_now = liveness
                .blocks
                .get(&block.label)
                .map(|b| b.live_out.clone())
                .unwrap_or_default();

            let mut retained = Vec::new();

            for inst in block.instructions.drain(..).rev() {
                let defs = inst.def_vars();
                let is_dead = is_pure_instruction(&inst)
                    && !defs.is_empty()
                    && defs
                        .iter()
                        .all(|dst| !live_now.contains(dst) && !captured.contains(dst));
                if is_dead {
                    // Dead instruction, eliminate it
                    changed = true;
                    any_changed = true;
                    continue;
                }

                // Update live_now backwards: remove def, add uses
                for dst in defs {
                    live_now.remove(&dst);
                }
                for u in inst.use_vars() {
                    live_now.insert(u);
                }

                retained.push(inst);
            }

            retained.reverse();
            block.instructions = retained;
        }
    }

    any_changed
}

pub fn dead_code_elimination(module: &mut IrModule) {
    let mut used_vars: HashSet<IrVar> = HashSet::new();

    for inst in &module.main.instructions {
        for u in inst.use_vars() {
            used_vars.insert(u);
        }
    }

    let mut filtered_insts = Vec::new();
    let mut unreachable = false;

    for inst in module.main.instructions.drain(..) {
        if unreachable {
            if let IrInst::Label(_) = inst {
                unreachable = false;
                filtered_insts.push(inst);
            }
            continue;
        }

        match &inst {
            IrInst::LoadConst { dst, .. } | IrInst::LoadNil { dst } => {
                if used_vars.contains(dst) {
                    filtered_insts.push(inst);
                }
            }
            IrInst::BinOp { dst, .. } | IrInst::UnOp { dst, .. } => {
                if used_vars.contains(dst) {
                    filtered_insts.push(inst);
                }
            }
            IrInst::Return(_) => {
                filtered_insts.push(inst);
                unreachable = true;
            }
            IrInst::Jump(_) => {
                filtered_insts.push(inst);
                unreachable = true;
            }
            _ => {
                filtered_insts.push(inst);
            }
        }
    }

    module.main.instructions = filtered_insts;
}