Hi,

Hi think this is a marvelous development and, for what it's worth, in the
right direction. Many, many thanks!

Maybe this is all completely obvious to you, but I want to remind, again,
about the plans and ideas I had for GOOPS before I had to leave it at its
rather prototypical and unfinished state:

As you recall, generic functions (GFs) then carried a cache (ideas taken
from PCL) with "instantiated methods" (IM; there is probably a better term
and I might have called them "compiled methods" or "cmethods"
before)---method code where the types of the arguments are known since each
instance come from an actual invocation of the GF. Given a new invocation,
the dispatch mechanism would just use argument types to look up the correct
IM.

I then had the idea that since we know the types of the arguments of the
IM, a lot of the type dispatch could be eliminated within the IM based on
flow information---very much in line with what you are doing here. If we
now add one more piece, things get really exciting: Wherever there is a
call to other GFs within one IM and the types of the arguments can be
deduced at the point of the call, then the polymorphic type dispatch of the
GF can be eliminated and we can replace the GF call with a direct call to
the corresponding IM.

Given now that most of the standard scheme functions can be regarded as
polymorphic GFs, I then imagined that most of the type dispatch in a
program could be eliminated. Actual execution would mostly be direct calls
of IMs to IMs, something which the optimizer could continue to work on,
especially if it all was represented as CPS.

Given your work here, I think that something like this could now rather
easily be implemented. That is, we re-introduce IMs, make them directly
callable, and substitute IM calls for GF calls when compiling them. I
gather that the code of IMs do not necessarily have to be hung onto GFs but
could be handled by some separate manager/data structures.

Happy new year!
Mikael


On Mon, Jan 8, 2018 at 4:01 PM, Andy Wingo <wingo@pobox.com> wrote:

> Hey all!
>
> This is an update along the road to Guile 3.  Check
> https://lists.gnu.org/archive/html/guile-devel/2017-11/msg00016.html for
> the previous entry.
>
> Since 25 November there have been around 100 commits or so.  Firstly I
> merged in patches from stable-2.0, including patches corresponding to
> the improvements in the Guile 2.2.3 stable series release.
>
> Then, I started to look at "instruction explosion" for vector-ref et
> al.  Basically the idea is to transform the various subcomponents of
> e.g. vector-ref into their constituent parts.  In the concrete case of
> vector-ref, we have to check that the vector is a heap object, that its
> heap object tag is "vector", we have to extract the length from the heap
> object, then we have to check that the index is an integer between 0 and
> length-1, and finally we dereference the field in the vector.
> Instruction explosion turns all of these into different primcalls and
> branches.
>
> One thing that became apparent was that with instruction explosion, we'd
> have a lot more control flow.  Information that the optimizer would
> learn in a specific way (e.g. via specialzied type inference / effects
> analysis handlers for vector-ref) would instead be learned by generic
> control flow.
>
> Concretely --
>
>     scheme@(guile-user)> ,x (lambda (v i) (vector-ref v i))
>     Disassembly of #<procedure 29f5e50 at <unknown port>:1:3 (v i)> at
> #x29f5b4c:
>
>        0    (assert-nargs-ee/locals 3 1)    ;; 4 slots (2 args)   at
> (unknown file):1:3
>        1    (immediate-tag=? 2 7 0)         ;; heap-object?       at
> (unknown file):1:17
>        3    (jne 23)                        ;; -> L3
>        4    (heap-tag=? 2 127 13)           ;; vector?
>        6    (jne 20)                        ;; -> L3
>        7    (word-ref/immediate 3 2 0)
>        8    (ursh/immediate 3 3 8)
>        9    (immediate-tag=? 1 3 2)         ;; fixnum?
>       11    (jne 13)                        ;; -> L2
>       12    (untag-fixnum 0 1)
>       13    (s64-imm<? 0 0)
>       14    (jl 8)                          ;; -> L1
>       15    (s64<? 0 3)
>       16    (jnl 6)                         ;; -> L1
>       17    (mov 3 0)
>       18    (uadd/immediate 3 3 1)
>       19    (scm-ref 2 2 3)
>       20    (handle-interrupts)
>       21    (return-values 2)               ;; 1 value
>     L1:
>       22    (throw/value+data 1 201)        ;; #(out-of-range "vector-ref"
> "Argument 2 out of range: ~S")
>     L2:
>       24    (throw/value+data 1 225)        ;; #(wrong-type-arg
> "vector-ref" "Wrong type argument in position 2 (expecting small integer):
> ~S")
>     L3:
>       26    (throw/value+data 2 239)        ;; #(wrong-type-arg
> "vector-ref" "Wrong type argument in position 1 (expecting vector): ~S")
>
> So this is a bit horrible and I need to make the disassembler do a
> better job, but anyway.  Instructions 1 through 6 check that V is a
> vector; instructions 7 and 8 extract the length; 9 and 11 check that the
> index is a fixnum, 12 extracts the fixnum value as an untagged 64-bit
> integer, and 13 through 16 check that the index is in range.
>
> L1, L2, and L3 are bailouts.  The idea here is that if this vector-ref
> is followed by some other operation on the vector, we'll at least get to
> elide the vector? checks, and maybe we can reuse the length extraction
> too.  Et cetera.
>
> The optimizer makes decisions like when to elide redundant checks based
> on flow information.  However for historical reasons unfortunately the
> "throw" terms actually did "continue" from the optimizer's perspective;
> whereas the information flowing to e.g. L3 shouldn't flow at all to
> instruction 7, the IR didn't have a way to denote terms that didn't
> continue at all.
>
> To fix this I had to make some changes to the IR.  On the plus side,
> $throw is its own term kind now that doesn't have a continuation.  Also,
> $branch is a term instead of an expression shoehorned into $continue;
> $prompt is a term too.  Maybe one day we'll get a $select term for
> proper case compilation.
>
> Finally, the instruction explosion.  I refactored the Tree-IL->CPS
> compiler to allow individual primcalls to have custom lowering routines,
> and tightened up $primcall so that it now always continues to $kargs.
> Then I added custom lowering routines for vector-ref et al, and cons and
> other things.  The CPS IR refactors allowed me to remove some useless
> passes (elide-values, prune-bailouts).  There were some optimizer bugs
> but generally things were already in a good state; e.g. here's a vector
> sum routine:
>
>   scheme@(guile-user)> (define (v-sum v)
>                          (let lp ((n 0) (sum 0))
>                            (if (< n (vector-length v))
>                                (lp (+ n 1) (+ sum (vector-ref v n)))
>                                sum)))
>   scheme@(guile-user)> ,x v-sum
>   Disassembly of #<procedure v-sum (v)> at #x1fa2750:
>
>      0    (assert-nargs-ee/locals 2 3)    ;; 5 slots (1 arg)    at
> (unknown file):1:0
>      1    (make-short-immediate 4 2)      ;; 0
>      2    (immediate-tag=? 3 7 0)         ;; heap-object?       at
> (unknown file):1:51
>      4    (jne 39)                        ;; -> L5
>      5    (heap-tag=? 3 127 13)           ;; vector?
>      7    (jne 36)                        ;; -> L5
>      8    (word-ref/immediate 2 3 0)
>      9    (ursh/immediate 2 2 8)
>     10    (imm-s64<? 2 0)                                       at
> (unknown file):1:46
>     11    (jnl 29)                        ;; -> L4
>     12    (load-s64 1 0 0)                                      at
> (unknown file):1:89
>     15    (s64<? 1 2)
>     16    (jnl 22)                        ;; -> L3
>     17    (mov 4 1)
>     18    (uadd/immediate 4 4 1)
>     19    (scm-ref 4 3 4)
>     20    (add/immediate 4 4 0)                                 at
> (unknown file):1:82
>     21    (load-s64 1 0 1)
>     24    (s64<? 1 2)                                           at
> (unknown file):1:46
>     25    (jnl 11)                        ;; -> L2
>   L1:
>     26    (handle-interrupts)
>     27    (mov 0 1)                                             at
> (unknown file):1:74
>     28    (uadd/immediate 0 0 1)
>     29    (uadd/immediate 1 1 1)                                at
> (unknown file):1:89
>     30    (scm-ref 1 3 1)
>     31    (add 4 4 1)                                           at
> (unknown file):1:82
>     32    (s64<? 0 2)                                           at
> (unknown file):1:46
>     33    (jnl 7)                         ;; -> L4
>     34    (mov 1 0)                                             at
> (unknown file):1:70
>     35    (j -9)                          ;; -> L1
>   L2:
>     36    (mov 0 1)                                             at
> (unknown file):1:46
>     37    (j 3)                           ;; -> L4
>   L3:
>     38    (throw/value+data 4 204)        ;; #(out-of-range "vector-ref"
> "Argument 2 out of range: ~S") at (unknown file):1:89
>   L4:
>     40    (handle-interrupts)
>     41    (mov 3 4)
>     42    (return-values 2)               ;; 1 value
>   L5:
>     43    (throw/value+data 3 233)        ;; #(wrong-type-arg
> "vector-length" "Wrong type argument in position 1 (expect…") at (unknown
> file):1:51
>
> The bit between L1 and L2 is the loop.  Note that the loop does no
> dynamic checks besides checking that the unboxed index is within bounds
> -- notably the vector? check, the length computation, and the index
> untagging were hoisted out.  The "scm-ref" instruction is the raw
> unchecked memory accessor instruction that will correspond to a load
> when compiled to machine code.
>
> This code runs a little slower than it did a month ago because
> instruction explosion is generally more instructions than what we had
> before.  But this is expected.  I expect the corresponding amount of
> machine code to be lower, when we emit machine code, sometimes
> significantly so.  Doing things this way takes away the temptation for
> an eventual JIT to do optimization-like tasks -- we keep it all in
> generic CPS, and the JIT will be easy to write and generate good code.
> Until then, hacking on Guile is a bit slow though, in terms of compile
> time.
>
> Next up is instruction explosion for other data structures (boxes,
> structs, strings, etc); then I have to figure out what to do for
> arithmetic that I can't specialize (like that "add" at IP 31).  I guess
> polymorphic inline caches are the real solution there; we'll see.
>
> OK that's the update.  Happy new year and happy hacking with Guile :)
>
> Cheers,
>
> Andy
>
>