Changeset 269107 in webkit

Timestamp:

Oct 28, 2020, 10:32:26 AM (6 years ago)

Author:

rmorisset@apple.com

Message:

DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
​https://bugs.webkit.org/show_bug.cgi?id=218073

Reviewed by Saam Barati.

JSTests:

The only testcase I managed to get for this bug loops forever when not crashing.
So I use a 1s timeout through --watchdog=1000.

• stress/bounds-checking-in-cold-loop.js: Added.

(true.vm.ftlTrue):

Source/JavaScriptCore:

In DFGIntegerRangeOptimization, when visiting an Upsilon node, we call setEquivalence, that calls setRelationship.
But despite its name, this function does not overwrite a pre-existing relationship, it simply replaces it by an over-approximation of the intersection of the old and new relationship (see the filter method).
Since the old relationship is always (by definition) an over-approximation of this intersection, it will often do nothing at all if it cannot find a closer approximation.
This is a problem specifically for Upsilon nodes, because several of them can store to the same "shadow node" corresponding to a given Phi, so they are the only case where there can already be a completely different relationship for the same nodes (coming from a different Upsilon).

The fix is very simple thanks to a suggestion by Phil: we just remove all relationships referring to the shadow node just before executing an Upsilon.
This is correct since the upsilon effectively kills that shadow node, before making it live again with a different value, and we already aggressively prune the relationshipMaps by liveness.

• dfg/DFGIntegerRangeOptimizationPhase.cpp:

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/bounds-checking-in-cold-loop.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp (modified) (5 diffs)

trunk/JSTests/ChangeLog

@@ +1 @@
+2020-10-28  Robin Morisset  <rmorisset@apple.com>
+
+        DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
+        https://bugs.webkit.org/show_bug.cgi?id=218073
+
+        Reviewed by Saam Barati.
+
+        The only testcase I managed to get for this bug loops forever when not crashing.
+        So I use a 1s timeout through --watchdog=1000.
+
+        * stress/bounds-checking-in-cold-loop.js: Added.
+        (true.vm.ftlTrue):
+
 2020-10-24  Yusuke Suzuki  <ysuzuki@apple.com>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2020-10-28  Robin Morisset  <rmorisset@apple.com>
+
+        DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
+        https://bugs.webkit.org/show_bug.cgi?id=218073
+
+        Reviewed by Saam Barati.
+
+        In DFGIntegerRangeOptimization, when visiting an Upsilon node, we call setEquivalence, that calls setRelationship.
+        But despite its name, this function does not overwrite a pre-existing relationship, it simply replaces it by an over-approximation of the intersection of the old and new relationship (see the filter method).
+        Since the old relationship is always (by definition) an over-approximation of this intersection, it will often do nothing at all if it cannot find a closer approximation.
+        This is a problem specifically for Upsilon nodes, because several of them can store to the same "shadow node" corresponding to a given Phi, so they are the only case where there can already be a completely different relationship for the same nodes (coming from a different Upsilon).
+
+        The fix is very simple thanks to a suggestion by Phil: we just remove all relationships referring to the shadow node just before executing an Upsilon.
+        This is correct since the upsilon effectively kills that shadow node, before making it live again with a different value, and we already aggressively prune the relationshipMaps by liveness.
+
+        * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+
 2020-10-27  Michael Catanzaro  <mcatanzaro@gnome.org>
 

trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp

@@ -1504 +1504 @@
             
         case Upsilon: {
-            setEquivalence(
-                node->child1().node(),
-                NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
+            auto shadowNode = NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow);
+            // We must first remove all relationships involving the shadow node, because setEquivalence does not overwrite them.
+            // Overwriting is only required here because the shadowNodes are not in SSA form (can be written to by several Upsilons).
+            // Another way to think of it, is that we are maintaining the invariant that relationshipMaps are pruned by liveness.
+            kill(shadowNode);
+            setEquivalence(node->child1().node(), shadowNode);
             break;
         }
@@ -1519 +1522 @@
         default:
             break;
+        }
+    }
+
+    void kill(NodeFlowProjection node)
+    {
+        m_relationships.remove(node);
+
+        for (auto& relationships : m_relationships.values()) {
+            unsigned i = 0, j = 0;
+            while (i < relationships.size()) {
+                const Relationship& rel = relationships[i++];
+                ASSERT(rel.left() != node);
+                if (rel.right() != node)
+                    relationships[j++] = rel;
+            }
+            relationships.shrink(j);
         }
     }
@@ -1561 +1580 @@
         
         if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
-            dataLog("    Setting: ", relationship, " (ttl = ", timeToLive, ")\n");
+            dataLogLn("    Setting: ", relationship, " (ttl = ", timeToLive, ")");
 
         auto result = relationshipMap.add(
@@ -1643 +1662 @@
                     ASSERT(filtered.left() == relationship.left());
                     otherRelationship = filtered;
+                    if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
+                        dataLogLn("      filtered: ", filtered);
                     found = true;
                 }
@@ -1700 +1721 @@
             }
         }
-        
+
         if (!found)
             relationships.append(relationship);