src/wam/dump.lisp @ 2ce458ef85fd

Implement last call optimization
author Steve Losh <steve@stevelosh.com>
date Tue, 12 Jul 2016 15:46:22 +0000
parents 8cd3257c58e3
children 184e610451c0
(in-package #:bones.wam)

(defun registers-pointing-to (wam addr)
  (loop
    :for r :from 0 :below +register-count+
    :for reg = (wam-local-register wam r)
    :when (= reg addr)
    :collect r))

(defun heap-debug (wam addr cell indent-p)
  (format
    nil "~A~A~{<-X~A ~}"
    (if indent-p
      "  "
      "")
    (switch ((cell-type cell))
      (+tag-reference+
        (if (= addr (cell-value cell))
          "unbound variable "
          (format nil "var pointer to ~4,'0X " (cell-value cell))))
      (+tag-structure+
        (format nil "structure pointer to ~4,'0X " (cell-value cell)))
      (+tag-functor+
        (destructuring-bind (functor . arity)
            (wam-functor-lookup wam (cell-value cell))
          (format nil "~A/~D " functor arity)))
      (+tag-constant+
        (format nil "~A/0 " (wam-functor-symbol wam (cell-value cell))))
      (t ""))
    (registers-pointing-to wam addr)))

(defun dump-heap (wam from to highlight)
  ;; This code is awful, sorry.
  (let ((store (wam-store wam)))
    (format t "HEAP~%")
    (format t "  +------+-----+------------------+--------------------------------------+~%")
    (format t "  | ADDR | TYP |            VALUE | DEBUG                                |~%")
    (format t "  +------+-----+------------------+--------------------------------------+~%")
    (when (> from +heap-start+)
      (format t "  |    ⋮ |  ⋮  |                ⋮ |                                      |~%"))
    (flet ((print-cell (i cell indent)
             (let ((hi (= i highlight)))
               (format t "~A ~4,'0X | ~A | ~16,'0X | ~36A ~A~%"
                       (if hi "==>" "  |")
                       i
                       (cell-type-short-name cell)
                       (cell-value cell)
                       (heap-debug wam i cell (> indent 0))
                       (if hi "<===" "|")))))
      (loop :for i :from from :below to
            :with indent = 0
            :for cell = (aref store i)
            :do
            (progn
              (print-cell i cell indent)
              (if (cell-functor-p cell)
                (setf indent (wam-functor-arity wam (cell-value cell)))
                (when (not (zerop indent))
                  (decf indent))))))
    (when (< to (wam-heap-pointer wam))
      (format t "  |    ⋮ |  ⋮  |                ⋮ |                                      |~%"))
    (format t "  +------+-----+------------------+--------------------------------------+~%")
    (values)))


(defun dump-stack (wam)
  (format t "STACK~%")
  (format t "  +------+------------------+-------------------------------+~%")
  (format t "  | ADDR |            VALUE |                               |~%")
  (format t "  +------+------------------+-------------------------------+~%")
  (with-accessors ((e wam-environment-pointer)
                   (b wam-backtrack-pointer))
      wam
    (when (not (= +stack-start+ e b))
      (loop
        :with nargs = nil
        :with arg = 0
        :with currently-in = nil
        :for addr :from (1+ +stack-start+) :below (wam-stack-top wam)
        :for cell = (wam-stack-word wam addr)
        :for offset = 0 :then (1+ offset)
        :do
        (when (not (zerop addr))
          (switch (addr :test #'=)
            (e (setf currently-in :frame offset 0 arg 0))
            (b (setf currently-in :choice offset 0 arg 0))))
        (format t "  | ~4,'0X | ~16,'0X | ~30A|~A~A~%"
                addr
                cell
                (case currently-in ; jesus christ this needs to get fixed
                  (:frame
                   (cond
                     ((= addr +stack-start+) "")
                     ((= offset 0) "CE ===========================")
                     ((= offset 1) "CP")
                     ((= offset 2) "CUT")
                     ((= offset 3)
                      (if (zerop cell)
                        (progn
                          (setf currently-in nil)
                          "N: EMPTY")
                        (progn
                          (setf nargs cell)
                          (format nil "N: ~D" cell))))
                     ((< arg nargs)
                      (prog1
                          (format nil " Y~D: ~8,'0X ~A"
                                  arg cell (cell-aesthetic cell))
                        (when (= nargs (incf arg))
                          (setf currently-in nil))))))
                  (:choice ; sweet lord make it stop
                   (cond
                     ((= addr +stack-start+) "")
                     ((= offset 0)
                      (if (zerop cell)
                        (progn
                          (setf currently-in nil)
                          "N: EMPTY =================")
                        (progn
                          (setf nargs cell)
                          (format nil "N: ~D =============" cell))))
                     ((= offset 1) "CE saved env pointer")
                     ((= offset 2) "CP saved cont pointer")
                     ((= offset 3) "CB previous choice")
                     ((= offset 4) "BP next clause")
                     ((= offset 5) "TR saved trail pointer")
                     ((= offset 6) "H  saved heap pointer")
                     ((< arg nargs)
                      (prog1
                          (format nil " A~D: ~8,'0X ~A"
                                  arg cell (cell-aesthetic cell))
                        (when (= nargs (incf arg))
                          (setf currently-in nil))))))
                  (t ""))
                (if (= addr e) " <- E" "")
                (if (= addr b) " <- B" "")))))
  (format t "  +------+------------------+-------------------------------+~%"))


(defun pretty-functor (functor-index functor-list)
  (when functor-list
    (destructuring-bind (symbol . arity)
        (elt functor-list functor-index)
      (format nil "~A/~D" symbol arity))))

(defun pretty-arguments (arguments)
  (format nil "~10<~{ ~4,'0X~}~;~>" arguments))


(defgeneric instruction-details (opcode arguments functor-list))

(defmethod instruction-details ((opcode t) arguments functor-list)
  (format nil "~A~A"
          (opcode-short-name opcode)
          (pretty-arguments arguments)))


(defmethod instruction-details ((opcode (eql +opcode-get-structure+)) arguments functor-list)
  (format nil "GETS~A ; X~A = ~A"
          (pretty-arguments arguments)
          (second arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-put-structure+)) arguments functor-list)
  (format nil "PUTS~A ; X~A <- new ~A"
          (pretty-arguments arguments)
          (second arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-get-variable-local+)) arguments functor-list)
  (format nil "GVAR~A ; X~A <- A~A"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-get-variable-stack+)) arguments functor-list)
  (format nil "GVAR~A ; Y~A <- A~A"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-get-value-local+)) arguments functor-list)
  (format nil "GVLU~A ; X~A = A~A"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-get-value-stack+)) arguments functor-list)
  (format nil "GVLU~A ; Y~A = A~A"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-put-variable-local+)) arguments functor-list)
  (format nil "PVAR~A ; X~A <- A~A <- new unbound REF"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-put-variable-stack+)) arguments functor-list)
  (format nil "PVAR~A ; Y~A <- A~A <- new unbound REF"
          (pretty-arguments arguments)
          (first arguments)
          (second arguments)))

(defmethod instruction-details ((opcode (eql +opcode-put-value-local+)) arguments functor-list)
  (format nil "PVLU~A ; A~A <- X~A"
          (pretty-arguments arguments)
          (second arguments)
          (first arguments)))

(defmethod instruction-details ((opcode (eql +opcode-put-value-stack+)) arguments functor-list)
  (format nil "PVLU~A ; A~A <- Y~A"
          (pretty-arguments arguments)
          (second arguments)
          (first arguments)))

(defmethod instruction-details ((opcode (eql +opcode-call+)) arguments functor-list)
  (format nil "CALL~A ; call ~A"
          (pretty-arguments arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-jump+)) arguments functor-list)
  (format nil "JUMP~A ; jump ~A"
          (pretty-arguments arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-dynamic-call+)) arguments functor-list)
  (format nil "DYCL~A ; dynamic call"
          (pretty-arguments arguments)))

(defmethod instruction-details ((opcode (eql +opcode-dynamic-jump+)) arguments functor-list)
  (format nil "DYJP~A ; dynamic jump"
          (pretty-arguments arguments)))

(defmethod instruction-details ((opcode (eql +opcode-get-constant+)) arguments functor-list)
  (format nil "GCON~A ; X~A = CONSTANT ~A"
          (pretty-arguments arguments)
          (second arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-put-constant+)) arguments functor-list)
  (format nil "PCON~A ; X~A <- CONSTANT ~A"
          (pretty-arguments arguments)
          (second arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-subterm-constant+)) arguments functor-list)
  (format nil "SCON~A ; SUBTERM CONSTANT ~A"
          (pretty-arguments arguments)
          (pretty-functor (first arguments) functor-list)))

(defmethod instruction-details ((opcode (eql +opcode-get-list+)) arguments functor-list)
  (format nil "GLST~A ; X~A = [vvv | vvv]"
          (pretty-arguments arguments)
          (first arguments)))

(defmethod instruction-details ((opcode (eql +opcode-put-list+)) arguments functor-list)
  (format nil "PLST~A ; X~A = [vvv | vvv]"
          (pretty-arguments arguments)
          (first arguments)))


(defun dump-code-store (wam code-store
                        &optional
                        (from 0)
                        (to (length code-store)))
  ;; This is a little trickier than might be expected.  We have to walk from
  ;; address 0 no matter what `from` we get, because instruction sizes vary and
  ;; aren't aligned.  So if we just start at `from` we might start in the middle
  ;; of an instruction and everything would be fucked.
  (let ((addr 0)
        (lbls (bones.utils::invert-hash-table (wam-code-labels wam)))) ; oh god
    (while (< addr to)
      (let ((instruction (retrieve-instruction code-store addr)))
        (when (>= addr from)
          (when (not (= +opcode-noop+ (aref instruction 0)))

            (let ((lbl (gethash addr lbls))) ; forgive me
              (when lbl
                (format t ";;;; BEGIN ~A~%"
                        (pretty-functor lbl (wam-functors wam)))))
            (format t ";~A~4,'0X: "
                    (if (= (wam-program-counter wam) addr)
                      ">>"
                      "  ")
                    addr)
            (format t "~A~%" (instruction-details (aref instruction 0)
                                                  (rest (coerce instruction 'list))
                                                  (wam-functors wam)))))
        (incf addr (length instruction))))))

(defun dump-code
    (wam
     &optional
     (from (max (- (wam-program-counter wam) 8) ; wow
                0)) ; this
     (to (min (+ (wam-program-counter wam) 8) ; is
              (length (wam-code wam))))) ; bad
  (format t "CODE (size: ~D frame(s) / ~:[OPEN~;CLOSED~])~%"
          (length (wam-logic-stack wam))
          (wam-logic-closed-p wam))
  (dump-code-store wam (wam-code wam) from to))


(defun dump-wam-registers (wam)
  (format t "REGISTERS:~%")
  (format t  "~5@A -> ~8X~%" "S" (wam-subterm wam))
  (loop :for register :from 0 :to +register-count+
        :for contents :across (wam-store wam)
        :when (not (cell-null-p contents))
        :do
        (format t "~5@A -> ~8,'0X ~10A ~A~%"
                (format nil "X~D" register)
                contents
                (cell-aesthetic contents)
                (format nil "; ~A" (first (extract-things wam (list register)))))))

(defun dump-wam-functors (wam)
  (format t "        FUNCTORS: ~S~%" (wam-functors wam)))

(defun dump-wam-trail (wam)
  (format t "    TRAIL: ")
  (loop :for addr :across (wam-trail wam) :do
        (format t "~4,'0X ~A //"
                addr
                (cell-aesthetic (wam-store-cell wam addr))))
  (format t "~%"))

(defun dump-labels (wam)
  (format t "LABELS:~%~{  ~A -> ~4,'0X~^~%~}~%"
          (loop :for functor-index
                :being :the :hash-keys :of (wam-code-labels wam)
                :using (hash-value address)
                :nconc (list (pretty-functor functor-index
                                             (wam-functors wam))
                             address))))


(defun dump-wam (wam from to highlight)
  (format t "            FAIL: ~A~%" (wam-fail wam))
  (format t "    BACKTRACKED?: ~A~%" (wam-backtracked wam))
  (format t "            MODE: ~S~%" (wam-mode wam))
  (dump-wam-functors wam)
  (format t "       HEAP SIZE: ~A~%" (- (wam-heap-pointer wam) +heap-start+))
  (format t " PROGRAM COUNTER: ~4,'0X~%" (wam-program-counter wam))
  (format t "CONTINUATION PTR: ~4,'0X~%" (wam-continuation-pointer wam))
  (format t " ENVIRONMENT PTR: ~4,'0X~%" (wam-environment-pointer wam))
  (format t "   BACKTRACK PTR: ~4,'0X~%" (wam-backtrack-pointer wam))
  (format t "         CUT PTR: ~4,'0X~%" (wam-cut-pointer wam))
  (format t "HEAP BCKTRCK PTR: ~4,'0X~%" (wam-heap-backtrack-pointer wam))
  (dump-wam-trail wam)
  (dump-wam-registers wam)
  (format t "~%")
  (dump-heap wam from to highlight)
  (format t "~%")
  (dump-stack wam)
  (format t "~%")
  (dump-labels wam)
  (dump-code wam))

(defun dump-wam-query-code (wam &optional (max +maximum-query-size+))
  (with-slots (code) wam
    (dump-code-store wam code 0 max)))

(defun dump-wam-code (wam)
  (with-slots (code) wam
    (dump-code-store wam code +maximum-query-size+ (length code))))

(defun dump-wam-full (wam)
  (dump-wam wam +heap-start+ (wam-heap-pointer wam) -1))

(defun dump-wam-around (wam addr width)
  (dump-wam wam
            (max +heap-start+ (- addr width))
            (min (wam-heap-pointer wam)
                 (+ addr width 1))
            addr))