3 ms·
This 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 remov
by kazinator 6y ago
This 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.