mijit 0.2.4

Experimental JIT compiler generator
Documentation 
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

use std::fmt::{Debug};

use super::{code, target};
use code::{Switch, EBB, Convention};

//-----------------------------------------------------------------------------

#[allow(unused)]
mod dep;
use dep::{Dep};

mod op;
use op::{Op};

mod resources;
use resources::{Resources};

mod cost;
use cost::{Cost, op_cost};

mod dataflow;
use dataflow::{Dataflow, Node};

mod cft;
use cft::{Cold, Exit, CFT};

mod simulation;
use simulation::{simulate};

mod builder;
use builder::{build};

/// Look up information about a control-flow merge point.
pub trait LookupLeaf {
    // A control-flow merge point.
    type Leaf: Debug + Clone;
    /// Return the convention in effect at `leaf`.
    fn after(&self, leaf: &Self::Leaf) -> &Convention;
    /// Return the estimated relative frequency of `leaf`.
    fn weight(&self, leaf: &Self::Leaf) -> usize;
}

/// Optimizes an [`EBB`].
pub fn optimize<L: LookupLeaf>(before: &Convention, input: &EBB<L::Leaf>, lookup_leaf: &L)
-> EBB<L::Leaf> {
    // Generate the [`Dataflow`] graph.
    let (dataflow, cft) = simulate(before, input, lookup_leaf);
    // Turn it back into an EBB.
    build(before, &dataflow, &cft, lookup_leaf)
}

//-----------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::code::{REGISTERS as R, BinaryOp, builder as cb};
    use BinaryOp::*;
    use crate::code::tests::{EmulatorResult, random_ebb, random_ebb_convention};

    // Several tests represent leaves as integers.
    impl LookupLeaf for Convention {
        type Leaf = usize;
        fn after(&self, _leaf: &usize) -> &Convention {
            self
        }
        fn weight(&self, leaf: &usize) -> usize {
            *leaf
        }
    }

    /// Optimize `input_ebb`, emulate the original and optimized `EBB`s, and
    /// panic with diagnostics if they behave differently.
    pub fn optimize_and_compare(input_ebb: EBB<usize>, convention: Convention) {
        let mut expected = EmulatorResult::new(&input_ebb, &convention);
        expected.keep_only(&convention.lives);
        let output_ebb = optimize(&convention, &input_ebb, &convention);
        let mut observed = EmulatorResult::new(&output_ebb, &convention);
        observed.keep_only(&convention.lives);
        if expected != observed {
            println!("input_ebb: {:#x?}", input_ebb);
            println!("expected: {:#x?}", expected);
            println!("output_ebb: {:#x?}", output_ebb);
            println!("observed: {:#x?}", observed);
            panic!("expected != observed");
        }
    }

    #[test]
    fn regression_0() {
        // This was once `random_ebb(0, 2)` but both have since changed.
        let ebb = cb::build(|mut b| {
            b.binary64(Xor, R[2], R[3], R[4]);
            b.binary64(Lt, R[3], R[3], R[4]);
            b.guard(R[3], false, cb::build(|b| b.jump(0)));
            b.binary64(Lt, R[2], R[2], R[2]);
            b.jump(1)
        });
        optimize_and_compare(ebb, random_ebb_convention());
    }

    #[test]
    fn regression_8() {
        // This was once `random_ebb(8, 3)` but both have since changed.
        let ebb = cb::build(|mut b| {
            b.const_binary64(Add, R[2], R[2], 0x3b386b745518224d as i64);
            b.binary64(Xor, R[4], R[2], R[4]);
            b.binary64(Lt, R[2], R[3], R[2]);
            b.guard(R[2], false, cb::build(|b| b.jump(0)));
            b.binary64(Lt, R[3], R[2], R[2]);
            b.guard(R[3], true, cb::build(|b| b.jump(1)));
            b.const_binary64(Add, R[2], R[2], 0xc531fbc2c4c7042 as i64);
            b.binary64(Xor, R[4], R[2], R[4]);
            b.guard(R[2], false, cb::build(|b| b.jump(2)));
            b.jump(3)
        });
        optimize_and_compare(ebb, random_ebb_convention());
    }

    #[test]
    fn regression_27() {
        // This was once `random_ebb(27, 2)` but both have since changed.
        let ebb = cb::build(|mut b| {
            b.const_binary64(Add, R[4], R[4], 0x523e32f31c82fa38 as i64);
            b.binary64(Xor, R[2], R[4], R[2]);
            b.binary64(Lt, R[4], R[3], R[3]);
            b.guard(R[4], true, cb::build(|b| b.jump(0)));
            b.const_binary64(Add, R[3], R[3], 0x2854088f4544aaa6 as i64);
            b.guard(R[3], false, cb::build(|b| b.jump(1)));
            b.jump(2)
        });
        optimize_and_compare(ebb, random_ebb_convention());
    }

    #[test]
    fn optimize_random_ebbs() {
        for seed in 0..1000 {
            let input_ebb = random_ebb(seed, 2);
            optimize_and_compare(input_ebb, random_ebb_convention());
        }
    }
}