Commit: 86c548543683f7b611db4351c39fce3e3147c885 - rpypkgs (git)

Nix flake for RPython interpreters

Commit MetaInfo

• Revisão: 86c548543683f7b611db4351c39fce3e3147c885 (tree)
• Hora: 2024-04-20 04:17:28
• Autor: Corbin <cds@corb...>
• Commiter: Corbin

Mensagem de Log

bf: Add optimizing ops, peephole, delooper.

Simpler than it sounds! I get to exploit the Abelian group actions on
the two pairs of ops Inc/Dec and Right/Left to track them with integers,
and they are free other than the type tag; this works because integers
are the initial Abelian group.

I've seen a couple folks go further down this particular direction, but
I'm going to say that this is sufficient for now, because we're now 20%
faster on Mandelbrot than Brown's original interpreter. Our main source
of speedups is fundamentally from reducing the tape from a
dynamically-allocated compound structure into a statically-allocated
arena. We also use op fusion to overcome otherwise-difficult sequences
for the JIT, like repeated subtraction and copying/moving memory.

Mudança Sumário

• modified: bf/bf.py

Diff

--- a/bf/bf.py
+++ b/bf/bf.py
@@ -13,7 +13,8 @@ def printableProgram(program): return program.asStr()
 jitdriver = JitDriver(greens=['program'], reds=['position', 'tape'],
                       get_printable_location=printableProgram)
 
-class Op(object): pass
+class Op(object):
+    _immutable_fields_ = "width",
 
 class _Input(Op):
     def asStr(self): return ','
@@ -27,35 +28,41 @@ class _Output(Op):
         os.write(1, chr(tape[position]))
         return position
 Output = _Output()
-class _Inc(Op):
-    def asStr(self): return '+'
+class Add(Op):
+    _immutable_fields_ = "imm",
+    def __init__(self, imm): self.imm = imm
+    def asStr(self): return "add(%d)" % self.imm
     def runOn(self, tape, position):
-        tape[position] += 1
+        tape[position] += self.imm
         return position
-Inc = _Inc()
-class _Dec(Op):
-    def asStr(self): return '-'
+Inc = Add(1)
+Dec = Add(-1)
+class Shift(Op):
+    _immutable_fields_ = "width",
+    def __init__(self, width): self.width = width
+    def asStr(self): return "shift(%d)" % self.width
+    def runOn(self, tape, position): return position + self.width
+Left = Shift(-1)
+Right = Shift(1)
+class _Zero(Op):
+    def asStr(self): return "0"
     def runOn(self, tape, position):
-        tape[position] -= 1
+        tape[position] = 0
         return position
-Dec = _Dec()
-class _Left(Op):
-    def asStr(self): return '<'
+Zero = _Zero()
+class ZeroAdd(Op):
+    _immutable_fields_ = "offset",
+    def __init__(self, offset): self.offset = offset
+    def asStr(self): return "zeroadd(%d)" % self.offset
     def runOn(self, tape, position):
-        if position == 0: raise Exception("Stack underflow")
-        return position - 1
-Left = _Left()
-class _Right(Op):
-    def asStr(self): return '>'
-    def runOn(self, tape, position):
-        if len(tape) <= position: tape.extend([0] * 1000)
-        return position + 1
-Right = _Right()
+        tape[position + self.offset] += tape[position]
+        tape[position] = 0
+        return position
 class Loop(Op):
     _immutable_fields_ = "ops[*]",
     def __init__(self, ops): self.ops = ops
     def asStr(self):
-        return '[' + ''.join([op.asStr() for op in self.ops]) + ']'
+        return '[' + '; '.join([op.asStr() for op in self.ops]) + ']'
     def runOn(self, tape, position):
         while tape[position]:
             jitdriver.jit_merge_point(program=self,
@@ -63,6 +70,35 @@ class Loop(Op):
             for op in self.ops: position = op.runOn(tape, position)
         return position
 
+def peep(ops):
+    rv = []
+    temp = ops[0]
+    for op in ops[1:]:
+        if isinstance(temp, Shift) and isinstance(op, Shift):
+            temp = Shift(temp.width + op.width)
+        elif isinstance(temp, Add) and isinstance(op, Add):
+            temp = Add(temp.imm + op.imm)
+        else:
+            rv.append(temp)
+            temp = op
+    rv.append(temp)
+    return rv
+
+def oppositeShifts(op1, op2):
+    if not isinstance(op1, Shift) or not isinstance(op2, Shift): return False
+    return op1.width == -op2.width
+
+def isConstAdd(op, imm): return isinstance(op, Add) and op.imm == imm
+
+def loopish(ops):
+    if len(ops) == 1 and isConstAdd(ops[0], -1):
+        return Zero
+    elif (len(ops) == 4 and
+          isConstAdd(ops[0], -1) and isConstAdd(ops[2], 1) and
+          oppositeShifts(ops[1], ops[3])):
+        return ZeroAdd(ops[1].width)
+    return Loop(ops[:])
+
 parseTable = {
     ',': Input, '.': Output,
     '+': Inc, '-': Dec,
@@ -75,17 +111,22 @@ def parse(s):
         if char in parseTable: ops[-1].append(parseTable[char])
         elif char == '[': ops.append([])
         elif char == ']':
-            loop = Loop(ops.pop()[:])
+            loop = loopish(peep(ops.pop()))
             ops[-1].append(loop)
     
-    return ops.pop()
+    return peep(ops.pop())
 
 def entryPoint(argv):
-    if len(argv) < 2:
-        print "You must supply a filename"
+    if len(argv) < 2 or "-h" in argv:
+        print "Usage: bf [-c <number of cells>] [-h] <program.bf>"
         return 1
-    with open(argv[1]) as handle: program = parse(handle.read())
-    tape = [0] * 30000
+    cells = 30000
+    if argv[1] == "-c":
+        cells = int(argv[2])
+        path = argv[3]
+    else: path = argv[1]
+    with open(path) as handle: program = parse(handle.read())
+    tape = [0] * cells
     position = 0
     for op in program: position = op.runOn(tape, position)
     return 0