Halide's CSE does not catch this case (but does it need to?)

[silvasean]

Here is a reduced test case where Halide's CSE does not fold two expressions that are identical:
silvasean@704babe
(in my cse_failure branch: https://github.com/silvasean/Halide/tree/cse_failure)

      f.0[0] = 0
      f.1[0] = 10
      let f.0.value = select((f.1[0] < f.0[0]), 762, 199)
      let f.1.value = select((f.1[0] < f.0[0]), 3, 780)
      f.0[0] = f.0.value
      f.1[0] = f.1.value

(there's also more we could do here w.r.t. constant folding, but let's focus on the CSE issue)

Of course, LLVM will simplify this away just fine (to a constant 199 for f.0; and it will find the f.1 result is dead). Feel free to close if the resolution is that we just want to let LLVM handle this. I'd love to hear if there is a high-level guiding principle w.r.t. what mid-level kinds of optimizations Halide decides to implement vs defer to LLVM; or perhaps the current state is just a historical artifact as motivating cases have pushed Halide to implement specific things.

On the one hand, doing redundant optimization work that LLVM will do later just adds maintenance burden to Halide. On the other hand, if these kinds of mid-level optimizations frequently expose high-level optimization opportunities (such as folding an expression down to a constant, as is possible in the case above), it may be worthwhile.

[abadams]

Our CSE sticks to mutating individual statements. Lifting expressions out across different statements means you have to do alias analysis - moving loads around might change their value if they cross over an intervening store.

A related optimization we don't do is lifting complex expressions that don't depend on loop variables from inside loops. Again, you need to worry about expressions that might change their value if you move them.

So for these sorts of things we defer to LLVM, because it's really good at this sort of reasoning.

One pass for which we do do the alias analysis is carrying loop values from one loop iteration to the next in a register. This is the LoopCarry pass, and it's only turned on for Hexagon. We do it because it lets us generate aligned loads and vector slice instructions cleverly. So it exposes the kind of higher level optimization opportunity that you're talking about.