2 * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 #include "DFGCSEPhase.h"
33 #include <wtf/FastBitVector.h>
35 namespace JSC { namespace DFG {
37 class CSEPhase : public Phase {
39 CSEPhase(Graph& graph)
40 : Phase(graph, "common subexpression elimination")
42 // Replacements are used to implement local common subexpression elimination.
43 m_replacements.resize(m_graph.size());
45 for (unsigned i = 0; i < m_graph.size(); ++i)
46 m_replacements[i] = NoNode;
48 m_relevantToOSR.resize(m_graph.size());
55 for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
56 performBlockCSE(m_graph.m_blocks[block].get());
63 NodeIndex canonicalize(NodeIndex nodeIndex)
65 if (nodeIndex == NoNode)
68 if (m_graph[nodeIndex].op() == ValueToInt32)
69 nodeIndex = m_graph[nodeIndex].child1().index();
73 NodeIndex canonicalize(Edge nodeUse)
75 return canonicalize(nodeUse.indexUnchecked());
78 unsigned endIndexForPureCSE()
80 unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
81 if (result == UINT_MAX)
85 ASSERT(result <= m_indexInBlock);
86 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
87 dataLogF(" limit %u: ", result);
92 NodeIndex pureCSE(Node& node)
94 NodeIndex child1 = canonicalize(node.child1());
95 NodeIndex child2 = canonicalize(node.child2());
96 NodeIndex child3 = canonicalize(node.child3());
98 for (unsigned i = endIndexForPureCSE(); i--;) {
99 NodeIndex index = m_currentBlock->at(i);
100 if (index == child1 || index == child2 || index == child3)
103 Node& otherNode = m_graph[index];
104 if (!otherNode.shouldGenerate())
107 if (node.op() != otherNode.op())
110 if (node.arithNodeFlags() != otherNode.arithNodeFlags())
113 NodeIndex otherChild = canonicalize(otherNode.child1());
114 if (otherChild == NoNode)
116 if (otherChild != child1)
119 otherChild = canonicalize(otherNode.child2());
120 if (otherChild == NoNode)
122 if (otherChild != child2)
125 otherChild = canonicalize(otherNode.child3());
126 if (otherChild == NoNode)
128 if (otherChild != child3)
136 NodeIndex constantCSE(Node& node)
138 for (unsigned i = endIndexForPureCSE(); i--;) {
139 NodeIndex index = m_currentBlock->at(i);
140 Node& otherNode = m_graph[index];
141 if (otherNode.op() != JSConstant)
144 if (otherNode.constantNumber() != node.constantNumber())
152 NodeIndex weakConstantCSE(Node& node)
154 for (unsigned i = endIndexForPureCSE(); i--;) {
155 NodeIndex index = m_currentBlock->at(i);
156 Node& otherNode = m_graph[index];
157 if (otherNode.op() != WeakJSConstant)
160 if (otherNode.weakConstant() != node.weakConstant())
168 NodeIndex getArrayLengthElimination(NodeIndex array)
170 for (unsigned i = m_indexInBlock; i--;) {
171 NodeIndex index = m_currentBlock->at(i);
172 Node& node = m_graph[index];
173 if (!node.shouldGenerate())
177 if (node.child1() == array)
182 if (!m_graph.byValIsPure(node))
184 if (node.arrayMode().mayStoreToHole())
189 if (m_graph.clobbersWorld(index))
196 NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
198 for (unsigned i = m_indexInBlock; i--;) {
199 NodeIndex index = m_currentBlock->at(i);
200 Node& node = m_graph[index];
201 if (!node.shouldGenerate())
205 if (node.registerPointer() == registerPointer)
209 if (node.registerPointer() == registerPointer)
210 return node.child1().index();
215 if (m_graph.clobbersWorld(index))
221 NodeIndex scopedVarLoadElimination(NodeIndex registers, unsigned varNumber)
223 for (unsigned i = m_indexInBlock; i--;) {
224 NodeIndex index = m_currentBlock->at(i);
225 Node& node = m_graph[index];
226 if (!node.shouldGenerate())
230 if (node.child1() == registers && node.varNumber() == varNumber)
235 if (node.child2() == registers && node.varNumber() == varNumber)
236 return node.child3().index();
240 VariableAccessData* variableAccessData = node.variableAccessData();
241 if (variableAccessData->isCaptured()
242 && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
249 if (m_graph.clobbersWorld(index))
255 bool globalVarWatchpointElimination(WriteBarrier<Unknown>* registerPointer)
257 for (unsigned i = m_indexInBlock; i--;) {
258 NodeIndex index = m_currentBlock->at(i);
259 Node& node = m_graph[index];
260 if (!node.shouldGenerate())
263 case GlobalVarWatchpoint:
264 if (node.registerPointer() == registerPointer)
268 if (node.registerPointer() == registerPointer)
274 if (m_graph.clobbersWorld(index))
280 NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
282 for (unsigned i = m_indexInBlock; i--;) {
283 NodeIndex index = m_currentBlock->at(i);
284 Node& node = m_graph[index];
285 if (!node.shouldGenerate())
289 case PutGlobalVarCheck:
290 if (node.registerPointer() == registerPointer)
295 if (node.registerPointer() == registerPointer)
302 if (m_graph.clobbersWorld(index) || node.canExit())
308 NodeIndex scopedVarStoreElimination(NodeIndex scope, NodeIndex registers, unsigned varNumber)
310 for (unsigned i = m_indexInBlock; i--;) {
311 NodeIndex index = m_currentBlock->at(i);
312 Node& node = m_graph[index];
313 if (!node.shouldGenerate())
317 if (node.child1() == scope && node.child2() == registers && node.varNumber() == varNumber)
323 // Let's be conservative.
324 if (node.varNumber() == varNumber)
330 VariableAccessData* variableAccessData = node.variableAccessData();
331 if (variableAccessData->isCaptured()
332 && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
340 if (m_graph.clobbersWorld(index) || node.canExit())
346 NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
348 for (unsigned i = m_indexInBlock; i--;) {
349 NodeIndex index = m_currentBlock->at(i);
350 if (index == child1 || index == canonicalize(child2))
353 Node& node = m_graph[index];
354 if (!node.shouldGenerate())
358 if (!m_graph.byValIsPure(node))
360 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
364 case PutByValAlias: {
365 if (!m_graph.byValIsPure(node))
367 if (m_graph.varArgChild(node, 0) == child1 && canonicalize(m_graph.varArgChild(node, 1)) == canonicalize(child2))
368 return m_graph.varArgChild(node, 2).index();
369 // We must assume that the PutByVal will clobber the location we're getting from.
370 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
371 // different type than the GetByVal, then we know that they won't clobber each other.
376 // GetByVal currently always speculates that it's accessing an
377 // array with an integer index, which means that it's impossible
378 // for a structure change or a put to property storage to affect
382 if (m_graph.clobbersWorld(index))
390 bool checkFunctionElimination(JSCell* function, NodeIndex child1)
392 for (unsigned i = endIndexForPureCSE(); i--;) {
393 NodeIndex index = m_currentBlock->at(i);
397 Node& node = m_graph[index];
398 if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
404 bool checkStructureElimination(const StructureSet& structureSet, NodeIndex child1)
406 for (unsigned i = m_indexInBlock; i--;) {
407 NodeIndex index = m_currentBlock->at(i);
411 Node& node = m_graph[index];
412 if (!node.shouldGenerate())
416 case ForwardCheckStructure:
417 if (node.child1() == child1
418 && structureSet.isSupersetOf(node.structureSet()))
422 case StructureTransitionWatchpoint:
423 case ForwardStructureTransitionWatchpoint:
424 if (node.child1() == child1
425 && structureSet.contains(node.structure()))
430 if (node.child1() == child1
431 && structureSet.contains(node.structureTransitionData().newStructure))
433 if (structureSet.contains(node.structureTransitionData().previousStructure))
438 // Setting a property cannot change the structure.
443 if (m_graph.byValIsPure(node)) {
444 // If PutByVal speculates that it's accessing an array with an
445 // integer index, then it's impossible for it to cause a structure
452 case ArrayifyToStructure:
453 // We could check if the arrayification could affect our structures.
454 // But that seems like it would take Effort.
458 if (m_graph.clobbersWorld(index))
466 bool structureTransitionWatchpointElimination(Structure* structure, NodeIndex child1)
468 for (unsigned i = m_indexInBlock; i--;) {
469 NodeIndex index = m_currentBlock->at(i);
473 Node& node = m_graph[index];
474 if (!node.shouldGenerate())
478 case ForwardCheckStructure:
479 if (node.child1() == child1
480 && node.structureSet().containsOnly(structure))
485 ASSERT(node.structureTransitionData().previousStructure != structure);
489 // Setting a property cannot change the structure.
494 if (m_graph.byValIsPure(node)) {
495 // If PutByVal speculates that it's accessing an array with an
496 // integer index, then it's impossible for it to cause a structure
502 case StructureTransitionWatchpoint:
503 case ForwardStructureTransitionWatchpoint:
504 if (node.structure() == structure && node.child1() == child1)
509 case ArrayifyToStructure:
510 // We could check if the arrayification could affect our structures.
511 // But that seems like it would take Effort.
515 if (m_graph.clobbersWorld(index))
523 NodeIndex putStructureStoreElimination(NodeIndex child1)
525 for (unsigned i = m_indexInBlock; i--;) {
526 NodeIndex index = m_currentBlock->at(i);
529 Node& node = m_graph[index];
530 if (!node.shouldGenerate())
534 case ForwardCheckStructure:
537 case PhantomPutStructure:
538 if (node.child1() == child1) // No need to retrace our steps.
543 if (node.child1() == child1)
547 // PutStructure needs to execute if we GC. Hence this needs to
548 // be careful with respect to nodes that GC.
549 case CreateArguments:
550 case TearOffArguments:
551 case NewFunctionNoCheck:
553 case NewFunctionExpression:
554 case CreateActivation:
555 case TearOffActivation:
563 case AllocatePropertyStorage:
564 case ReallocatePropertyStorage:
570 if (m_graph.clobbersWorld(index) || node.canExit())
576 NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
578 for (unsigned i = m_indexInBlock; i--;) {
579 NodeIndex index = m_currentBlock->at(i);
583 Node& node = m_graph[index];
584 if (!node.shouldGenerate())
588 if (node.child1() == child1
589 && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
594 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
595 if (node.child1() == child1) // Must be same property storage.
596 return node.child3().index();
602 // Changing the structure cannot change the outcome of a property get.
607 if (m_graph.byValIsPure(node)) {
608 // If PutByVal speculates that it's accessing an array with an
609 // integer index, then it's impossible for it to cause a structure
616 if (m_graph.clobbersWorld(index))
624 NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
626 for (unsigned i = m_indexInBlock; i--;) {
627 NodeIndex index = m_currentBlock->at(i);
631 Node& node = m_graph[index];
632 if (!node.shouldGenerate())
636 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
641 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
642 if (node.child1() == child1) // Must be same property storage.
651 if (m_graph.byValIsPure(node)) {
652 // If PutByVal speculates that it's accessing an array with an
653 // integer index, then it's impossible for it to cause a structure
660 if (m_graph.clobbersWorld(index))
670 NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
672 for (unsigned i = m_indexInBlock; i--;) {
673 NodeIndex index = m_currentBlock->at(i);
677 Node& node = m_graph[index];
678 if (!node.shouldGenerate())
682 if (node.child1() == child1)
686 case AllocatePropertyStorage:
687 case ReallocatePropertyStorage:
688 // If we can cheaply prove this is a change to our object's storage, we
689 // can optimize and use its result.
690 if (node.child1() == child1)
692 // Otherwise, we currently can't prove that this doesn't change our object's
693 // storage, so we conservatively assume that it may change the storage
694 // pointer of any object, including ours.
699 // Changing the structure or putting to the storage cannot
700 // change the property storage pointer.
705 if (m_graph.byValIsPure(node)) {
706 // If PutByVal speculates that it's accessing an array with an
707 // integer index, then it's impossible for it to cause a structure
714 case ArrayifyToStructure:
715 // We could check if the arrayification could affect our butterfly.
716 // But that seems like it would take Effort.
720 if (m_graph.clobbersWorld(index))
728 bool checkArrayElimination(NodeIndex child1, ArrayMode arrayMode)
730 for (unsigned i = m_indexInBlock; i--;) {
731 NodeIndex index = m_currentBlock->at(i);
735 Node& node = m_graph[index];
736 if (!node.shouldGenerate())
741 // Changing the structure or putting to the storage cannot
742 // change the property storage pointer.
746 if (node.child1() == child1 && node.arrayMode() == arrayMode)
751 case ArrayifyToStructure:
752 // We could check if the arrayification could affect our array.
753 // But that seems like it would take Effort.
757 if (m_graph.clobbersWorld(index))
765 NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, ArrayMode arrayMode)
767 for (unsigned i = m_indexInBlock; i--;) {
768 NodeIndex index = m_currentBlock->at(i);
772 Node& node = m_graph[index];
773 if (!node.shouldGenerate())
776 case GetIndexedPropertyStorage: {
777 if (node.child1() == child1 && node.arrayMode() == arrayMode)
784 // Changing the structure or putting to the storage cannot
785 // change the property storage pointer.
789 if (m_graph.clobbersWorld(index))
797 NodeIndex getMyScopeLoadElimination()
799 for (unsigned i = m_indexInBlock; i--;) {
800 NodeIndex index = m_currentBlock->at(i);
801 Node& node = m_graph[index];
802 if (!node.shouldGenerate())
805 case CreateActivation:
806 // This may cause us to return a different scope.
817 NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp, bool careAboutClobbering)
819 relevantLocalOp = NoNode;
821 for (unsigned i = m_indexInBlock; i--;) {
822 NodeIndex index = m_currentBlock->at(i);
823 Node& node = m_graph[index];
824 if (!node.shouldGenerate())
828 if (node.local() == local) {
829 relevantLocalOp = index;
834 case GetLocalUnlinked:
835 if (node.unlinkedLocal() == local) {
836 relevantLocalOp = index;
842 if (node.local() == local) {
843 relevantLocalOp = index;
844 return node.child1().index();
849 if (static_cast<VirtualRegister>(node.varNumber()) == local)
854 if (careAboutClobbering && m_graph.clobbersWorld(index))
862 struct SetLocalStoreEliminationResult {
863 SetLocalStoreEliminationResult()
864 : mayBeAccessed(false)
866 , mayClobberWorld(false)
872 bool mayClobberWorld;
874 SetLocalStoreEliminationResult setLocalStoreElimination(
875 VirtualRegister local, NodeIndex expectedNodeIndex)
877 SetLocalStoreEliminationResult result;
878 for (unsigned i = m_indexInBlock; i--;) {
879 NodeIndex index = m_currentBlock->at(i);
880 Node& node = m_graph[index];
881 if (!node.shouldGenerate())
886 if (node.local() == local)
887 result.mayBeAccessed = true;
890 case GetLocalUnlinked:
891 if (node.unlinkedLocal() == local)
892 result.mayBeAccessed = true;
896 if (node.local() != local)
898 if (index != expectedNodeIndex)
899 result.mayBeAccessed = true;
900 if (m_graph[index].refCount() > 1)
901 result.mayBeAccessed = true;
906 if (static_cast<VirtualRegister>(node.varNumber()) == local)
907 result.mayBeAccessed = true;
912 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
913 result.mayBeAccessed = true;
916 case CheckArgumentsNotCreated:
917 case GetMyArgumentsLength:
918 case GetMyArgumentsLengthSafe:
919 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
920 result.mayBeAccessed = true;
923 case GetMyArgumentByVal:
924 case GetMyArgumentByValSafe:
925 result.mayBeAccessed = true;
929 // If this is accessing arguments then it's potentially accessing locals.
930 if (m_graph[node.child1()].shouldSpeculateArguments())
931 result.mayBeAccessed = true;
934 case CreateArguments:
935 case TearOffActivation:
936 case TearOffArguments:
937 // If an activation is being torn off then it means that captured variables
938 // are live. We could be clever here and check if the local qualifies as an
939 // argument register. But that seems like it would buy us very little since
940 // any kind of tear offs are rare to begin with.
941 result.mayBeAccessed = true;
947 result.mayExit |= node.canExit();
948 result.mayClobberWorld |= m_graph.clobbersWorld(index);
950 ASSERT_NOT_REACHED();
951 // Be safe in release mode.
952 result.mayBeAccessed = true;
956 void performSubstitution(Edge& child, bool addRef = true)
958 // Check if this operand is actually unused.
962 // Check if there is any replacement.
963 NodeIndex replacement = m_replacements[child.index()];
964 if (replacement == NoNode)
967 child.setIndex(replacement);
969 // There is definitely a replacement. Assert that the replacement does not
970 // have a replacement.
971 ASSERT(m_replacements[child.index()] == NoNode);
977 void eliminateIrrelevantPhantomChildren(Node& node)
979 ASSERT(node.op() == Phantom);
980 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
981 Edge edge = node.children.child(i);
984 if (m_relevantToOSR.get(edge.index()))
987 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
988 dataLog(" Eliminating edge @", m_compileIndex, " -> @", edge.index());
991 node.children.removeEdgeFromBag(i--);
996 enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
997 bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
999 if (replacement == NoNode)
1002 // Be safe. Don't try to perform replacements if the predictions don't
1004 if (predictionHandlingMode == RequireSamePrediction
1005 && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
1008 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1009 dataLogF(" Replacing @%u -> @%u", m_compileIndex, replacement);
1012 Node& node = m_graph[m_compileIndex];
1013 node.setOpAndDefaultFlags(Phantom);
1014 node.setRefCount(1);
1015 eliminateIrrelevantPhantomChildren(node);
1017 // At this point we will eliminate all references to this node.
1018 m_replacements[m_compileIndex] = replacement;
1027 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1028 dataLogF(" Eliminating @%u", m_compileIndex);
1031 Node& node = m_graph[m_compileIndex];
1032 ASSERT(node.refCount() == 1);
1033 ASSERT(node.mustGenerate());
1034 node.setOpAndDefaultFlags(Phantom);
1035 eliminateIrrelevantPhantomChildren(node);
1040 void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
1042 if (nodeIndex == NoNode)
1044 Node& node = m_graph[nodeIndex];
1045 if (node.refCount() != 1)
1047 ASSERT(node.mustGenerate());
1048 node.setOpAndDefaultFlags(phantomType);
1049 if (phantomType == Phantom)
1050 eliminateIrrelevantPhantomChildren(node);
1055 void performNodeCSE(Node& node)
1057 bool shouldGenerate = node.shouldGenerate();
1059 if (node.flags() & NodeHasVarArgs) {
1060 for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1061 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
1063 performSubstitution(node.children.child1(), shouldGenerate);
1064 performSubstitution(node.children.child2(), shouldGenerate);
1065 performSubstitution(node.children.child3(), shouldGenerate);
1068 if (node.op() == SetLocal)
1069 m_relevantToOSR.set(node.child1().index());
1071 if (!shouldGenerate)
1074 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1075 dataLogF(" %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
1078 // NOTE: there are some nodes that we deliberately don't CSE even though we
1079 // probably could, like StrCat and ToPrimitive. That's because there is no
1080 // evidence that doing CSE on these nodes would result in a performance
1081 // progression. Hence considering these nodes in CSE would just mean that this
1082 // code does more work with no win. Of course, we may want to reconsider this,
1083 // since StrCat is trivially CSE-able. It's not trivially doable for
1084 // ToPrimitive, but we could change that with some speculations if we really
1087 switch (node.op()) {
1090 setReplacement(node.child1().index());
1093 // Handle the pure nodes. These nodes never have any side-effects.
1112 case StringCharCodeAt:
1124 case GetScopeRegisters:
1125 setReplacement(pureCSE(node));
1129 VariableAccessData* variableAccessData = node.variableAccessData();
1130 if (!variableAccessData->isCaptured())
1132 NodeIndex relevantLocalOp;
1133 NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
1134 if (relevantLocalOp == NoNode)
1136 if (m_graph[relevantLocalOp].op() != GetLocalUnlinked
1137 && m_graph[relevantLocalOp].variableAccessData() != variableAccessData)
1139 NodeIndex phiIndex = node.child1().index();
1140 if (!setReplacement(possibleReplacement))
1142 // If the GetLocal we replaced used to refer to a SetLocal, then it now
1143 // should refer to the child of the SetLocal instead.
1144 if (m_graph[phiIndex].op() == SetLocal) {
1145 ASSERT(node.child1().index() == phiIndex);
1146 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
1148 NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
1149 variableAccessData->local());
1150 if (oldTailIndex == m_compileIndex) {
1151 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
1154 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
1155 // make sure that the GetLocalUnlinked is now linked.
1156 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
1157 m_graph[relevantLocalOp].setOp(GetLocal);
1158 m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
1159 m_graph.ref(phiIndex);
1166 case GetLocalUnlinked: {
1167 NodeIndex relevantLocalOpIgnored;
1168 setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored, true));
1173 VariableAccessData* variableAccessData = node.variableAccessData();
1174 VirtualRegister local = variableAccessData->local();
1175 NodeIndex replacementIndex = node.child1().index();
1176 Node& replacement = m_graph[replacementIndex];
1177 if (replacement.op() != SetLocal)
1179 ASSERT(replacement.variableAccessData() == variableAccessData);
1180 // FIXME: We should be able to remove SetLocals that can exit; we just need
1181 // to replace them with appropriate type checks.
1182 if (m_graph.m_fixpointState == FixpointNotConverged) {
1183 // Need to be conservative at this time; if the SetLocal has any chance of performing
1184 // any speculations then we cannot do anything.
1185 if (variableAccessData->isCaptured()) {
1186 // Captured SetLocals never speculate and hence never exit.
1188 if (variableAccessData->shouldUseDoubleFormat())
1190 SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
1191 if (isInt32Speculation(prediction))
1193 if (isArraySpeculation(prediction))
1195 if (isBooleanSpeculation(prediction))
1199 if (replacement.canExit())
1202 SetLocalStoreEliminationResult result =
1203 setLocalStoreElimination(local, replacementIndex);
1204 if (result.mayBeAccessed || result.mayClobberWorld)
1206 ASSERT(replacement.op() == SetLocal);
1207 ASSERT(replacement.refCount() == 1);
1208 ASSERT(replacement.shouldGenerate());
1209 // FIXME: Investigate using mayExit as a further optimization.
1210 node.setOpAndDefaultFlags(Phantom);
1211 NodeIndex dataNodeIndex = replacement.child1().index();
1212 ASSERT(m_graph[dataNodeIndex].hasResult());
1213 m_graph.clearAndDerefChild1(node);
1214 node.children.child1() = Edge(dataNodeIndex);
1215 m_graph.ref(dataNodeIndex);
1216 NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
1217 if (oldTailIndex == m_compileIndex)
1218 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
1224 // This is strange, but necessary. Some phases will convert nodes to constants,
1225 // which may result in duplicated constants. We use CSE to clean this up.
1226 setReplacement(constantCSE(node), AllowPredictionMismatch);
1229 case WeakJSConstant:
1230 // FIXME: have CSE for weak constants against strong constants and vice-versa.
1231 setReplacement(weakConstantCSE(node));
1234 case GetArrayLength:
1235 setReplacement(getArrayLengthElimination(node.child1().index()));
1239 setReplacement(getMyScopeLoadElimination());
1242 // Handle nodes that are conditionally pure: these are pure, and can
1243 // be CSE'd, so long as the prediction is the one we want.
1247 case CompareGreater:
1248 case CompareGreaterEq:
1250 if (m_graph.isPredictedNumerical(node)) {
1251 NodeIndex replacementIndex = pureCSE(node);
1252 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
1253 setReplacement(replacementIndex);
1258 // Finally handle heap accesses. These are not quite pure, but we can still
1259 // optimize them provided that some subtle conditions are met.
1261 setReplacement(globalVarLoadElimination(node.registerPointer()));
1264 case GetScopedVar: {
1265 setReplacement(scopedVarLoadElimination(node.child1().index(), node.varNumber()));
1269 case GlobalVarWatchpoint:
1270 if (globalVarWatchpointElimination(node.registerPointer()))
1275 case PutGlobalVarCheck:
1276 if (m_graph.m_fixpointState == FixpointNotConverged)
1278 eliminate(globalVarStoreElimination(node.registerPointer()));
1281 case PutScopedVar: {
1282 if (m_graph.m_fixpointState == FixpointNotConverged)
1284 eliminate(scopedVarStoreElimination(node.child1().index(), node.child2().index(), node.varNumber()));
1289 if (m_graph.byValIsPure(node))
1290 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
1294 Edge child1 = m_graph.varArgChild(node, 0);
1295 Edge child2 = m_graph.varArgChild(node, 1);
1296 if (node.arrayMode().canCSEStorage()) {
1297 NodeIndex nodeIndex = getByValLoadElimination(child1.index(), child2.index());
1298 if (nodeIndex == NoNode)
1300 node.setOp(PutByValAlias);
1305 case CheckStructure:
1306 case ForwardCheckStructure:
1307 if (checkStructureElimination(node.structureSet(), node.child1().index()))
1311 case StructureTransitionWatchpoint:
1312 case ForwardStructureTransitionWatchpoint:
1313 if (structureTransitionWatchpointElimination(node.structure(), node.child1().index()))
1318 if (m_graph.m_fixpointState == FixpointNotConverged)
1320 eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1324 if (checkFunctionElimination(node.function(), node.child1().index()))
1329 if (checkArrayElimination(node.child1().index(), node.arrayMode()))
1333 case GetIndexedPropertyStorage: {
1334 setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), node.arrayMode()));
1339 setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1343 setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1347 if (m_graph.m_fixpointState == FixpointNotConverged)
1349 eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1353 // FIXME: we ought to remove Phantom's that have no children.
1355 eliminateIrrelevantPhantomChildren(node);
1363 m_lastSeen[node.op()] = m_indexInBlock;
1364 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1369 void performBlockCSE(BasicBlock* block)
1373 if (!block->isReachable)
1376 m_currentBlock = block;
1377 for (unsigned i = 0; i < LastNodeType; ++i)
1378 m_lastSeen[i] = UINT_MAX;
1380 // Make all of my Phi nodes relevant to OSR.
1381 for (unsigned i = 0; i < block->phis.size(); ++i)
1382 m_relevantToOSR.set(block->phis[i]);
1384 // Make all of my SetLocal nodes relevant to OSR.
1385 for (unsigned i = 0; i < block->size(); ++i) {
1386 NodeIndex nodeIndex = block->at(i);
1387 Node& node = m_graph[nodeIndex];
1388 switch (node.op()) {
1390 m_relevantToOSR.set(nodeIndex);
1397 for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1398 m_compileIndex = block->at(m_indexInBlock);
1399 performNodeCSE(m_graph[m_compileIndex]);
1403 BasicBlock* m_currentBlock;
1404 NodeIndex m_compileIndex;
1405 unsigned m_indexInBlock;
1406 Vector<NodeIndex, 16> m_replacements;
1407 FixedArray<unsigned, LastNodeType> m_lastSeen;
1408 FastBitVector m_relevantToOSR;
1409 bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1412 bool performCSE(Graph& graph)
1414 SamplingRegion samplingRegion("DFG CSE Phase");
1415 return runPhase<CSEPhase>(graph);
1418 } } // namespace JSC::DFG
1420 #endif // ENABLE(DFG_JIT)