Cranelift: implement path-sensitive constant propagation

In a discussion of egraph-framework extensions today, the idea of path-sensitive constant propagation, or propagating a constant-value fact through the dom-subtree below a branch that tests that value, came up. I wanted to record the idea, some issues it will run into, and some subsequent ideas I had for how to solve them.

In brief, the idea is that if we have a value `x`, it may not have a constant value overall, but past a branch `v0 := icmp_imm eq x, 0; brif v0, ...` we know that `x == 0` on the taken branch (precisely, the target block and any blocks it dominates). We can thus do a form of cprop that is specific to that region of code. (There are some Spectre-safety implications here that we need to consider, but I'll gloss over for now.)

This is different than "classical" cprop because we don't have a constant fact about `x`; thus, we can't simply union it with `iconst 0` in an eclass in the aegraph framework. Rather we need some notion of "true in this region".

The formulation of constant propagation in the aegraph framework provides both a nice property to help with this, and a significant problem:

- Benefit: the immutable data structure representation of eclasses, with union nodes, means that we can have a handle to the "original" eclass that is true for `x` everywhere, and derived from that (unioned with it), another handle that represents the eclass just within the dominated-by-`x==0` region. So there's no need to "unwind" union operations when we leave the region, or anything like that.

- Significant problem: it is incompatible with the eager-rewrite strategy that we have, and requires revisiting nodes to rewrite again.

To see why the latter, consider this example:

```
block1:
v1 = ...
v2 = ...
v3 = ishl v1, v2
v4 = icmp_imm eq v2, 0
brif v4, block2, block3

block2:
return v3 ;; *should* rewrite to v1: we know only in this branch that `v2 == 0`, so `v1 << 0 == v1`

block3:
... ; left-shift-by-nonzero case; no further rewrites here
```

We process `v3`, and do all rewrites we can; this doesn't include the key simplification for left-shift-by-zero, because the shift amount *isn't* constant-zero at this program point. We have a final eclass for `v3`. Then, at some later time, we process the branch, we enter the subtree at block2, and here we have an additional assumption `v2 == 0`. What do we do?

We can union `v2` with `iconst 0`; but then there may be an arbitrary number of other expression nodes built on top of `v2` that we also should rebuild, propagating the implications of that assumption through. Furthermore we might even have later branches with *other* values (say `v2 == 1`); generally, we may have an arbitrary number of "sub-contexts" in which we do rewrites on the same expression nodes over again. And we have to process these later -- visiting and re-visiting the nodes over and over again -- because the branch assumptions that cause further implications may come only deep in the domtree, after we've already eagerly processed all of these expression nodes at their original appearance.

To say it another way: dominance, use-before-def processing order, and acyclicity do *not* save us here, because the branches are inputs to the rewrite reasoning but come much later than the things they affect. (Someone mentioned during this discussion that it had to do with pure enodes not having a notion of dominance or location, but this would be true even if they did.)

---

What to do? I don't think adding back parent pointers to the aegraph is the right solution here: that implies mutating the original knowledge base, then we have to unwind it when we leave the subregion.

I also briefly considered making all nodes in a given subtree dependent on the closest dominating branch (or just an identifier for the domtree node), but I suspect this would cause significantly more harm in compile-time blowup: it would mean we can no longer amortize the storage and work of optimizations on pure nodes in the common case when branch conditions don't affect them.

One solution may be to add a notion of context to the original value -> eclass mapping (so we have a mapping from "original value in this context" tuples to eclass handles). Then probably we shouldn't eagerly compute rewrites in all possible contexts; rather we should lazily query and memoize.

In the above example imagine we have some context `c0` at the root, and `c1` at the dom-subtree at block2. Then when we use `v2` at the `return` we can query the hashmap for `(c1, v2)`; if not present, re-process in that context. We can short-circuit most cases: a value is different in a context and requires a reprocessing if the context updates its mapping directly (e.g. `c2` updates `v1` to the eclass union'd with `0`) or if any of its args require reprocessing. Otherwise, pass through from parent context. Perhaps there's also a way to filter processing down to only values that feed into any control dependency and their downstream dataflow (compute with prepass).

That's a pretty handwavy pointer to a possible solution but I at least wanted to record the major issue/question to ensure there is no confusion! (cc @jameysharp, @fitzgen, @elliottt, @avanhatt, @mwillsey)