bf 0.4.8

An optimizing Brainfuck interpeter and JIT compiler
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

//! Loop movement balance analysis.
//!
//! This analysis determines, for the body of a loop, whether its net movement is an exact
//! amount, an unknown amount in a given direction, or unknown altogether. This is used by the
//! bound checking analysis when it encounters loops.

use std::collections::HashMap;
use peephole::{Statement, Program};

/// The body of a loop is a boxed slice of `Statement`s.
pub type LoopBody = Box<[Statement]>;

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
/// The net movement of a loop.
pub enum LoopBalance {
    /// The exact movement of one iteration.
    Exact(isize),
    /// May move right but not left.
    RightOnly,
    /// May move left but not right.
    LeftOnly,
    /// Net movement may be either direction.
    Unknown,
}

/// An index to a loop.
///
/// This is represented as the address of the first instruction of the loop.
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
struct LoopIndex(usize);

/// The computed net movement for each loop.
#[derive(Debug)]
pub struct LoopBalanceMap(HashMap<LoopIndex, LoopBalance>);

impl LoopBalance {
    /// Is the loop body exactly balanced between right and left?
    pub fn is_balanced(self) -> bool {
        self == LoopBalance::Exact(0)
    }

    /// Does the loop move net right (if at all)?
    pub fn is_right_only(self) -> bool {
        use self::LoopBalance::*;

        match self {
            Exact(disp)         => disp >= 0,
            RightOnly           => true,
            LeftOnly | Unknown  => false,
        }
    }

    /// Does the loop move net left (if at all)?
    pub fn is_left_only(self) -> bool {
        use self::LoopBalance::*;

        match self {
            Exact(disp)         => disp <= 0,
            LeftOnly            => true,
            RightOnly | Unknown => false,
        }
    }
}

impl LoopIndex {
    /// Gets the loop index from a boxed loop.
    fn from_loop_body(body: &LoopBody) -> Self {
        LoopIndex(body.as_ptr() as usize)
    }
}

impl LoopBalanceMap {
    /// Initializes the map for the given program.
    pub fn new(program: &Program) -> Self {
        let mut result = LoopBalanceMap(HashMap::new());

        for statement in program {
            match *statement {
                Statement::Instr(_) => (),
                Statement::Loop(ref body) => {
                    result.analyze_loop(body);
                }
            }
        }

        result
    }

    /// Gets the balance of the given loop body.
    pub fn get(&self, body: &LoopBody) -> LoopBalance {
        *self.0.get(&LoopIndex::from_loop_body(body)).unwrap_or(&LoopBalance::Unknown)
    }

    /// Performs the analysis for the given loop body and any sub-loops.
    ///
    /// Stores the result of the analysis in `self`.
    fn analyze_loop(&mut self, body: &LoopBody) -> LoopBalance {
        use peephole::Statement::*;
        use common::Instruction::*;
        use self::LoopBalance::*;

        let mut net = Exact(0);

        for statement in &**body {
            match *statement {
                Instr(Right(count)) => net = match net {
                    Exact(disp) => Exact(disp + count as isize),
                    RightOnly   => RightOnly,
                    _           => Unknown,
                },

                Instr(Left(count)) => net = match net {
                    Exact(disp) => Exact(disp - count as isize),
                    LeftOnly    => LeftOnly,
                    _           => Unknown,
                },

                Instr(Add(_)) | Instr(In) | Instr(Out) |
                Instr(SetZero) | Instr(OffsetAddRight(_)) | Instr(OffsetAddLeft(_)) => (),

                Instr(JumpZero(_)) | Instr(JumpNotZero(_)) =>
                    panic!("unexpected jump instruction"),

                Instr(FindZeroRight(_)) =>
                    net = if net.is_right_only() { RightOnly } else { Unknown },

                Instr(FindZeroLeft(_)) =>
                    net = if net.is_left_only() { LeftOnly } else { Unknown },

                Loop(ref body) => {
                    let body = self.analyze_loop(body);

                    net = match net {
                        Exact(disp) if body.is_balanced()                   => Exact(disp),
                        _ if net.is_right_only() && body.is_right_only()    => RightOnly,
                        _ if net.is_left_only() && body.is_left_only()      => LeftOnly,
                        _                                                   => Unknown,
                    }
                }
            }
        }

        self.0.insert(LoopIndex::from_loop_body(body), net);

        net
    }
}