Bug 195303 – Air::reportUsedRegisters must padInterference

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Saam Barati]

We need something like EarlyAndLateUse. Taking a Use (early) and converting it to LateUse changes liveness semantics and is not correct.

[Saam Barati]

<rdar://problem/48270343>

[Saam Barati]

Created attachment 363589 [details]
patch

[Saam Barati]

Created attachment 363590 [details]
patch

[Filip Pizlo]

Comment on attachment 363590 [details]
patch

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

I'm not sure about this because the example you give doesn't exhibit the problem you describe, at least not as far as I can tell.

> Source/JavaScriptCore/ChangeLog:26
> +        3. Patch &BranchSub32(3,SameAsRep)4, Overflow, $-2147483648, %rax, %rbx, %rax,LateUse:%rcx, %r13, @71

Why is this wrong?

> Source/JavaScriptCore/ChangeLog:31
> +        instruction (3). This allowed Air to eliminate instruction (2)
> +        entirely, since it was loading into a dead register.

That doesn't seem right.  If %rcx is used late, then it's still live in.

[Saam Barati]

Yeah it was initially non-obvious and confusing to me too, but it works out and makes more sense when you ignore what the instructions are and just write out the actions at each boundary.

I'm going to ignore everything besides rcx since that's all that matters in this example.

Initial program:
2. Move ..., %rcx
def = {rcx} use={rcx}
3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., EarlyUse:%rcx, ...
def={rcx} use={}
4. Patch ..., EarlyDef & LateUse:%rcx, ...
def={} use={rcx}

Creating live-in sets:
...
2. Move ..., %rcx
live={rcx}
3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., EarlyUse:%rcx, ...
live={rcx}
4. Patch ..., EarlyDef & LateUse:%rcx, ...
live={rcx}


Incorrectly modified program:
2. Move ..., %rcx
def = {rcx} use={}
3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., LateUse:%rcx, ...
def={rcx} use={rcx}
4. Patch ..., EarlyDef & LateUse:%rcx, ...
def={} use={rcx}

Creating live-in sets, the bug happens when we step backwards over defs of 3/4 and uses of 2/3, we no longer model the use of rcx at the 2/3 boundary, which allows the 3/4 def to clear it:
2. Move ..., %rcx
live={}
3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., LateUse:%rcx, ...
live={rcx}
4. Patch ..., EarlyDef & LateUse:%rcx, ...
live={rcx}

Do you agree with my analysis?

(I can update the changelog with this info)

[EWS Watchlist]

Comment on attachment 363590 [details]
patch

Attachment 363590 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: https://webkit-queues.webkit.org/results/11372495

New failing tests:
editing/pasteboard/ios/dom-paste-requires-user-gesture.html
fast/scrolling/ios/hit-testing-iframe-002.html
fast/scrolling/ios/mixing-user-and-programmatic-scroll-006.html
editing/selection/thai-word-at-document-end.html
fast/scrolling/ios/hit-testing-iframe-003.html

[EWS Watchlist]

Created attachment 363604 [details]
Archive of layout-test-results from ews124 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews124  Port: ios-simulator-wk2  Platform: Mac OS X 10.13.6

[Filip Pizlo]

(In reply to Saam Barati from comment #5)
> Yeah it was initially non-obvious and confusing to me too, but it works out
> and makes more sense when you ignore what the instructions are and just
> write out the actions at each boundary.
> 
> I'm going to ignore everything besides rcx since that's all that matters in
> this example.
> 
> Initial program:
> 2. Move ..., %rcx
> def = {rcx} use={rcx}
> 3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., EarlyUse:%rcx, ...
> def={rcx} use={}
> 4. Patch ..., EarlyDef & LateUse:%rcx, ...
> def={} use={rcx}
> 
> Creating live-in sets:
> ...
> 2. Move ..., %rcx
> live={rcx}
> 3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., EarlyUse:%rcx, ...
> live={rcx}
> 4. Patch ..., EarlyDef & LateUse:%rcx, ...
> live={rcx}
> 
> 
> Incorrectly modified program:
> 2. Move ..., %rcx
> def = {rcx} use={}
> 3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., LateUse:%rcx, ...
> def={rcx} use={rcx}
> 4. Patch ..., EarlyDef & LateUse:%rcx, ...
> def={} use={rcx}
> 
> Creating live-in sets, the bug happens when we step backwards over defs of
> 3/4 and uses of 2/3, we no longer model the use of rcx at the 2/3 boundary,
> which allows the 3/4 def to clear it:
> 2. Move ..., %rcx
> live={}
> 3. Patch &BranchSub32(3,SameAsRep)4, Overflow, ..., LateUse:%rcx, ...
> live={rcx}
> 4. Patch ..., EarlyDef & LateUse:%rcx, ...
> live={rcx}
> 
> Do you agree with my analysis?
> 
> (I can update the changelog with this info)

The solution is Air::padInterference().

That's how RA handles it.

[Saam Barati]

Interesting. Good to know. I just read through your old bug on this and it makes sense. I will also vet other code that uses liveness to make sure it's not missing pad interference as well.

[Filip Pizlo]

Note that padInterference is totally a gross hack. If we have to do it a lot then we should consider switching from a 2-point liveness model to a 4-point one. 

In particular, we currently say that there is a point where we reason about liveness  before an Inst and one after. But both points correspond to the after and before (respectively) of the Insts before and after (respectively). We could say there are four points: after prev Inst, before current Inst, after current Inst, and before next Inst. 

The linear scan RA already does this so I know it’s possible.

[Filip Pizlo]

(In reply to Filip Pizlo from comment #10)
> Note that padInterference is totally a gross hack. If we have to do it a lot
> then we should consider switching from a 2-point liveness model to a 4-point
> one. 
> 
> In particular, we currently say that there is a point where we reason about
> liveness  before an Inst and one after. But both points correspond to the
> after and before (respectively) of the Insts before and after
> (respectively). We could say there are four points: after prev Inst, before
> current Inst, after current Inst, and before next Inst. 
> 
> The linear scan RA already does this so I know it’s possible.

But I totally support just using padInteference for this fix. It should work, gross or not.

[Saam Barati]

Created attachment 363652 [details]
patch

I wonder if I should add a validation assertion that to run liveness, no insns need to be padded.

[Saam Barati]

(In reply to Filip Pizlo from comment #10)
> Note that padInterference is totally a gross hack. If we have to do it a lot
> then we should consider switching from a 2-point liveness model to a 4-point
> one. 
Yeah my takeaway from this bug is that anything that reasons about liveness at instruction boundaries must padInterference. Otherwise, you could get the wrong result.

> 
> In particular, we currently say that there is a point where we reason about
> liveness  before an Inst and one after. But both points correspond to the
> after and before (respectively) of the Insts before and after
> (respectively). We could say there are four points: after prev Inst, before
> current Inst, after current Inst, and before next Inst. 
Interesting. I agree this would work and it would be natural for reportUsedRegisters to reason about liveness in this way.

> 
> The linear scan RA already does this so I know it’s possible.

[Keith Miller]

Comment on attachment 363652 [details]
patch

r=me. Can you also add a testair test for this? Seems like that will be more robust against future changes upstream from air itself.

[Saam Barati]

(In reply to Keith Miller from comment #14)
> Comment on attachment 363652 [details]
> patch
> 
> r=me. Can you also add a testair test for this? Seems like that will be more
> robust against future changes upstream from air itself.

I spoke with Keith offline, we're going to add a b3 test since using patchpoint makes writing such a test easy.

[Saam Barati]

Created attachment 363793 [details]
patch for landing

[WebKit Commit Bot]

Comment on attachment 363793 [details]
patch for landing

Clearing flags on attachment: 363793

Committed r242569: <https://trac.webkit.org/changeset/242569>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Saam Barati]

*** Bug 194896 has been marked as a duplicate of this bug. ***