Commit: be55e727840cd7ed53fc8a9d8a92802aedf578f8 - cammy (git)

A categorical programming language

Commit MetaInfo

• Revisión: be55e727840cd7ed53fc8a9d8a92802aedf578f8 (tree)
• Tiempo: 2022-04-13 13:52:38
• Autor: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

Start optimizing emitted bytecode.

Cambiar Resumen

• modified: cammy-rpy/cammylib/arrows.py
• modified: cammy-rpy/cammylib/cam.py
• modified: cammy-rpy/cammylib/elements.py
• modified: todo.txt

Diferencia incremental

--- a/cammy-rpy/cammylib/arrows.py
+++ b/cammy-rpy/cammylib/arrows.py
@@ -277,7 +277,7 @@ FZero = makeConstantF(0.0)
 FOne = makeConstantF(1.0)
 FPi = makeConstantF(math.pi)
 
-def sign(f): return math.copysign(1.0, f) > 0.0
+def sign(f): return abs(f) == f
 class FSign(Arrow):
     _immutable_ = True
     def compile(self, compiler): compiler.sign()

--- a/cammy-rpy/cammylib/cam.py
+++ b/cammy-rpy/cammylib/cam.py
@@ -69,11 +69,11 @@ class CAM(object):
         return runCAM(self.code, self.constants, term)
 
 
-def location(pc, code):
+def location(pc, code, constants):
     return "%d: %s" % (pc, decode(code[pc]))
 
 CAMDriver = JitDriver(name="cam",
-        greens=["pc", "code"], reds="auto",
+        greens=["pc", "code", "constants"], reds=["term", "stack"],
         get_printable_location=location,
         is_recursive=True)
 
@@ -82,7 +82,8 @@ def runCAM(code, constants, term):
     stack = T()
 
     while pc < len(code):
-        CAMDriver.jit_merge_point(code=code, pc=pc)
+        CAMDriver.jit_merge_point(pc=pc, code=code, constants=constants,
+                term=term, stack=stack)
         op = code[pc]; pc += 1
 
         # print "pc", self.pc, "op", decode(op)
@@ -116,13 +117,19 @@ def runCAM(code, constants, term):
             stack = P(N(pc), stack.second())
             term = P(v1, v2)
             pc = l
+            CAMDriver.can_enter_jit(pc=pc, code=code, constants=constants,
+                    term=term, stack=stack)
         elif op == BRANCH:
             term = L(T()) if term.b() else R(T())
         elif op == RET:
             pc = stack.first().n()
             stack = stack.second()
+            CAMDriver.can_enter_jit(pc=pc, code=code, constants=constants,
+                    term=term, stack=stack)
         elif op == GOTO:
             pc = code[pc]
+            CAMDriver.can_enter_jit(pc=pc, code=code, constants=constants,
+                    term=term, stack=stack)
         elif op == HALT:
             return term
         elif op == LEFT:
@@ -194,6 +201,14 @@ class Compiler(object):
     Compile an arrow to CAM bytecode.
     """
 
+    # The location behind which we will not erase any instructions during
+    # peephole optimization. Labels behind the barrier will not shift.
+    barrier = 0
+
+    # The last location that was written, to make it easy to erase bytecodes
+    # with parameters.
+    lastLocation = 0
+
     def __init__(self):
         self.constants = []
         self.insts = []
@@ -204,6 +219,19 @@ class Compiler(object):
         # Queue of curried arrows to compile.
         self.curryQueue = []
 
+    def emit(self, inst):
+        self.insts.append(inst)
+
+    def emitParam(self, inst, param):
+        self.lastLocation = len(self.insts)
+        self.insts.append(inst)
+        self.insts.append(param)
+
+    def peek(self, inst):
+        # if self.lastLocation < len(self.insts):
+        #     return self.insts[self.lastLocation] == inst
+        return False
+
     def quote(self, constant):
         # Don't repeat constants.
         for i, const in enumerate(self.constants):
@@ -213,18 +241,26 @@ class Compiler(object):
         else:
             c = len(self.constants)
             self.constants.append(constant)
-        self.insts.append(QUOTE)
-        self.insts.append(c)
+        if self.peek(QUOTE):
+            # Peephole: QUOTE c; QUOTE d -> QUOTE d
+            # XXX icky patch
+            # XXX respect the barrier!!
+            self.insts[-1] = c
+        else:
+            self.emitParam(QUOTE, c)
 
     # A label is a location where execution can go. A (forward) jump is a
     # location that needs to be patched with a label. Backward jumps are
-    # emitted immediately without a patch site.
+    # emitted immediately without a patch site. To protect labels from
+    # shifting during peephole optimization, a barrier is shifted forward to
+    # commit to each label as it is taken.
 
     def here(self):
-        return len(self.insts)
+        rv = self.barrier = len(self.insts)
+        return rv
 
     def jumpForward(self):
-        rv = len(self.insts)
+        rv = self.barrier = len(self.insts)
         self.insts.append(-1)
         return rv
 
@@ -232,7 +268,7 @@ class Compiler(object):
         self.insts.append(label)
 
     def jumpHere(self, jump):
-        self.insts[jump] = len(self.insts)
+        self.insts[jump] = self.barrier = len(self.insts)
 
     def curry(self, arrow):
         self.insts.append(CUR)
@@ -244,6 +280,7 @@ class Compiler(object):
         self.halt()
         while self.curryQueue:
             jump, arrow = self.curryQueue.pop()
+            # XXX if already seen this arrow, then jump to it instead
             self.jumpHere(jump)
             arrow.compile(self)
             self.ret()
@@ -251,38 +288,38 @@ class Compiler(object):
     def makeMachine(self):
         return CAM(self.insts[:], self.constants[:])
 
-    def fst(self): self.insts.append(FST)
-    def snd(self): self.insts.append(SND)
-    def push(self): self.insts.append(PUSH)
-    def pop(self): self.insts.append(POP)
-    def swap(self): self.insts.append(SWAP)
-    def cons(self): self.insts.append(CONS)
-    def app(self): self.insts.append(APP)
-    def branch(self): self.insts.append(BRANCH)
-    def ret(self): self.insts.append(RET)
-    def goto(self): self.insts.append(GOTO)
-    def halt(self): self.insts.append(HALT)
-    def left(self): self.insts.append(LEFT)
-    def right(self): self.insts.append(RIGHT)
-    def gotoRight(self): self.insts.append(GOTORIGHT)
-    def notOp(self): self.insts.append(NOTOP)
-    def andOp(self): self.insts.append(ANDOP)
-    def orOp(self): self.insts.append(OROP)
-    def pred(self): self.insts.append(PRED)
-    def succ(self): self.insts.append(SUCC)
-    def isNil(self): self.insts.append(ISNIL)
-    def assoc(self): self.insts.append(ASSOC)
-    def sign(self): self.insts.append(SIGN)
-    def floor(self): self.insts.append(FLOOR)
-    def negate(self): self.insts.append(NEGATE)
-    def recip(self): self.insts.append(RECIP)
-    def lessThan(self): self.insts.append(LESSTHAN)
-    def add(self): self.insts.append(ADD)
-    def mul(self): self.insts.append(MUL)
-    def sqrt(self): self.insts.append(SQRT)
-    def sin(self): self.insts.append(SIN)
-    def cos(self): self.insts.append(COS)
-    def atan2(self): self.insts.append(ATAN2)
+    def fst(self): self.emit(FST)
+    def snd(self): self.emit(SND)
+    def push(self): self.emit(PUSH)
+    def pop(self): self.emit(POP)
+    def swap(self): self.emit(SWAP)
+    def cons(self): self.emit(CONS)
+    def app(self): self.emit(APP)
+    def branch(self): self.emit(BRANCH)
+    def ret(self): self.emit(RET)
+    def goto(self): self.emit(GOTO)
+    def halt(self): self.emit(HALT)
+    def left(self): self.emit(LEFT)
+    def right(self): self.emit(RIGHT)
+    def gotoRight(self): self.emit(GOTORIGHT)
+    def notOp(self): self.emit(NOTOP)
+    def andOp(self): self.emit(ANDOP)
+    def orOp(self): self.emit(OROP)
+    def pred(self): self.emit(PRED)
+    def succ(self): self.emit(SUCC)
+    def isNil(self): self.emit(ISNIL)
+    def assoc(self): self.emit(ASSOC)
+    def sign(self): self.emit(SIGN)
+    def floor(self): self.emit(FLOOR)
+    def negate(self): self.emit(NEGATE)
+    def recip(self): self.emit(RECIP)
+    def lessThan(self): self.emit(LESSTHAN)
+    def add(self): self.emit(ADD)
+    def mul(self): self.emit(MUL)
+    def sqrt(self): self.emit(SQRT)
+    def sin(self): self.emit(SIN)
+    def cos(self): self.emit(COS)
+    def atan2(self): self.emit(ATAN2)
 
 # Generate most of the emission methods.
 # insts = ("fst", "snd", "push", "pop", "swap", "cons", "app", "branch", "ret",

--- a/cammy-rpy/cammylib/elements.py
+++ b/cammy-rpy/cammylib/elements.py
@@ -1,6 +1,6 @@
 import math
 
-from rpython.rlib.jit import promote, we_are_jitted
+from rpython.rlib.jit import we_are_jitted
 # from rpython.rlib.rbigint import rbigint
 
 
@@ -109,30 +109,10 @@ class R(Element):
     def asStr(self):
         return "R(%s)" % self._x.asStr()
 
-class H(Element):
-    _immutable_ = True
-    def __init__(self, f, x):
-        self._f = f
-        self._x = x
-    def apply(self, y):
-        # Defunctionalize by assuming that f can only take on finitely many
-        # values. This trick was suggested by cfbolz; they do a similar trick
-        # in Pycket for similar ends.
-        return promote(self._f).run(P(self._x, y))
-    def asStr(self):
-        return "%s @ %s" % (self._f, self._x.asStr())
-
-class Xs(Element):
-    _immutable_ = True
-    _immutable_fields_ = "xs[*]",
-    def __init__(self, xs):
-        self.xs = xs
-    def l(self): return self.xs
-    def asStr(self):
-        return "[%s]" % ", ".join([x.asStr() for x in self.xs])
-
 
 def equal(e1, e2):
+    if e1 is e2:
+        return True
     return False
     # if isinstance(e1, T) and isinstance(e2, T):
     #     return True
@@ -150,12 +130,3 @@ def equal(e1, e2):
     #     return equal(e1._x, e2._x)
     # elif isinstance(e1, R) and isinstance(e2, R):
     #     return equal(e1._x, e2._x)
-    # elif isinstance(e1, Xs) and isinstance(e2, Xs):
-    #     if len(e1.xs) != len(e2.xs):
-    #         return False
-    #     for i, x in enumerate(e1.xs):
-    #         if not equal(x, e2.xs[i]):
-    #             return False
-    #     return True
-    # else:
-    #     return False

--- a/todo.txt
+++ b/todo.txt
@@ -97,6 +97,17 @@
         recompute jumps
   * TCO, or really any call optimizations
   * snoc and other backwards versions of ops
+  * term ops can be applied to quoted elements, creating new quotes with
+    pre-computed elements
+    * needs equality for elements
+  * curried arrows sometimes repeat, or at least they compile down to the same
+    code
+    * needs equality for arrows
+  * sometimes we end up with two quotes in a row, should only use the second
+    * requires code barrier
+  * Currying everything really does look like it might generate better
+    bytecode
+    * Or at least let binary term ops be stack ops?
 * fun/precomp is an ingredient of CPS transformation
   * https://okmij.org/ftp/continuations/undelimited.html
 * A serious cost model