3 ms·
This stuff is fun. In the TXR Lisp compiler was running into pattern matching code refusing to optimize nicely. My test case was this Ackermann: (defun ack (
by kazinator 6y ago
This stuff is fun. In the TXR Lisp compiler was running into pattern matching code refusing to optimize nicely. My test case was this Ackermann:
(defun ack (:match)
((0 @n) (+ n 1))
((@m 0) (ack (- m 1) 1))
((@m @n) (ack (- m 1) (ack m (- n 1)))))
I then added an "early peephole" pass which works on the input code before it has been divided into basic blocks:
http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimize.tl?h=txr-255#n588 http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimi... (function at line 588)
There, I added recognition for a certain four-instruction kernel occurring out of pattern matching code, and rewrote it to three instructions.
Poof; I was left rubbing my eyes as out popped an instruction sequence identical to the one for this non-pattern-matching Ackermann, modulo some register names:
(defun ack (m n)
(cond
((eq m 0) (+ n 1))
((eq n 0) (ack (- m 1) 1))
(t (ack (- m 1) (ack m (- n 1))))))
That early reduction kind of removed a logjam, allowing other optimizations to proceed.
The pattern matching code generates a flag which is set true upon matching, so that subsequent cases are skipped. This flag completely disappears.
The recognized instruction pattern spans (what would be) two basic blocks because it includes a jmp instruction. The rewritten instruction sequence eliminates one conditional branch, which gets rid of a basic block division, which is part of why it works.
Anyway, a big picture lesson here is that a big reason for the existence of pattern matching is so that so you have a tool that can be applied to optimize pattern matching.
- kazinator 6y agoThis is more related to the story than meets the eye. early-peephole matches a pattern that will span two basic blocks if it is not replaced. The rewrite removes a conditional which tests a temporary flag; that test ends up in a basic block by itself: (defun early-peephole (code) (rewrite-case insns code (((mov (t @t1) (d @d1)) (jmp @lab2) @(symbolp @lab1) (mov (t @t1) (t 0)) A label is matched (backreferencing the earlier (jmp @lab2), so we know this item must be a label) followed by an ifq: @lab2 (ifq (t @t1) (t 0) @lab3) and so the above label and ifq form a basic block which does nothing more than tests a register to go somewhere else: the following code or some lab3 elsewhere. This is very reminiscent to the numerous temporary-testing basic blocks shown the messy "unoptimizable" flow graph in the submission. . @rest) ^((mov (t ,t1) (d ,d1)) (jmp ,lab3) ,lab1 (mov (t ,t1) (t 0)) ,lab2 ,*rest)) In the rewritten pattern, that ifq is gone. If we look at the diagram in the submission: some things are striking. For instance, have a basic block 14: bb14: fill temp5 with false And another one: bb13: fill temp5 with true Both of these jumps unconditionally to bb16: check temp5 The situation tested by my pattern above is exactly this sort of thing. E.g. if we look at the pattern matching ack without optimization, we can find them: 2> (disassemble (let ((*opt-level* 0)) (compile 'ack))) data: 0: ack 1: 0 2: 1 3: t Note 3: t means that in this VM description, register d3 holds t, the canonical Boolean true symbol: [ snip ] 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 33: 2C060000 movsr t6 nil 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 Here is an instance of the pattern. Except for the "end t6" has to do with closing a "frame ..." instruction earlier. We don't see this "end t6" in the pattern, and so it would cause a mismatch; but this instruction is removed by frame elimination, which is earlier in the compiler and happens at a lower optimization level. So then, what do we have here? basic block A: "fill temp6 with true, jump to C" 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 basic block B: "fill temp6 with false, fall to C" 33: 2C060000 movsr t6 nil basic block C: "check temp6" 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 That very similar that aforementioned situation in that basic block diagram! In my case, what breaks the logjam is that we get rid of the check, because the pattern knows that the check is only being reached from those two sources. And then, register t6 succumbs to dead register removal. A subsequent data flow analysis, done after flow control optimizations (jump threading) discovers that these definitions of the t6 value have no next use. I think that thanks to work done since then, that early-peephole thing could be moved into jump threading. There could be jump threading patterns which infer that the target of a jump is a conditional instruction which depends on the value of a register which is set to a true/false value prior to the jump, and then adjust the original jump. It's more general, but more annoying to code because of pattern matching across multiple discontinuous basic blocks.
- sillysaurusx 6y agoIs the code up anywhere? I’d be interested in studying a lisp compiler.
- kazinator 6y agoYes: http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/ http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/ Files compiler.tl, optimize.tl. asm.tl. Main entry points into it are the functions compile and compile-file, as well as compile-toplevel which is public and used by those two.
- sillysaurusx 6y agoThere's some interesting syntax in those files that I haven't seen before. What's ^((,me.(get-sidx 'exception-subtype-p) mean? Specifically, dot followed by open paren. Is it a method call? In my own lisp, I settled on a convention like (foo (.bar 1) (.baz 2)) but that might be an interesting alternative. ^ seems like quasiquote. Is it?
- kazinator 6y agoYes, ^ is quasiquote. The only other weird thing is that ,* is splicing, and not ,@. With that mapping, your quasiquote skills transfer. ` cannot be quasiquote because it's used for quasistrings. @ is also a notational prefix with a number of uses. When an earmuffed special variable has to be inserted inserted without splicing, it is written , *variable* with extra whitespace. ,**variable* inserts *variable* with splicing. obj.(fun arg ...) is indeed a method call. Within certain constraints, a.b.c.d stands for (qref a b c d). The elements can be symbols or compound expressions. obj.(fun arg) is (qref obj (fun arg)). The qref macro transforms that into the method calls and slot accesses. From time to time qref appears in backquote templates. The syntax ^(lorem ipsum ,var.(abc)) calls the abc method on var and inserts the return value into the template, which is wrong if what we want is for just the value of var to be inserted into the template, in order to generate a method call on whatever syntax var stands for. That can only be directly written as ^(lorem ipsum (qref ,foo (abc))). ^(... ,me.(get-sidx 'exception-subtype-p) ...) means that we call the get-sidx method on the me object with that exception-subtype-p symbol as its argument. The return value of that method calls is inserted. get-sidx builds a table of symbols which have integer indices, referenced from the virtual machine code. The catch needs to be able to call exception-subtype-p at run-time, so it nails down an integer index for it and generates a gcall instruction referencing it. The symbol index looks like a vector in the compiled VM description; the VM turns it into an array which provides efficient access to global bindings: the symbol is looked up the first time the index position is accessed, and the binding is forwarded into the table for faster access next time.