JIT

Simple Example

The following example is a interpreter of brainfuck language with JIT. There is a detailed tutorial (part1, part2) on how to write a simple interpreter with RPython. Here, we briefly introduce some JIT-related data structures, functions, and decorators.

 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
import os
from rpython.rlib.jit import JitDriver, elidable

def get_location(pc, program, bracket_map):
    return "%s_%s_%s" % (program[:pc], program[pc], program[pc+1:])

jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'],
                      reds=['tape'],
                      get_printable_location=get_location)

@elidable
def get_matching_bracket(bracket_map, pc):
    return bracket_map[pc]

def mainloop(program, bracket_map):
    pc = 0
    tape = Tape()

    while pc < len(program):
        jitdriver.jit_merge_point(pc=pc,
                                  tape=tape,
                                  program=program,
                                  bracket_map=bracket_map)

        code = program[pc]

        if code == ">": tape.advance()
        elif code == "<": tape.devance()
        elif code == "+": tape.inc()
        elif code == "-": tape.dec()
        elif code == ".": os.write(1, chr(tape.get()))      # write
        elif code == ",": tape.set(ord(os.read(0, 1)[0]))   # read from stdin
        elif code == "[" and tape.get() == 0:
            # Skip forward to the matching ]
            pc = get_matching_bracket(bracket_map, pc)
        elif code == "]" and tape.get() != 0:
            # Skip back to the matching [
            pc = get_matching_bracket(bracket_map, pc)

        pc += 1

class Tape(object):
    def __init__(self):
        self.thetape = [0]
        self.position = 0

    def get(self): return self.thetape[self.position]
    def set(self, val): self.thetape[self.position] = val
    def inc(self): self.thetape[self.position] += 1
    def dec(self): self.thetape[self.position] -= 1
    def advance(self):
        self.position += 1
        if len(self.thetape) <= self.position:
            self.thetape.append(0)
    def devance(self): self.position -= 1

def parse(program):
    parsed = []
    bracket_map = {}
    leftstack = []

    pc = 0
    for char in program:
        if char in ('[', ']', '<', '>', '+', '-', ',', '.'):
            parsed.append(char)

            if char == '[':
                leftstack.append(pc)
            elif char == ']':
                left = leftstack.pop()
                right = pc
                bracket_map[left] = right
                bracket_map[right] = left
            pc += 1

    return "".join(parsed), bracket_map

def run(filename):
    with open(filename) as f:
        program_contents = f.read()
    program, bm = parse(program_contents)
    mainloop(program, bm)

def entry_point(argv):
    try:
        filename = argv[1]
    except IndexError:
        print "You must supply a filename"
        return 1

    run(filename)
    return 0

def target(*args): return entry_point, None

JitDriver

An interpreter wishing to use the RPython JIT generator must define a list of green variables and a list of red variables. The green variables are loop constants. They are used to identify the current loop. Red variables are for everything else used in the execution loop.

JIT Decorators and Functions

  • elidable

  • hint

  • promote

  • promote_string

  • dont_look_inside

  • look_inside

  • look_inside_iff

  • unroll_safe

  • loop_invariant

  • elidable_promote

  • oopspec

  • not_in_trace

  • isconstant

  • isvirtual

  • loop_unroll_heuristic

  • we_are_jitted

JIT Parameters

  • threshold: number of times a loop has to run for it to become hot

  • function_threshold: number of times a function must run for it to become traced from start

  • trace_eagerness: number of times a guard has to fail before we start compiling a bridge

  • decay: amount to regularly decay counters by (0=none, 1000=max)

  • trace_limit: number of recorded operations before we abort tracing with ABORT_TOO_LONG

  • inlining: inline python functions or not (1/0)

  • loop_longevity: a parameter controlling how long loops will be kept before being freed, an estimate

  • retrace_limit: how many times we can try retracing before giving up

  • max_retrace_guards: number of extra guards a retrace can cause

  • max_unroll_loops: number of extra unrollings a loop can cause

  • disable_unrolling: after how many operations we should not unroll

  • enable_opts: internal use only (may not work or lead to crashes): optimizations to enable, or all = intbounds:rewrite:virtualize:string:pure:earlyforce:heap:unroll

  • max_unroll_recursion: how many levels deep to unroll a recursive function

  • vec: turn on the vectorization optimization (vecopt). Supports x86 (SSE 4.1), powerpc (SVX), s390x SIMD

  • vec_cost: threshold for which traces to bail. Unpacking increases the counter, vector operation decrease the cost,

  • vec_all: try to vectorize trace loops that occur outside of the numpypy library

The default parameters are:

PARAMETERS = {'threshold': 1039, # just above 1024, prime
              'function_threshold': 1619, # slightly more than one above, also prime
              'trace_eagerness': 200,
              'decay': 40,
              'trace_limit': 6000,
              'inlining': 1,
              'loop_longevity': 1000,
              'retrace_limit': 0,
              'max_retrace_guards': 15,
              'max_unroll_loops': 0,
              'disable_unrolling': 200,
              'enable_opts': 'all',
              'max_unroll_recursion': 7,
              'vec': 0,
              'vec_all': 0,
              'vec_cost': 0,
              }