Merging an IC variant may lead to the IC status containing overlapping structure...
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Nov 2018 05:15:31 +0000 (05:15 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Nov 2018 05:15:31 +0000 (05:15 +0000)
https://bugs.webkit.org/show_bug.cgi?id=191869
<rdar://problem/45403453>

Reviewed by Mark Lam.

JSTests:

* stress/merging-ic-variants-should-bail-if-structures-overlap.js: Added.

Source/JavaScriptCore:

When merging two IC variant lists, we may end up in a world where we have
overlapping structure sets. We defend against this when we append a new
variant, but we should also defend against it once we merge in a new variant.

Consider this case with MultiPutByOffset, where we merge two PutByIdStatuses
together, P1 and P2.

Let's consider these structures:
s1 = {}
s2 = {p: 0}
s3 = {p: 0, p2: 1}

P1 contains these variants:
Transition: [s1 => s2]
Replace: [s2, s3]

P2 contains:
Replace: [s2]

Because of the ordering of the variants, we may end up combining
P2's replace into P1's transition, forming this new list:
Transition: [(s1, s2) => s2]
Replace: [s2, s3]

Obviously the ideal thing here is to have some ordering when we merge
in variants to choose the most ideal option. It'd be ideal for P2's
Replace to be merged into P1's replace.

If we notice that this is super important, we can implement some kind
of ordering. None of our tests (until this patch) stress this. This patch
just makes it so we defend against this crazy scenario by falling back
to the slow path gracefully. This prevents us from emitting invalid
IR in FTL->B3 lowering by creating a switch with two case labels being
identical values.

* bytecode/ICStatusUtils.h:
(JSC::appendICStatusVariant):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@238411 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/merging-ic-variants-should-bail-if-structures-overlap.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/ICStatusUtils.h

index 2858ea1..6467d07 100644 (file)
@@ -1,3 +1,13 @@
+2018-11-20  Saam barati  <sbarati@apple.com>
+
+        Merging an IC variant may lead to the IC status containing overlapping structure sets
+        https://bugs.webkit.org/show_bug.cgi?id=191869
+        <rdar://problem/45403453>
+
+        Reviewed by Mark Lam.
+
+        * stress/merging-ic-variants-should-bail-if-structures-overlap.js: Added.
+
 2018-11-19  Mark Lam  <mark.lam@apple.com>
 
         globalFuncImportModule() should return a promise when it clears exceptions.
diff --git a/JSTests/stress/merging-ic-variants-should-bail-if-structures-overlap.js b/JSTests/stress/merging-ic-variants-should-bail-if-structures-overlap.js
new file mode 100644 (file)
index 0000000..43e5bc9
--- /dev/null
@@ -0,0 +1,16 @@
+//@ runDefault("--validateGraphAtEachPhase=1", "--useLLInt=0")
+
+let items = [];
+for (let i = 0; i < 8; ++i) {
+    class C {
+    }
+    items.push(new C());
+}
+function foo(x) {
+    x.z = 0;
+}
+for (let i = 0; i < 100000; ++i) {
+    for (let j = 0; j < items.length; ++j) {
+        foo(items[j]);
+    }
+}
index 1f2073f..bb465f5 100644 (file)
@@ -1,3 +1,49 @@
+2018-11-20  Saam barati  <sbarati@apple.com>
+
+        Merging an IC variant may lead to the IC status containing overlapping structure sets
+        https://bugs.webkit.org/show_bug.cgi?id=191869
+        <rdar://problem/45403453>
+
+        Reviewed by Mark Lam.
+
+        When merging two IC variant lists, we may end up in a world where we have
+        overlapping structure sets. We defend against this when we append a new
+        variant, but we should also defend against it once we merge in a new variant.
+        
+        Consider this case with MultiPutByOffset, where we merge two PutByIdStatuses
+        together, P1 and P2.
+        
+        Let's consider these structures:
+        s1 = {}
+        s2 = {p: 0}
+        s3 = {p: 0, p2: 1}
+        
+        P1 contains these variants:
+        Transition: [s1 => s2]
+        Replace: [s2, s3]
+        
+        P2 contains:
+        Replace: [s2]
+        
+        Because of the ordering of the variants, we may end up combining
+        P2's replace into P1's transition, forming this new list:
+        Transition: [(s1, s2) => s2]
+        Replace: [s2, s3]
+        
+        Obviously the ideal thing here is to have some ordering when we merge
+        in variants to choose the most ideal option. It'd be ideal for P2's
+        Replace to be merged into P1's replace.
+        
+        If we notice that this is super important, we can implement some kind
+        of ordering. None of our tests (until this patch) stress this. This patch
+        just makes it so we defend against this crazy scenario by falling back
+        to the slow path gracefully. This prevents us from emitting invalid
+        IR in FTL->B3 lowering by creating a switch with two case labels being
+        identical values.
+
+        * bytecode/ICStatusUtils.h:
+        (JSC::appendICStatusVariant):
+
 2018-11-20  Fujii Hironori  <Hironori.Fujii@sony.com>
 
         REGRESSION(r238039) WebCore::JSDOMGlobalObject::createStructure is using JSC::Structure::create without including StructureInlines.h
index 067a997..0e2a98d 100644 (file)
@@ -34,8 +34,16 @@ bool appendICStatusVariant(VariantVectorType& variants, const VariantType& varia
 {
     // Attempt to merge this variant with an already existing variant.
     for (unsigned i = 0; i < variants.size(); ++i) {
-        if (variants[i].attemptToMerge(variant))
+        VariantType& mergedVariant = variants[i];
+        if (mergedVariant.attemptToMerge(variant)) {
+            for (unsigned j = 0; j < variants.size(); ++j) {
+                if (i == j)
+                    continue;
+                if (variants[j].structureSet().overlaps(mergedVariant.structureSet()))
+                    return false;
+            }
             return true;
+        }
     }
     
     // Make sure there is no overlap. We should have pruned out opportunities for