Skip to content
This repository has been archived by the owner on Jun 17, 2024. It is now read-only.

TopM.get always succeeds if dominance check passes #45

Open
bollu opened this issue Oct 7, 2022 · 1 comment
Open

TopM.get always succeeds if dominance check passes #45

bollu opened this issue Oct 7, 2022 · 1 comment

Comments

@bollu
Copy link
Contributor

bollu commented Oct 7, 2022

@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.
@math-fehr
Copy link
Contributor

Yes! I'm currently working on a quite hard proof that will make your set part easy!

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants