Strength reduction in an Analysis pass?

[mmp]

I'm trying to write an Analysis pass that both does constant folding and also does things like rewrite (/ x 2) to (* x 0.5); I haven't been able to figure out the right way to do that (or, if that is something I should be trying to do in an Analysis pass in the first place).

The approach I had tried was to define Data as Option<MyLanguage> in my analysis pass. That works fine for constant folding; I can just return Some(MyLanguage::Constant(xyz)). For strength reduction I had tried the following (in a match statement):

    MyLanguage::Div([a, b]) if is_pow2(x(b).ok()?) => {
          let inv = Constant::new(1.).ok()? / x(b).ok()?;
          let inv_node = egraph.add(MyLanguage::Constant(inv));
         Some(MyLanguage::Mul([*a, inv_node]))
    },

However, that doesn't work since the EGraph passed to Analysis.make() is not mutable, so the egraph.add() call is invalid. (And I can't see another way to properly make a node for an operation in my language otherwise.)

I was thinking that I could just make Data be an Option<String> or something like that and then parse those strings into proper nodes in my modify() method, but that seemed a little hacky (and also seems like it might prevent optimizations that depend on e.g. first constant folding and then strength reduction, e.g. for (/ x (+ 1 1)), though I'm not sure if that's the case...)

Any guidance would be much appreciated!

[mmp]

Upon further pondering, I've realized that I can handle this via a rewrite rule along the lines of:

        rw!("div-pow2"; "(/ ?x ?y)" => "(* ?x (/ 1 ?y))" if is_pow2("?y")),

and then let constant folding take care of it from there.

However, I'm still curious whether this could have been done via an analysis pass (and in general, how to think about the difference between what to do via Analysis and what to do via rewrite rules...)

[remysucre]

Combining a rewrite rule and constant folding is exactly the right way to handle this. In general I think of Analysis as a type system. When type-checking a program you usually have a fixed program, unless you have dependent types. So currently egg only supports non-dependent analyses, where the Analysis assumes the egraph is fixed and cannot modify it.