Bug 195303 - Air::reportUsedRegisters must padInterference
Summary: Air::reportUsedRegisters must padInterference
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Saam Barati
URL:
Keywords: InRadar
: 194896 (view as bug list)
Depends on:
Blocks:
 
Reported: 2019-03-04 18:41 PST by Saam Barati
Modified: 2019-03-21 12:20 PDT (History)
16 users (show)

See Also:


Attachments
patch (9.73 KB, patch)
2019-03-04 20:05 PST, Saam Barati
no flags Details | Formatted Diff | Diff
patch (9.67 KB, patch)
2019-03-04 20:08 PST, Saam Barati
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews124 for ios-simulator-wk2 (10.16 MB, application/zip)
2019-03-04 22:40 PST, Build Bot
no flags Details
patch (5.88 KB, patch)
2019-03-05 10:41 PST, Saam Barati
keith_miller: review+
Details | Formatted Diff | Diff
patch for landing (8.45 KB, patch)
2019-03-06 14:30 PST, Saam Barati
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Saam Barati 2019-03-04 18:41:33 PST
We need something like EarlyAndLateUse. Taking a Use (early) and converting it to LateUse changes liveness semantics and is not correct.
Comment 1 Saam Barati 2019-03-04 20:04:32 PST
<rdar://problem/48270343>
Comment 2 Saam Barati 2019-03-04 20:05:06 PST
Created attachment 363589 [details]
patch
Comment 3 Saam Barati 2019-03-04 20:08:33 PST
Created attachment 363590 [details]
patch
Comment 4 Filip Pizlo 2019-03-04 21:47:23 PST
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.
Comment 5 Saam Barati 2019-03-04 22:35:47 PST
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)
Comment 6 Build Bot 2019-03-04 22:40:19 PST
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
Comment 7 Build Bot 2019-03-04 22:40:21 PST
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
Comment 8 Filip Pizlo 2019-03-04 22:51:47 PST
(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.
Comment 9 Saam Barati 2019-03-05 09:58:36 PST
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.
Comment 10 Filip Pizlo 2019-03-05 10:14:01 PST
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.
Comment 11 Filip Pizlo 2019-03-05 10:14:31 PST
(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.
Comment 12 Saam Barati 2019-03-05 10:41:52 PST
Created attachment 363652 [details]
patch

I wonder if I should add a validation assertion that to run liveness, no insns need to be padded.
Comment 13 Saam Barati 2019-03-05 10:54:11 PST
(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.
Comment 14 Keith Miller 2019-03-06 13:19:38 PST
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.
Comment 15 Saam Barati 2019-03-06 14:23:57 PST
(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.
Comment 16 Saam Barati 2019-03-06 14:30:15 PST
Created attachment 363793 [details]
patch for landing
Comment 17 WebKit Commit Bot 2019-03-06 14:57:14 PST
Comment on attachment 363793 [details]
patch for landing

Clearing flags on attachment: 363793

Committed r242569: <https://trac.webkit.org/changeset/242569>
Comment 18 WebKit Commit Bot 2019-03-06 14:57:15 PST
All reviewed patches have been landed.  Closing bug.
Comment 19 Saam Barati 2019-03-06 16:47:48 PST
*** Bug 194896 has been marked as a duplicate of this bug. ***