Revertir números mágicos matemáticamente

[aguml]

Buenas, he visto que los compiladores pueden optimizar las divisiones con constantes, por ejemplo, si divides entre 9 al optimizar se vería algo así:

Código PHP:

mov eax, 38e38e38
mul esi
mov eax,edx
shr eax,1 


La cosa es invertir eso y que cuando vea ese código pueda obtener el divisor.
He encontrado informacion en inglés y con un nivel de matemáticas que no comprendo y que el inglés no me ayuda porque no sé mucho.
Hasta ahora hago algo como:
(2^(32+s))/M=D
D es divisor
s es el valor de desplazamiento lógico
M es el número mágico .
Esto funciona pero no para todos, por ejemplo con el 62, 63, 70...
Dónde esa formula no sirve y el compilador no hace lo mismo y hace algo así por ejemplo para el 63:

Código PHP:

mov eax,41041041
mul esi
sub esi,edx
shr esi,1
add esi, edx
shr esi,5 


Como ven enreda bastante más y no sé a que fórmula equivale ni como decidir cuándo debo usar una u otra.
¿Alguien que entienda y pueda ayudarme?

[mamcx]

Esto tiene 2 niveles: Como hace un compilador para optimizar el codigo, y como se optimiza una formula matematica.

Con las matematicas soy un asco, asi que la segunda parte la dejo para otro, pero la primera si se.

Empezemos con la forma mas "simple" de hacer esto: Compila a Pascal/C/Rust/webAssembly y deja que su compilador se encarge del asunto.

Un compilador/interprete se construye como una secuencia de "passes/pasos". La mas simple es "lexing -> AST formation -> code/assembler generation". Pero entre cada pasos(pass) puedes meter otros pasos. Entre ellos se introducen los pasos de optimizacion, los mas comunes:

https://www.geeksforgeeks.org/code-o...mpiler-design/

Estos "pasos" son simplemente REESCRITURAS AL AST, osea, transformar un arbol a otro.

Hay 2 pasos en especial que son utiles: Constant folding y Compile Time Evaluation (y desugaring, que no es un paso concreto, mas bien una tecnica general).

Te pongo un ejemplo concreto usando Rust que es donde mas he trabajado esto.

Nuestro lenguaje: Sabe sumar y usar variables predefinidas

Puedes ejecutarlo sin instalar Rust aqui (con codigo completo):

https://play.rust-lang.org/?version=...1586db6affd7fa

Código PHP:

#[derive(Debug, Clone)]
enum Expr {
    Var(String),                              //acceso a una variable
    Number(i64),                           //numero constante
    Add(Box<Expr>, Box<Expr>),  //suma
} 


* La parte de como definir las variables se usa con un "environment store" osea, un hashtable. El compilador/interpreter va acumulando las variables en el store.

Ahora el lio:

Código PHP:

//El interprete. Para convertilo en compiler, generar codigo en vez de ejecturlo
fn eval(store: &HashMap<String, Expr>, ast: Expr) -> Expr {
    dbg!(&ast);
    match ast {
        Expr::Var(x) => store[&x].clone(),
        Expr::Number(num) => Expr::Number(num),
        Expr::Add(a, b) => {
            let x = to_num(store, *a).expect("No es un numero");
            let y = to_num(store, *b).expect("No es un numero");
            println!("Suma {} + {}", x, y);
            Expr::Number(x + y)
        }
    }
}

fn main() {
    let mut variables = HashMap::new();
    variables.insert("a".to_string(), Expr::Number(1));
    variables.insert("b".to_string(), Expr::Number(2));

    //a + b
    let ast = Expr::Add(
        Box::new(Expr::Var("a".into())),
        Box::new(Expr::Var("b".into())),
    );

    println!("Sin optimizar....");
    println!("a + b = {:?}", eval(&variables, ast.clone()));
} 


Nuestro lenguaje al usar vbles requiere el uso de memoria en el heap (eso son los Box<...>) dereferenciar pointers y cada vez que salga la variable, interpretarla, que para algo tan idiota como "a=1, b=2; a+b" es mucha vuelta.

Al ejecutar, veras la traza de operacion de como se toca todos los nodos del AST y se evalua en runtime a + b.

Asi que hacemos:

Constant folding

Buscar que vbles son realmente constantes +

Compile time evaluation

Ejecutar al compilar el AST +

Desugaring

Transformar una operacion en otra, en este caso: convertir un paso a + b -> 1 + 2 -> 3, osea desugaring es el termino generico de todo esto.

Esto en este caso es tan simple como:

Código PHP:

fn constant_folding(store: &HashMap<String, Expr>, ast: Expr) -> Expr {
    dbg!(&ast);
    if let Expr::Add(a, b) = ast {
        println!("Folded!"); //<--Si sale esto se optimizo!
        let x = to_num(store, *a).expect("No es un numero");
        let y = to_num(store, *b).expect("No es un numero");

        Expr::Number(x + y)
    } else {
        ast //paila ir por el camino largo
    }
}

fn main() {
    let mut variables = HashMap::new();

    println!("Sin optimizar....");
    println!("a + b = {:?}", eval(&variables, ast.clone()));

    println!("Haciendo constant folding");
    let ast = constant_folding(&variables, ast);
    println!("{:?} = {:?}", &ast, eval(&variables, ast.clone()));
} 


Al ejecutar, veraz que en "println!("{:?} = {:?}", &ast, eval(&variables, ast.clone()));" ast se ha transformado en 3.