CompareEq should be using KnownOtherUse instead of OtherUse

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Saam Barati]

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.

[Saam Barati]

<rdar://problem/39720030>

[Saam Barati]

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.

[Saam Barati]

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

[Filip Pizlo]

(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.

[Filip Pizlo]

(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).

[Saam Barati]

(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.

[Saam Barati]

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

[Saam Barati]

Created attachment 344388 [details]
patch

[Filip Pizlo]

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

[Filip Pizlo]

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.

[Saam Barati]

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.

[Saam Barati]

Created attachment 344744 [details]
patch

[WebKit Commit Bot]

Comment on attachment 344744 [details]
patch

Clearing flags on attachment: 344744

Committed r234060: <https://trac.webkit.org/changeset/234060>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.