Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (134163 => 134164)
--- trunk/Source/_javascript_Core/ChangeLog 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/ChangeLog 2012-11-10 23:33:29 UTC (rev 134164)
@@ -1,3 +1,43 @@
+2012-11-10 Filip Pizlo <[email protected]>
+
+ DFG constant folding and CFG simplification should be smart enough to know that if a logical op's operand is proven to have a non-masquerading structure then it always evaluates to true
+ https://bugs.webkit.org/show_bug.cgi?id=101511
+
+ Reviewed by Geoffrey Garen.
+
+ This is the second attempt at this patch, which fixes the !"" case.
+
+ To make life easier, this moves BranchDirection into BasicBlock so that after
+ running the CFA, we always know, for each block, what direction the CFA
+ proved. CFG simplification now both uses and preserves cfaBranchDirection in
+ its transformations.
+
+ Also made both LogicalNot and Branch check whether the operand is a known cell
+ with a known structure, and if so, made them do the appropriate folding.
+
+ 5% speed-up on V8/raytrace because it makes raytrace's own null checks
+ evaporate (i.e. idioms like 'if (!x) throw "unhappiness"') thanks to the fact
+ that we were already doing structure check hoisting.
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * dfg/DFGAbstractState.cpp:
+ (JSC::DFG::AbstractState::endBasicBlock):
+ (JSC::DFG::AbstractState::execute):
+ (JSC::DFG::AbstractState::mergeToSuccessors):
+ * dfg/DFGAbstractState.h:
+ (AbstractState):
+ * dfg/DFGBasicBlock.h:
+ (JSC::DFG::BasicBlock::BasicBlock):
+ (BasicBlock):
+ * dfg/DFGBranchDirection.h: Added.
+ (DFG):
+ (JSC::DFG::branchDirectionToString):
+ (JSC::DFG::isKnownDirection):
+ (JSC::DFG::branchCondition):
+ * dfg/DFGCFGSimplificationPhase.cpp:
+ (JSC::DFG::CFGSimplificationPhase::run):
+ (JSC::DFG::CFGSimplificationPhase::mergeBlocks):
+
2012-11-10 Sheriff Bot <[email protected]>
Unreviewed, rolling out r133971.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (134163 => 134164)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2012-11-10 23:33:29 UTC (rev 134164)
@@ -165,6 +165,7 @@
0F7B294C14C3CD43007C3DB1 /* DFGByteCodeCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5F08CC146BE602000472A9 /* DFGByteCodeCache.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F7B294D14C3CD4C007C3DB1 /* DFGCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC0977E1469EBC400CF2442 /* DFGCommon.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F8023EA1613832B00A0BA45 /* ByValInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8023E91613832300A0BA45 /* ByValInfo.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F8335B71639C1E6001443B5 /* ArrayAllocationProfile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */; };
0F8335B81639C1EA001443B5 /* ArrayAllocationProfile.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F919D0C157EE09F004A4E7D /* JSSymbolTableObject.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F919D09157EE09D004A4E7D /* JSSymbolTableObject.cpp */; };
@@ -953,6 +954,7 @@
0F7700911402FF280078EB39 /* SamplingCounter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SamplingCounter.cpp; sourceTree = "<group>"; };
0F7B294814C3CD23007C3DB1 /* DFGCCallHelpers.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCCallHelpers.h; path = dfg/DFGCCallHelpers.h; sourceTree = "<group>"; };
0F8023E91613832300A0BA45 /* ByValInfo.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ByValInfo.h; sourceTree = "<group>"; };
+ 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBranchDirection.h; path = dfg/DFGBranchDirection.h; sourceTree = "<group>"; };
0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ArrayAllocationProfile.cpp; sourceTree = "<group>"; };
0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ArrayAllocationProfile.h; sourceTree = "<group>"; };
0F919D09157EE09D004A4E7D /* JSSymbolTableObject.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSSymbolTableObject.cpp; sourceTree = "<group>"; };
@@ -2366,6 +2368,7 @@
0FC0976B1468AB4A00CF2442 /* DFGAssemblyHelpers.cpp */,
0FC0976C1468AB4A00CF2442 /* DFGAssemblyHelpers.h */,
0F620170143FCD2F0068B77C /* DFGBasicBlock.h */,
+ 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
0F5F08CC146BE602000472A9 /* DFGByteCodeCache.h */,
86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
86EC9DB51328DF82002B2AD7 /* DFGByteCodeParser.h */,
@@ -3014,6 +3017,7 @@
0FEB3ECD16237F4D00AB67AD /* TypedArrayDescriptor.h in Headers */,
0F256C361627B0AD007F2783 /* DFGCallArrayAllocatorSlowPathGenerator.h in Headers */,
C2239D1B16262BDD005AC5FD /* GCThread.h in Headers */,
+ 0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */,
0F8335B81639C1EA001443B5 /* ArrayAllocationProfile.h in Headers */,
A7B601821639FD2A00372BA3 /* UnlinkedCodeBlock.h in Headers */,
A77F1822164088B200640A47 /* CodeCache.h in Headers */,
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractState.cpp (134163 => 134164)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractState.cpp 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractState.cpp 2012-11-10 23:33:29 UTC (rev 134164)
@@ -159,7 +159,7 @@
}
}
-bool AbstractState::endBasicBlock(MergeMode mergeMode, BranchDirection* branchDirectionPtr)
+bool AbstractState::endBasicBlock(MergeMode mergeMode)
{
ASSERT(m_block);
@@ -167,6 +167,7 @@
block->cfaFoundConstants = m_foundConstants;
block->cfaDidFinish = m_isValid;
+ block->cfaBranchDirection = m_branchDirection;
if (!m_isValid) {
reset();
@@ -195,12 +196,8 @@
ASSERT(mergeMode != DontMerge || !changed);
- BranchDirection branchDirection = m_branchDirection;
- if (branchDirectionPtr)
- *branchDirectionPtr = branchDirection;
-
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLog(" Branch direction = %s\n", branchDirectionToString(branchDirection));
+ dataLog(" Branch direction = %s\n", branchDirectionToString(m_branchDirection));
#endif
reset();
@@ -208,7 +205,7 @@
if (mergeMode != MergeToSuccessors)
return changed;
- return mergeToSuccessors(m_graph, block, branchDirection);
+ return mergeToSuccessors(m_graph, block);
}
void AbstractState::reset()
@@ -218,6 +215,27 @@
m_branchDirection = InvalidBranchDirection;
}
+AbstractState::BooleanResult AbstractState::booleanResult(Node& node, AbstractValue& value)
+{
+ JSValue childConst = value.value();
+ if (childConst) {
+ if (childConst.toBoolean(m_codeBlock->globalObjectFor(node.codeOrigin)->globalExec()))
+ return DefinitelyTrue;
+ return DefinitelyFalse;
+ }
+
+ // Next check if we can fold because we know that the source is an object or string and does not equal undefined.
+ if (isCellSpeculation(value.m_type)
+ && value.m_currentKnownStructure.hasSingleton()) {
+ Structure* structure = value.m_currentKnownStructure.singleton();
+ if (!structure->masqueradesAsUndefined(m_codeBlock->globalObjectFor(node.codeOrigin))
+ && structure->typeInfo().type() != StringType)
+ return DefinitelyTrue;
+ }
+
+ return UnknownBooleanResult;
+}
+
bool AbstractState::execute(unsigned indexInBlock)
{
ASSERT(m_block);
@@ -616,8 +634,18 @@
}
case LogicalNot: {
- JSValue childConst = forNode(node.child1()).value();
- if (childConst && trySetConstant(nodeIndex, jsBoolean(!childConst.toBoolean(m_codeBlock->globalObjectFor(node.codeOrigin)->globalExec())))) {
+ bool didSetConstant = false;
+ switch (booleanResult(node, forNode(node.child1()))) {
+ case DefinitelyTrue:
+ didSetConstant = trySetConstant(nodeIndex, jsBoolean(false));
+ break;
+ case DefinitelyFalse:
+ didSetConstant = trySetConstant(nodeIndex, jsBoolean(true));
+ break;
+ default:
+ break;
+ }
+ if (didSetConstant) {
m_foundConstants = true;
node.setCanExit(false);
break;
@@ -1105,23 +1133,21 @@
break;
case Branch: {
- JSValue value = forNode(node.child1()).value();
- if (value) {
- bool booleanValue = value.toBoolean(m_codeBlock->globalObjectFor(node.codeOrigin)->globalExec());
- if (booleanValue)
- m_branchDirection = TakeTrue;
- else
- m_branchDirection = TakeFalse;
+ BooleanResult result = booleanResult(node, forNode(node.child1()));
+ if (result == DefinitelyTrue) {
+ m_branchDirection = TakeTrue;
node.setCanExit(false);
break;
}
+ if (result == DefinitelyFalse) {
+ m_branchDirection = TakeFalse;
+ node.setCanExit(false);
+ break;
+ }
// FIXME: The above handles the trivial cases of sparse conditional
// constant propagation, but we can do better:
- // 1) If the abstract value does not have a concrete value but describes
- // something that is known to evaluate true (or false) then we ought
- // to sparse conditional that.
- // 2) We can specialize the source variable's value on each direction of
- // the branch.
+ // We can specialize the source variable's value on each direction of
+ // the branch.
Node& child = m_graph[node.child1()];
if (child.shouldSpeculateBoolean())
speculateBooleanUnary(node);
@@ -1784,7 +1810,7 @@
}
inline bool AbstractState::mergeToSuccessors(
- Graph& graph, BasicBlock* basicBlock, BranchDirection branchDirection)
+ Graph& graph, BasicBlock* basicBlock)
{
Node& terminal = graph[basicBlock->last()];
@@ -1792,7 +1818,7 @@
switch (terminal.op()) {
case Jump: {
- ASSERT(branchDirection == InvalidBranchDirection);
+ ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
#endif
@@ -1800,17 +1826,17 @@
}
case Branch: {
- ASSERT(branchDirection != InvalidBranchDirection);
+ ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
bool changed = false;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
#endif
- if (branchDirection != TakeFalse)
+ if (basicBlock->cfaBranchDirection != TakeFalse)
changed |= merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.notTakenBlockIndex());
#endif
- if (branchDirection != TakeTrue)
+ if (basicBlock->cfaBranchDirection != TakeTrue)
changed |= merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
return changed;
}
@@ -1818,7 +1844,7 @@
case Return:
case Throw:
case ThrowReferenceError:
- ASSERT(branchDirection == InvalidBranchDirection);
+ ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
return false;
default:
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractState.h (134163 => 134164)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractState.h 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractState.h 2012-11-10 23:33:29 UTC (rev 134164)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -31,6 +31,7 @@
#if ENABLE(DFG_JIT)
#include "DFGAbstractValue.h"
+#include "DFGBranchDirection.h"
#include "DFGGraph.h"
#include "DFGNode.h"
#include <wtf/Vector.h>
@@ -92,36 +93,6 @@
MergeToSuccessors
};
- enum BranchDirection {
- // This is not a branch and so there is no branch direction, or
- // the branch direction has yet to be set.
- InvalidBranchDirection,
-
- // The branch takes the true case.
- TakeTrue,
-
- // The branch takes the false case.
- TakeFalse,
-
- // For all we know, the branch could go either direction, so we
- // have to assume the worst.
- TakeBoth
- };
-
- static const char* branchDirectionToString(BranchDirection branchDirection)
- {
- switch (branchDirection) {
- case InvalidBranchDirection:
- return "Invalid";
- case TakeTrue:
- return "TakeTrue";
- case TakeFalse:
- return "TakeFalse";
- case TakeBoth:
- return "TakeBoth";
- }
- }
-
AbstractState(Graph&);
~AbstractState();
@@ -174,11 +145,7 @@
// A true return means that you must revisit (at least) the successor
// blocks. This also sets cfaShouldRevisit to true for basic blocks
// that must be visited next.
- //
- // If you'd like to know what direction the branch at the end of the
- // basic block is thought to have taken, you can pass a non-0 pointer
- // for BranchDirection.
- bool endBasicBlock(MergeMode, BranchDirection* = 0);
+ bool endBasicBlock(MergeMode);
// Reset the AbstractState. This throws away any results, and at this point
// you can safely call beginBasicBlock() on any basic block.
@@ -211,8 +178,8 @@
// successors. Returns true if any of the successors' states changed. Note
// that this is automatically called in endBasicBlock() if MergeMode is
// MergeToSuccessors.
- bool mergeToSuccessors(Graph&, BasicBlock*, BranchDirection);
-
+ bool mergeToSuccessors(Graph&, BasicBlock*);
+
void dump(FILE* out);
private:
@@ -268,6 +235,13 @@
childValue2.filter(SpecNumber);
}
+ enum BooleanResult {
+ UnknownBooleanResult,
+ DefinitelyFalse,
+ DefinitelyTrue
+ };
+ BooleanResult booleanResult(Node&, AbstractValue&);
+
bool trySetConstant(NodeIndex nodeIndex, JSValue value)
{
// Make sure we don't constant fold something that will produce values that contravene
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (134163 => 134164)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2012-11-10 23:33:29 UTC (rev 134164)
@@ -29,6 +29,7 @@
#if ENABLE(DFG_JIT)
#include "DFGAbstractValue.h"
+#include "DFGBranchDirection.h"
#include "DFGNode.h"
#include "Operands.h"
#include <wtf/OwnPtr.h>
@@ -46,6 +47,7 @@
, cfaShouldRevisit(false)
, cfaFoundConstants(false)
, cfaDidFinish(true)
+ , cfaBranchDirection(InvalidBranchDirection)
#if !ASSERT_DISABLED
, isLinked(false)
#endif
@@ -105,6 +107,7 @@
bool cfaShouldRevisit;
bool cfaFoundConstants;
bool cfaDidFinish;
+ BranchDirection cfaBranchDirection;
#if !ASSERT_DISABLED
bool isLinked;
#endif
Added: trunk/Source/_javascript_Core/dfg/DFGBranchDirection.h (0 => 134164)
--- trunk/Source/_javascript_Core/dfg/DFGBranchDirection.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGBranchDirection.h 2012-11-10 23:33:29 UTC (rev 134164)
@@ -0,0 +1,88 @@
+/*
+ * Copyright (C) 2012 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 DFGBranchDirection_h
+#define DFGBranchDirection_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+enum BranchDirection {
+ // This is not a branch and so there is no branch direction, or
+ // the branch direction has yet to be set.
+ InvalidBranchDirection,
+
+ // The branch takes the true case.
+ TakeTrue,
+
+ // The branch takes the false case.
+ TakeFalse,
+
+ // For all we know, the branch could go either direction, so we
+ // have to assume the worst.
+ TakeBoth
+};
+
+static inline const char* branchDirectionToString(BranchDirection branchDirection)
+{
+ switch (branchDirection) {
+ case InvalidBranchDirection:
+ return "Invalid";
+ case TakeTrue:
+ return "TakeTrue";
+ case TakeFalse:
+ return "TakeFalse";
+ case TakeBoth:
+ return "TakeBoth";
+ }
+}
+
+static inline bool isKnownDirection(BranchDirection branchDirection)
+{
+ switch (branchDirection) {
+ case TakeTrue:
+ case TakeFalse:
+ return true;
+ default:
+ return false;
+ }
+}
+
+static inline bool branchCondition(BranchDirection branchDirection)
+{
+ if (branchDirection == TakeTrue)
+ return true;
+ ASSERT(branchDirection == TakeFalse);
+ return false;
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBranchDirection_h
Modified: trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (134163 => 134164)
--- trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2012-11-10 22:35:46 UTC (rev 134163)
+++ trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2012-11-10 23:33:29 UTC (rev 134164)
@@ -99,9 +99,8 @@
case Branch: {
// Branch on constant -> jettison the not-taken block and merge.
- if (m_graph[m_graph[block->last()].child1()].hasConstant()) {
- bool condition =
- m_graph.valueOfJSConstant(m_graph[block->last()].child1().index()).toBoolean(m_graph.globalObjectFor(m_graph[block->last()].codeOrigin)->globalExec());
+ if (isKnownDirection(block->cfaBranchDirection)) {
+ bool condition = branchCondition(block->cfaBranchDirection);
BasicBlock* targetBlock = m_graph.m_blocks[
m_graph.successorForCondition(block, condition)].get();
if (targetBlock->m_predecessors.size() == 1) {
@@ -730,6 +729,7 @@
}
firstBlock->valuesAtTail = secondBlock->valuesAtTail;
+ firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
m_graph.m_blocks[secondBlockIndex].clear();
}
