lean-mlir icon indicating copy to clipboard operation
lean-mlir copied to clipboard

`TopM.get` always succeeds if dominance check passes

Open bollu opened this issue 3 years ago • 1 comments

@math-fehr

When we reason about linalg.runRegion, we want to show that we can safely reorder running of regions.

  • errors can be reordered with anything
  • set can be reordered with set, because we enforce SSA: if two sets do not interfere, then they commute. If two sets try to set at the same key, and they don't set the same value, then it's an error, and this error commutes with anything. Thus, in SSA, set commutes with everything.
  • get need not commute, because get can ask for something that's defined later. But if a regions obeys dominance (under the constraint of IsIsolatedFromAbove), then runRegion commutes, because I can choose to run a region either now, or later, and the region "can't tell the difference" (it's completely isolated from above, so it only knows about its input arguments). For this, we need a theorem about how dominance relates to getting/setting SSA values. I am unsure what precise shape this theorem must take, but it's going to be key to get a sensible version of eg. loop reversal.

bollu avatar Oct 07 '22 19:10 bollu

LGTM, I'm assuming this is based off of https://github.com/bollu/alive/pull/2?

bollu avatar Jun 19 '23 16:06 bollu

@goens May I merge this?

bollu avatar Jun 19 '23 16:06 bollu

@bollu there's a couple of changes missing I found while debugging this, I will push later tonight/tomorrow!

goens avatar Jun 19 '23 18:06 goens

If the changes in this PR are already an improvement, it might make sense to merge and then push the next batch of changes into another PR.

tobiasgrosser avatar Jun 20 '23 07:06 tobiasgrosser

this is also made obsolete by #49

goens avatar Jun 21 '23 01:06 goens