Bug 167919 – Air IRC might spill a terminal that produces a value after the terminal

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Saam Barati]

This can happen when a value producing patchpoint is a terminal. Air will happily spill in the block after the terminal. It should instead spill in all successor blocks.

[Saam Barati]

<rdar://problem/29754721>

[Filip Pizlo]

Thought about this a bit. I think that the cleanest solution is to just have a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing phase but separately from the main algorithm, that just looks for instructions after terminals and fixes them. The fix-up would then:

- If any of the successor edges of the block with the Inst after terminal are critial, break them.

- Shove the code after the terminal to each of the successors.

I believe that this is best done as a post-IRC fixup because inside IRC we reuse some analysis results and what-not.  It would be awkward if we were adding blocks on the fly.  Also, adding the critical edge blocks before IRC would increase IRC's running time.  Finally, I think that adding code to IRC that adds the spill code either in this block via InsertionSet or in another block using some other method sounds like it would complicate IRC a lot.  But the post-hoc fixup would be a simple algorithm.

I can't think of any reason why this would be wrong, since IRC doesn't care if something is a terminal.

The other options would be:

- Break critical edges before IRC.  This sounds expensive.  It increases the amount of per-edge work for IRC in cases where we wouldn't have spilled or wouldn't have had a temrinal that produces a result.  But, this would trivially allow the spiller to put spill code in the successor.

- Break critical edges before IRC only when the previous block has a terminal with a Def.  This is beginning to sound more complicated than my proposal.

Note that these options are definitely or probably borked:

- Just put the spill code in the successor block.  That doesn't work because the successor edge could be critical: the successor could have a predecessor other than us.  Air allows critical edges and they are very likely to come into existence via taildup.  So, this approach is definitely wrong, even if it passes tests.

- Break the critical edges as we try to insert the spill code.  It's important for Air to preserve sane block order.  Also, IRC has a bunch of analyses live while it's running, and it would be confusing if the number of basic blocks was changing while IRC ran.  So, this approach is undesirable, but not definitely wrong.

[Saam Barati]

(In reply to comment #2)
> Thought about this a bit. I think that the cleanest solution is to just have
> a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing
> phase but separately from the main algorithm, that just looks for
> instructions after terminals and fixes them. The fix-up would then:
> 
> - If any of the successor edges of the block with the Inst after terminal
> are critial, break them.
> 
> - Shove the code after the terminal to each of the successors.
> 
> I believe that this is best done as a post-IRC fixup because inside IRC we
> reuse some analysis results and what-not.  It would be awkward if we were
> adding blocks on the fly.  Also, adding the critical edge blocks before IRC
> would increase IRC's running time.  Finally, I think that adding code to IRC
> that adds the spill code either in this block via InsertionSet or in another
> block using some other method sounds like it would complicate IRC a lot. 
> But the post-hoc fixup would be a simple algorithm.
> 
> I can't think of any reason why this would be wrong, since IRC doesn't care
> if something is a terminal.
> 
> The other options would be:
> 
> - Break critical edges before IRC.  This sounds expensive.  It increases the
> amount of per-edge work for IRC in cases where we wouldn't have spilled or
> wouldn't have had a temrinal that produces a result.  But, this would
> trivially allow the spiller to put spill code in the successor.
> 
> - Break critical edges before IRC only when the previous block has a
> terminal with a Def.  This is beginning to sound more complicated than my
> proposal.
> 
> Note that these options are definitely or probably borked:
> 
> - Just put the spill code in the successor block.  That doesn't work because
> the successor edge could be critical: the successor could have a predecessor
> other than us.  Air allows critical edges and they are very likely to come
> into existence via taildup.  So, this approach is definitely wrong, even if
> it passes tests.
> 
> - Break the critical edges as we try to insert the spill code.  It's
> important for Air to preserve sane block order.  Also, IRC has a bunch of
> analyses live while it's running, and it would be confusing if the number of
> basic blocks was changing while IRC ran.  So, this approach is undesirable,
> but not definitely wrong.

I'm going to go with your suggestion.
That said, thinking more about what it means to have a critical edge branch-value-producing patchpoint is somewhat awkward.
I'm consider these two cases:
1. The patchpoint's successors each have *only* the patchpoint as the predecessor. This is simple.
   Each successor can happily use the patchpoint's result.
2. One or more of the patchpoint's successors have other predecessors that are not the patchpoint.
   This is somewhat awkward. Because we create these in B3 in SSA, I think this means that
   such a successor won't be able to use the patchpoint's result.

That said, I believe we precisely do (2) inside the FTL, because we'll use the patchpoint's value
on success, but not on failure. The success path has exactly one predecessor, the patchpoint,
and the failure path may have many edges to it.

[Filip Pizlo]

(In reply to comment #3)
> (In reply to comment #2)
> > Thought about this a bit. I think that the cleanest solution is to just have
> > a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing
> > phase but separately from the main algorithm, that just looks for
> > instructions after terminals and fixes them. The fix-up would then:
> > 
> > - If any of the successor edges of the block with the Inst after terminal
> > are critial, break them.
> > 
> > - Shove the code after the terminal to each of the successors.
> > 
> > I believe that this is best done as a post-IRC fixup because inside IRC we
> > reuse some analysis results and what-not.  It would be awkward if we were
> > adding blocks on the fly.  Also, adding the critical edge blocks before IRC
> > would increase IRC's running time.  Finally, I think that adding code to IRC
> > that adds the spill code either in this block via InsertionSet or in another
> > block using some other method sounds like it would complicate IRC a lot. 
> > But the post-hoc fixup would be a simple algorithm.
> > 
> > I can't think of any reason why this would be wrong, since IRC doesn't care
> > if something is a terminal.
> > 
> > The other options would be:
> > 
> > - Break critical edges before IRC.  This sounds expensive.  It increases the
> > amount of per-edge work for IRC in cases where we wouldn't have spilled or
> > wouldn't have had a temrinal that produces a result.  But, this would
> > trivially allow the spiller to put spill code in the successor.
> > 
> > - Break critical edges before IRC only when the previous block has a
> > terminal with a Def.  This is beginning to sound more complicated than my
> > proposal.
> > 
> > Note that these options are definitely or probably borked:
> > 
> > - Just put the spill code in the successor block.  That doesn't work because
> > the successor edge could be critical: the successor could have a predecessor
> > other than us.  Air allows critical edges and they are very likely to come
> > into existence via taildup.  So, this approach is definitely wrong, even if
> > it passes tests.
> > 
> > - Break the critical edges as we try to insert the spill code.  It's
> > important for Air to preserve sane block order.  Also, IRC has a bunch of
> > analyses live while it's running, and it would be confusing if the number of
> > basic blocks was changing while IRC ran.  So, this approach is undesirable,
> > but not definitely wrong.
> 
> I'm going to go with your suggestion.
> That said, thinking more about what it means to have a critical edge
> branch-value-producing patchpoint is somewhat awkward.
> I'm consider these two cases:
> 1. The patchpoint's successors each have *only* the patchpoint as the
> predecessor. This is simple.
>    Each successor can happily use the patchpoint's result.
> 2. One or more of the patchpoint's successors have other predecessors that
> are not the patchpoint.
>    This is somewhat awkward. Because we create these in B3 in SSA, I think
> this means that
>    such a successor won't be able to use the patchpoint's result.
> 
> That said, I believe we precisely do (2) inside the FTL, because we'll use
> the patchpoint's value
> on success, but not on failure. The success path has exactly one
> predecessor, the patchpoint,
> and the failure path may have many edges to it.

I think that the Air way of handling this case is:

1) IRC emits spill code all over the place.
2) allocateStack DCEs the spill on those paths where it's not needed. This happens for free in allocateStack.

Otherwise, you'd need to query more things about the liveness of the variable.  Not impossible, but seems harder.

Also, Tmp in Air is not an SSA variable.  Things may have happened.  So, it's possible that you have:

Block #A:
    Patch def:%tmp42
  Successors: #C

Block #B:
    Move ..., %tmp42
  Successors: #C

Block #C:
    ... use %tmp42

It's not obvious that we would see such Air because it's ordinarily generated from B3.  However, we perform transformations in Air that duplicate code, which can trivially introduce two assignments to the same tmp.  Maybe this can cause this pattern.  Therefore, I think it's best to ensure that every Air phase can handle any Air input, and that includes the above.

[Saam Barati]

(In reply to comment #4)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > Thought about this a bit. I think that the cleanest solution is to just have
> > > a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing
> > > phase but separately from the main algorithm, that just looks for
> > > instructions after terminals and fixes them. The fix-up would then:
> > > 
> > > - If any of the successor edges of the block with the Inst after terminal
> > > are critial, break them.
> > > 
> > > - Shove the code after the terminal to each of the successors.
> > > 
> > > I believe that this is best done as a post-IRC fixup because inside IRC we
> > > reuse some analysis results and what-not.  It would be awkward if we were
> > > adding blocks on the fly.  Also, adding the critical edge blocks before IRC
> > > would increase IRC's running time.  Finally, I think that adding code to IRC
> > > that adds the spill code either in this block via InsertionSet or in another
> > > block using some other method sounds like it would complicate IRC a lot. 
> > > But the post-hoc fixup would be a simple algorithm.
> > > 
> > > I can't think of any reason why this would be wrong, since IRC doesn't care
> > > if something is a terminal.
> > > 
> > > The other options would be:
> > > 
> > > - Break critical edges before IRC.  This sounds expensive.  It increases the
> > > amount of per-edge work for IRC in cases where we wouldn't have spilled or
> > > wouldn't have had a temrinal that produces a result.  But, this would
> > > trivially allow the spiller to put spill code in the successor.
> > > 
> > > - Break critical edges before IRC only when the previous block has a
> > > terminal with a Def.  This is beginning to sound more complicated than my
> > > proposal.
> > > 
> > > Note that these options are definitely or probably borked:
> > > 
> > > - Just put the spill code in the successor block.  That doesn't work because
> > > the successor edge could be critical: the successor could have a predecessor
> > > other than us.  Air allows critical edges and they are very likely to come
> > > into existence via taildup.  So, this approach is definitely wrong, even if
> > > it passes tests.
> > > 
> > > - Break the critical edges as we try to insert the spill code.  It's
> > > important for Air to preserve sane block order.  Also, IRC has a bunch of
> > > analyses live while it's running, and it would be confusing if the number of
> > > basic blocks was changing while IRC ran.  So, this approach is undesirable,
> > > but not definitely wrong.
> > 
> > I'm going to go with your suggestion.
> > That said, thinking more about what it means to have a critical edge
> > branch-value-producing patchpoint is somewhat awkward.
> > I'm consider these two cases:
> > 1. The patchpoint's successors each have *only* the patchpoint as the
> > predecessor. This is simple.
> >    Each successor can happily use the patchpoint's result.
> > 2. One or more of the patchpoint's successors have other predecessors that
> > are not the patchpoint.
> >    This is somewhat awkward. Because we create these in B3 in SSA, I think
> > this means that
> >    such a successor won't be able to use the patchpoint's result.
> > 
> > That said, I believe we precisely do (2) inside the FTL, because we'll use
> > the patchpoint's value
> > on success, but not on failure. The success path has exactly one
> > predecessor, the patchpoint,
> > and the failure path may have many edges to it.
> 
> I think that the Air way of handling this case is:
> 
> 1) IRC emits spill code all over the place.
> 2) allocateStack DCEs the spill on those paths where it's not needed. This
> happens for free in allocateStack.
> 
> Otherwise, you'd need to query more things about the liveness of the
> variable.  Not impossible, but seems harder.
> 
> Also, Tmp in Air is not an SSA variable.  Things may have happened.  So,
> it's possible that you have:
> 
> Block #A:
>     Patch def:%tmp42
>   Successors: #C
> 
> Block #B:
>     Move ..., %tmp42
>   Successors: #C
> 
> Block #C:
>     ... use %tmp42
> 
> It's not obvious that we would see such Air because it's ordinarily
> generated from B3.  However, we perform transformations in Air that
> duplicate code, which can trivially introduce two assignments to the same
> tmp.  Maybe this can cause this pattern.  Therefore, I think it's best to
> ensure that every Air phase can handle any Air input, and that includes the
> above.

Indeed. I agree we should handle it, and the code I have written does. I just don't know how to write a test uses the value being spilled along that path. I've written a test that makes sure we break the critical edge, but not one that uses the value along the path of the critical edge.

[Saam Barati]

Created attachment 300792 [details]
patch

[Filip Pizlo]

(In reply to comment #5)
> (In reply to comment #4)
> > (In reply to comment #3)
> > > (In reply to comment #2)
> > > > Thought about this a bit. I think that the cleanest solution is to just have
> > > > a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing
> > > > phase but separately from the main algorithm, that just looks for
> > > > instructions after terminals and fixes them. The fix-up would then:
> > > > 
> > > > - If any of the successor edges of the block with the Inst after terminal
> > > > are critial, break them.
> > > > 
> > > > - Shove the code after the terminal to each of the successors.
> > > > 
> > > > I believe that this is best done as a post-IRC fixup because inside IRC we
> > > > reuse some analysis results and what-not.  It would be awkward if we were
> > > > adding blocks on the fly.  Also, adding the critical edge blocks before IRC
> > > > would increase IRC's running time.  Finally, I think that adding code to IRC
> > > > that adds the spill code either in this block via InsertionSet or in another
> > > > block using some other method sounds like it would complicate IRC a lot. 
> > > > But the post-hoc fixup would be a simple algorithm.
> > > > 
> > > > I can't think of any reason why this would be wrong, since IRC doesn't care
> > > > if something is a terminal.
> > > > 
> > > > The other options would be:
> > > > 
> > > > - Break critical edges before IRC.  This sounds expensive.  It increases the
> > > > amount of per-edge work for IRC in cases where we wouldn't have spilled or
> > > > wouldn't have had a temrinal that produces a result.  But, this would
> > > > trivially allow the spiller to put spill code in the successor.
> > > > 
> > > > - Break critical edges before IRC only when the previous block has a
> > > > terminal with a Def.  This is beginning to sound more complicated than my
> > > > proposal.
> > > > 
> > > > Note that these options are definitely or probably borked:
> > > > 
> > > > - Just put the spill code in the successor block.  That doesn't work because
> > > > the successor edge could be critical: the successor could have a predecessor
> > > > other than us.  Air allows critical edges and they are very likely to come
> > > > into existence via taildup.  So, this approach is definitely wrong, even if
> > > > it passes tests.
> > > > 
> > > > - Break the critical edges as we try to insert the spill code.  It's
> > > > important for Air to preserve sane block order.  Also, IRC has a bunch of
> > > > analyses live while it's running, and it would be confusing if the number of
> > > > basic blocks was changing while IRC ran.  So, this approach is undesirable,
> > > > but not definitely wrong.
> > > 
> > > I'm going to go with your suggestion.
> > > That said, thinking more about what it means to have a critical edge
> > > branch-value-producing patchpoint is somewhat awkward.
> > > I'm consider these two cases:
> > > 1. The patchpoint's successors each have *only* the patchpoint as the
> > > predecessor. This is simple.
> > >    Each successor can happily use the patchpoint's result.
> > > 2. One or more of the patchpoint's successors have other predecessors that
> > > are not the patchpoint.
> > >    This is somewhat awkward. Because we create these in B3 in SSA, I think
> > > this means that
> > >    such a successor won't be able to use the patchpoint's result.
> > > 
> > > That said, I believe we precisely do (2) inside the FTL, because we'll use
> > > the patchpoint's value
> > > on success, but not on failure. The success path has exactly one
> > > predecessor, the patchpoint,
> > > and the failure path may have many edges to it.
> > 
> > I think that the Air way of handling this case is:
> > 
> > 1) IRC emits spill code all over the place.
> > 2) allocateStack DCEs the spill on those paths where it's not needed. This
> > happens for free in allocateStack.
> > 
> > Otherwise, you'd need to query more things about the liveness of the
> > variable.  Not impossible, but seems harder.
> > 
> > Also, Tmp in Air is not an SSA variable.  Things may have happened.  So,
> > it's possible that you have:
> > 
> > Block #A:
> >     Patch def:%tmp42
> >   Successors: #C
> > 
> > Block #B:
> >     Move ..., %tmp42
> >   Successors: #C
> > 
> > Block #C:
> >     ... use %tmp42
> > 
> > It's not obvious that we would see such Air because it's ordinarily
> > generated from B3.  However, we perform transformations in Air that
> > duplicate code, which can trivially introduce two assignments to the same
> > tmp.  Maybe this can cause this pattern.  Therefore, I think it's best to
> > ensure that every Air phase can handle any Air input, and that includes the
> > above.
> 
> Indeed. I agree we should handle it, and the code I have written does. I
> just don't know how to write a test uses the value being spilled along that
> path. I've written a test that makes sure we break the critical edge, but
> not one that uses the value along the path of the critical edge.

You could write an Air unit test, maybe in testair. Just feed IR straight into IRC and then assert things about the output, like maybe just validating terminals.

[Saam Barati]

(In reply to comment #7)
> (In reply to comment #5)
> > (In reply to comment #4)
> > > (In reply to comment #3)
> > > > (In reply to comment #2)
> > > > > Thought about this a bit. I think that the cleanest solution is to just have
> > > > > a post-IRC fixup, implemented as part of the iteratedRegisterCoalescing
> > > > > phase but separately from the main algorithm, that just looks for
> > > > > instructions after terminals and fixes them. The fix-up would then:
> > > > > 
> > > > > - If any of the successor edges of the block with the Inst after terminal
> > > > > are critial, break them.
> > > > > 
> > > > > - Shove the code after the terminal to each of the successors.
> > > > > 
> > > > > I believe that this is best done as a post-IRC fixup because inside IRC we
> > > > > reuse some analysis results and what-not.  It would be awkward if we were
> > > > > adding blocks on the fly.  Also, adding the critical edge blocks before IRC
> > > > > would increase IRC's running time.  Finally, I think that adding code to IRC
> > > > > that adds the spill code either in this block via InsertionSet or in another
> > > > > block using some other method sounds like it would complicate IRC a lot. 
> > > > > But the post-hoc fixup would be a simple algorithm.
> > > > > 
> > > > > I can't think of any reason why this would be wrong, since IRC doesn't care
> > > > > if something is a terminal.
> > > > > 
> > > > > The other options would be:
> > > > > 
> > > > > - Break critical edges before IRC.  This sounds expensive.  It increases the
> > > > > amount of per-edge work for IRC in cases where we wouldn't have spilled or
> > > > > wouldn't have had a temrinal that produces a result.  But, this would
> > > > > trivially allow the spiller to put spill code in the successor.
> > > > > 
> > > > > - Break critical edges before IRC only when the previous block has a
> > > > > terminal with a Def.  This is beginning to sound more complicated than my
> > > > > proposal.
> > > > > 
> > > > > Note that these options are definitely or probably borked:
> > > > > 
> > > > > - Just put the spill code in the successor block.  That doesn't work because
> > > > > the successor edge could be critical: the successor could have a predecessor
> > > > > other than us.  Air allows critical edges and they are very likely to come
> > > > > into existence via taildup.  So, this approach is definitely wrong, even if
> > > > > it passes tests.
> > > > > 
> > > > > - Break the critical edges as we try to insert the spill code.  It's
> > > > > important for Air to preserve sane block order.  Also, IRC has a bunch of
> > > > > analyses live while it's running, and it would be confusing if the number of
> > > > > basic blocks was changing while IRC ran.  So, this approach is undesirable,
> > > > > but not definitely wrong.
> > > > 
> > > > I'm going to go with your suggestion.
> > > > That said, thinking more about what it means to have a critical edge
> > > > branch-value-producing patchpoint is somewhat awkward.
> > > > I'm consider these two cases:
> > > > 1. The patchpoint's successors each have *only* the patchpoint as the
> > > > predecessor. This is simple.
> > > >    Each successor can happily use the patchpoint's result.
> > > > 2. One or more of the patchpoint's successors have other predecessors that
> > > > are not the patchpoint.
> > > >    This is somewhat awkward. Because we create these in B3 in SSA, I think
> > > > this means that
> > > >    such a successor won't be able to use the patchpoint's result.
> > > > 
> > > > That said, I believe we precisely do (2) inside the FTL, because we'll use
> > > > the patchpoint's value
> > > > on success, but not on failure. The success path has exactly one
> > > > predecessor, the patchpoint,
> > > > and the failure path may have many edges to it.
> > > 
> > > I think that the Air way of handling this case is:
> > > 
> > > 1) IRC emits spill code all over the place.
> > > 2) allocateStack DCEs the spill on those paths where it's not needed. This
> > > happens for free in allocateStack.
> > > 
> > > Otherwise, you'd need to query more things about the liveness of the
> > > variable.  Not impossible, but seems harder.
> > > 
> > > Also, Tmp in Air is not an SSA variable.  Things may have happened.  So,
> > > it's possible that you have:
> > > 
> > > Block #A:
> > >     Patch def:%tmp42
> > >   Successors: #C
> > > 
> > > Block #B:
> > >     Move ..., %tmp42
> > >   Successors: #C
> > > 
> > > Block #C:
> > >     ... use %tmp42
> > > 
> > > It's not obvious that we would see such Air because it's ordinarily
> > > generated from B3.  However, we perform transformations in Air that
> > > duplicate code, which can trivially introduce two assignments to the same
> > > tmp.  Maybe this can cause this pattern.  Therefore, I think it's best to
> > > ensure that every Air phase can handle any Air input, and that includes the
> > > above.
> > 
> > Indeed. I agree we should handle it, and the code I have written does. I
> > just don't know how to write a test uses the value being spilled along that
> > path. I've written a test that makes sure we break the critical edge, but
> > not one that uses the value along the path of the critical edge.
> 
> You could write an Air unit test, maybe in testair. Just feed IR straight
> into IRC and then assert things about the output, like maybe just validating
> terminals.
Good point. I forgot about testair's existsence.

[Saam Barati]

landed in:
https://trac.webkit.org/changeset/211896

[Filip Pizlo]

Comment on attachment 300792 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=300792&action=review

> Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1578
> +    void fixSpillsAfterTerminals()

Too bad we didn't make this an independent function so that spillEverything() could call it!

> Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1621
> +                    // FIXME: We probably want better block ordering here.

That's why we have BlockInsertionSet.

It's super important that we always have clean basic block order.

Can I rely on Wasm's B3IRGen giving us sensible block order?