Bug 186814 - CompareEq should be using KnownOtherUse instead of OtherUse
Summary: CompareEq should be using KnownOtherUse instead of OtherUse
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
Depends on:
Blocks:
 
Reported: 2018-06-19 13:16 PDT by Saam Barati
Modified: 2018-07-20 12:16 PDT (History)
13 users (show)

See Also:


Attachments
WIP (6.06 KB, patch)
2018-06-28 19:15 PDT, Saam Barati
no flags Details | Formatted Diff | Diff
patch (8.40 KB, patch)
2018-07-05 18:04 PDT, Saam Barati
sbarati: review-
Details | Formatted Diff | Diff
patch (10.84 KB, patch)
2018-07-10 18:42 PDT, 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 2018-06-19 13:16:57 PDT
This is an interesting bug. We have two GetByOffsets, something like this:

block#1:
a: GetByOffset(@base, “x”, [Load, Constant:undefined, Constant:undefined])
Branch (#2, #3)
block#2:
b: GetByOffset(@base, “x”, [Constant:undefined, Constant:undefined])
d: Check(@Other:@b)
c: CompareEq(@something, Other:@b)

In Fixup, the CompareEq emits that check node @d. We remove @d from the IR, because we know @b produces undefined.  We get this IR:

block#1:
a: GetByOffset(@base, “x”, [Load, Constant:undefined, Constant:undefined])
Branch (#2, #3)
block#2:
b: GetByOffset(@base, “x”, [Constant:undefined, Constant:undefined])
c: CompareEq(@something, Other:@b)

Then, CSE changes the program to:
block#1:
a: GetByOffset(@base, “x”, [Load, Constant:undefined, Constant:undefined])
Branch (#2, #3)
block#2:
b: CheckStructure(@base, …)
c: CompareEq(@something, Other:@a)

But, we don’t emit type checks in the FTL backend for CompareEq, because we emitted the Check node in Fixup. This is quite the interesting bug. It’s interesting that we end up in a state with a GetByOffset that has less specific type info.
Comment 1 Saam Barati 2018-06-19 13:17:30 PDT
<rdar://problem/39720030>
Comment 2 Saam Barati 2018-06-19 13:19:46 PDT
I'm not sure yet on the exact way to fix this. Who knows what kind of optimizations we may have performed on the MultiGetByOffset before we eliminate it.
Comment 3 Saam Barati 2018-06-28 12:19:18 PDT
Seems like the cleanest solution here is for the variants to be part of the CSE key. We'd just need to make sure this doesn't prevent a bunch of CSEs. My bet is it won't
Comment 4 Filip Pizlo 2018-06-28 12:33:50 PDT
(In reply to Saam Barati from comment #3)
> Seems like the cleanest solution here is for the variants to be part of the
> CSE key. We'd just need to make sure this doesn't prevent a bunch of CSEs.
> My bet is it won't

I recommend something else: add code to CSE to do a posthoc verification that the replacement is valid.

If you tried to make this part of the key then the key would get a lot more complicated. Also, keys have no notion of "key subtype" so I don't see how that would work.
Comment 5 Filip Pizlo 2018-06-28 12:55:23 PDT
(In reply to Filip Pizlo from comment #4)
> (In reply to Saam Barati from comment #3)
> > Seems like the cleanest solution here is for the variants to be part of the
> > CSE key. We'd just need to make sure this doesn't prevent a bunch of CSEs.
> > My bet is it won't
> 
> I recommend something else: add code to CSE to do a posthoc verification
> that the replacement is valid.
> 
> If you tried to make this part of the key then the key would get a lot more
> complicated. Also, keys have no notion of "key subtype" so I don't see how
> that would work.

Thinking about this more, I think this even means CSE doing the AbstractValue computation for both MultiGetByOffsets and refusing if the first one (the one that survives) is not a subset of the second one (the one that gets replaced).
Comment 6 Saam Barati 2018-06-28 17:48:32 PDT
(In reply to Filip Pizlo from comment #5)
> (In reply to Filip Pizlo from comment #4)
> > (In reply to Saam Barati from comment #3)
> > > Seems like the cleanest solution here is for the variants to be part of the
> > > CSE key. We'd just need to make sure this doesn't prevent a bunch of CSEs.
> > > My bet is it won't
> > 
> > I recommend something else: add code to CSE to do a posthoc verification
> > that the replacement is valid.
> > 
> > If you tried to make this part of the key then the key would get a lot more
> > complicated. Also, keys have no notion of "key subtype" so I don't see how
> > that would work.
> 
> Thinking about this more, I think this even means CSE doing the
> AbstractValue computation for both MultiGetByOffsets and refusing if the
> first one (the one that survives) is not a subset of the second one (the one
> that gets replaced).

Right. This is what I first thought when I found this bug.

Let's go with this architecture. I'll work on a patch.
Comment 7 Saam Barati 2018-06-28 19:15:07 PDT
Created attachment 343886 [details]
WIP

I need to figure out what to do w/ GetByOffset. We may need to note what StructureSet GetByOffset emits a check for.

We want to enable CSE between MultiGetByOffset and GetByOffset
and GetByOffset w/ GetByOffset. But we need to make sure the resulting type of the replacement w/ GetByOffset is a subtype of the node being replaced. Same w/ Multi
Comment 8 Saam Barati 2018-07-05 18:04:42 PDT
Created attachment 344388 [details]
patch
Comment 9 Filip Pizlo 2018-07-06 13:00:47 PDT
Comment on attachment 344388 [details]
patch

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

Holding off r+ because it seems like there are two things that could be cleaner.

> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:307
> +        RegisteredStructureSet baseSet; // This is the structure set that this node does the moral equivalent of a CheckStructure on.

Why do you do anything with the structure set?  The Node::remove() code that replaces a MultiGetByOffset with a CheckStructure ensures that you don't have to worry about it.

> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:376
> +    if (forReplacement.second.value() != forNode.second.value()) {
> +        if (DFGCSEPhaseInternal::verbose)
> +            dataLogLn("Blocked replacement because values are not equal");
> +        return true;
> +    }
> +    if (!forReplacement.second.isType(forNode.second.m_type)) {
> +        if (DFGCSEPhaseInternal::verbose)
> +            dataLogLn("Blocked replacement because type for replacement is not subtype of node");
> +        return true;
> +    }
> +    if (forNode.second.m_structure.isFinite()) {
> +        if (!forReplacement.second.m_structure.isSubsetOf(forNode.second.m_structure)) {
> +            if (DFGCSEPhaseInternal::verbose)
> +                dataLogLn("Blocked replacement because replacement result is not structure subset of node");
> +            return true;
> +        }
> +    }
> +    if (forReplacement.second.m_arrayModes != forNode.second.m_arrayModes) {
> +        if (DFGCSEPhaseInternal::verbose)
> +            dataLogLn("Blocked replacement because array modes are different");
> +        return true;
> +    }

Why not just do:

AbstractValue tmp = forNode;
tmp.merge(forReplacement);
if (tmp != forNode)
    return true; // blocked replacement because the replacement is more general
Comment 10 Filip Pizlo 2018-07-07 13:00:33 PDT
I thought about this more, and I'm not sure that this fix is right anymore.

If we have:

a: MultiGetByOffset(@o, S1 -> Int32, S2 -> Object, S3 -> Boolean)
...
b: MultiGetByOffset(@o, S1 -> Int32, S2 -> Object)

Then it's actually totally OK to do the replacement.  It's true that @a could return a boolean, but we will replace @b with a CheckStructure(@o, [S1, S2]).  That CheckStructure actually proves that @a must only have returned either Int32 or Object, not Boolean.

Maybe the problem here is that we just have an overzealous assertion.
Comment 11 Saam Barati 2018-07-10 17:48:41 PDT
I spoke with Phil offline, and the bug isn't in MultiGetByOffset, but rather, in CompareEq. CompareEq has code like this in fixup:

```
                m_insertionSet.insertNode(m_indexInBlock, SpecNone, Check, node->origin,
                    Edge(node->child1().node(), OtherUse));
                fixEdge<OtherUse>(node->child1());
```

Because it inserts this Check, it has no intention of emitting the check itself. So when its input is this MultiGetByOffset, we end up confusing AI. This exact scenario is why we need a KnownOtherUse node, and we need to use it here, like we use it for other KnownXYZ UseKinds in similar fixup rules.
Comment 12 Saam Barati 2018-07-10 18:42:19 PDT
Created attachment 344744 [details]
patch
Comment 13 WebKit Commit Bot 2018-07-20 12:16:36 PDT
Comment on attachment 344744 [details]
patch

Clearing flags on attachment: 344744

Committed r234060: <https://trac.webkit.org/changeset/234060>
Comment 14 WebKit Commit Bot 2018-07-20 12:16:38 PDT
All reviewed patches have been landed.  Closing bug.