Optimize unnecessary `JUMP-FALSE` instructions

[jpellegrini]

1) Optimize [IM-something; JUMP-FALSE] => []

For the case (if #t ...), or (if CONSTANT ...), which could perhaps be generated by a macro.

For example:

stklos> (disassemble-expr '(if 0 1 -1))

000:  IM-ONE
001:  GOTO                 1    ;; ==> 004
003:  IM-MINUS1

No conditional in the final code!

2) Optimize [IM-FALSE; JUMP-FALSE] => GOTO

For the case (when #f ...) or (if #f ...), which could perhaps be generated by macros.

[jpellegrini]

As you can see in the code, I also tried to optimize JUMP-TRUE, but for some reason it doesn't work...

[jpellegrini]

Ah, The peephole optimizer does change

000:  IM-TRUE             
001:  IN-NOT              
002:  JUMP-FALSE           3    ;; ==> 007

into

000:  IM-TRUE             
001:  JUMP-TRUE            3    ;; ==> 006

but then it's too late to change the JUMP-TRUE, because it's not looking at the IM-TRUE before it anymore...

[egallesio]

Hi @jpellegrini,

I think that we need to work on the source tree rather than on the generated code in this case. This permits to eliminate the production of dead code.

In the last commits, I have added a general purpose code rewrite tool. It is called on each expression before compilation and try to rewrite the expression in a more efficient form (function rewrite-expression). For instance, we can transform:

    (if (not #t)
     (begin 1 (print 2) 3 4)
     (begin 5 (print 6) 'useless 7 8))

in

    (begin (print 6) 8)

For now, we have only some simple rewriting rules that are available. Rules are easily plugged to the compiler (so that we cans imagine that it could be possible to add rewriting rules with the loading of a library).

For instance, the rule for eliminating dead code in an if is added to the compiler with:

(compiler:add-rewriter!            ;; 'IF' rewriter
 'if
 (lambda (expr len env)
   (if (<= 3 len 4)
       (let ((Cond (rewrite-expression (cadr expr) env))
             (Then (caddr expr))
             (Else (if (null? (cdddr expr))
                       #void
                       (cadddr expr))))
         (if (const-expr? Cond)
             (if (const-value Cond)
                 (rewrite-expression Then env)
                 (rewrite-expression Else env))
             expr))
       expr)))

I think that all the work you have done on constant folding could have been done here. As I said before, we can imagine that, we can add some rewriting rules when loading a library (after having exported a minimal set of functions). This could be useful to implement your idea, without modifying the compiler.

Code rewriting this way incurs a little compile-time penalty, but I think it could (potentially) be useful. I said potentially, because, after having added traces to the rewriting rules, I have not seen a lot of rewrites when bootstrapping STklos (mainly some expressions such as (define undefined (if #f #f)) in srfis code). On the other way, we have a lot of rewrites in the tests, since we have a lot a stupid tests which are rewritten at compile time, whereas they were tested at runtime before.

Consequently, I permit myself to close this PR.

[jpellegrini]

Hi @egallesio !

I have added a general purpose code rewrite tool

That's great news! :)

(And, by the way, it compiles and works fine on Android!)

I think that all the work you have done on constant folding could have been done here. As I said before, we can imagine that, we can add some rewriting rules when loading a library (after having exported a minimal set of functions). This could be useful to implement your idea, without modifying the compiler.

Yes, I agree! I did think of that when I implemented constant folding, but it seemed like what I did was more close to the way the compiler already works. But yes, maybe someday we could rewrite the constant folding code to simplify the compiler!