Diff
Modified: trunk/LayoutTests/ChangeLog (201181 => 201182)
--- trunk/LayoutTests/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/LayoutTests/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,3 +1,25 @@
+2016-05-18 Filip Pizlo <fpi...@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ Add tests for LICM hoisting things that would only exit if hoisted.
+
+ * js/regress/licm-dragons-expected.txt: Added.
+ * js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
+ * js/regress/licm-dragons-out-of-bounds.html: Added.
+ * js/regress/licm-dragons-overflow-expected.txt: Added.
+ * js/regress/licm-dragons-overflow.html: Added.
+ * js/regress/licm-dragons.html: Added.
+ * js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
+ (foo):
+ * js/regress/script-tests/licm-dragons-overflow.js: Added.
+ (foo):
+ * js/regress/script-tests/licm-dragons.js: Added.
+ (foo):
+
2016-05-19 Brian Burg <bb...@apple.com>
Web Inspector: use a consistent prefix for injected scripts
Added: trunk/LayoutTests/js/regress/licm-dragons-expected.txt (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons-out-of-bounds
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons-overflow
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/licm-dragons-overflow.html (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons-overflow.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-overflow.html 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/licm-dragons.html (0 => 201182)
--- trunk/LayoutTests/js/regress/licm-dragons.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons.html 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js (0 => 201182)
--- trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,30 @@
+function foo(p, o, i) {
+ var result = 0;
+ for (var j = 0; j < 1000; ++j) {
+ if (p)
+ result += o[i];
+ else
+ result++;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var o = [42];
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, o, 0);
+ result += foo(false, o, 1);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, o, 1);
+
+for (var i = 0; i < 20000; ++i)
+ result += foo(true, o, 0);
+
+if (result != 893000000)
+ throw "Error: bad result: " + result;
Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js (0 => 201182)
--- trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,28 @@
+function foo(p, a, b) {
+ var result = 0;
+ for (var i = 0; i < 1000; ++i) {
+ if (p)
+ result += a + b;
+ else
+ result += a - b;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, 1, 2);
+ result += foo(false, 2000000000, 2000000000);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, 2000000000, 2000000000);
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(true, 1, 2);
+
+if (result != 33000000)
+ throw "Error: bad result: " + result;
Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons.js (0 => 201182)
--- trunk/LayoutTests/js/regress/script-tests/licm-dragons.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons.js 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,31 @@
+function foo(p, o) {
+ var result = 0;
+ for (var i = 0; i < 1000; ++i) {
+ if (p)
+ result += o.f;
+ else
+ result++;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var o = {f:42};
+var p = {};
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, o);
+ result += foo(false, p);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, p);
+
+for (var i = 0; i < 30000; ++i)
+ result += foo(true, o);
+
+if (result != 1313000000)
+ throw "Error: bad result: " + result;
Modified: trunk/Source/_javascript_Core/ChangeLog (201181 => 201182)
--- trunk/Source/_javascript_Core/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,3 +1,98 @@
+2016-05-18 Filip Pizlo <fpi...@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
+ dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
+ the execution of one implies that the other one must also execute. It means that the two
+ blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
+ A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
+ this has caused problems in the past. If we hoist something that may exit from a block that
+ was not control equivalent to the pre-header then it's possible that the node's speculation
+ will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
+ origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
+ turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
+ HoistingFailed exit kind.
+
+ Note that this deliberately still allows us to hoist things that may exit even if they are
+ not control equivalent to the pre-header. This is necessary because the profitability of
+ hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
+ shot.
+
+ This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
+ operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
+ and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
+ problems on that program even though LICM previously did the wrong thing).
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * bytecode/ExitKind.cpp:
+ (JSC::exitKindToString):
+ * bytecode/ExitKind.h:
+ * dfg/DFGAtTailAbstractState.h:
+ (JSC::DFG::AtTailAbstractState::operator bool):
+ (JSC::DFG::AtTailAbstractState::initializeTo):
+ * dfg/DFGBackwardsCFG.h: Added.
+ (JSC::DFG::BackwardsCFG::BackwardsCFG):
+ * dfg/DFGBackwardsDominators.h: Added.
+ (JSC::DFG::BackwardsDominators::BackwardsDominators):
+ * dfg/DFGCommon.h:
+ (JSC::DFG::checkAndSet): Deleted.
+ * dfg/DFGControlEquivalenceAnalysis.h: Added.
+ (JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
+ (JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
+ (JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dump):
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::invalidateCFG):
+ (JSC::DFG::Graph::substituteGetLocal):
+ (JSC::DFG::Graph::handleAssertionFailure):
+ (JSC::DFG::Graph::ensureDominators):
+ (JSC::DFG::Graph::ensurePrePostNumbering):
+ (JSC::DFG::Graph::ensureNaturalLoops):
+ (JSC::DFG::Graph::ensureBackwardsCFG):
+ (JSC::DFG::Graph::ensureBackwardsDominators):
+ (JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
+ (JSC::DFG::Graph::methodOfGettingAValueProfileFor):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::hasDebuggerEnabled):
+ * dfg/DFGInPlaceAbstractState.h:
+ (JSC::DFG::InPlaceAbstractState::operator bool):
+ (JSC::DFG::InPlaceAbstractState::createValueForNode):
+ (JSC::DFG::InPlaceAbstractState::forNode):
+ * dfg/DFGLICMPhase.cpp:
+ (JSC::DFG::LICMPhase::run):
+ (JSC::DFG::LICMPhase::attemptHoist):
+ * dfg/DFGMayExit.cpp:
+ (JSC::DFG::mayExit):
+ * dfg/DFGMayExit.h:
+ * dfg/DFGNode.h:
+ * dfg/DFGNodeOrigin.cpp:
+ (JSC::DFG::NodeOrigin::dump):
+ * dfg/DFGNodeOrigin.h:
+ (JSC::DFG::NodeOrigin::takeValidExit):
+ (JSC::DFG::NodeOrigin::withWasHoisted):
+ (JSC::DFG::NodeOrigin::forInsertingAfter):
+ * dfg/DFGNullAbstractState.h: Added.
+ (JSC::DFG::NullAbstractState::NullAbstractState):
+ (JSC::DFG::NullAbstractState::operator bool):
+ (JSC::DFG::NullAbstractState::forNode):
+ * dfg/DFGOSRExit.cpp:
+ (JSC::DFG::OSRExit::OSRExit):
+ * dfg/DFGOSRExitBase.cpp:
+ (JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
+ * dfg/DFGOSRExitBase.h:
+ (JSC::DFG::OSRExitBase::OSRExitBase):
+ * dfg/DFGTypeCheckHoistingPhase.cpp:
+ (JSC::DFG::TypeCheckHoistingPhase::run):
+ * ftl/FTLOSRExit.cpp:
+ (JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
+ (JSC::FTL::OSRExit::OSRExit):
+ * ftl/FTLOSRExit.h:
+
2016-05-19 Mark Lam <mark....@apple.com>
Code that null checks the VM pointer before any use should ref the VM.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (201181 => 201182)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1998,6 +1998,10 @@
DC605B601CE26EA700593718 /* ProfilerUID.h in Headers */ = {isa = PBXBuildFile; fileRef = DC605B5C1CE26E9800593718 /* ProfilerUID.h */; settings = {ATTRIBUTES = (Private, ); }; };
DC7997831CDE9FA0004D4A09 /* TagRegistersMode.h in Headers */ = {isa = PBXBuildFile; fileRef = DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
DC7997841CDE9FA2004D4A09 /* TagRegistersMode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */; };
+ DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */; };
+ DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */; };
+ DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */; };
+ DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */; };
DCF3D5691CD2946D003D5C65 /* LazyClassStructure.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */; };
DCF3D56A1CD29470003D5C65 /* LazyClassStructure.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */; settings = {ATTRIBUTES = (Private, ); }; };
DCF3D56B1CD29472003D5C65 /* LazyClassStructureInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */; };
@@ -4216,6 +4220,10 @@
DC605B5C1CE26E9800593718 /* ProfilerUID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ProfilerUID.h; path = profiler/ProfilerUID.h; sourceTree = "<group>"; };
DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TagRegistersMode.cpp; sourceTree = "<group>"; };
DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TagRegistersMode.h; sourceTree = "<group>"; };
+ DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsCFG.h; path = dfg/DFGBackwardsCFG.h; sourceTree = "<group>"; };
+ DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsDominators.h; path = dfg/DFGBackwardsDominators.h; sourceTree = "<group>"; };
+ DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGControlEquivalenceAnalysis.h; path = dfg/DFGControlEquivalenceAnalysis.h; sourceTree = "<group>"; };
+ DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNullAbstractState.h; path = dfg/DFGNullAbstractState.h; sourceTree = "<group>"; };
DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LazyClassStructure.cpp; sourceTree = "<group>"; };
DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructure.h; sourceTree = "<group>"; };
DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructureInlines.h; sourceTree = "<group>"; };
@@ -6131,6 +6139,8 @@
0F666EC31835672B00D017F1 /* DFGAvailability.h */,
0F2B9CD619D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp */,
0F2B9CD719D0BA7D00B1D1B5 /* DFGAvailabilityMap.h */,
+ DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */,
+ DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */,
0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */,
@@ -6177,6 +6187,7 @@
0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */,
0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */,
+ DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */,
0FBE0F6B16C1DB010082C5E8 /* DFGCPSRethreadingPhase.cpp */,
0FBE0F6C16C1DB010082C5E8 /* DFGCPSRethreadingPhase.h */,
A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */,
@@ -6288,6 +6299,7 @@
0F5D085C1B8CF99D001143B4 /* DFGNodeOrigin.cpp */,
0F300B7718AB051100A6D72E /* DFGNodeOrigin.h */,
0FA581B9150E952A00B9A2D9 /* DFGNodeType.h */,
+ DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */,
0F2B9CDA19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.cpp */,
0F2B9CDB19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.h */,
0F2B9CDC19D0BA7D00B1D1B5 /* DFGObjectMaterializationData.cpp */,
@@ -6955,6 +6967,7 @@
buildActionMask = 2147483647;
files = (
0FFA549816B8835300B3A982 /* A64DOpcode.h in Headers */,
+ DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */,
0F1FE51C1922A3BC006987C5 /* AbortReason.h in Headers */,
860161E30F3A83C100F84710 /* AbstractMacroAssembler.h in Headers */,
0F55F0F514D1063C00AC7649 /* AbstractPC.h in Headers */,
@@ -6999,6 +7012,7 @@
BC18C3E50E16F5CD00B34460 /* APICast.h in Headers */,
FE3A06BE1C11041200390FDD /* JITLeftShiftGenerator.h in Headers */,
BCF605140E203EF800B9A64D /* ArgList.h in Headers */,
+ DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */,
0FE050141AA9091100D33B33 /* ArgumentsMode.h in Headers */,
0F6B1CB91861244C00845D97 /* ArityCheckMode.h in Headers */,
A1A009C11831A26E00CF8711 /* ARM64Assembler.h in Headers */,
@@ -7912,6 +7926,7 @@
0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */,
0F13912A16771C36009CCB07 /* ProfilerBytecodeSequence.h in Headers */,
0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */,
+ DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */,
0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
0F4A38FA1C8E13DF00190318 /* SuperSampler.h in Headers */,
@@ -8056,6 +8071,7 @@
141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
2684D4381C00161C0081D663 /* AirLiveness.h in Headers */,
0F55989817C86C5800A1E543 /* ToNativeFromValue.h in Headers */,
+ DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */,
0F2D4DE919832DAC007D4B19 /* ToThisStatus.h in Headers */,
0F952ABD1B487A7700C367C5 /* TrackedReferences.h in Headers */,
0F2B670617B6B5AB00A7AE3F /* TypedArrayAdaptors.h in Headers */,
Modified: trunk/Source/_javascript_Core/bytecode/ExitKind.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/bytecode/ExitKind.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/bytecode/ExitKind.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-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
@@ -76,6 +76,8 @@
return "VarargsOverflow";
case TDZFailure:
return "TDZFailure";
+ case HoistingFailed:
+ return "HoistingFailed";
case Uncountable:
return "Uncountable";
case UncountableInvalidation:
Modified: trunk/Source/_javascript_Core/bytecode/ExitKind.h (201181 => 201182)
--- trunk/Source/_javascript_Core/bytecode/ExitKind.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/bytecode/ExitKind.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-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
@@ -50,6 +50,7 @@
NotStringObject, // We exited because we shouldn't have attempted to optimize string object access.
VarargsOverflow, // We exited because a varargs call passed more arguments than we expected.
TDZFailure, // We exited because we were in the TDZ and accessed the variable.
+ HoistingFailed, // Something that was hoisted exited. So, assume that hoisting is a bad idea.
Uncountable, // We exited for none of the above reasons, and we should not count it. Most uses of this should be viewed as a FIXME.
UncountableInvalidation, // We exited because the code block was invalidated; this means that we've already counted the reasons why the code block was invalidated.
WatchdogTimerFired, // We exited because we need to service the watchdog timer.
Modified: trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 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
@@ -40,6 +40,8 @@
~AtTailAbstractState();
+ explicit operator bool() const { return true; }
+
void initializeTo(BasicBlock* block)
{
m_block = block;
Added: trunk/Source/_javascript_Core/dfg/DFGBackwardsCFG.h (0 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGBackwardsCFG.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGBackwardsCFG.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,51 @@
+/*
+ * 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.
+ */
+
+#ifndef DFGBackwardsCFG_h
+#define DFGBackwardsCFG_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCFG.h"
+#include <wtf/BackwardsGraph.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsCFG : public BackwardsGraph<CFG> {
+ WTF_MAKE_NONCOPYABLE(BackwardsCFG);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ BackwardsCFG(Graph& graph)
+ : BackwardsGraph<CFG>(*graph.m_cfg)
+ {
+ }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBackwardsCFG_h
+
Added: trunk/Source/_javascript_Core/dfg/DFGBackwardsDominators.h (0 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGBackwardsDominators.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGBackwardsDominators.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,52 @@
+/*
+ * 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.
+ */
+
+#ifndef DFGBackwardsDominators_h
+#define DFGBackwardsDominators_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsCFG.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsDominators : public WTF::Dominators<BackwardsCFG> {
+ WTF_MAKE_NONCOPYABLE(BackwardsDominators);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ BackwardsDominators(Graph& graph)
+ : WTF::Dominators<BackwardsCFG>(graph.ensureBackwardsCFG())
+ {
+ }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGDominators_h
Modified: trunk/Source/_javascript_Core/dfg/DFGCommon.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGCommon.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGCommon.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -255,15 +255,6 @@
AfterFixup
};
-template<typename T, typename U>
-bool checkAndSet(T& left, U right)
-{
- if (left == right)
- return false;
- left = right;
- return true;
-}
-
// If possible, this will acquire a lock to make sure that if multiple threads
// start crashing at the same time, you get coherent dump output. Use this only
// when you're forcing a crash with diagnostics.
Added: trunk/Source/_javascript_Core/dfg/DFGControlEquivalenceAnalysis.h (0 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGControlEquivalenceAnalysis.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGControlEquivalenceAnalysis.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,88 @@
+/*
+ * 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.
+ */
+
+#ifndef DFGControlEquivalenceAnalysis_h
+#define DFGControlEquivalenceAnalysis_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsDominators.h"
+#include "DFGDominators.h"
+
+namespace JSC { namespace DFG {
+
+class ControlEquivalenceAnalysis {
+ WTF_MAKE_NONCOPYABLE(ControlEquivalenceAnalysis);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ ControlEquivalenceAnalysis(Graph& graph)
+ : m_dominators(graph.ensureDominators())
+ , m_backwardsDominators(graph.ensureBackwardsDominators())
+ {
+ }
+
+ // This returns true iff:
+ //
+ // - If b executes then a must have executed before it (a dominates b).
+ // - If a executes then b will execute after it (b backwards-dominates a).
+ //
+ // Note that like Dominators and BackwardsDominators, this analysis ignores OSR:
+ //
+ // - This may return true even if we OSR enter in beteen a and b. OSR entry would mean that b
+ // could execute even if a had not executed. This is impossible in DFG SSA but it's possible
+ // in DFG CPS.
+ // - This may return true even if we OSR exit in between a and b. OSR exit would mean that a
+ // could execute even though b will not execute. This is possible in all forms of DFG IR.
+ //
+ // In DFG SSA you only have to worry about the definition being weaked by exits. This is usually
+ // OK, since we use this analysis to determine the cost of moving exits from one block to
+ // another. If we move an exit from b to a and a equivalently dominates b then at worst we have
+ // made the exit happen sooner. If we move an exit from b to a and a dominates b but not
+ // equivalently then we've done something much worse: the program may now exit even if it would
+ // not have ever exited before.
+ bool dominatesEquivalently(BasicBlock* a, BasicBlock* b)
+ {
+ return m_dominators.dominates(a, b)
+ && m_backwardsDominators.dominates(b, a);
+ }
+
+ // This returns true iff the execution of a implies that b also executes and vice-versa.
+ bool areEquivalent(BasicBlock* a, BasicBlock* b)
+ {
+ return dominatesEquivalently(a, b)
+ || dominatesEquivalently(b, a);
+ }
+
+private:
+ Dominators& m_dominators;
+ BackwardsDominators& m_backwardsDominators;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGControlEquivalenceAnalysis_h
+
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -32,10 +32,13 @@
#include "BytecodeLivenessAnalysisInlines.h"
#include "CodeBlock.h"
#include "CodeBlockWithJITType.h"
+#include "DFGBackwardsCFG.h"
+#include "DFGBackwardsDominators.h"
#include "DFGBlockWorklist.h"
+#include "DFGCFG.h"
#include "DFGClobberSet.h"
#include "DFGClobbersExitState.h"
-#include "DFGCFG.h"
+#include "DFGControlEquivalenceAnalysis.h"
#include "DFGDominators.h"
#include "DFGJITCode.h"
#include "DFGMayExit.h"
@@ -375,6 +378,8 @@
}
if (!node->origin.exitOK)
out.print(comma, "ExitInvalid");
+ if (node->origin.wasHoisted)
+ out.print(comma, "WasHoisted");
out.print(")");
if (node->hasVariableAccessData(*this) && node->tryGetVariableAccessData())
@@ -419,6 +424,18 @@
out.print(prefix, " Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
out.print(prefix, " Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
}
+ if (m_backwardsDominators && terminalsAreValid()) {
+ out.print(prefix, " Backwards dominates by: ", m_backwardsDominators->dominatorsOf(block), "\n");
+ out.print(prefix, " Backwards dominates: ", m_backwardsDominators->blocksDominatedBy(block), "\n");
+ }
+ if (m_controlEquivalenceAnalysis && terminalsAreValid()) {
+ out.print(prefix, " Control equivalent to:");
+ for (BasicBlock* otherBlock : blocksInNaturalOrder()) {
+ if (m_controlEquivalenceAnalysis->areEquivalent(block, otherBlock))
+ out.print(" ", *otherBlock);
+ }
+ out.print("\n");
+ }
if (m_prePostNumbering)
out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
if (m_naturalLoops) {
@@ -753,6 +770,9 @@
m_dominators = nullptr;
m_naturalLoops = nullptr;
m_prePostNumbering = nullptr;
+ m_controlEquivalenceAnalysis = nullptr;
+ m_backwardsDominators = nullptr;
+ m_backwardsCFG = nullptr;
}
void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
@@ -1426,25 +1446,49 @@
crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
}
-void Graph::ensureDominators()
+Dominators& Graph::ensureDominators()
{
if (!m_dominators)
m_dominators = std::make_unique<Dominators>(*this);
+ return *m_dominators;
}
-void Graph::ensurePrePostNumbering()
+PrePostNumbering& Graph::ensurePrePostNumbering()
{
if (!m_prePostNumbering)
m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
+ return *m_prePostNumbering;
}
-void Graph::ensureNaturalLoops()
+NaturalLoops& Graph::ensureNaturalLoops()
{
ensureDominators();
if (!m_naturalLoops)
m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+ return *m_naturalLoops;
}
+BackwardsCFG& Graph::ensureBackwardsCFG()
+{
+ if (!m_backwardsCFG)
+ m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
+ return *m_backwardsCFG;
+}
+
+BackwardsDominators& Graph::ensureBackwardsDominators()
+{
+ if (!m_backwardsDominators)
+ m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
+ return *m_backwardsDominators;
+}
+
+ControlEquivalenceAnalysis& Graph::ensureControlEquivalenceAnalysis()
+{
+ if (!m_controlEquivalenceAnalysis)
+ m_controlEquivalenceAnalysis = std::make_unique<ControlEquivalenceAnalysis>(*this);
+ return *m_controlEquivalenceAnalysis;
+}
+
MethodOfGettingAValueProfile Graph::methodOfGettingAValueProfileFor(Node* node)
{
while (node) {
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -56,7 +56,10 @@
namespace DFG {
+class BackwardsCFG;
+class BackwardsDominators;
class CFG;
+class ControlEquivalenceAnalysis;
class Dominators;
class NaturalLoops;
class PrePostNumbering;
@@ -800,9 +803,12 @@
bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
- void ensureDominators();
- void ensurePrePostNumbering();
- void ensureNaturalLoops();
+ Dominators& ensureDominators();
+ PrePostNumbering& ensurePrePostNumbering();
+ NaturalLoops& ensureNaturalLoops();
+ BackwardsCFG& ensureBackwardsCFG();
+ BackwardsDominators& ensureBackwardsDominators();
+ ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
// This function only makes sense to call after bytecode parsing
// because it queries the m_hasExceptionHandlers boolean whose value
@@ -879,6 +885,9 @@
std::unique_ptr<PrePostNumbering> m_prePostNumbering;
std::unique_ptr<NaturalLoops> m_naturalLoops;
std::unique_ptr<CFG> m_cfg;
+ std::unique_ptr<BackwardsCFG> m_backwardsCFG;
+ std::unique_ptr<BackwardsDominators> m_backwardsDominators;
+ std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
unsigned m_localVars;
unsigned m_nextMachineLocal;
unsigned m_parameterSlots;
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 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
@@ -42,6 +42,8 @@
~InPlaceAbstractState();
+ explicit operator bool() const { return true; }
+
void createValueForNode(Node*) { }
AbstractValue& forNode(Node* node)
Modified: trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-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
@@ -33,9 +33,11 @@
#include "DFGBasicBlockInlines.h"
#include "DFGClobberSet.h"
#include "DFGClobberize.h"
+#include "DFGControlEquivalenceAnalysis.h"
#include "DFGEdgeDominates.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
+#include "DFGMayExit.h"
#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "DFGSafeToExecute.h"
@@ -74,6 +76,7 @@
m_graph.ensureDominators();
m_graph.ensureNaturalLoops();
+ m_graph.ensureControlEquivalenceAnalysis();
if (verbose) {
dataLog("Graph before LICM:\n");
@@ -260,43 +263,6 @@
// we could still hoist just the checks.
// https://bugs.webkit.org/show_bug.cgi?id=144525
- // FIXME: If a node has a type check - even something like a CheckStructure - then we should
- // only hoist the node if we know that it will execute on every loop iteration or if we know
- // that the type check will always succeed at the loop pre-header through some other means
- // (like looking at prediction propagation results). Otherwise, we might make a mistake like
- // this:
- //
- // var o = ...; // sometimes null and sometimes an object with structure S1.
- // for (...) {
- // if (o)
- // ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
- // }
- //
- // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
- // will have a recompile. We'll then end up thinking that the get_by_id needs to be
- // polymorphic, which is false.
- //
- // We can counter this by either having a control flow equivalence check, or by consulting
- // prediction propagation to see if the check would always succeed. Prediction propagation
- // would not be enough for things like:
- //
- // var p = ...; // some boolean predicate
- // var o = {};
- // if (p)
- // o.f = 42;
- // for (...) {
- // if (p)
- // ... = o.f;
- // }
- //
- // Prediction propagation can't tell us anything about the structure, and the CheckStructure
- // will appear to be hoistable because the loop doesn't clobber structures. The cell check
- // in the CheckStructure will be hoistable though, since prediction propagation can tell us
- // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
- // only effective guard.
- //
- // https://bugs.webkit.org/show_bug.cgi?id=144527
-
if (readsOverlap(m_graph, node, data.writes)) {
if (verbose) {
dataLog(
@@ -315,6 +281,25 @@
return false;
}
+ NodeOrigin originalOrigin = node->origin;
+
+ // NOTE: We could just use BackwardsDominators here directly, since we already know that the
+ // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
+ // dominance checks are O(1) and only a few integer compares.
+ bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
+ && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
+
+ if (addsBlindSpeculation
+ && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
+ if (verbose) {
+ dataLog(
+ " Not hoisting ", node, " because it may exit and the pre-header (",
+ *data.preHeader, ") is not control equivalent to the node's original block (",
+ *fromBlock, ") and hoisting had previously failed.\n");
+ }
+ return false;
+ }
+
if (verbose) {
dataLog(
" Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
@@ -326,8 +311,9 @@
// https://bugs.webkit.org/show_bug.cgi?id=148544
data.preHeader->insertBeforeTerminal(node);
node->owner = data.preHeader;
- NodeOrigin originalOrigin = node->origin;
- node->origin = data.preHeader->terminal()->origin.withSemantic(node->origin.semantic);
+ NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+ node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+ node->origin.wasHoisted |= addsBlindSpeculation;
// Modify the states at the end of the preHeader of the loop we hoisted to,
// and all pre-headers inside the loop. This isn't a stability bottleneck right now
Modified: trunk/Source/_javascript_Core/dfg/DFGMayExit.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGMayExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGMayExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-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
@@ -28,60 +28,18 @@
#if ENABLE(DFG_JIT)
+#include "DFGAtTailAbstractState.h"
#include "DFGGraph.h"
#include "DFGNode.h"
+#include "DFGNullAbstractState.h"
#include "Operations.h"
namespace JSC { namespace DFG {
namespace {
-class EdgeMayExit {
-public:
- EdgeMayExit()
- : m_result(false)
- {
- }
-
- void operator()(Node*, Edge edge)
- {
- // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
- // https://bugs.webkit.org/show_bug.cgi?id=148545
- if (edge.willHaveCheck()) {
- m_result = true;
- return;
- }
-
- switch (edge.useKind()) {
- // These are shady because nodes that have these use kinds will typically exit for
- // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses ObjectUse
- // then it will.
- case ObjectUse:
- case ObjectOrOtherUse:
- m_result = true;
- break;
-
- // These are shady because they check the structure even if the type of the child node
- // passes the StringObject type filter.
- case StringObjectUse:
- case StringOrStringObjectUse:
- m_result = true;
- break;
-
- default:
- break;
- }
- }
-
- bool result() const { return m_result; }
-
-private:
- bool m_result;
-};
-
-} // anonymous namespace
-
-ExitMode mayExit(Graph& graph, Node* node)
+template<typename StateType>
+ExitMode mayExitImpl(Graph& graph, Node* node, StateType& state)
{
ExitMode result = DoesNotExit;
@@ -154,15 +112,68 @@
// If in doubt, return true.
return Exits;
}
+
+ graph.doToChildren(
+ node,
+ [&] (Edge& edge) {
+ if (state) {
+ // Ignore the Check flag on the edge. This is important because that flag answers
+ // the question: "would this edge have had a check if it executed wherever it
+ // currently resides in control flow?" But when a state is passed, we want to ask a
+ // different question: "would this edge have a check if it executed wherever this
+ // state is?" Using the Check flag for this purpose wouldn't even be conservatively
+ // correct. It would be wrong in both directions.
+ if (mayHaveTypeCheck(edge.useKind())
+ && (state.forNode(edge).m_type & ~typeFilterFor(edge.useKind()))) {
+ result = Exits;
+ return;
+ }
+ } else {
+ // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
+ // https://bugs.webkit.org/show_bug.cgi?id=148545
+ if (edge.willHaveCheck()) {
+ result = Exits;
+ return;
+ }
+ }
+
+ switch (edge.useKind()) {
+ // These are shady because nodes that have these use kinds will typically exit for
+ // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses
+ // ObjectUse then it will.
+ case ObjectUse:
+ case ObjectOrOtherUse:
+ result = Exits;
+ break;
+
+ // These are shady because they check the structure even if the type of the child node
+ // passes the StringObject type filter.
+ case StringObjectUse:
+ case StringOrStringObjectUse:
+ result = Exits;
+ break;
+
+ default:
+ break;
+ }
+ });
- EdgeMayExit functor;
- DFG_NODE_DO_TO_CHILDREN(graph, node, functor);
- if (functor.result())
- result = Exits;
-
return result;
}
+} // anonymous namespace
+
+ExitMode mayExit(Graph& graph, Node* node)
+{
+ NullAbstractState state;
+ return mayExitImpl(graph, node, state);
+}
+
+ExitMode mayExit(Graph& graph, Node* node, AtTailAbstractState& state)
+{
+ return mayExitImpl(graph, node, state);
+}
+
} } // namespace JSC::DFG
namespace WTF {
Modified: trunk/Source/_javascript_Core/dfg/DFGMayExit.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGMayExit.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGMayExit.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-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
@@ -30,6 +30,7 @@
namespace JSC { namespace DFG {
+class AtTailAbstractState;
class Graph;
struct Node;
@@ -74,6 +75,11 @@
ExitMode mayExit(Graph&, Node*);
+// Like mayExit(), but instead of using the Check: flag to determine if something exits, it
+// evaluates whether it will exit based on the tail state. This is useful for LICM. This *may* also
+// use the AtTailAbstractState to return more precise answers for other nodes.
+ExitMode mayExit(Graph&, Node*, AtTailAbstractState&);
+
} } // namespace JSC::DFG
namespace WTF {
Modified: trunk/Source/_javascript_Core/dfg/DFGNode.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -2299,7 +2299,7 @@
private:
unsigned m_op : 10; // real type is NodeType
- unsigned m_flags : 22;
+ unsigned m_flags : 20;
// The virtual register number (spill location) associated with this .
VirtualRegister m_virtualRegister;
// The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
Modified: trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-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
@@ -32,7 +32,7 @@
void NodeOrigin::dump(PrintStream& out) const
{
- out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, "}");
+ out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, ", wasHoisted: ", wasHoisted, "}");
}
} } // namespace JSC::DFG
Modified: trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-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
@@ -92,6 +92,13 @@
return withExitOK(exitOK & std::exchange(canExit, false));
}
+ NodeOrigin withWasHoisted() const
+ {
+ NodeOrigin result = *this;
+ result.wasHoisted = true;
+ return result;
+ }
+
NodeOrigin forInsertingAfter(Graph& graph, Node* node) const
{
NodeOrigin result = *this;
@@ -121,6 +128,8 @@
CodeOrigin forExit;
// Whether or not it is legal to exit here.
bool exitOK { false };
+ // Whether or not the node has been hoisted.
+ bool wasHoisted { false };
};
} } // namespace JSC::DFG
Added: trunk/Source/_javascript_Core/dfg/DFGNullAbstractState.h (0 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGNullAbstractState.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNullAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,66 @@
+/*
+ * 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.
+ */
+
+#ifndef DFGNullAbstractState_h
+#define DFGNullAbstractState_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Edge;
+struct AbstractValue;
+struct Node;
+
+// Use this as a stub for things that can optionally take some kind of abstract state but you wish
+// to not pass any abstract state. This works if the templatized code also does a check (using the
+// operator bool) to see if the state is valid.
+class NullAbstractState {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ NullAbstractState() { }
+
+ explicit operator bool() const { return false; }
+
+ AbstractValue& forNode(Node*)
+ {
+ RELEASE_ASSERT_NOT_REACHED();
+ return *bitwise_cast<AbstractValue*>(static_cast<intptr_t>(0x1234));
+ }
+
+ AbstractValue& forNode(Edge)
+ {
+ return forNode(nullptr);
+ }
+
+ // It's valid to add more stub methods here as needed.
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNullAbstractState_h
+
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRExit.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGOSRExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -37,7 +37,7 @@
namespace JSC { namespace DFG {
OSRExit::OSRExit(ExitKind kind, JSValueSource jsValueSource, MethodOfGettingAValueProfile valueProfile, SpeculativeJIT* jit, unsigned streamIndex, unsigned recoveryIndex)
- : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic)
+ : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic, jit->m_origin.wasHoisted)
, m_jsValueSource(jsValueSource)
, m_valueProfile(valueProfile)
, m_patchableCodeOffset(0)
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 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
@@ -41,8 +41,14 @@
CodeBlock* sourceProfiledCodeBlock =
baselineCodeBlockForOriginAndBaselineCodeBlock(
m_codeOriginForExitProfile, profiledCodeBlock);
- if (sourceProfiledCodeBlock)
- sourceProfiledCodeBlock->addFrequentExitSite(FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType));
+ if (sourceProfiledCodeBlock) {
+ FrequentExitSite site;
+ if (m_wasHoisted)
+ site = FrequentExitSite(HoistingFailed, jitType);
+ else
+ site = FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType);
+ sourceProfiledCodeBlock->addFrequentExitSite(site);
+ }
}
} } // namespace JSC::DFG
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.h (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRExitBase.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -40,9 +40,10 @@
// and the FTL.
struct OSRExitBase {
- OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile)
+ OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile, bool wasHoisted)
: m_kind(kind)
, m_count(0)
+ , m_wasHoisted(wasHoisted)
, m_codeOrigin(origin)
, m_codeOriginForExitProfile(originForProfile)
{
@@ -52,6 +53,7 @@
ExitKind m_kind;
uint32_t m_count;
+ bool m_wasHoisted;
CodeOrigin m_codeOrigin;
CodeOrigin m_codeOriginForExitProfile;
Modified: trunk/Source/_javascript_Core/dfg/DFGTypeCheckHoistingPhase.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/dfg/DFGTypeCheckHoistingPhase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/dfg/DFGTypeCheckHoistingPhase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -88,7 +88,7 @@
bool run()
{
ASSERT(m_graph.m_form == ThreadedCPS);
-
+
clearVariableVotes();
identifyRedundantStructureChecks();
disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();
Modified: trunk/Source/_javascript_Core/ftl/FTLOSRExit.cpp (201181 => 201182)
--- trunk/Source/_javascript_Core/ftl/FTLOSRExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/ftl/FTLOSRExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
@@ -92,7 +92,7 @@
{
unsigned index = state.jitCode->osrExit.size();
OSRExit& exit = state.jitCode->osrExit.alloc(
- this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic);
+ this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic, nodeOrigin.wasHoisted);
RefPtr<OSRExitHandle> handle = adoptRef(new OSRExitHandle(index, exit));
for (unsigned i = offset; i < params.size(); ++i)
exit.m_valueReps.append(params[i]);
@@ -101,9 +101,9 @@
}
OSRExit::OSRExit(
- OSRExitDescriptor* descriptor,
- ExitKind exitKind, CodeOrigin codeOrigin, CodeOrigin codeOriginForExitProfile)
- : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile)
+ OSRExitDescriptor* descriptor, ExitKind exitKind, CodeOrigin codeOrigin,
+ CodeOrigin codeOriginForExitProfile, bool wasHoisted)
+ : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile, wasHoisted)
, m_descriptor(descriptor)
{
}
Modified: trunk/Source/_javascript_Core/ftl/FTLOSRExit.h (201181 => 201182)
--- trunk/Source/_javascript_Core/ftl/FTLOSRExit.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/_javascript_Core/ftl/FTLOSRExit.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -117,10 +117,7 @@
};
struct OSRExit : public DFG::OSRExitBase {
- OSRExit(
- OSRExitDescriptor*, ExitKind,
- CodeOrigin, CodeOrigin codeOriginForExitProfile
- );
+ OSRExit(OSRExitDescriptor*, ExitKind, CodeOrigin, CodeOrigin codeOriginForExitProfile, bool wasHoisted);
OSRExitDescriptor* m_descriptor;
MacroAssemblerCodeRef m_code;
Modified: trunk/Source/WTF/ChangeLog (201181 => 201182)
--- trunk/Source/WTF/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,3 +1,61 @@
+2016-05-18 Filip Pizlo <fpi...@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
+ passing around a Graph template argument that follows the protocol shared by DFG::CFG,
+ B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
+ nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
+ node that it uses as the root in the inverted graph. This currently may resort to some
+ heuristics in programs that have an infinite loop, but other than that, it'll work well in
+ the general case.
+
+ This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
+ backwards dominators, which then allows us to easily answer control flow equivalence
+ queries.
+
+ * CMakeLists.txt:
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/BackwardsGraph.h: Added.
+ (WTF::BackwardsGraph::Node::Node):
+ (WTF::BackwardsGraph::Node::root):
+ (WTF::BackwardsGraph::Node::operator==):
+ (WTF::BackwardsGraph::Node::operator!=):
+ (WTF::BackwardsGraph::Node::operator bool):
+ (WTF::BackwardsGraph::Node::isRoot):
+ (WTF::BackwardsGraph::Node::node):
+ (WTF::BackwardsGraph::Set::Set):
+ (WTF::BackwardsGraph::Set::add):
+ (WTF::BackwardsGraph::Set::remove):
+ (WTF::BackwardsGraph::Set::contains):
+ (WTF::BackwardsGraph::Set::dump):
+ (WTF::BackwardsGraph::Map::Map):
+ (WTF::BackwardsGraph::Map::clear):
+ (WTF::BackwardsGraph::Map::size):
+ (WTF::BackwardsGraph::Map::operator[]):
+ (WTF::BackwardsGraph::BackwardsGraph):
+ (WTF::BackwardsGraph::root):
+ (WTF::BackwardsGraph::newMap):
+ (WTF::BackwardsGraph::successors):
+ (WTF::BackwardsGraph::predecessors):
+ (WTF::BackwardsGraph::index):
+ (WTF::BackwardsGraph::node):
+ (WTF::BackwardsGraph::numNodes):
+ (WTF::BackwardsGraph::dump):
+ * wtf/Dominators.h:
+ (WTF::Dominators::Dominators):
+ (WTF::Dominators::dump):
+ (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+ * wtf/GraphNodeWorklist.h:
+ (WTF::GraphNodeWith::GraphNodeWith):
+ (WTF::GraphNodeWith::operator bool):
+ * wtf/StdLibExtras.h:
+ (WTF::callStatelessLambda):
+ (WTF::checkAndSet):
+
2016-05-18 Saam barati <sbar...@apple.com>
StringBuilder::appendQuotedJSONString doesn't properly protect against the math it's doing. Make the math fit the assertion.
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (201181 => 201182)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-05-19 21:25:29 UTC (rev 201182)
@@ -301,6 +301,7 @@
CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */ = {isa = PBXBuildFile; fileRef = CD5497AB15857D0300B5BC30 /* MediaTime.h */; };
CE46516E19DB1FB4003ECA05 /* NSMapTableSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */; };
CE73E02519DCB7AB00580D5C /* XPCSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE73E02419DCB7AB00580D5C /* XPCSPI.h */; };
+ DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22041CEB9869000C2396 /* BackwardsGraph.h */; };
DCEE21FB1CEA7538000C2396 /* CFBundleSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */; };
DCEE22001CEA7551000C2396 /* BlockObjCExceptions.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */; };
DCEE22011CEA7551000C2396 /* BlockObjCExceptions.mm in Sources */ = {isa = PBXBuildFile; fileRef = DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */; };
@@ -627,6 +628,7 @@
CD5497AB15857D0300B5BC30 /* MediaTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaTime.h; sourceTree = "<group>"; };
CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NSMapTableSPI.h; sourceTree = "<group>"; };
CE73E02419DCB7AB00580D5C /* XPCSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = XPCSPI.h; sourceTree = "<group>"; };
+ DCEE22041CEB9869000C2396 /* BackwardsGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BackwardsGraph.h; sourceTree = "<group>"; };
DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CFBundleSPI.h; path = cf/CFBundleSPI.h; sourceTree = "<group>"; };
DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BlockObjCExceptions.h; sourceTree = "<group>"; };
DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = BlockObjCExceptions.mm; sourceTree = "<group>"; };
@@ -773,6 +775,7 @@
A8A4725D151A825A004123FF /* Atomics.h */,
1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
+ DCEE22041CEB9869000C2396 /* BackwardsGraph.h */,
0FB14E18180FA218009B6B4D /* Bag.h */,
0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
A8A4725F151A825A004123FF /* Bitmap.h */,
@@ -1179,6 +1182,7 @@
A8A47391151A825B004123FF /* BumpPointerAllocator.h in Headers */,
EB95E1F0161A72410089A2F5 /* ByteOrder.h in Headers */,
A8A473AD151A825B004123FF /* cached-powers.h in Headers */,
+ DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */,
A8A4745E151A825B004123FF /* CharacterNames.h in Headers */,
A8A47394151A825B004123FF /* CheckedArithmetic.h in Headers */,
A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
Added: trunk/Source/WTF/wtf/BackwardsGraph.h (0 => 201182)
--- trunk/Source/WTF/wtf/BackwardsGraph.h (rev 0)
+++ trunk/Source/WTF/wtf/BackwardsGraph.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -0,0 +1,296 @@
+/*
+ * 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.
+ */
+
+#ifndef WTF_BackwardsGraph_h
+#define WTF_BackwardsGraph_h
+
+#include <wtf/FastMalloc.h>
+#include <wtf/GraphNodeWorklist.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/Optional.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+template<typename Graph>
+class BackwardsGraph {
+ WTF_MAKE_NONCOPYABLE(BackwardsGraph);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ // We use "#end" to refer to the synthetic root we have created.
+ static const char* rootName = "#end";
+
+ class Node {
+ public:
+ Node(typename Graph::Node node = typename Graph::Node())
+ : m_node(node)
+ {
+ }
+
+ static Node root()
+ {
+ Node result;
+ result.m_node = 0;
+ result.m_isRoot = true;
+ return result;
+ }
+
+ bool operator==(const Node& other) const
+ {
+ return m_node == other.m_node
+ && m_isRoot == other.m_isRoot;
+ }
+
+ bool operator!=(const Node& other) const
+ {
+ return !(*this == other);
+ }
+
+ explicit operator bool() const { return *this != Node(); }
+
+ bool isRoot() const
+ {
+ return m_isRoot;
+ }
+
+ typename Graph::Node node() const { return m_node; }
+
+ private:
+ typename Graph::Node m_node;
+ bool m_isRoot { false };
+ };
+
+ class Set {
+ public:
+ Set()
+ {
+ }
+
+ bool add(const Node& node)
+ {
+ if (node.isRoot())
+ return checkAndSet(m_hasRoot, true);
+ return m_set.add(node.node());
+ }
+
+ bool remove(const Node& node)
+ {
+ if (node.isRoot())
+ return checkAndSet(m_hasRoot, false);
+ return m_set.remove(node.node());
+ }
+
+ bool contains(const Node& node)
+ {
+ if (node.isRoot())
+ return m_hasRoot;
+ return m_set.contains(node.node());
+ }
+
+ void dump(PrintStream& out) const
+ {
+ if (m_hasRoot)
+ out.print(rootName, " ");
+ out.print(m_set);
+ }
+
+ private:
+ typename Graph::Set m_set;
+ bool m_hasRoot { false };
+ };
+
+ template<typename T>
+ class Map {
+ public:
+ Map(Graph& graph)
+ : m_map(graph.template newMap<T>())
+ {
+ }
+
+ void clear()
+ {
+ m_map.clear();
+ m_root = T();
+ }
+
+ size_t size() const { return m_map.size() + 1; }
+
+ T& operator[](size_t index)
+ {
+ if (!index)
+ return m_root;
+ return m_map[index - 1];
+ }
+
+ const T& operator[](size_t index) const
+ {
+ return (*const_cast<Map*>(this))[index];
+ }
+
+ T& operator[](const Node& node)
+ {
+ if (node.isRoot())
+ return m_root;
+ return m_map[node.node()];
+ }
+
+ const T& operator[](const Node& node) const
+ {
+ return (*const_cast<Map*>(this))[node];
+ }
+
+ private:
+ typename Graph::template Map<T> m_map;
+ T m_root;
+ };
+
+ typedef Vector<Node, 4> List;
+
+ BackwardsGraph(Graph& graph)
+ : m_graph(graph)
+ {
+ GraphNodeWorklist<typename Graph::Node, typename Graph::Set> worklist;
+
+ auto addRootSuccessor = [&] (typename Graph::Node node) {
+ if (worklist.push(node)) {
+ m_rootSuccessorList.append(node);
+ m_rootSuccessorSet.add(node);
+ while (typename Graph::Node node = worklist.pop())
+ worklist.pushAll(graph.predecessors(node));
+ }
+ };
+
+ for (unsigned i = 0; i < graph.numNodes(); ++i) {
+ if (typename Graph::Node node = graph.node(i)) {
+ if (!graph.successors(node).size())
+ addRootSuccessor(node);
+ }
+ }
+
+ // At this point there will be some nodes in the graph that aren't known to the worklist. We
+ // could add any or all of them to the root successors list. Adding all of them would be a bad
+ // pessimisation. Ideally we would pick the ones that have backward edges but no forward
+ // edges. That would require thinking, so we just use a rough heuristic: add the highest
+ // numbered nodes first, which is totally fine if the input program is already sorted nicely.
+ for (unsigned i = graph.numNodes(); i--;) {
+ if (typename Graph::Node node = graph.node(i))
+ addRootSuccessor(node);
+ }
+ }
+
+ Node root() { return Node::root(); }
+
+ template<typename T>
+ Map<T> newMap() { return Map<T>(m_graph); }
+
+ List successors(const Node& node) const
+ {
+ if (node.isRoot())
+ return m_rootSuccessorList;
+ List result;
+ for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
+ result.append(predecessor);
+ return result;
+ }
+
+ List predecessors(const Node& node) const
+ {
+ if (node.isRoot())
+ return { };
+
+ List result;
+
+ if (m_rootSuccessorSet.contains(node.node()))
+ result.append(Node::root());
+
+ for (typename Graph::Node successor : m_graph.successors(node.node()))
+ result.append(successor);
+
+ return result;
+ }
+
+ unsigned index(const Node& node) const
+ {
+ if (node.isRoot())
+ return 0;
+ return m_graph.index(node.node()) + 1;
+ }
+
+ Node node(unsigned index) const
+ {
+ if (!index)
+ return Node::root();
+ return m_graph.node(index - 1);
+ }
+
+ unsigned numNodes() const
+ {
+ return m_graph.numNodes() + 1;
+ }
+
+ CString dump(Node node) const
+ {
+ StringPrintStream out;
+ if (!node)
+ out.print("<null>");
+ else if (node.isRoot())
+ out.print(rootName);
+ else
+ out.print(m_graph.dump(node.node()));
+ return out.toCString();
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned i = 0; i < numNodes(); ++i) {
+ Node node = this->node(i);
+ if (!node)
+ continue;
+ out.print(dump(node), ":\n");
+ out.print(" Preds: ");
+ CommaPrinter comma;
+ for (Node predecessor : predecessors(node))
+ out.print(comma, dump(predecessor));
+ out.print("\n");
+ out.print(" Succs: ");
+ comma = CommaPrinter();
+ for (Node successor : successors(node))
+ out.print(comma, dump(successor));
+ out.print("\n");
+ }
+ }
+
+private:
+ Graph& m_graph;
+ List m_rootSuccessorList;
+ typename Graph::Set m_rootSuccessorSet;
+};
+
+} // namespace WTF
+
+using WTF::BackwardsGraph;
+
+#endif // WTF_BackwardsGraph_h
+
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (201181 => 201182)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-05-19 21:25:29 UTC (rev 201182)
@@ -2,6 +2,7 @@
ASCIICType.h
Assertions.h
Atomics.h
+ BackwardsGraph.h
Bag.h
BagToHashMap.h
BitVector.h
Modified: trunk/Source/WTF/wtf/Dominators.h (201181 => 201182)
--- trunk/Source/WTF/wtf/Dominators.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/Dominators.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014-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
@@ -41,6 +41,7 @@
public:
Dominators(Graph& graph, bool selfCheck = false)
: m_graph(graph)
+ , m_data(graph.template newMap<BlockData>())
{
LengauerTarjan lengauerTarjan(m_graph);
lengauerTarjan.compute();
@@ -67,7 +68,7 @@
// Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
Vector<GraphNodeWithOrder<typename Graph::Node>> worklist;
- worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.root(), GraphVisitOrder::Pre));
while (!worklist.isEmpty()) {
GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
switch (item.order) {
@@ -279,10 +280,10 @@
if (m_data[blockIndex].preNumber == UINT_MAX)
continue;
- out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
+ out.print(" Block #", blockIndex, ": idom = ", m_graph.dump(m_data[blockIndex].idomParent), ", idomKids = [");
CommaPrinter comma;
for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
- out.print(comma, *m_data[blockIndex].idomKids[i]);
+ out.print(comma, m_graph.dump(m_data[blockIndex].idomKids[i]));
out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
}
}
@@ -347,7 +348,7 @@
// of not noticing A->C until we're done processing B.
ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
- worklist.push(m_graph.node(0), 0);
+ worklist.push(m_graph.root(), 0);
while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
typename Graph::Node block = item.node;
Modified: trunk/Source/WTF/wtf/GraphNodeWorklist.h (201181 => 201182)
--- trunk/Source/WTF/wtf/GraphNodeWorklist.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/GraphNodeWorklist.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -83,7 +83,7 @@
{
}
- explicit operator bool() const { return node; }
+ explicit operator bool() const { return !!node; }
Node node;
T data;
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (201181 => 201182)
--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-05-19 21:25:29 UTC (rev 201182)
@@ -299,6 +299,15 @@
return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
}
+template<typename T, typename U>
+bool checkAndSet(T& left, U right)
+{
+ if (left == right)
+ return false;
+ left = right;
+ return true;
+}
+
} // namespace WTF
// This version of placement new omits a 0 check.
@@ -409,17 +418,18 @@
using WTF::KB;
using WTF::MB;
+using WTF::approximateBinarySearch;
+using WTF::binarySearch;
+using WTF::bitwise_cast;
+using WTF::callStatelessLambda;
+using WTF::checkAndSet;
+using WTF::insertIntoBoundedVector;
using WTF::isCompilationThread;
-using WTF::insertIntoBoundedVector;
using WTF::isPointerAligned;
+using WTF::isStatelessLambda;
using WTF::is8ByteAligned;
-using WTF::binarySearch;
+using WTF::safeCast;
using WTF::tryBinarySearch;
-using WTF::approximateBinarySearch;
-using WTF::bitwise_cast;
-using WTF::safeCast;
-using WTF::isStatelessLambda;
-using WTF::callStatelessLambda;
#if COMPILER_SUPPORTS(CXX_USER_LITERALS)
// We normally don't want to bring in entire std namespaces, but literals are an exception.
