Skip to content

cranelift-frontend: Fix stack maps and liveness for loops#9071

Merged
fitzgen merged 2 commits intobytecodealliance:mainfrom
fitzgen:stack-maps-and-liveness-and-loops
Aug 2, 2024
Merged

cranelift-frontend: Fix stack maps and liveness for loops#9071
fitzgen merged 2 commits intobytecodealliance:mainfrom
fitzgen:stack-maps-and-liveness-and-loops

Conversation

@fitzgen
Copy link
Copy Markdown
Member

@fitzgen fitzgen commented Aug 2, 2024

Previously, we were not properly handling back edges. This manifested in values incorrectly being considered not-live inside loop bodies where they definitely were live. Consider the following example:

block0:
  v0 = needs stack map

block1:
  call foo(v0)
  call foo(v0)
  jump block1

We were previously considering v0 live only for the first call foo(v0) but not the second, because we mistakenly concluded that v0 would not be used again after that second call. While it won't be used again in this iteration of the loop, it will be used again in the next iteration of the loop.

Trevor and I initially tried implementing a clever trick suggested by Chris where, if we know the minimum post-order index of all of a block's transitive predecessors, we can continue to compute liveness in a single pass over the IR. We believed we could compute the minimum predecessor post-order index via dynamic programming. It turns out, however, that approach doesn't provide correct answers out of the box for certain kinds of irreducible control flow, only nearly correct answers, and would require an additional clever fix-up pass afterwards. We deemed this cleverness on cleverness unacceptable.

Instead, Trevor and I opted to implement a worklist algorithm where we process blocks to a fixed-point. This has the advantages of being obviously correct and producing more-precise results. It has the disadvantage of requiring multiple passes over the IR in the face of loops and back edges. Because this analysis is only used when needs-stack-map values are present (i.e. when the function uses GC values) and is otherwise skipped, this additional compile-time overhead is tolerable.

@fitzgen fitzgen requested a review from a team as a code owner August 2, 2024 19:36
@fitzgen fitzgen requested review from elliottt and removed request for a team August 2, 2024 19:36
Previously, we were not properly handling back edges. This manifested in values
incorrectly being considered not-live inside loop bodies where they definitely
were live. Consider the following example:

    block0:
      v0 = needs stack map

    block1:
      call foo(v0)
      call foo(v0)
      jump block1

We were previously considering `v0` live only for the first `call foo(v0)` but
not the second, because we mistakenly concluded that `v0` would not be used
again after that second `call`. While it won't be used again in *this* iteration
of the loop, it will be used again in the *next* iteration of the loop.

Trevor and I initially tried implementing a clever trick suggested by Chris
where, if we know the minimum post-order index of all of a block's transitive
predecessors, we can continue to compute liveness in a single pass over the
IR. We believed we could compute the minimum predecessor post-order index via
dynamic programming. It turns out, however, that approach doesn't provide
correct answers out of the box for certain kinds of irreducible control flow,
only nearly correct answers, and would require an additional clever fix-up pass
afterwards. We deemed this cleverness on cleverness unacceptable.

Instead, Trevor and I opted to implement a worklist algorithm where we process
blocks to a fixed-point. This has the advantages of being obviously correct and
producing more-precise results. It has the disadvantage of requiring multiple
passes over the IR in the face of loops and back edges. Because this analysis is
only used when needs-stack-map values are present (i.e. when the function uses
GC values) and is otherwise skipped, this additional compile-time overhead is
tolerable.

Co-Authored-By: Trevor Elliott <telliott@fastly.com>
@fitzgen fitzgen force-pushed the stack-maps-and-liveness-and-loops branch from 13e56db to c145baf Compare August 2, 2024 19:36
@fitzgen fitzgen requested review from cfallin and removed request for elliottt August 2, 2024 19:46
Copy link
Copy Markdown
Member

@cfallin cfallin left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks great, thanks! Some minor requests for clarification in comments but otherwise good to go.

@fitzgen fitzgen enabled auto-merge August 2, 2024 21:45
@fitzgen fitzgen added this pull request to the merge queue Aug 2, 2024
Merged via the queue into bytecodealliance:main with commit dbc503f Aug 2, 2024
@fitzgen fitzgen deleted the stack-maps-and-liveness-and-loops branch August 2, 2024 22:08
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants