Gustavo

Introducción

Buscando un ejemplo

#lang racket

(define (-check-non-negative-integer who i false-ok?)
  (when (or i (not false-ok?))
    (unless (and (integer? i) (exact? i) (not (negative? i)))
      (raise-argument-error [...]))))

(define (check-non-negative-integer who i)
  (-check-non-negative-integer who i #f))

(define (check-non-negative-integer/false who i)
  (-check-non-negative-integer who i #t))

#lang racket
  
{define (check my-false)
  (if (if (random 1) #t my-false) 2 3)}

(check #f)

#lang racket

{define check
  (#%closed check
    {lambda (my-false)
      (if (if (random 1) #t my-false) 2 3)})}

(print-values (if (random 1) (if #t 2 3) 3))

El origen del problema

(if #t X Y)  -->  X
(if #f X Y)  -->  Y
(if (not P) X Y)  -->  (if P Y X)

Viejas y nuevas optimizaciones

a: [boolean] (if M #t #f)  -->  M
b: [boolean] (if v v X)  -->  (if v #t X)
c: [new] (if v X v)  -->  (if v X #f)

d: (if (not P) X Y)  -->  (if P Y X)
d: (if #t X Y)  -->  X
e: (if #f X Y)  -->  Y

f: (if v v #f)  -->  v
g: (if <omitable> v v)  -->  v

h: (if (if M N #f) P K) => (if M (if N P K) K)
i: [new] (if M (if (not Q) P K) K) => (if M (if Q K P) K)
j: [new] (if M (if #t P K) K) => (if M P K)
k: [new] (if M (if #f P K) K) => (if M K K)

  /* Convert (if <id> expr <id>) to (if <id> expr #f) */
  if (SAME_TYPE(SCHEME_TYPE(t), scheme_local_type)
      && SAME_TYPE(SCHEME_TYPE(fb), scheme_local_type)
      && (SCHEME_LOCAL_POS(t) == SCHEME_LOCAL_POS(fb))) {
    b->fbranch = fb = scheme_false;
  }
  
  if (context & OPT_CONTEXT_BOOLEAN) {
    /* Convert (if <id> <id> expr) to (if <id> #t expr) */
    if (SAME_TYPE(SCHEME_TYPE(t), scheme_local_type)
        && SAME_TYPE(SCHEME_TYPE(tb), scheme_local_type)
        && (SCHEME_LOCAL_POS(t) == SCHEME_LOCAL_POS(tb))) {
      b->tbranch = tb = scheme_true;
    }

    /* For test position, convert (if <expr> #t #f) to <expr> */
    if (SAME_OBJ(tb, scheme_true) && SAME_OBJ(fb, scheme_false))
      return scheme_optimize_expr(t, info, context);
  }

Versiones para compilar y testear

Resultados de a-b-c

• con sólo "a"
• con "a-b", este es código sin modificaciones que usa Racket
• con "b-a", en el orden inverso
• con "c-b-a", en el orden inverso y agregando "c" 

• La optimización "b" transforma unos 170 apariciones de (if v v ?) en (if v #t ?).
• Análogamente, la optimización "c" transforma unos 260 apariciones de (if v ? v) en (if v ? #f).
• Yo esperaba que al intercambiar las optimizaciones "a" y "b" se pudieran componer, de manera que se transforme (if v v #f) en (if v #t #f) en v, pero no aparecen muchos de estos casos.
• (Si eliminamos la optimización "a", aparecen como 5000 "nuevos" (if ? #t #f), muy mala idea.)

Resultados de h-i-j-k

• sin "h"
• con "h", este es el código sin modificaciones que usa Racket
• con "h-i-j-k", o sea optimizando el resultado de "h"

• Con respecto a los (if #t ? ?) y (if #f ? ?), al comparar las distintas versiones, vemos que la optimización "h" que teníamos como candidato a culpable es la culpable. Los if con #t y #f No aparecen cuándo no está "h" y optimizando el resultado de "h" vuelven a desaparecer.
• Sin embargo hay varios (if (not ?) ? ?) en todas las versiones. Es más, al optimizar el resultado de "h" no desaparecen todas las nuevas apariciones. Me gustaría investigar su origen y ver cómo se los puede eliminar, porque aparecen mas de 1500 veces.

Ideas y comentarios

• Lo más razonable hubiera sido utilizar la función interna del optimizador scheme_optimize_expr o optimize_branch para optimizar el segundo if del resultado de aplicar "h". Sería más elegante porque no haría falta repetir el código y además con este método se aplicarían todas las otras optimizaciones, aunque sería un poquito más lento. El problema es que para llamar a estas funciones hay que utilizar estructura Optimize_Info que contiene información sobre el estado del programa que se está optimizando. Aunque intente varias veces no pude armarla correctamente.
• Hay muchos (if ? #f #t), quizás se los pueda reemplazar por (not ?). Hice algunas microbenchmarks para medir la diferencia de velocidad, y no vi casi ninguna diferencia. Sin embargo el cambio quizás ayude a que se puedan realizar otras optimizaciones. Algo similar con (if ? #t #f) aunque no se cuál sería el nombre de la función asociada.
• Hay 31 apariciones de (if (if ? #<void> ?) ? ?) y 11 apariciones de (if (if ? '() #f) ? ?). Se podrían tratar de optimizarlos, pero lo más probable es que no valga la pena porque son muy pocos.
• Al recompilar, la cantidad de veces que aparece cada cosa cambia un poco. Muy extraño. No afecta mucho los resultados, pero hay que ser cuidadoso al comparar valores muy cercanos.
• Hay exactamente un (if (if ? 1 0) ? ?). No busqué el código que lo produce, pero a simple vista parece un (if (bool->binary ?) ? ?), suponiendo que existiera bool->binary. ¿Será un error o simplemente una coincidencia extraña producida por todas las expansiones intermedias?