conform benchmark - r7rs benchmark

higepon commented 2 years ago

$ ./bench mosh conform

It finishes too early in less than 1 sec. But in gosh it takes 26 secs.
It returns wrong answer ("(b ^ d)" "c" "(a ^ c)" "d" "any" "none").

  (define (does-conform t1 t2)
    (newline)(display "does-conform")(newline)
    ;(write "t1=")(write t1)(newline)
    ;(write "t2=")(write t2)(newline)    
    (cond ;((or (none-node? t1) (any-node? t2)) (display "  return first #t") #t)
          ;((or (any-node? t1) (none-node? t2)) (display "  return secon #t") #f)
          ;((green-edge? t1 t2) (display "<3>") #t)
          ((red-edge? t1 t2) (display "  return forth #t") #t)
          (else
           (display "  else")
           (add-red-edge! t1 t2)
           (let loop ((blues (blue-edges t2)))
             (if (null? blues)
                 (begin (display "  end of loop") #t)
                 (let* ((current-edge (car blues))
                        (phi (operation current-edge)))
                   (and
                        (does-conform
                         (res (sig phi t1))
                         (res (sig phi t2)))
                        (loop (cdr blues)))))))))
  (let ((result (does-conform t1 t2)))
    (newline)
    (display "final ret=")

Mosh output

does-conform
  else
does-conform
  else
does-conform
  return forth #t
final ret=#t

Gauche output

does-conform
  else
does-conform
  else
does-conform
  return forth #t  end of loop
does-conform
  else

higepon commented 2 years ago

Hypothesis

Compiler output code

This is pre-optimization but looks correct?

($if ($asm [insn 53]
       ($lref azsbd@l[2;0]))
  ($asm [insn 53]
    ($asm [insn 23]
      ($lref azsbd@l[2;0])))
  ($it))
($if ($call ($lref azs190@does-conform[1;0])
       ($call ($gref azs79@res)
         ($call ($gref azs75@sig)
           ($lref azs19d@phi[2;0])
           ($lref azs193@t1[3;0])))
       ($call ($gref azs79@res)
         ($call ($gref azs75@sig)
           ($lref azs19d@phi[2;0])
           ($lref azs194@t2[3;0]))))
  ($call ($lref azs199@loop[1;0])
    ($asm [insn 23]
      ($lref azs197@blues[3;0])))
  ($it))
($if ($call ($gref azs7f@conforms?)
       ($lref azs19f@a[2;0])
       ($lref azs1a0@b[2;0]))
  ($call ($gref azs7f@conforms?)
    ($lref azs1a0@b[2;0])
    ($lref azs19f@a[2;0]))
  ($it))

Output w/o pass2/optimize

OK. Now we confirm this is optimization bug!

does-conform
  else
does-conform
  else
does-conform
  return forth #t  end of loop
does-conform
  else

higepon commented 2 years ago

Hmm. I got stuck at somewhere. Let's start over here.

Next steps

[x] Set up easy way to run the test in Mosh
[x] Set up easy way to run the test in Gauche
[x] Set up tmp branch where we can make any stupid change
[ ] See if their results are different in small input.
[ ] Minimize the code to reproduce it.

higepon commented 2 years ago

does-conform
else
=> recusive1
    does-conform
    else
    => recusive1
        does-conform
        4=>#t
    => recusive2
        does-conform
        1=>#t
    => loop
    =>else out
=> recusive2
    does-conform
    1=>#t
=> loop

final
#f

Testing conform under Mosh

does-conform
else
=> recusive1
    does-conform
    else
    => recusive1
        does-conform
        4=>#t

higepon commented 2 years ago

Small reproducible case

(define (foo)
  (define (bar  n)
    (cond ((= n 1) #t)
          (else
           (let loop ((lst '(1)))
             (if (null? lst)
                 #t
                 (and 
                  (display "=> recusive1\n")
                  (bar 1)
                  (display "=> loop\n")                         
                  (loop (cdr lst))))))))
    (bar 0)
    )

(foo)

Gauche output

=> recusive1
=> loop

Mosh output

$  ../mosh.git/mosh -5 src/reproduce.scm 
=> recusive1

Mosh Scheme VM output Optmize ON.

gosh ../../r7rs-benchmarks/src/reproduce.scm 
=> recusive1

Optimize OFF

vm.scm ../../r7rs-benchmarks/src/reproduce.scm 
=> recusive1
=> loop

higepon commented 2 years ago

This is the pass2/optimize log.

[pass2/$define] IN  =>
($define () foo
  ($lambda[foo;0] ()
    ($letrec ((bar[2;0] ($lambda[bar;0] (n[1;0])
                          ($if ($asm NUMBER_EQUAL
                                 ($lref n[1;0])
                                 ($const 1))
                            ($const #t)
                            ($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                                                   ($if ($asm NULL_P
                                                          ($lref lst[2;0]))
                                                     ($const #t)
                                                     ($if ($call ($gref display)
                                                            ($const "=> recusive1\n"))
                                                       ($if ($call ($lref bar[2;0])
                                                              ($const 1))
                                                         ($if ($call ($gref display)
                                                                ($const "=> loop\n"))
                                                           ($call ($lref loop[2;0])
                                                             ($asm CDR
                                                               ($lref lst[2;0])))
                                                           ($it))
                                                         ($it))
                                                       ($it)))))
                                      )
                              ($call ($lref loop[2;0])
                                ($const (1)))))))
              )
      ($call ($lref bar[2;0])
        ($const 0)))))
[pass2/$lambda] IN  =>
($lambda[foo;0] ()
  ($letrec ((bar[2;0] ($lambda[bar;0] (n[1;0])
                        ($if ($asm NUMBER_EQUAL
                               ($lref n[1;0])
                               ($const 1))
                          ($const #t)
                          ($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                                                 ($if ($asm NULL_P
                                                        ($lref lst[2;0]))
                                                   ($const #t)
                                                   ($if ($call ($gref display)
                                                          ($const "=> recusive1\n"))
                                                     ($if ($call ($lref bar[2;0])
                                                            ($const 1))
                                                       ($if ($call ($gref display)
                                                              ($const "=> loop\n"))
                                                         ($call ($lref loop[2;0])
                                                           ($asm CDR
                                                             ($lref lst[2;0])))
                                                         ($it))
                                                       ($it))
                                                     ($it)))))
                                    )
                            ($call ($lref loop[2;0])
                              ($const (1)))))))
            )
    ($call ($lref bar[2;0])
      ($const 0))))
[pass2/$let] IN  =>
($letrec ((bar[2;0] ($lambda[bar;0] (n[1;0])
                      ($if ($asm NUMBER_EQUAL
                             ($lref n[1;0])
                             ($const 1))
                        ($const #t)
                        ($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                                               ($if ($asm NULL_P
                                                      ($lref lst[2;0]))
                                                 ($const #t)
                                                 ($if ($call ($gref display)
                                                        ($const "=> recusive1\n"))
                                                   ($if ($call ($lref bar[2;0])
                                                          ($const 1))
                                                     ($if ($call ($gref display)
                                                            ($const "=> loop\n"))
                                                       ($call ($lref loop[2;0])
                                                         ($asm CDR
                                                           ($lref lst[2;0])))
                                                       ($it))
                                                     ($it))
                                                   ($it)))))
                                  )
                          ($call ($lref loop[2;0])
                            ($const (1)))))))
          )
  ($call ($lref bar[2;0])
    ($const 0)))
[pass2/$lambda] IN  =>
($lambda[bar;0] (n[1;0])
  ($if ($asm NUMBER_EQUAL
         ($lref n[1;0])
         ($const 1))
    ($const #t)
    ($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                           ($if ($asm NULL_P
                                  ($lref lst[2;0]))
                             ($const #t)
                             ($if ($call ($gref display)
                                    ($const "=> recusive1\n"))
                               ($if ($call ($lref bar[2;0])
                                      ($const 1))
                                 ($if ($call ($gref display)
                                        ($const "=> loop\n"))
                                   ($call ($lref loop[2;0])
                                     ($asm CDR
                                       ($lref lst[2;0])))
                                   ($it))
                                 ($it))
                               ($it)))))
              )
      ($call ($lref loop[2;0])
        ($const (1))))))
[pass2/$if] IN  =>
($if ($asm NUMBER_EQUAL
       ($lref n[1;0])
       ($const 1))
  ($const #t)
  ($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                         ($if ($asm NULL_P
                                ($lref lst[2;0]))
                           ($const #t)
                           ($if ($call ($gref display)
                                  ($const "=> recusive1\n"))
                             ($if ($call ($lref bar[2;0])
                                    ($const 1))
                               ($if ($call ($gref display)
                                      ($const "=> loop\n"))
                                 ($call ($lref loop[2;0])
                                   ($asm CDR
                                     ($lref lst[2;0])))
                                 ($it))
                               ($it))
                             ($it)))))
            )
    ($call ($lref loop[2;0])
      ($const (1)))))
[pass2/$asm] IN  =>
($asm NUMBER_EQUAL
  ($lref n[1;0])
  ($const 1))
[pass2/$local-ref] IN  =>
($lref n[1;0])
[pass2/$local-ref] OUT =>
($lref n[1;0])

[pass2/$asm] OUT =>
($asm NUMBER_EQUAL
  ($lref n[1;0])
  ($const 1))

[pass2/$let] IN  =>
($letrec ((loop[2;0] ($lambda[loop;0] (lst[2;0])
                       ($if ($asm NULL_P
                              ($lref lst[2;0]))
                         ($const #t)
                         ($if ($call ($gref display)
                                ($const "=> recusive1\n"))
                           ($if ($call ($lref bar[2;0])
                                  ($const 1))
                             ($if ($call ($gref display)
                                    ($const "=> loop\n"))
                               ($call ($lref loop[2;0])
                                 ($asm CDR
                                   ($lref lst[2;0])))
                               ($it))
                             ($it))
                           ($it)))))
          )
  ($call ($lref loop[2;0])
    ($const (1))))
[pass2/$lambda] IN  =>
($lambda[loop;0] (lst[2;0])
  ($if ($asm NULL_P
         ($lref lst[2;0]))
    ($const #t)
    ($if ($call ($gref display)
           ($const "=> recusive1\n"))
      ($if ($call ($lref bar[2;0])
             ($const 1))
        ($if ($call ($gref display)
               ($const "=> loop\n"))
          ($call ($lref loop[2;0])
            ($asm CDR
              ($lref lst[2;0])))
          ($it))
        ($it))
      ($it))))
[pass2/$if] IN  =>
($if ($asm NULL_P
       ($lref lst[2;0]))
  ($const #t)
  ($if ($call ($gref display)
         ($const "=> recusive1\n"))
    ($if ($call ($lref bar[2;0])
           ($const 1))
      ($if ($call ($gref display)
             ($const "=> loop\n"))
        ($call ($lref loop[2;0])
          ($asm CDR
            ($lref lst[2;0])))
        ($it))
      ($it))
    ($it)))
[pass2/$asm] IN  =>
($asm NULL_P
  ($lref lst[2;0]))
[pass2/$local-ref] IN  =>
($lref lst[2;0])
[pass2/$local-ref] OUT =>
($lref lst[2;0])

[pass2/$asm] OUT =>
($asm NULL_P
  ($lref lst[2;0]))

[pass2/$if] IN  =>
($if ($call ($gref display)
       ($const "=> recusive1\n"))
  ($if ($call ($lref bar[2;0])
         ($const 1))
    ($if ($call ($gref display)
           ($const "=> loop\n"))
      ($call ($lref loop[2;0])
        ($asm CDR
          ($lref lst[2;0])))
      ($it))
    ($it))
  ($it))
[pass2/$call] IN  =>
($call ($gref display)
  ($const "=> recusive1\n"))
[pass2/$call] OUT =>
($call ($gref display)
  ($const "=> recusive1\n"))

[pass2/$if] IN  =>
($if ($call ($lref bar[2;0])
       ($const 1))
  ($if ($call ($gref display)
         ($const "=> loop\n"))
    ($call ($lref loop[2;0])
      ($asm CDR
        ($lref lst[2;0])))
    ($it))
  ($it))
[pass2/$call] IN  =>
($call ($lref bar[2;0])
  ($const 1))
[pass2/$local-ref] IN  =>
($lref bar[2;0])
[pass2/$local-ref] OUT =>
($lref bar[2;0])

[pass2/classify-local-ref-call] IN  =>
($lref bar[2;0])
[pass2/classify-local-ref-call] OUT =>
($lref bar[2;0])

[pass2/$call] OUT =>
($call[tail-rec] ($lref bar[2;0])
  ($const 1))

[pass2/$if] IN  =>
($if ($call ($gref display)
       ($const "=> loop\n"))
  ($call ($lref loop[2;0])
    ($asm CDR
      ($lref lst[2;0])))
  ($it))
[pass2/$call] IN  =>
($call ($gref display)
  ($const "=> loop\n"))
[pass2/$call] OUT =>
($call ($gref display)
  ($const "=> loop\n"))

[pass2/$call] IN  =>
($call ($lref loop[2;0])
  ($asm CDR
    ($lref lst[2;0])))
[pass2/$local-ref] IN  =>
($lref loop[2;0])
[pass2/$local-ref] OUT =>
($lref loop[2;0])

[pass2/classify-local-ref-call] IN  =>
($lref loop[2;0])
[pass2/classify-local-ref-call] OUT =>
($lref loop[2;0])

[pass2/$asm] IN  =>
($asm CDR
  ($lref lst[2;0]))
[pass2/$local-ref] IN  =>
($lref lst[2;0])
[pass2/$local-ref] OUT =>
($lref lst[2;0])

[pass2/$asm] OUT =>
($asm CDR
  ($lref lst[2;0]))

[pass2/$call] OUT =>
($call[tail-rec] ($lref loop[2;0])
  ($asm CDR
    ($lref lst[2;0])))

[pass2/$if] OUT =>
($if ($call ($gref display)
       ($const "=> loop\n"))
  ($call[tail-rec] ($lref loop[2;0])
    ($asm CDR
      ($lref lst[2;0])))
  ($it))

[pass2/$if] OUT =>
($if ($call[tail-rec] ($lref bar[2;0])
       ($const 1))
  ($if ($call ($gref display)
         ($const "=> loop\n"))
    ($call[tail-rec] ($lref loop[2;0])
      ($asm CDR
        ($lref lst[2;0])))
    ($it))
  ($it))

[pass2/$if] OUT =>
($if ($call ($gref display)
       ($const "=> recusive1\n"))
  ($if ($call[tail-rec] ($lref bar[2;0])
         ($const 1))
    ($if ($call ($gref display)
           ($const "=> loop\n"))
      ($call[tail-rec] ($lref loop[2;0])
        ($asm CDR
          ($lref lst[2;0])))
      ($it))
    ($it))
  ($it))

[pass2/$if] OUT =>
($if ($asm NULL_P
       ($lref lst[2;0]))
  ($const #t)
  ($if ($call ($gref display)
         ($const "=> recusive1\n"))
    ($if ($call[tail-rec] ($lref bar[2;0])
           ($const 1))
      ($if ($call ($gref display)
             ($const "=> loop\n"))
        ($call[tail-rec] ($lref loop[2;0])
          ($asm CDR
            ($lref lst[2;0])))
        ($it))
      ($it))
    ($it)))

[pass2/$lambda] OUT =>
($lambda[loop;1] (lst[2;0])
  ($if ($asm NULL_P
         ($lref lst[2;0]))
    ($const #t)
    ($if ($call ($gref display)
           ($const "=> recusive1\n"))
      ($if ($call[tail-rec] ($lref bar[2;0])
             ($const 1))
        ($if ($call ($gref display)
               ($const "=> loop\n"))
          ($call[tail-rec] ($lref loop[2;0])
            ($asm CDR
              ($lref lst[2;0])))
          ($it))
        ($it))
      ($it))))

[pass2/$call] IN  =>
($call ($lref loop[2;0])
  ($const (1)))
[pass2/$local-ref] IN  =>
($lref loop[2;0])
[pass2/$local-ref] OUT =>
($lref loop[2;0])

[pass2/classify-local-ref-call] IN  =>
($lref loop[2;0])
[pass2/classify-local-ref-call] OUT =>
($lref loop[2;0])

[pass2/$call] OUT =>
($call[local] ($lref loop[2;0])
  ($const (1)))

[pass2/$let] OUT =>
($letrec ((loop[0;0] ($lambda[loop;2] (lst[2;0])
                       ($label #0
                         ($if ($asm NULL_P
                                ($lref lst[2;0]))
                           ($const #t)
                           ($if ($call ($gref display)
                                  ($const "=> recusive1\n"))
                             ($if ($call[tail-rec] ($lref bar[2;0])
                                    ($const 1))
                               ($if ($call ($gref display)
                                      ($const "=> loop\n"))
                                 ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                              label#0)
                                                ($const (1)))
                                   ($asm CDR
                                     ($lref lst[2;0])))
                                 ($it))
                               ($it))
                             ($it))))))
          )
  ($call[embed] ($lambda[loop;2] (lst[2;0])
                  label#0)
    ($const (1))))

[pass2/$if] OUT =>
($if ($asm NUMBER_EQUAL
       ($lref n[1;0])
       ($const 1))
  ($const #t)
  ($letrec ((loop[0;0] ($lambda[loop;2] (lst[2;0])
                         ($label #0
                           ($if ($asm NULL_P
                                  ($lref lst[2;0]))
                             ($const #t)
                             ($if ($call ($gref display)
                                    ($const "=> recusive1\n"))
                               ($if ($call[tail-rec] ($lref bar[2;0])
                                      ($const 1))
                                 ($if ($call ($gref display)
                                        ($const "=> loop\n"))
                                   ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                                label#0)
                                                  ($const (1)))
                                     ($asm CDR
                                       ($lref lst[2;0])))
                                   ($it))
                                 ($it))
                               ($it))))))
            )
    ($call[embed] ($lambda[loop;2] (lst[2;0])
                    label#0)
      ($const (1)))))

[pass2/$lambda] OUT =>
($lambda[bar;1] (n[1;0])
  ($if ($asm NUMBER_EQUAL
         ($lref n[1;0])
         ($const 1))
    ($const #t)
    ($call[embed] ($lambda[loop;2] (lst[2;0])
                    ($label #0
                      ($if ($asm NULL_P
                             ($lref lst[2;0]))
                        ($const #t)
                        ($if ($call ($gref display)
                               ($const "=> recusive1\n"))
                          ($if ($call[tail-rec] ($lref bar[2;0])
                                 ($const 1))
                            ($if ($call ($gref display)
                                   ($const "=> loop\n"))
                              ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                           label#0)
                                             ($const (1)))
                                ($asm CDR
                                  ($lref lst[2;0])))
                              ($it))
                            ($it))
                          ($it)))))
      ($const (1)))))

[pass2/$call] IN  =>
($call ($lref bar[2;0])
  ($const 0))
[pass2/$local-ref] IN  =>
($lref bar[2;0])
[pass2/$local-ref] OUT =>
($lref bar[2;0])

[pass2/classify-local-ref-call] IN  =>
($lref bar[2;0])
[pass2/classify-local-ref-call] OUT =>
($lref bar[2;0])

[pass2/$call] OUT =>
($call[local] ($lref bar[2;0])
  ($const 0))

[pass2/$let] OUT =>
($letrec ((bar[0;0] ($lambda[bar;2] (n[1;0])
                      ($label #0
                        ($if ($asm NUMBER_EQUAL
                               ($lref n[1;0])
                               ($const 1))
                          ($const #t)
                          ($call[embed] ($lambda[loop;2] (lst[2;0])
                                          ($label #1
                                            ($if ($asm NULL_P
                                                   ($lref lst[2;0]))
                                              ($const #t)
                                              ($if ($call ($gref display)
                                                     ($const "=> recusive1\n"))
                                                ($if ($call[jump] ($call[embed] ($lambda[bar;2] (n[1;0])
                                                                                  label#0)
                                                                    ($const 0))
                                                       ($const 1))
                                                  ($if ($call ($gref display)
                                                         ($const "=> loop\n"))
                                                    ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                                                 label#1)
                                                                   ($const (1)))
                                                      ($asm CDR
                                                        ($lref lst[2;0])))
                                                    ($it))
                                                  ($it))
                                                ($it)))))
                            ($const (1)))))))
          )
  ($call[embed] ($lambda[bar;2] (n[1;0])
                  label#0)
    ($const 0)))

[pass2/$lambda] OUT =>
($lambda[foo;0] ()
  ($call[embed] ($lambda[bar;2] (n[1;0])
                  ($label #0
                    ($if ($asm NUMBER_EQUAL
                           ($lref n[1;0])
                           ($const 1))
                      ($const #t)
                      ($call[embed] ($lambda[loop;2] (lst[2;0])
                                      ($label #1
                                        ($if ($asm NULL_P
                                               ($lref lst[2;0]))
                                          ($const #t)
                                          ($if ($call ($gref display)
                                                 ($const "=> recusive1\n"))
                                            ($if ($call[jump] ($call[embed] ($lambda[bar;2] (n[1;0])
                                                                              label#0)
                                                                ($const 0))
                                                   ($const 1))
                                              ($if ($call ($gref display)
                                                     ($const "=> loop\n"))
                                                ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                                             label#1)
                                                               ($const (1)))
                                                  ($asm CDR
                                                    ($lref lst[2;0])))
                                                ($it))
                                              ($it))
                                            ($it)))))
                        ($const (1))))))
    ($const 0)))

[pass2/$define] OUT =>
($define () foo
  ($lambda[foo;0] ()
    ($call[embed] ($lambda[bar;2] (n[1;0])
                    ($label #0
                      ($if ($asm NUMBER_EQUAL
                             ($lref n[1;0])
                             ($const 1))
                        ($const #t)
                        ($call[embed] ($lambda[loop;2] (lst[2;0])
                                        ($label #1
                                          ($if ($asm NULL_P
                                                 ($lref lst[2;0]))
                                            ($const #t)
                                            ($if ($call ($gref display)
                                                   ($const "=> recusive1\n"))
                                              ($if ($call[jump] ($call[embed] ($lambda[bar;2] (n[1;0])
                                                                                label#0)
                                                                  ($const 0))
                                                     ($const 1))
                                                ($if ($call ($gref display)
                                                       ($const "=> loop\n"))
                                                  ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0])
                                                                               label#1)
                                                                 ($const (1)))
                                                    ($asm CDR
                                                      ($lref lst[2;0])))
                                                  ($it))
                                                ($it))
                                              ($it)))))
                          ($const (1))))))
      ($const 0))))

[pass2/$call] IN  =>
($call ($gref foo))
[pass2/$call] OUT =>
($call ($gref foo))

Facts

Disabling pass2/optimize-closure makes the script work.
Where in pass2/optimize-closure?
- Disabling pass2/local-call-embedder make the script work.
- How is it triggered?
- Disabling pass2/local-call-inliner doesn't change the output.
- Disabling pass2/local-call-optimizer doesn't change the output

higepon commented 2 years ago

Hmm. The pass2 results above look correct to me. Maybe we are making mistake in pass3/call where we subtract stack size where the jump call is crossing lambda boundry?

higepon commented 2 years ago

This is VM instructions for the optimized code.

  CLOSURE
  81
  0
  #f
  0
  11
  ((reproduce.scm 1) foo)
  LET_FRAME
  7
  CONSTANT_PUSH
  0
  ENTER  ;; Label #0
  1
  REFER_LOCAL_PUSH_CONSTANT
  0
  1
  BRANCH_NOT_NUMBER_EQUAL ;; if (= n 1)
  5
  CONSTANT
  #t
  LOCAL_JMP ;; goto label #1
  57
  LET_FRAME 5
  REFER_LOCAL_PUSH
  0
  DISPLAY
  1
  CONSTANT_PUSH
  (1)
  ENTER
  1
  REFER_LOCAL_BRANCH_NOT_NULL
  0
  5
  CONSTANT
  #t
  LOCAL_JMP
  38
  FRAME
  6
  CONSTANT_PUSH
  => recusive1
  REFER_GLOBAL_CALL
  display  ;; (display "=> recusive1\n")
  1        ;; # of args
  TEST     ;; (display ...) return value is true. So we skip the +1 next line and go to +2 line.
  29
  CONSTANT_PUSH ;; Come here after (display ...) call
  1
  SHIFTJ ;; adjust SP and FP
  1      ;; depth
  4      ;; diff
  0      ;; How many closure to go up?
  LOCAL_JMP ;; Jump to label #0
  -42
  TEST
  19
  FRAME
  6
  CONSTANT_PUSH
  => loop
  REFER_GLOBAL_CALL
  display
  1
  TEST
  10
  REFER_LOCAL
  0
  CDR_PUSH
  SHIFTJ
  1
  1
  0
  LOCAL_JMP
  -43
  LEAVE
  1
  LEAVE ;; label #2
  1     ;; adjust stack
  RETURN ;; return to the code (the code is taken from the top of stack). ** But we don't have the code in the stack?***
  0
  DEFINE_GLOBAL
  foo
  HALT NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP)

higepon commented 2 years ago

With this PR https://github.com/higepon/mosh/pull/219 I confirmed this benchmark runs if we disable the optimizer.

higepon commented 2 years ago

pass2 input

(define foo
  (lambda ()
    (letrec* ((bar (lambda (n)
                     (cond ((= n 1) #t)
                           (else (letrec ((loop (lambda (lst)
                                                  (if (null? lst)
                                                      #t
                                                    (and (display "=> recusive1\n")
                                                         (bar 1)
                                                         (display "=> loop\n")
                                                         (loop (cdr lst)))))))
                                   (loop '(1))))))))
             (bar 0))))
(foo)

pass2 output looks right to me.

($define () foo ;; pass3/$define depth=0.
  ($lambda[foo;0] () ;; pass3/$define lambda.body depth=depth + num_args(=0) + frame_size(=4) = 4
    (s[embed 0 0] ($lambda[bar;2] (n[1;0]) ;; call-depth is set! as 4

                        ($label #0 ;; depth for label.body = depth (4) + num_args(1) + let_frame_size(=2)=7
                          ($if ($asm NUMBER_EQUAL ;; pass3/$if depth=7
                                 ($lref n[1;0])
                                 ($const 1))
                            ($const #t)
                            ($call[embed 0 0] ($lambda[loop;2] (lst[2;0]) ;; call depth is set as 7
                                                ($label #1 ;; in lambda body depth=depth+num_args(=1) + let_frame_size(=2) = 10
                                                  ($if ($asm NULL_P
                                                         ($lref lst[2;0]))
                                                    ($const #t)
                                                    ($if ($call ($gref display)
                                                           ($const "=> recusive1\n"))
                                                      ($if ($call[jump 0 0] ($call[embed 0 0] ($lambda[bar;2] (n[1;0]) ;; SHIFTJ depth(10) - $call.depth(4) - - let_frame_size(2) = 4
                                                                                                label#0)
                                                                              ($const 0))
                                                             ($const 1))
                                                        ($if ($call ($gref display)
                                                               ($const "=> loop\n"))
                                                          ($call[jump 0 0] ($call[embed 0 0] ($lambda[loop;2] (lst[2;0]) ;; SHIFTJ 10- $call.depth(7) - 2   = 1
                                                                                               label#1)
                                                                             ($const (1)))
                                                            ($asm CDR
                                                              ($lref lst[2;0])))
                                                          ($it))
                                                        ($it))
                                                      ($it)))))
                              ($const (1))))))
      ($const 0))))

pass3 final iform

($define () foo
  ($lambda[foo;0] ()
    ($call[embed 4 0] ($lambda[bar;2] (n[1;0])
                        ($label #0
                          ($if ($asm NUMBER_EQUAL
                                 ($lref n[1;0])
                                 ($const 1))
                            ($const #t)
                            ($call[embed 7 0] ($lambda[loop;2] (lst[2;0])
                                                ($label #1
                                                  ($if ($asm NULL_P
                                                         ($lref lst[2;0]))
                                                    ($const #t)
                                                    ($if ($call ($gref display)
                                                           ($const "=> recusive1\n"))
                                                      ($if ($call[jump 0 0] ($call[embed 4 0] ($lambda[bar;2] (n[1;0])
                                                                                                label#0)
                                                                              ($const 0))
                                                             ($const 1))
                                                        ($if ($call ($gref display)
                                                               ($const "=> loop\n"))
                                                          ($call[jump 0 0] ($call[embed 7 0] ($lambda[loop;2] (lst[2;0])
                                                                                               label#1)
                                                                             ($const (1)))
                                                            ($asm CDR
                                                              ($lref lst[2;0])))
                                                          ($it))
                                                        ($it))
                                                      ($it)))))
                              ($const (1))))))
      ($const 0))))

VM instructions debug

========================
FRAME
  FP|0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
========================
REFER_GLOBAL
  FP|0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
========================
CALL
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
========================
LET_FRAME                   # LET_FRAME for lambda[foo]
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
  FP|4: 4                   # Save fp
    |5: "#(#(CLOSURE ...))" # Closure
========================
CONSTANT
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
  FP|4: 4
    |5: "#(#(CLOSURE ...))"
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
  FP|4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0                  # Constant 0
========================
ENTER                      # Adjust fp
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
========================
REFER_LOCAL               # a=(Constant 0)
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0                  # Constant 0
    |7: 0                  # Constant 0
========================
CONSTANT                   # a=(Constant 1)
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 0
========================
BRANCH_NOT_NUMBER_EQUAL   # a != stack-bottom(Constant 0)
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0                  # Discarded stack top.
========================
LET_FRAME                  # LET_FRAME for loop.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6                   # Save fp
    |8: "#(#(CLOSURE ...))" # Push closure
========================
REFER_LOCAL                 # a=(Constant 0) REALLY???
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 0                  # push (Constant 0)
========================
DISPLAY                    # Create a display and set it to closure.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"# Note stack is popped.
========================
CONSTANT                   # a=(1)
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1                  # (1)
========================
ENTER
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1                 # New FP.
========================
REFER_LOCAL               # a=(1)
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
========================
BRANCH_NOT_NULL          # Go to else.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
========================
FRAME                     # Push stuff.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
    |10: "(#(#f ...)"      # closure
    |11: 9                 # fp
    |12: 54                # pc + n
    |13: "(#(CLOSURE ...)" # Current codes
========================
CONSTANT                   # a="=> recursive1"
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
    |14: "=> recusive1\n"
========================
REFER_GLOBAL               # a=<display>
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
    |14: "=> recusive1\n"
========================
CALL                       # call a=<display>. Note codes is now body of display.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()               # display has optional-arg '()
========================
REFER_LOCAL               # a="=> recursive1\n"
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()
========================
BRANCH_NOT_NULL           # a is not null so we go to Else. But this is really weird.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()
========================
REFER_LOCAL                # a="=> recursive1"
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()
    |16: "=> recusive1\n"
========================
REFER_FREE 0               # Point codes + 6
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
    |15: ()
    |16: "=> recusive1\n"
========================
TAIL_CALL                  # call <display> and jump to #(RETURN 1 ...)
=> recusive1
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
    |9: 1
    |10: "(#(#f ...)"
    |11: 9
    |12: 54
    |13: "(#(CLOSURE ...)"
  FP|14: "=> recusive1\n"
========================
RETURN
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1                   # this is ()
========================
TEST                        # Return value of display is #t
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
========================
CONSTANT
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
    |6: 0
    |7: 6
    |8: "#(#(CLOSURE ...))"
  FP|9: 1                    # (1)
    |10: 1                   # 1
========================
SHIFTJ 1 4 0                 # Adjust frame for jump. Stack is now for bar call.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
LOCAL_JMP
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
REFER_LOCAL                # a=1
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
PUSH
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
    |7: 1
========================
CONSTANT
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
    |7: 1
========================
BRANCH_NOT_NUMBER_EQUAL    # Now 1=1. Jump to else.
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
CONSTANT #t
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
LOCAL_JMP 66
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
    |4: 4
    |5: "#(#(CLOSURE ...))"
  FP|6: 1
========================
LEAVE
    |0: "#(#(FRAME ...))"
    |1: 0
    |2: 6
    |3: "(#(FRAME ...)"
========================
RETURN
========================
HALT

Steps

[x] Debug print depth parameter for each $call (Final state).
[x] Manually calculate depth by hand and compare with above.
[x] If they match.
- [ ]Go to ShiftJ part.
[x] Otherwise
- [ ]Investigate why they don't match
[ ] Understand SHIFTJ
Understand depth step by step

pass3 output

See this spreadsheet

Understand SHIFJ

higepon commented 2 years ago

IIUC LOCAL_JMP 66 has wrong jump destination. I have to figure out why.

Steps

Identify where LOCAL_JMP instruction is emitted.
Identify which part of pass2 output is causing it.

higepon commented 2 years ago

In

PUSH CONSTANT 1 BRANCH_NOT_NUMBER_EQUAL #(15 #f #f)
CONSTANT #t
UNFIXED_JUMP #(15 #f #f)
LET_FRAME

What is #(15 #f #f)? => ($LABEl body visited?)

Labels are fixed up as follows.

CLOSURE 93 0 #f 0 11 (("reproduce.scm" 1) foo) LET_FRAME 7 CONSTANT 0 PUSH ENTER 1 REFER_LOCAL 0 PUSH CONSTANT 1 BRANCH_NOT_NUMBER_EQUAL 5 CONSTANT #117 
LOCAL_JMP 66 
** this jump**
LET_FRAME 5 REFER_LOCAL 0 PUSH DISPLAY 1 CONSTANT (1) PUSH ENTER 1 REFER_LOCAL 0 BRANCH_NOT_NULL 5 CONSTANT #t LOCAL_JMP 44 FRAME 8 CONSTANT "=> recusive1\n" PUSH REFER_GLOBAL display CALL 1 TEST 33 CONSTANT 1 PUSH SHIFTJ 1 4 0 LOCAL_JMP -50 TEST 22 FRAME 8 CONSTANT "=> loop\n" PUSH REFER_GLOBAL display CALL 1 TEST 11 REFER_LOCAL 0 CDR PUSH SHIFTJ 1 1 0 LOCAL_JMP -50
**Jump desitnation** LEAVE 1 LEAVE 1 RETURN 0 DEFINE_GLOBAL foo HALT NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP

I think pass4/fixup is doing it right. But is jump destination in pass3 correct? => Jump destination is end of if clause. So looks correct.

higepon commented 2 years ago

#(CLOSURE label_1 0 #f 0 11 ((reproduce.scm 1) foo)
LET_FRAME 7 <== embeded call of bar
CONSTANT 0 PUSH ENTER 1 label_14 REFER_LOCAL 0 PUSH CONSTANT 1 BRANCH_NOT_NUMBER_EQUAL label_21 CONSTANT #t 
UNFIXED_JUMP jump_to_label_100 label_26
LET_FRAME 5 <== embeded call of loop
REFER_LOCAL 0 PUSH DISPLAY 1 CONSTANT (1) PUSH ENTER 1 label_39
REFER_LOCAL 0 BRANCH_NOT_NULL label_43 CONSTANT #t
UNFIXED_JUMP jump_to_label_97 label_48 FRAME label_50 CONSTANT => recusive1
PUSH REFER_GLOBAL display CALL 1 label_58 TEST label_60 CONSTANT 1 PUSH
SHIFTJ 1 4 0 UNFIXED_JUMP jump_to_label_14 TEST label_71
FRAME label_73 CONSTANT => loop
PUSH REFER_GLOBAL display CALL 1 label_81 TEST label_83 REFER_LOCAL 0 CDR PUSH
SHIFTJ 1 1 0 UNFIXED_JUMP jump_to_label_39 label_94 label_95 label_96 label_97
LEAVE 1 label_100
LEAVE 1 <== end of embeded call of bar
RETURN 0 label_105 <== This is end of closure foo
DEFINE_GLOBAL foo HALT)

TODO

Where the LEAVE 1 and RETURN 0 issued?
- LEAVE is issued for embedded call, let, letrec and receive and always paird with LET_FRAME
- (bar 1) is jumping to LEAVE1(end of embeded call of bar). I think this is correct.
How about RETURN?
- $lambda has CLOSURE ... snip ... RETURN N LABEL(end of closure)
- This is RETURN for foo.
Where it should have jumped to?
Hmm. Well this should have been treated as normal call? This is not tail-call.
- Check call-type

higepon commented 2 years ago

I guess this tail-rec is wrong.

                             ($lref lst[2;0]))
                        ($const #t)
                        ($if ($call ($gref display)
                               ($const "=> recusive1\n"))
                          ($if ($call[tail-rec] ($lref bar[2;0])
                                 ($const 1))

The bar call is not tail-rec. How did it happen.

higepon commented 2 years ago

I was right. We had miss classified test clause of if as tail-call. https://github.com/higepon/mosh/pull/224

higepon / mosh