webkitgtk-2.16.5HEADwebkitgtk-2.16.5master

1 files changed, 270 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/b3/B3FixSSA.cpp b/Source/JavaScriptCore/b3/B3FixSSA.cpp
new file mode 100644
index 000000000..730c2c876
--- /dev/null
+++ b/Source/JavaScriptCore/b3/B3FixSSA.cpp
@@ -0,0 +1,270 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "B3FixSSA.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BreakCriticalEdges.h"
+#include "B3Dominators.h"
+#include "B3InsertionSetInlines.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3SSACalculator.h"
+#include "B3UpsilonValue.h"
+#include "B3ValueInlines.h"
+#include "B3Variable.h"
+#include "B3VariableValue.h"
+#include <wtf/CommaPrinter.h>
+#include <wtf/IndexSet.h>
+
+namespace JSC { namespace B3 {
+
+namespace {
+const bool verbose = false;
+} // anonymous namespace
+
+void demoteValues(Procedure& proc, const IndexSet<Value>& values)
+{
+    HashMap<Value*, Variable*> map;
+    HashMap<Value*, Variable*> phiMap;
+
+    // Create stack slots.
+    for (Value* value : values.values(proc.values())) {
+        map.add(value, proc.addVariable(value->type()));
+
+        if (value->opcode() == Phi)
+            phiMap.add(value, proc.addVariable(value->type()));
+    }
+
+    if (verbose) {
+        dataLog("Demoting values as follows:\n");
+        dataLog("   map = ");
+        CommaPrinter comma;
+        for (auto& entry : map)
+            dataLog(comma, *entry.key, "=>", *entry.value);
+        dataLog("\n");
+        dataLog("   phiMap = ");
+        comma = CommaPrinter();
+        for (auto& entry : phiMap)
+            dataLog(comma, *entry.key, "=>", *entry.value);
+        dataLog("\n");
+    }
+
+    // Change accesses to the values to accesses to the stack slots.
+    InsertionSet insertionSet(proc);
+    for (BasicBlock* block : proc) {
+        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+            Value* value = block->at(valueIndex);
+
+            if (value->opcode() == Phi) {
+                if (Variable* variable = phiMap.get(value)) {
+                    value->replaceWithIdentity(
+                        insertionSet.insert<VariableValue>(
+                            valueIndex, Get, value->origin(), variable));
+                }
+            } else {
+                for (Value*& child : value->children()) {
+                    if (Variable* variable = map.get(child)) {
+                        child = insertionSet.insert<VariableValue>(
+                            valueIndex, Get, value->origin(), variable);
+                    }
+                }
+
+                if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
+                    if (Variable* variable = phiMap.get(upsilon->phi())) {
+                        insertionSet.insert<VariableValue>(
+                            valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
+                        value->replaceWithNop();
+                    }
+                }
+            }
+
+            if (Variable* variable = map.get(value)) {
+                insertionSet.insert<VariableValue>(
+                    valueIndex + 1, Set, value->origin(), variable, value);
+            }
+        }
+        insertionSet.execute(block);
+    }
+}
+
+bool fixSSA(Procedure& proc)
+{
+    PhaseScope phaseScope(proc, "fixSSA");
+
+    // Just for sanity, remove any unused variables first. It's unlikely that this code has any
+    // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
+    // it did arise.
+    IndexSet<Variable> liveVariables;
+    for (Value* value : proc.values()) {
+        if (VariableValue* variableValue = value->as<VariableValue>())
+            liveVariables.add(variableValue->variable());
+    }
+
+    for (Variable* variable : proc.variables()) {
+        if (!liveVariables.contains(variable))
+            proc.deleteVariable(variable);
+    }
+
+    if (proc.variables().isEmpty())
+        return false;
+
+    // We know that we have variables to optimize, so do that now.
+    breakCriticalEdges(proc);
+
+    SSACalculator ssa(proc);
+
+    // Create a SSACalculator::Variable ("calcVar") for every variable.
+    Vector<Variable*> calcVarToVariable;
+    IndexMap<Variable, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
+
+    for (Variable* variable : proc.variables()) {
+        SSACalculator::Variable* calcVar = ssa.newVariable();
+        RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
+        calcVarToVariable.append(variable);
+        variableToCalcVar[variable] = calcVar;
+    }
+
+    // Create Defs for all of the stores to the stack variable.
+    for (BasicBlock* block : proc) {
+        for (Value* value : *block) {
+            if (value->opcode() != Set)
+                continue;
+
+            Variable* variable = value->as<VariableValue>()->variable();
+
+            if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
+                ssa.newDef(calcVar, block, value->child(0));
+        }
+    }
+
+    // Decide where Phis are to be inserted. This creates them but does not insert them.
+    ssa.computePhis(
+        [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
+            Variable* variable = calcVarToVariable[calcVar->index()];
+            Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
+            if (verbose) {
+                dataLog(
+                    "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
+                    deepDump(proc, phi), "\n");
+            }
+            return phi;
+        });
+
+    // Now perform the conversion.
+    InsertionSet insertionSet(proc);
+    IndexMap<Variable, Value*> mapping(proc.variables().size());
+    for (BasicBlock* block : proc.blocksInPreOrder()) {
+        mapping.clear();
+
+        for (unsigned index = calcVarToVariable.size(); index--;) {
+            Variable* variable = calcVarToVariable[index];
+            SSACalculator::Variable* calcVar = ssa.variable(index);
+
+            SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
+            if (def)
+                mapping[variable] = def->value();
+        }
+
+        for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
+            Variable* variable = calcVarToVariable[phiDef->variable()->index()];
+
+            insertionSet.insertValue(0, phiDef->value());
+            mapping[variable] = phiDef->value();
+        }
+
+        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+            Value* value = block->at(valueIndex);
+            value->performSubstitution();
+
+            switch (value->opcode()) {
+            case Get: {
+                VariableValue* variableValue = value->as<VariableValue>();
+                Variable* variable = variableValue->variable();
+
+                if (Value* replacement = mapping[variable])
+                    value->replaceWithIdentity(replacement);
+                else {
+                    value->replaceWithIdentity(
+                        insertionSet.insertBottom(valueIndex, value));
+                }
+                break;
+            }
+                
+            case Set: {
+                VariableValue* variableValue = value->as<VariableValue>();
+                Variable* variable = variableValue->variable();
+
+                mapping[variable] = value->child(0);
+                value->replaceWithNop();
+                break;
+            }
+
+            default:
+                break;
+            }
+        }
+
+        unsigned upsilonInsertionPoint = block->size() - 1;
+        Origin upsilonOrigin = block->last()->origin();
+        for (BasicBlock* successorBlock : block->successorBlocks()) {
+            for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
+                Value* phi = phiDef->value();
+                SSACalculator::Variable* calcVar = phiDef->variable();
+                Variable* variable = calcVarToVariable[calcVar->index()];
+
+                Value* mappedValue = mapping[variable];
+                if (verbose) {
+                    dataLog(
+                        "Mapped value for ", *variable, " with successor Phi ", *phi,
+                        " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
+                }
+                
+                if (!mappedValue)
+                    mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
+                
+                insertionSet.insert<UpsilonValue>(
+                    upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
+            }
+        }
+
+        insertionSet.execute(block);
+    }
+
+    if (verbose) {
+        dataLog("B3 after SSA conversion:\n");
+        dataLog(proc);
+    }
+
+    return true;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+