[New Optimization Proposal] Propagate conditional result to branch / switch arms

[MaxGraey]

Example:

if (x == 5) {
   return x + 1;
} else {
   return x - 1;
}

if (y == true) { // maxBits(y) <= 1
   return y | x; // maxBits(x) <= 1
} else {
   return y ^ x;
}

if (z < 5) {
   return z >= 5;
}

could be optimize to:

if (x == 5) {
   return 6; // 5 + 1
} else {
   return x - 1;
}

if (y == true) {
   return true; // we know y == true, so true | bool(x)  ->  true
} else {
   return x; // here y always `false` so `false ^ x` -> x
}

if (z < 5) {
   return false;
}

and same for br tables.

WDYT?

[kripken]

This definitely makes sense to do. But it would be a large addition that we'd need to design carefully. Looking at how LLVM does it could be interesting.

[MaxGraey]

It seems this handling by Interprocedural Sparse Conditional Constant Propagation (-ipsccp pass): https://godbolt.org/z/z6nev7Pdd

The main problem is SSA form requirement. See original paper: https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf But I admit that it is possible to design an algorithm without SSA only in this case the time complexity will be O(E × V²) or O(E² × V) instead O(E × V) in best case.

Also GVN pass could optimize this as well: https://godbolt.org/z/qvd8n1e1z

[MaxGraey]

@kripken As I understand with new GUFA pass can potentially handle this? Just need to teach this pass visit switches (bt_table) and if / br_if ?

[kripken]

Hmm, no, GUFA doesn't help in this type of situation. GUFA does constant propagation and handles GC types, and it does that across the entire program at once, but it doesn't infer values based on control flow like this.

Thinking on this, at least the case of == could be handled like this:

if (x == 5) {
   return x + 1;
}
// => add new code to "assert" the value
if (x == 5) {
   x = 5; // new code inserted here (maybe not literally)
   return x + 1;
}
// => precompute-propagate runs normally
if (x == 5) {
   x = 5;
   return 5 + 1; // 5 propagated to here
}

So == might be easy. But != (like in the else) and >= would take nontrivial work I think. Maybe a mini SAT solver but focused on simple math would be nice here, but that's no small amount of work.

[MaxGraey]

Well, I guess constant propagation for == will be enough for most of the cases for (if, br_if, select and br_table)