Attachment 339168 Details for Bug 185151 – the patch

[patch] the patch

blah.patch (text/plain), 12.14 KB, created by Filip Pizlo on 2018-04-30 17:59:58 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2018-04-30 17:59:58 PDT

Size: 12.14 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 231189)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,46 @@
>+2018-04-30  Filip Pizlo  <fpizlo@apple.com>
>+
>+        B3::demoteValues should be able to handle patchpoint terminals
>+        https://bugs.webkit.org/show_bug.cgi?id=185151
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        If we try to demote a patchpoint terminal then prior to this change we would append a Set to
>+        the basic block that the patchpoint terminated. That's wrong because then the terminal is no
>+        longer the last thing in the block.
>+        
>+        Air encounters this problem in spilling and solves it by doing a fixup afterwards. We can't
>+        really do that because demotion happens as a prerequisite to other transformations.
>+        
>+        One solution might have been to make demoteValues insert a basic block whenever it encounters
>+        this problem. But that would break clients that do CFG analysis before demoteValues and use
>+        the results of the CFG analysis after demoteValues. Taildup does this. Fortunately, taildup
>+        also runs breakCriticalEdges. Probably anyone using demoteValues will use breakCriticalEdges,
>+        so it's not bad to introduce that requirement.
>+        
>+        So, this patch solves the problem by ensuring that breakCriticalEdges treats any patchpoint
>+        terminal as if it had multiple successors. This means that a patchpoint terminal's successors
>+        will only have it as their predecessor. Then, demoteValues just prepends the Set to the
>+        successors of the patchpoint terminal.
>+        
>+        This was probably asymptomatic. It's hard to write a JS test that triggers this, so I added
>+        a unit test in testb3.
>+
>+        * b3/B3BreakCriticalEdges.cpp:
>+        (JSC::B3::breakCriticalEdges):
>+        * b3/B3BreakCriticalEdges.h:
>+        * b3/B3FixSSA.cpp:
>+        (JSC::B3::demoteValues):
>+        (JSC::B3::fixSSA):
>+        * b3/B3FixSSA.h:
>+        * b3/B3Value.cpp:
>+        (JSC::B3::Value::foldIdentity const):
>+        (JSC::B3::Value::performSubstitution):
>+        * b3/B3Value.h:
>+        * b3/testb3.cpp:
>+        (JSC::B3::testDemotePatchpointTerminal):
>+        (JSC::B3::run):
>+
> 2018-04-29  Filip Pizlo  <fpizlo@apple.com>
> 
>         LICM shouldn't hoist nodes if hoisted nodes exited in that code block
>Index: Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2016 Apple Inc. All rights reserved.
>+ * Copyright (C) 2016-2018 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -40,7 +40,10 @@ void breakCriticalEdges(Procedure& proc)
>     BlockInsertionSet insertionSet(proc);
>     
>     for (BasicBlock* block : proc) {
>-        if (block->numSuccessors() <= 1)
>+        // Non-void terminals that are the moral equivalent of jumps trigger critical edge braking
>+        // because of fixSSA's demoteValues.
>+        if (block->numSuccessors() <= 1
>+            && block->last()->type() == Void)
>             continue;
> 
>         for (BasicBlock*& successor : block->successorBlocks()) {
>@@ -57,8 +60,8 @@ void breakCriticalEdges(Procedure& proc)
>         }
>     }
> 
>-    insertionSet.execute();
>-    proc.invalidateCFG();
>+    if (insertionSet.execute())
>+        proc.invalidateCFG();
> }
> 
> } } // namespace JSC::B3
>Index: Source/JavaScriptCore/b3/B3BreakCriticalEdges.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3BreakCriticalEdges.h	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3BreakCriticalEdges.h	(working copy)
>@@ -31,7 +31,7 @@ namespace JSC { namespace B3 {
> 
> class Procedure;
> 
>-void breakCriticalEdges(Procedure&);
>+JS_EXPORT_PRIVATE void breakCriticalEdges(Procedure&);
> 
> } } // namespace JSC::B3
> 
>Index: Source/JavaScriptCore/b3/B3FixSSA.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3FixSSA.cpp	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3FixSSA.cpp	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
>+ * Copyright (C) 2016-2018 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -172,6 +172,7 @@ void fixSSAGlobally(Procedure& proc)
>     TimingScope timingScope("fixSSA: convert");
>     InsertionSet insertionSet(proc);
>     IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
>+    IndexSet<Value*> valuesToDelete;
>     for (BasicBlock* block : proc.blocksInPreOrder()) {
>         mapping.clear();
>         
>@@ -207,6 +208,7 @@ void fixSSAGlobally(Procedure& proc)
>                 Variable* variable = variableValue->variable();
> 
>                 value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
>+                valuesToDelete.add(value);
>                 break;
>             }
>                 
>@@ -240,12 +242,25 @@ void fixSSAGlobally(Procedure& proc)
>                 }
>                 
>                 insertionSet.insert<UpsilonValue>(
>-                    upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
>+                    upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
>             }
>         }
> 
>         insertionSet.execute(block);
>     }
>+    
>+    // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
>+    // useful for phases that do size estimates.
>+    for (BasicBlock* block : proc) {
>+        block->values().removeAllMatching(
>+            [&] (Value* value) -> bool {
>+                if (!valuesToDelete.contains(value) && value->opcode() != Nop)
>+                    return false;
>+                
>+                proc.deleteValue(value);
>+                return true;
>+            });
>+    }
> 
>     if (B3FixSSAInternal::verbose) {
>         dataLog("B3 after SSA conversion:\n");
>@@ -285,6 +300,15 @@ void demoteValues(Procedure& proc, const
>     // Change accesses to the values to accesses to the stack slots.
>     InsertionSet insertionSet(proc);
>     for (BasicBlock* block : proc) {
>+        if (block->numPredecessors()) {
>+            Value* value = block->predecessor(0)->last();
>+            Variable* variable = map.get(value);
>+            if (variable) {
>+                RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
>+                insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
>+            }
>+        }
>+        
>         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
>             Value* value = block->at(valueIndex);
> 
>@@ -312,8 +336,10 @@ void demoteValues(Procedure& proc, const
>             }
> 
>             if (Variable* variable = map.get(value)) {
>-                insertionSet.insert<VariableValue>(
>-                    valueIndex + 1, Set, value->origin(), variable, value);
>+                if (valueIndex + 1 < block->size()) {
>+                    insertionSet.insert<VariableValue>(
>+                        valueIndex + 1, Set, value->origin(), variable, value);
>+                }
>             }
>         }
>         insertionSet.execute(block);
>@@ -324,6 +350,9 @@ bool fixSSA(Procedure& proc)
> {
>     PhaseScope phaseScope(proc, "fixSSA");
> 
>+    if (proc.variables().isEmpty())
>+        return false;
>+    
>     // Lots of variables have trivial local liveness. We can allocate those without any
>     // trouble.
>     fixSSALocally(proc);
>@@ -336,7 +365,6 @@ bool fixSSA(Procedure& proc)
>     if (proc.variables().isEmpty())
>         return false;
>     
>-    // We know that we have variables to optimize, so do that now.
>     breakCriticalEdges(proc);
> 
>     fixSSAGlobally(proc);
>Index: Source/JavaScriptCore/b3/B3FixSSA.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3FixSSA.h	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3FixSSA.h	(working copy)
>@@ -37,7 +37,7 @@ class Procedure;
> 
> // Turns all mentions of the given values into accesses to variables. This is meant to be used
> // from phases that don't like SSA for whatever reason.
>-void demoteValues(Procedure&, const IndexSet<Value*>&);
>+JS_EXPORT_PRIVATE void demoteValues(Procedure&, const IndexSet<Value*>&);
> 
> // This fixes SSA for you. Use this after you have done demoteValues() and you have performed
> // whatever evil transformation you needed.
>Index: Source/JavaScriptCore/b3/B3Value.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3Value.cpp	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3Value.cpp	(working copy)
>@@ -778,13 +778,21 @@ ValueKey Value::key() const
>     }
> }
> 
>+Value* Value::foldIdentity() const
>+{
>+    Value* current = const_cast<Value*>(this);
>+    while (current->opcode() == Identity)
>+        current = current->child(0);
>+    return current;
>+}
>+
> bool Value::performSubstitution()
> {
>     bool result = false;
>     for (Value*& child : children()) {
>-        while (child->opcode() == Identity) {
>+        if (child->opcode() == Identity) {
>             result = true;
>-            child = child->child(0);
>+            child = child->foldIdentity();
>         }
>     }
>     return result;
>Index: Source/JavaScriptCore/b3/B3Value.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3Value.h	(revision 231186)
>+++ Source/JavaScriptCore/b3/B3Value.h	(working copy)
>@@ -260,6 +260,8 @@ public:
>     // empty ValueKey if this Value is impure. Note that an operation that returns Void could still
>     // have a non-empty ValueKey. This happens for example with Check operations.
>     ValueKey key() const;
>+    
>+    Value* foldIdentity() const;
> 
>     // Makes sure that none of the children are Identity's. If a child points to Identity, this will
>     // repoint it at the Identity's child. For simplicity, this will follow arbitrarily long chains
>Index: Source/JavaScriptCore/b3/testb3.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/testb3.cpp	(revision 231186)
>+++ Source/JavaScriptCore/b3/testb3.cpp	(working copy)
>@@ -32,6 +32,7 @@
> #include "B3ArgumentRegValue.h"
> #include "B3AtomicValue.h"
> #include "B3BasicBlockInlines.h"
>+#include "B3BreakCriticalEdges.h"
> #include "B3CCallValue.h"
> #include "B3Compilation.h"
> #include "B3Compile.h"
>@@ -40,6 +41,7 @@
> #include "B3ConstPtrValue.h"
> #include "B3Effects.h"
> #include "B3FenceValue.h"
>+#include "B3FixSSA.h"
> #include "B3Generate.h"
> #include "B3LowerToAir.h"
> #include "B3MathExtras.h"
>@@ -69,6 +71,7 @@
> #include <cmath>
> #include <string>
> #include <wtf/FastTLS.h>
>+#include <wtf/IndexSet.h>
> #include <wtf/ListDump.h>
> #include <wtf/Lock.h>
> #include <wtf/NumberOfCores.h>
>@@ -16210,6 +16213,27 @@ void testShuffleDoesntTrashCalleeSaves()
>     fastFree(inputPtr);
> }
> 
>+void testDemotePatchpointTerminal()
>+{
>+    Procedure proc;
>+    
>+    BasicBlock* root = proc.addBlock();
>+    BasicBlock* done = proc.addBlock();
>+    
>+    PatchpointValue* patchpoint = root->appendNew<PatchpointValue>(proc, Int32, Origin());
>+    patchpoint->effects.terminal = true;
>+    root->setSuccessors(done);
>+    
>+    done->appendNew<Value>(proc, Return, Origin(), patchpoint);
>+    
>+    proc.resetReachability();
>+    breakCriticalEdges(proc);
>+    IndexSet<Value*> valuesToDemote;
>+    valuesToDemote.add(patchpoint);
>+    demoteValues(proc, valuesToDemote);
>+    validate(proc);
>+}
>+
> // Make sure the compiler does not try to optimize anything out.
> NEVER_INLINE double zero()
> {
>@@ -17777,6 +17801,7 @@ void run(const char* filter)
>     RUN(testFloatEqualOrUnorderedDontFold());
>     
>     RUN(testShuffleDoesntTrashCalleeSaves());
>+    RUN(testDemotePatchpointTerminal());
> 
>     if (isX86()) {
>         RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));

Flags:

saam: review+

Actions: View | Formatted Diff | Diff

Attachments on bug 185151: 339168