Page MenuHomePhabricator

[WebAssembly] Fix subregion relationship in CFGSort

Authored by aheejin on Mar 31 2020, 3:32 PM.



The previous code for determining the innermost region in CFGSort was
not correct. We determine subregion relationship by domination of their
headers, i.e., if region A's header dominates region B's header, B is a
subregion of A. Previously we assumed that if a BB belongs to both a
loop and an exception, the region with fewer number of BBs is the
innermost one. This may not be true, because while WebAssemblyException
contains BBs in all its subregions (loops or exceptions), MachineLoop
may not, because MachineLoop does not contain BBs that don't have a path
to its header even if they are dominated by its header.

  Loop header  <---|
      |            |
Exception header   |
      | \          |
      A  B         |
      |   \        |
      |    C       |
      |            |
  Loop latch       |
      |            |

For example, in this CFG, the loop does not contain B and C, because
they don't have a path back to the loops header. But for CFGSort we
consider the exception here belongs to the loop and the exception should
be a subregion of the loop and scheduled together.

So here we should use WE->contains(ML->getHeader()) (but not
ML->contains(WE->getHeader()), for the stated region above).

This also fixes some comments and deletes Regions vector in
RegionInfo class, which was not used anywere.

Diff Detail

Event Timeline

aheejin created this revision.Mar 31 2020, 3:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 31 2020, 3:32 PM
aheejin updated this revision to Diff 254032.Mar 31 2020, 4:00 PM
  • Test fix
dschuff accepted this revision.Mar 31 2020, 5:39 PM
dschuff added inline comments.

do you mean "path" instead of "pass" here and in the commit message?

This revision is now accepted and ready to land.Mar 31 2020, 5:39 PM
aheejin marked 2 inline comments as done.Apr 1 2020, 8:01 AM
aheejin added inline comments.

Thanks, fixed.

aheejin edited the summary of this revision. (Show Details)Apr 1 2020, 8:05 AM
This revision was automatically updated to reflect the committed changes.
aheejin marked an inline comment as done.