Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (214882 => 214883)
--- trunk/Source/_javascript_Core/ChangeLog 2017-04-04 16:12:17 UTC (rev 214882)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-04-04 17:20:43 UTC (rev 214883)
@@ -1,3 +1,31 @@
+2017-04-03 Filip Pizlo <[email protected]>
+
+ Air liveness should build constraints and solve them rather than repeatedly parsing IR
+ https://bugs.webkit.org/show_bug.cgi?id=170421
+
+ Reviewed by Saam Barati.
+
+ Inst::forEach<> is expensive. The LivenessAdapter uses forEach with a particularly
+ gnarly lambda that has many extra checks. Therefore, a lot of the time spent in
+ liveness analysis is just recomputing forEach<> and that lambda to get uses and defs.
+
+ This introduces LivenessConstraints<>, which is a liveness constraint system based on
+ Adapter. It basically caches the results of doing forEach. It'll give you the uses and
+ defs at each instruction boundary.
+
+ This is a ~5% compile time progression at optLevel=1. It's also a ~3% compile time
+ progression at optLevel=2.
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * b3/air/AirLivenessAdapter.h:
+ (JSC::B3::Air::LivenessAdapter::LivenessAdapter):
+ (JSC::B3::Air::LivenessAdapter::forEachUse):
+ (JSC::B3::Air::LivenessAdapter::forEachDef):
+ * b3/air/AirLivenessConstraints.h: Added.
+ (JSC::B3::Air::LivenessConstraints::Actions::Actions):
+ (JSC::B3::Air::LivenessConstraints::LivenessConstraints):
+ (JSC::B3::Air::LivenessConstraints::at):
+
2017-04-03 Mark Lam <[email protected]>
Fix incorrect capacity delta calculation reported in SparseArrayValueMap::add().
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (214882 => 214883)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-04-04 16:12:17 UTC (rev 214882)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-04-04 17:20:43 UTC (rev 214883)
@@ -119,6 +119,7 @@
0F15F15F14B7A73E005DE37D /* CommonSlowPaths.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F15F15D14B7A73A005DE37D /* CommonSlowPaths.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F1725FF1B48719A00AC3A55 /* DFGMinifiedGraph.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F1725FE1B48719A00AC3A55 /* DFGMinifiedGraph.cpp */; };
0F1829691E92EE54005B1EA8 /* AirLivenessAdapter.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1829681E92EE51005B1EA8 /* AirLivenessAdapter.h */; };
+ 0F18296B1E92F6DC005B1EA8 /* AirLivenessConstraints.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F18296A1E92F6DA005B1EA8 /* AirLivenessConstraints.h */; };
0F18D3CF1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F18D3CD1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.cpp */; };
0F18D3D01B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F18D3CE1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h */; };
0F190CAC189D82F6000AE5F0 /* ProfilerJettisonReason.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F190CAA189D82F6000AE5F0 /* ProfilerJettisonReason.cpp */; };
@@ -2654,6 +2655,7 @@
0F15F15D14B7A73A005DE37D /* CommonSlowPaths.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CommonSlowPaths.h; sourceTree = "<group>"; };
0F1725FE1B48719A00AC3A55 /* DFGMinifiedGraph.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGMinifiedGraph.cpp; path = dfg/DFGMinifiedGraph.cpp; sourceTree = "<group>"; };
0F1829681E92EE51005B1EA8 /* AirLivenessAdapter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLivenessAdapter.h; path = b3/air/AirLivenessAdapter.h; sourceTree = "<group>"; };
+ 0F18296A1E92F6DA005B1EA8 /* AirLivenessConstraints.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLivenessConstraints.h; path = b3/air/AirLivenessConstraints.h; sourceTree = "<group>"; };
0F18D3CD1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGAdaptiveStructureWatchpoint.cpp; path = dfg/DFGAdaptiveStructureWatchpoint.cpp; sourceTree = "<group>"; };
0F18D3CE1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAdaptiveStructureWatchpoint.h; path = dfg/DFGAdaptiveStructureWatchpoint.h; sourceTree = "<group>"; };
0F190CAA189D82F6000AE5F0 /* ProfilerJettisonReason.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ProfilerJettisonReason.cpp; path = profiler/ProfilerJettisonReason.cpp; sourceTree = "<group>"; };
@@ -5613,6 +5615,7 @@
0FDF67D51D9DC43E001B9825 /* AirKind.h */,
2684D4371C00161C0081D663 /* AirLiveness.h */,
0F1829681E92EE51005B1EA8 /* AirLivenessAdapter.h */,
+ 0F18296A1E92F6DA005B1EA8 /* AirLivenessConstraints.h */,
0FE34C171C4B39AE0003A512 /* AirLogRegisterPressure.cpp */,
0FE34C181C4B39AE0003A512 /* AirLogRegisterPressure.h */,
0F6183251C45BF070072450B /* AirLowerAfterRegAlloc.cpp */,
@@ -8966,6 +8969,7 @@
2A4BB7F318A41179008A0FCD /* JSManagedValueInternal.h in Headers */,
A700874217CBE8EB00C3E643 /* JSMap.h in Headers */,
A74DEF96182D991400522C22 /* JSMapIterator.h in Headers */,
+ 0F18296B1E92F6DC005B1EA8 /* AirLivenessConstraints.h in Headers */,
9959E92D1BD17FA4001AA413 /* jsmin.py in Headers */,
E3D239C91B829C1C00BBEF67 /* JSModuleEnvironment.h in Headers */,
D9722752DC54459B9125B539 /* JSModuleLoader.h in Headers */,
Modified: trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h (214882 => 214883)
--- trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h 2017-04-04 16:12:17 UTC (rev 214882)
+++ trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h 2017-04-04 17:20:43 UTC (rev 214883)
@@ -31,6 +31,7 @@
#include "AirCFG.h"
#include "AirCode.h"
#include "AirInstInlines.h"
+#include "AirLivenessConstraints.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
@@ -42,6 +43,7 @@
LivenessAdapter(Code& code)
: code(code)
+ , constraints(code)
{
}
@@ -53,52 +55,19 @@
template<typename Func>
void forEachUse(BasicBlock* block, size_t instBoundaryIndex, const Func& func)
{
- if (Inst* prevInst = block->get(instBoundaryIndex - 1)) {
- prevInst->forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- func(Adapter::valueToIndex(thing));
- });
- }
-
- if (Inst* nextInst = block->get(instBoundaryIndex)) {
- nextInst->forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- func(Adapter::valueToIndex(thing));
- });
- }
+ for (unsigned index : constraints.at(block, instBoundaryIndex).use)
+ func(index);
}
template<typename Func>
void forEachDef(BasicBlock* block, size_t instBoundaryIndex, const Func& func)
{
- if (Inst* prevInst = block->get(instBoundaryIndex - 1)) {
- prevInst->forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- func(Adapter::valueToIndex(thing));
- });
- }
-
- if (Inst* nextInst = block->get(instBoundaryIndex)) {
- nextInst->forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- func(Adapter::valueToIndex(thing));
- });
- }
+ for (unsigned index : constraints.at(block, instBoundaryIndex).def)
+ func(index);
}
Code& code;
+ LivenessConstraints<Adapter> constraints;
};
template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
Added: trunk/Source/_javascript_Core/b3/air/AirLivenessConstraints.h (0 => 214883)
--- trunk/Source/_javascript_Core/b3/air/AirLivenessConstraints.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirLivenessConstraints.h 2017-04-04 17:20:43 UTC (rev 214883)
@@ -0,0 +1,94 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "AirBasicBlock.h"
+#include "AirCode.h"
+#include "AirInstInlines.h"
+#include <wtf/IndexMap.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+template<typename Adapter>
+class LivenessConstraints {
+public:
+ typedef Vector<unsigned, 4> ActionsList;
+
+ struct Actions {
+ Actions() { }
+
+ ActionsList use;
+ ActionsList def;
+ };
+
+ typedef Vector<Actions, 0, UnsafeVectorOverflow> ActionsForBoundary;
+
+ LivenessConstraints(Code& code)
+ : m_code(code)
+ , m_actions(code.size())
+ {
+ for (BasicBlock* block : m_code) {
+ ActionsForBoundary& actionsForBoundary = m_actions[block];
+ actionsForBoundary.resize(block->size() + 1);
+
+ for (size_t instIndex = block->size(); instIndex--;) {
+ Inst& inst = block->at(instIndex);
+ inst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (!Adapter::acceptsBank(bank) || !Adapter::acceptsRole(role))
+ return;
+
+ unsigned index = Adapter::valueToIndex(thing);
+
+ if (Arg::isEarlyUse(role))
+ actionsForBoundary[instIndex].use.appendIfNotContains(index);
+ if (Arg::isEarlyDef(role))
+ actionsForBoundary[instIndex].def.appendIfNotContains(index);
+ if (Arg::isLateUse(role))
+ actionsForBoundary[instIndex + 1].use.appendIfNotContains(index);
+ if (Arg::isLateDef(role))
+ actionsForBoundary[instIndex + 1].def.appendIfNotContains(index);
+ });
+ }
+ }
+ }
+
+ Actions& at(BasicBlock* block, unsigned instBoundaryIndex)
+ {
+ return m_actions[block][instBoundaryIndex];
+ }
+
+private:
+ Code& m_code;
+ IndexMap<BasicBlock*, ActionsForBoundary> m_actions;
+};
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
Modified: trunk/Source/WTF/ChangeLog (214882 => 214883)
--- trunk/Source/WTF/ChangeLog 2017-04-04 16:12:17 UTC (rev 214882)
+++ trunk/Source/WTF/ChangeLog 2017-04-04 17:20:43 UTC (rev 214883)
@@ -1,3 +1,13 @@
+2017-04-03 Filip Pizlo <[email protected]>
+
+ Air liveness should build constraints and solve them rather than repeatedly parsing IR
+ https://bugs.webkit.org/show_bug.cgi?id=170421
+
+ Reviewed by Saam Barati.
+
+ * wtf/Vector.h:
+ (WTF::minCapacity>::appendIfNotContains): Because sometimes Vector<> is the best kind of set.
+
2017-04-03 Yusuke Suzuki <[email protected]>
[WTF] Introduce WTF::RandomDevice which keeps /dev/urandom opened
Modified: trunk/Source/WTF/wtf/Vector.h (214882 => 214883)
--- trunk/Source/WTF/wtf/Vector.h 2017-04-04 16:12:17 UTC (rev 214882)
+++ trunk/Source/WTF/wtf/Vector.h 2017-04-04 17:20:43 UTC (rev 214883)
@@ -706,6 +706,8 @@
template<typename U> bool contains(const U&) const;
template<typename U> size_t find(const U&) const;
template<typename U> size_t reverseFind(const U&) const;
+
+ template<typename U> bool appendIfNotContains(const U&);
void shrink(size_t size);
void grow(size_t size);
@@ -926,6 +928,16 @@
}
template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+template<typename U>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendIfNotContains(const U& value)
+{
+ if (contains(value))
+ return false;
+ append(value);
+ return true;
+}
+
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
{
if (size() > newSize)
