e34beb3755ebebc1605ed3a832bd1e12360fe6de
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGGraph.h
1 /*
2  * Copyright (C) 2011-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
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.
12  *
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. 
24  */
25
26 #pragma once
27
28 #if ENABLE(DFG_JIT)
29
30 #include "AssemblyHelpers.h"
31 #include "BytecodeLivenessAnalysisInlines.h"
32 #include "CodeBlock.h"
33 #include "DFGArgumentPosition.h"
34 #include "DFGBasicBlock.h"
35 #include "DFGFrozenValue.h"
36 #include "DFGNode.h"
37 #include "DFGPlan.h"
38 #include "DFGPropertyTypeKey.h"
39 #include "DFGScannable.h"
40 #include "FullBytecodeLiveness.h"
41 #include "MethodOfGettingAValueProfile.h"
42 #include <unordered_map>
43 #include <wtf/BitVector.h>
44 #include <wtf/HashMap.h>
45 #include <wtf/Vector.h>
46 #include <wtf/StdLibExtras.h>
47
48 namespace JSC {
49
50 class CodeBlock;
51 class ExecState;
52
53 namespace DFG {
54
55 class BackwardsCFG;
56 class BackwardsDominators;
57 class CFG;
58 class ControlEquivalenceAnalysis;
59 class Dominators;
60 class FlowIndexing;
61 class NaturalLoops;
62 class PrePostNumbering;
63
64 template<typename> class FlowMap;
65
66 #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
67         Node* _node = (node);                                           \
68         if (_node->flags() & NodeHasVarArgs) {                          \
69             for (unsigned _childIdx = _node->firstChild();              \
70                 _childIdx < _node->firstChild() + _node->numChildren(); \
71                 _childIdx++) {                                          \
72                 if (!!(graph).m_varArgChildren[_childIdx])              \
73                     thingToDo(_node, (graph).m_varArgChildren[_childIdx]); \
74             }                                                           \
75         } else {                                                        \
76             if (!_node->child1()) {                                     \
77                 ASSERT(                                                 \
78                     !_node->child2()                                    \
79                     && !_node->child3());                               \
80                 break;                                                  \
81             }                                                           \
82             thingToDo(_node, _node->child1());                          \
83                                                                         \
84             if (!_node->child2()) {                                     \
85                 ASSERT(!_node->child3());                               \
86                 break;                                                  \
87             }                                                           \
88             thingToDo(_node, _node->child2());                          \
89                                                                         \
90             if (!_node->child3())                                       \
91                 break;                                                  \
92             thingToDo(_node, _node->child3());                          \
93         }                                                               \
94     } while (false)
95
96 #define DFG_ASSERT(graph, node, assertion) do {                         \
97         if (!!(assertion))                                              \
98             break;                                                      \
99         (graph).handleAssertionFailure(                                 \
100             (node), __FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
101     } while (false)
102
103 #define DFG_CRASH(graph, node, reason) do {                             \
104         (graph).handleAssertionFailure(                                 \
105             (node), __FILE__, __LINE__, WTF_PRETTY_FUNCTION, (reason)); \
106     } while (false)
107
108 struct InlineVariableData {
109     InlineCallFrame* inlineCallFrame;
110     unsigned argumentPositionStart;
111     VariableAccessData* calleeVariable;
112 };
113
114 enum AddSpeculationMode {
115     DontSpeculateInt32,
116     SpeculateInt32AndTruncateConstants,
117     SpeculateInt32
118 };
119
120 //
121 // === Graph ===
122 //
123 // The order may be significant for nodes with side-effects (property accesses, value conversions).
124 // Nodes that are 'dead' remain in the vector with refCount 0.
125 class Graph : public virtual Scannable {
126 public:
127     Graph(VM&, Plan&);
128     ~Graph();
129     
130     void changeChild(Edge& edge, Node* newNode)
131     {
132         edge.setNode(newNode);
133     }
134     
135     void changeEdge(Edge& edge, Edge newEdge)
136     {
137         edge = newEdge;
138     }
139     
140     void compareAndSwap(Edge& edge, Node* oldNode, Node* newNode)
141     {
142         if (edge.node() != oldNode)
143             return;
144         changeChild(edge, newNode);
145     }
146     
147     void compareAndSwap(Edge& edge, Edge oldEdge, Edge newEdge)
148     {
149         if (edge != oldEdge)
150             return;
151         changeEdge(edge, newEdge);
152     }
153     
154     void performSubstitution(Node* node)
155     {
156         if (node->flags() & NodeHasVarArgs) {
157             for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++)
158                 performSubstitutionForEdge(m_varArgChildren[childIdx]);
159         } else {
160             performSubstitutionForEdge(node->child1());
161             performSubstitutionForEdge(node->child2());
162             performSubstitutionForEdge(node->child3());
163         }
164     }
165     
166     void performSubstitutionForEdge(Edge& child)
167     {
168         // Check if this operand is actually unused.
169         if (!child)
170             return;
171         
172         // Check if there is any replacement.
173         Node* replacement = child->replacement();
174         if (!replacement)
175             return;
176         
177         child.setNode(replacement);
178         
179         // There is definitely a replacement. Assert that the replacement does not
180         // have a replacement.
181         ASSERT(!child->replacement());
182     }
183     
184     template<typename... Params>
185     Node* addNode(Params... params)
186     {
187         return m_nodes.addNew(params...);
188     }
189
190     template<typename... Params>
191     Node* addNode(SpeculatedType type, Params... params)
192     {
193         Node* node = m_nodes.addNew(params...);
194         node->predict(type);
195         return node;
196     }
197
198     void deleteNode(Node*);
199     unsigned maxNodeCount() const { return m_nodes.size(); }
200     Node* nodeAt(unsigned index) const { return m_nodes[index]; }
201     void packNodeIndices();
202
203     void dethread();
204     
205     FrozenValue* freeze(JSValue); // We use weak freezing by default.
206     FrozenValue* freezeStrong(JSValue); // Shorthand for freeze(value)->strengthenTo(StrongValue).
207     
208     void convertToConstant(Node* node, FrozenValue* value);
209     void convertToConstant(Node* node, JSValue value);
210     void convertToStrongConstant(Node* node, JSValue value);
211     
212     RegisteredStructure registerStructure(Structure* structure)
213     {
214         StructureRegistrationResult ignored;
215         return registerStructure(structure, ignored);
216     }
217     RegisteredStructure registerStructure(Structure*, StructureRegistrationResult&);
218     void assertIsRegistered(Structure* structure);
219     
220     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
221     void dump(PrintStream& = WTF::dataFile(), DumpContext* = 0);
222     
223     bool terminalsAreValid();
224     
225     enum PhiNodeDumpMode { DumpLivePhisOnly, DumpAllPhis };
226     void dumpBlockHeader(PrintStream&, const char* prefix, BasicBlock*, PhiNodeDumpMode, DumpContext*);
227     void dump(PrintStream&, Edge);
228     void dump(PrintStream&, const char* prefix, Node*, DumpContext* = 0);
229     static int amountOfNodeWhiteSpace(Node*);
230     static void printNodeWhiteSpace(PrintStream&, Node*);
231
232     // Dump the code origin of the given node as a diff from the code origin of the
233     // preceding node. Returns true if anything was printed.
234     bool dumpCodeOrigin(PrintStream&, const char* prefix, Node*& previousNode, Node* currentNode, DumpContext*);
235
236     AddSpeculationMode addSpeculationMode(Node* add, bool leftShouldSpeculateInt32, bool rightShouldSpeculateInt32, PredictionPass pass)
237     {
238         ASSERT(add->op() == ValueAdd || add->op() == ArithAdd || add->op() == ArithSub);
239         
240         RareCaseProfilingSource source = add->sourceFor(pass);
241         
242         Node* left = add->child1().node();
243         Node* right = add->child2().node();
244         
245         if (left->hasConstant())
246             return addImmediateShouldSpeculateInt32(add, rightShouldSpeculateInt32, right, left, source);
247         if (right->hasConstant())
248             return addImmediateShouldSpeculateInt32(add, leftShouldSpeculateInt32, left, right, source);
249         
250         return (leftShouldSpeculateInt32 && rightShouldSpeculateInt32 && add->canSpeculateInt32(source)) ? SpeculateInt32 : DontSpeculateInt32;
251     }
252     
253     AddSpeculationMode valueAddSpeculationMode(Node* add, PredictionPass pass)
254     {
255         return addSpeculationMode(
256             add,
257             add->child1()->shouldSpeculateInt32OrBooleanExpectingDefined(),
258             add->child2()->shouldSpeculateInt32OrBooleanExpectingDefined(),
259             pass);
260     }
261     
262     AddSpeculationMode arithAddSpeculationMode(Node* add, PredictionPass pass)
263     {
264         return addSpeculationMode(
265             add,
266             add->child1()->shouldSpeculateInt32OrBooleanForArithmetic(),
267             add->child2()->shouldSpeculateInt32OrBooleanForArithmetic(),
268             pass);
269     }
270     
271     AddSpeculationMode addSpeculationMode(Node* add, PredictionPass pass)
272     {
273         if (add->op() == ValueAdd)
274             return valueAddSpeculationMode(add, pass);
275         
276         return arithAddSpeculationMode(add, pass);
277     }
278     
279     bool addShouldSpeculateInt32(Node* add, PredictionPass pass)
280     {
281         return addSpeculationMode(add, pass) != DontSpeculateInt32;
282     }
283     
284     bool addShouldSpeculateAnyInt(Node* add)
285     {
286         if (!enableInt52())
287             return false;
288         
289         Node* left = add->child1().node();
290         Node* right = add->child2().node();
291
292         if (hasExitSite(add, Int52Overflow))
293             return false;
294
295         if (Node::shouldSpeculateAnyInt(left, right))
296             return true;
297
298         auto shouldSpeculateAnyIntForAdd = [](Node* node) {
299             auto isAnyIntSpeculationForAdd = [](SpeculatedType value) {
300                 return !!value && (value & (SpecAnyInt | SpecAnyIntAsDouble)) == value;
301             };
302
303             // When DoubleConstant node appears, it means that users explicitly write a constant in their code with double form instead of integer form (1.0 instead of 1).
304             // In that case, we should honor this decision: using it as integer is not appropriate.
305             if (node->op() == DoubleConstant)
306                 return false;
307             return isAnyIntSpeculationForAdd(node->prediction());
308         };
309
310         // Allow AnyInt ArithAdd only when the one side of the binary operation should be speculated AnyInt. It is a bit conservative
311         // decision. This is because Double to Int52 conversion is not so cheap. Frequent back-and-forth conversions between Double and Int52
312         // rather hurt the performance. If the one side of the operation is already Int52, the cost for constructing ArithAdd becomes
313         // cheap since only one Double to Int52 conversion could be required.
314         // This recovers some regression in assorted tests while keeping kraken crypto improvements.
315         if (!left->shouldSpeculateAnyInt() && !right->shouldSpeculateAnyInt())
316             return false;
317
318         auto usesAsNumbers = [](Node* node) {
319             NodeFlags flags = node->flags() & NodeBytecodeBackPropMask;
320             if (!flags)
321                 return false;
322             return (flags & (NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex)) == flags;
323         };
324
325         // Wrapping Int52 to Value is also not so cheap. Thus, we allow Int52 addition only when the node is used as number.
326         if (!usesAsNumbers(add))
327             return false;
328
329         return shouldSpeculateAnyIntForAdd(left) && shouldSpeculateAnyIntForAdd(right);
330     }
331     
332     bool binaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
333     {
334         Node* left = node->child1().node();
335         Node* right = node->child2().node();
336         
337         return Node::shouldSpeculateInt32OrBooleanForArithmetic(left, right)
338             && node->canSpeculateInt32(node->sourceFor(pass));
339     }
340     
341     bool binaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
342     {
343         if (!enableInt52())
344             return false;
345         
346         Node* left = node->child1().node();
347         Node* right = node->child2().node();
348
349         return Node::shouldSpeculateAnyInt(left, right)
350             && node->canSpeculateInt52(pass)
351             && !hasExitSite(node, Int52Overflow);
352     }
353     
354     bool unaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
355     {
356         return node->child1()->shouldSpeculateInt32OrBooleanForArithmetic()
357             && node->canSpeculateInt32(pass);
358     }
359     
360     bool unaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
361     {
362         if (!enableInt52())
363             return false;
364         return node->child1()->shouldSpeculateAnyInt()
365             && node->canSpeculateInt52(pass)
366             && !hasExitSite(node, Int52Overflow);
367     }
368
369     bool canOptimizeStringObjectAccess(const CodeOrigin&);
370
371     bool getRegExpPrototypeProperty(JSObject* regExpPrototype, Structure* regExpPrototypeStructure, UniquedStringImpl* uid, JSValue& returnJSValue);
372
373     bool roundShouldSpeculateInt32(Node* arithRound, PredictionPass pass)
374     {
375         ASSERT(arithRound->op() == ArithRound || arithRound->op() == ArithFloor || arithRound->op() == ArithCeil || arithRound->op() == ArithTrunc);
376         return arithRound->canSpeculateInt32(pass) && !hasExitSite(arithRound->origin.semantic, Overflow) && !hasExitSite(arithRound->origin.semantic, NegativeZero);
377     }
378     
379     static const char *opName(NodeType);
380     
381     RegisteredStructureSet* addStructureSet(const StructureSet& structureSet)
382     {
383         m_structureSets.append();
384         RegisteredStructureSet* result = &m_structureSets.last();
385
386         for (Structure* structure : structureSet)
387             result->add(registerStructure(structure));
388
389         return result;
390     }
391
392     RegisteredStructureSet* addStructureSet(const RegisteredStructureSet& structureSet)
393     {
394         m_structureSets.append();
395         RegisteredStructureSet* result = &m_structureSets.last();
396
397         for (RegisteredStructure structure : structureSet)
398             result->add(structure);
399
400         return result;
401     }
402     
403     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
404     {
405         return m_codeBlock->globalObjectFor(codeOrigin);
406     }
407     
408     JSObject* globalThisObjectFor(CodeOrigin codeOrigin)
409     {
410         JSGlobalObject* object = globalObjectFor(codeOrigin);
411         return jsCast<JSObject*>(object->methodTable()->toThis(object, object->globalExec(), NotStrictMode));
412     }
413     
414     ScriptExecutable* executableFor(InlineCallFrame* inlineCallFrame)
415     {
416         if (!inlineCallFrame)
417             return m_codeBlock->ownerScriptExecutable();
418         
419         return inlineCallFrame->baselineCodeBlock->ownerScriptExecutable();
420     }
421     
422     ScriptExecutable* executableFor(const CodeOrigin& codeOrigin)
423     {
424         return executableFor(codeOrigin.inlineCallFrame);
425     }
426     
427     CodeBlock* baselineCodeBlockFor(InlineCallFrame* inlineCallFrame)
428     {
429         if (!inlineCallFrame)
430             return m_profiledBlock;
431         return baselineCodeBlockForInlineCallFrame(inlineCallFrame);
432     }
433     
434     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
435     {
436         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
437     }
438     
439     bool isStrictModeFor(CodeOrigin codeOrigin)
440     {
441         if (!codeOrigin.inlineCallFrame)
442             return m_codeBlock->isStrictMode();
443         return codeOrigin.inlineCallFrame->isStrictMode();
444     }
445     
446     ECMAMode ecmaModeFor(CodeOrigin codeOrigin)
447     {
448         return isStrictModeFor(codeOrigin) ? StrictMode : NotStrictMode;
449     }
450     
451     bool masqueradesAsUndefinedWatchpointIsStillValid(const CodeOrigin& codeOrigin)
452     {
453         return globalObjectFor(codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid();
454     }
455     
456     bool hasGlobalExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
457     {
458         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(exitKind));
459     }
460     
461     bool hasExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
462     {
463         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(codeOrigin.bytecodeIndex, exitKind));
464     }
465     
466     bool hasExitSite(Node* node, ExitKind exitKind)
467     {
468         return hasExitSite(node->origin.semantic, exitKind);
469     }
470     
471     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(Node* currentNode, Node* operandNode);
472     
473     BlockIndex numBlocks() const { return m_blocks.size(); }
474     BasicBlock* block(BlockIndex blockIndex) const { return m_blocks[blockIndex].get(); }
475     BasicBlock* lastBlock() const { return block(numBlocks() - 1); }
476
477     void appendBlock(Ref<BasicBlock>&& basicBlock)
478     {
479         basicBlock->index = m_blocks.size();
480         m_blocks.append(WTFMove(basicBlock));
481     }
482     
483     void killBlock(BlockIndex blockIndex)
484     {
485         m_blocks[blockIndex] = nullptr;
486     }
487     
488     void killBlock(BasicBlock* basicBlock)
489     {
490         killBlock(basicBlock->index);
491     }
492     
493     void killBlockAndItsContents(BasicBlock*);
494     
495     void killUnreachableBlocks();
496     
497     void determineReachability();
498     void resetReachability();
499     
500     void computeRefCounts();
501     
502     unsigned varArgNumChildren(Node* node)
503     {
504         ASSERT(node->flags() & NodeHasVarArgs);
505         return node->numChildren();
506     }
507     
508     unsigned numChildren(Node* node)
509     {
510         if (node->flags() & NodeHasVarArgs)
511             return varArgNumChildren(node);
512         return AdjacencyList::Size;
513     }
514     
515     Edge& varArgChild(Node* node, unsigned index)
516     {
517         ASSERT(node->flags() & NodeHasVarArgs);
518         return m_varArgChildren[node->firstChild() + index];
519     }
520     
521     Edge& child(Node* node, unsigned index)
522     {
523         if (node->flags() & NodeHasVarArgs)
524             return varArgChild(node, index);
525         return node->children.child(index);
526     }
527     
528     void voteNode(Node* node, unsigned ballot, float weight = 1)
529     {
530         switch (node->op()) {
531         case ValueToInt32:
532         case UInt32ToNumber:
533             node = node->child1().node();
534             break;
535         default:
536             break;
537         }
538         
539         if (node->op() == GetLocal)
540             node->variableAccessData()->vote(ballot, weight);
541     }
542     
543     void voteNode(Edge edge, unsigned ballot, float weight = 1)
544     {
545         voteNode(edge.node(), ballot, weight);
546     }
547     
548     void voteChildren(Node* node, unsigned ballot, float weight = 1)
549     {
550         if (node->flags() & NodeHasVarArgs) {
551             for (unsigned childIdx = node->firstChild();
552                 childIdx < node->firstChild() + node->numChildren();
553                 childIdx++) {
554                 if (!!m_varArgChildren[childIdx])
555                     voteNode(m_varArgChildren[childIdx], ballot, weight);
556             }
557             return;
558         }
559         
560         if (!node->child1())
561             return;
562         voteNode(node->child1(), ballot, weight);
563         if (!node->child2())
564             return;
565         voteNode(node->child2(), ballot, weight);
566         if (!node->child3())
567             return;
568         voteNode(node->child3(), ballot, weight);
569     }
570     
571     template<typename T> // T = Node* or Edge
572     void substitute(BasicBlock& block, unsigned startIndexInBlock, T oldThing, T newThing)
573     {
574         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
575             Node* node = block[indexInBlock];
576             if (node->flags() & NodeHasVarArgs) {
577                 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); ++childIdx) {
578                     if (!!m_varArgChildren[childIdx])
579                         compareAndSwap(m_varArgChildren[childIdx], oldThing, newThing);
580                 }
581                 continue;
582             }
583             if (!node->child1())
584                 continue;
585             compareAndSwap(node->children.child1(), oldThing, newThing);
586             if (!node->child2())
587                 continue;
588             compareAndSwap(node->children.child2(), oldThing, newThing);
589             if (!node->child3())
590                 continue;
591             compareAndSwap(node->children.child3(), oldThing, newThing);
592         }
593     }
594     
595     // Use this if you introduce a new GetLocal and you know that you introduced it *before*
596     // any GetLocals in the basic block.
597     // FIXME: it may be appropriate, in the future, to generalize this to handle GetLocals
598     // introduced anywhere in the basic block.
599     void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal);
600     
601     void invalidateCFG();
602     void invalidateNodeLiveness();
603     
604     void clearFlagsOnAllNodes(NodeFlags);
605     
606     void clearReplacements();
607     void clearEpochs();
608     void initializeNodeOwners();
609     
610     BlockList blocksInPreOrder();
611     BlockList blocksInPostOrder();
612     
613     class NaturalBlockIterable {
614     public:
615         NaturalBlockIterable()
616             : m_graph(nullptr)
617         {
618         }
619         
620         NaturalBlockIterable(Graph& graph)
621             : m_graph(&graph)
622         {
623         }
624         
625         class iterator {
626         public:
627             iterator()
628                 : m_graph(nullptr)
629                 , m_index(0)
630             {
631             }
632             
633             iterator(Graph& graph, BlockIndex index)
634                 : m_graph(&graph)
635                 , m_index(findNext(index))
636             {
637             }
638             
639             BasicBlock *operator*()
640             {
641                 return m_graph->block(m_index);
642             }
643             
644             iterator& operator++()
645             {
646                 m_index = findNext(m_index + 1);
647                 return *this;
648             }
649             
650             bool operator==(const iterator& other) const
651             {
652                 return m_index == other.m_index;
653             }
654             
655             bool operator!=(const iterator& other) const
656             {
657                 return !(*this == other);
658             }
659             
660         private:
661             BlockIndex findNext(BlockIndex index)
662             {
663                 while (index < m_graph->numBlocks() && !m_graph->block(index))
664                     index++;
665                 return index;
666             }
667             
668             Graph* m_graph;
669             BlockIndex m_index;
670         };
671         
672         iterator begin()
673         {
674             return iterator(*m_graph, 0);
675         }
676         
677         iterator end()
678         {
679             return iterator(*m_graph, m_graph->numBlocks());
680         }
681         
682     private:
683         Graph* m_graph;
684     };
685     
686     NaturalBlockIterable blocksInNaturalOrder()
687     {
688         return NaturalBlockIterable(*this);
689     }
690     
691     template<typename ChildFunctor>
692     void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
693     {
694         DFG_NODE_DO_TO_CHILDREN(*this, node, functor);
695     }
696     
697     template<typename ChildFunctor>
698     void doToChildren(Node* node, const ChildFunctor& functor)
699     {
700         doToChildrenWithNode(
701             node,
702             [&functor] (Node*, Edge& edge) {
703                 functor(edge);
704             });
705     }
706     
707     bool uses(Node* node, Node* child)
708     {
709         bool result = false;
710         doToChildren(node, [&] (Edge edge) { result |= edge == child; });
711         return result;
712     }
713
714     bool isWatchingHavingABadTimeWatchpoint(Node* node)
715     {
716         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
717         return watchpoints().isWatched(globalObject->havingABadTimeWatchpoint());
718     }
719
720     bool isWatchingArrayIteratorProtocolWatchpoint(Node* node)
721     {
722         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
723         InlineWatchpointSet& set = globalObject->arrayIteratorProtocolWatchpoint();
724         if (watchpoints().isWatched(set))
725             return true;
726
727         if (set.isStillValid()) {
728             // Since the global object owns this watchpoint, we make ourselves have a weak pointer to it.
729             // If the global object got deallocated, it wouldn't fire the watchpoint. It's unlikely the
730             // global object would get deallocated without this code ever getting thrown away, however,
731             // it's more sound logically to depend on the global object lifetime weakly.
732             freeze(globalObject);
733             watchpoints().addLazily(set);
734             return true;
735         }
736
737         return false;
738     }
739     
740     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
741     
742     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
743     DesiredWatchpoints& watchpoints() { return m_plan.watchpoints; }
744     
745     // Returns false if the key is already invalid or unwatchable. If this is a Presence condition,
746     // this also makes it cheap to query if the condition holds. Also makes sure that the GC knows
747     // what's going on.
748     bool watchCondition(const ObjectPropertyCondition&);
749     bool watchConditions(const ObjectPropertyConditionSet&);
750
751     // Checks if it's known that loading from the given object at the given offset is fine. This is
752     // computed by tracking which conditions we track with watchCondition().
753     bool isSafeToLoad(JSObject* base, PropertyOffset);
754
755     void registerInferredType(const InferredType::Descriptor& type)
756     {
757         if (type.structure())
758             registerStructure(type.structure());
759     }
760
761     // Tells us what inferred type we are able to prove the property to have now and in the future.
762     InferredType::Descriptor inferredTypeFor(const PropertyTypeKey&);
763     InferredType::Descriptor inferredTypeForProperty(Structure* structure, UniquedStringImpl* uid)
764     {
765         return inferredTypeFor(PropertyTypeKey(structure, uid));
766     }
767
768     AbstractValue inferredValueForProperty(
769         const RegisteredStructureSet& base, UniquedStringImpl* uid, StructureClobberState = StructuresAreWatched);
770
771     // This uses either constant property inference or property type inference to derive a good abstract
772     // value for some property accessed with the given abstract value base.
773     AbstractValue inferredValueForProperty(
774         const AbstractValue& base, UniquedStringImpl* uid, PropertyOffset, StructureClobberState);
775     
776     FullBytecodeLiveness& livenessFor(CodeBlock*);
777     FullBytecodeLiveness& livenessFor(InlineCallFrame*);
778     
779     // Quickly query if a single local is live at the given point. This is faster than calling
780     // forAllLiveInBytecode() if you will only query one local. But, if you want to know all of the
781     // locals live, then calling this for each local is much slower than forAllLiveInBytecode().
782     bool isLiveInBytecode(VirtualRegister, CodeOrigin);
783     
784     // Quickly get all of the non-argument locals live at the given point. This doesn't give you
785     // any arguments because those are all presumed live. You can call forAllLiveInBytecode() to
786     // also get the arguments. This is much faster than calling isLiveInBytecode() for each local.
787     template<typename Functor>
788     void forAllLocalsLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
789     {
790         // Support for not redundantly reporting arguments. Necessary because in case of a varargs
791         // call, only the callee knows that arguments are live while in the case of a non-varargs
792         // call, both callee and caller will see the variables live.
793         VirtualRegister exclusionStart;
794         VirtualRegister exclusionEnd;
795
796         CodeOrigin* codeOriginPtr = &codeOrigin;
797         
798         for (;;) {
799             InlineCallFrame* inlineCallFrame = codeOriginPtr->inlineCallFrame;
800             VirtualRegister stackOffset(inlineCallFrame ? inlineCallFrame->stackOffset : 0);
801             
802             if (inlineCallFrame) {
803                 if (inlineCallFrame->isClosureCall)
804                     functor(stackOffset + CallFrameSlot::callee);
805                 if (inlineCallFrame->isVarargs())
806                     functor(stackOffset + CallFrameSlot::argumentCount);
807             }
808             
809             CodeBlock* codeBlock = baselineCodeBlockFor(inlineCallFrame);
810             FullBytecodeLiveness& fullLiveness = livenessFor(codeBlock);
811             const FastBitVector& liveness = fullLiveness.getLiveness(codeOriginPtr->bytecodeIndex);
812             for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
813                 VirtualRegister reg = stackOffset + virtualRegisterForLocal(relativeLocal);
814                 
815                 // Don't report if our callee already reported.
816                 if (reg >= exclusionStart && reg < exclusionEnd)
817                     continue;
818                 
819                 if (liveness[relativeLocal])
820                     functor(reg);
821             }
822             
823             if (!inlineCallFrame)
824                 break;
825
826             // Arguments are always live. This would be redundant if it wasn't for our
827             // op_call_varargs inlining. See the comment above.
828             exclusionStart = stackOffset + CallFrame::argumentOffsetIncludingThis(0);
829             exclusionEnd = stackOffset + CallFrame::argumentOffsetIncludingThis(inlineCallFrame->arguments.size());
830             
831             // We will always have a "this" argument and exclusionStart should be a smaller stack
832             // offset than exclusionEnd.
833             ASSERT(exclusionStart < exclusionEnd);
834
835             for (VirtualRegister reg = exclusionStart; reg < exclusionEnd; reg += 1)
836                 functor(reg);
837             
838             codeOriginPtr = inlineCallFrame->getCallerSkippingTailCalls();
839
840             // The first inline call frame could be an inline tail call
841             if (!codeOriginPtr)
842                 break;
843         }
844     }
845     
846     // Get a BitVector of all of the non-argument locals live right now. This is mostly useful if
847     // you want to compare two sets of live locals from two different CodeOrigins.
848     BitVector localsLiveInBytecode(CodeOrigin);
849     
850     // Tells you all of the arguments and locals live at the given CodeOrigin. This is a small
851     // extension to forAllLocalsLiveInBytecode(), since all arguments are always presumed live.
852     template<typename Functor>
853     void forAllLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
854     {
855         forAllLocalsLiveInBytecode(codeOrigin, functor);
856         
857         // Report all arguments as being live.
858         for (unsigned argument = block(0)->variablesAtHead.numberOfArguments(); argument--;)
859             functor(virtualRegisterForArgument(argument));
860     }
861     
862     BytecodeKills& killsFor(CodeBlock*);
863     BytecodeKills& killsFor(InlineCallFrame*);
864     
865     static unsigned parameterSlotsForArgCount(unsigned);
866     
867     unsigned frameRegisterCount();
868     unsigned stackPointerOffset();
869     unsigned requiredRegisterCountForExit();
870     unsigned requiredRegisterCountForExecutionAndExit();
871     
872     JSValue tryGetConstantProperty(JSValue base, const RegisteredStructureSet&, PropertyOffset);
873     JSValue tryGetConstantProperty(JSValue base, Structure*, PropertyOffset);
874     JSValue tryGetConstantProperty(JSValue base, const StructureAbstractValue&, PropertyOffset);
875     JSValue tryGetConstantProperty(const AbstractValue&, PropertyOffset);
876     
877     JSValue tryGetConstantClosureVar(JSValue base, ScopeOffset);
878     JSValue tryGetConstantClosureVar(const AbstractValue&, ScopeOffset);
879     JSValue tryGetConstantClosureVar(Node*, ScopeOffset);
880     
881     JSArrayBufferView* tryGetFoldableView(JSValue);
882     JSArrayBufferView* tryGetFoldableView(JSValue, ArrayMode arrayMode);
883
884     bool canDoFastSpread(Node*, const AbstractValue&);
885     
886     void registerFrozenValues();
887     
888     void visitChildren(SlotVisitor&) override;
889     
890     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
891         std::nullptr_t, const char* file, int line, const char* function,
892         const char* assertion);
893     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
894         Node*, const char* file, int line, const char* function,
895         const char* assertion);
896     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
897         BasicBlock*, const char* file, int line, const char* function,
898         const char* assertion);
899
900     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
901
902     Dominators& ensureDominators();
903     PrePostNumbering& ensurePrePostNumbering();
904     NaturalLoops& ensureNaturalLoops();
905     BackwardsCFG& ensureBackwardsCFG();
906     BackwardsDominators& ensureBackwardsDominators();
907     ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
908
909     // This function only makes sense to call after bytecode parsing
910     // because it queries the m_hasExceptionHandlers boolean whose value
911     // is only fully determined after bytcode parsing.
912     bool willCatchExceptionInMachineFrame(CodeOrigin, CodeOrigin& opCatchOriginOut, HandlerInfo*& catchHandlerOut);
913     
914     bool needsScopeRegister() const { return m_hasDebuggerEnabled || m_codeBlock->usesEval(); }
915     bool needsFlushedThis() const { return m_codeBlock->usesEval(); }
916
917     VM& m_vm;
918     Plan& m_plan;
919     CodeBlock* m_codeBlock;
920     CodeBlock* m_profiledBlock;
921     
922     Vector< RefPtr<BasicBlock> , 8> m_blocks;
923     Vector<Edge, 16> m_varArgChildren;
924
925     HashMap<EncodedJSValue, FrozenValue*, EncodedJSValueHash, EncodedJSValueHashTraits> m_frozenValueMap;
926     Bag<FrozenValue> m_frozenValues;
927
928     Vector<uint32_t> m_uint32ValuesInUse;
929     
930     Bag<StorageAccessData> m_storageAccessData;
931     
932     // In CPS, this is all of the SetArgument nodes for the arguments in the machine code block
933     // that survived DCE. All of them except maybe "this" will survive DCE, because of the Flush
934     // nodes.
935     //
936     // In SSA, this is all of the GetStack nodes for the arguments in the machine code block that
937     // may have some speculation in the prologue and survived DCE. Note that to get the speculation
938     // for an argument in SSA, you must use m_argumentFormats, since we still have to speculate
939     // even if the argument got killed. For example:
940     //
941     //     function foo(x) {
942     //        var tmp = x + 1;
943     //     }
944     //
945     // Assume that x is always int during profiling. The ArithAdd for "x + 1" will be dead and will
946     // have a proven check for the edge to "x". So, we will not insert a Check node and we will
947     // kill the GetStack for "x". But, we must do the int check in the progolue, because that's the
948     // thing we used to allow DCE of ArithAdd. Otherwise the add could be impure:
949     //
950     //     var o = {
951     //         valueOf: function() { do side effects; }
952     //     };
953     //     foo(o);
954     //
955     // If we DCE the ArithAdd and we remove the int check on x, then this won't do the side
956     // effects.
957     Vector<Node*, 8> m_arguments;
958     
959     // In CPS, this is meaningless. In SSA, this is the argument speculation that we've locked in.
960     Vector<FlushFormat> m_argumentFormats;
961     
962     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
963     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
964     Bag<Transition> m_transitions;
965     SegmentedVector<NewArrayBufferData, 4> m_newArrayBufferData;
966     Bag<BranchData> m_branchData;
967     Bag<SwitchData> m_switchData;
968     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
969     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
970     Bag<ObjectMaterializationData> m_objectMaterializationData;
971     Bag<CallVarargsData> m_callVarargsData;
972     Bag<LoadVarargsData> m_loadVarargsData;
973     Bag<StackAccessData> m_stackAccessData;
974     Bag<LazyJSValue> m_lazyJSValues;
975     Bag<CallDOMGetterData> m_callDOMGetterData;
976     Bag<BitVector> m_bitVectors;
977     Vector<InlineVariableData, 4> m_inlineVariableData;
978     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
979     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
980     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
981     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
982     Vector<Ref<Snippet>> m_domJITSnippets;
983     std::unique_ptr<Dominators> m_dominators;
984     std::unique_ptr<PrePostNumbering> m_prePostNumbering;
985     std::unique_ptr<NaturalLoops> m_naturalLoops;
986     std::unique_ptr<CFG> m_cfg;
987     std::unique_ptr<BackwardsCFG> m_backwardsCFG;
988     std::unique_ptr<BackwardsDominators> m_backwardsDominators;
989     std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
990     unsigned m_localVars;
991     unsigned m_nextMachineLocal;
992     unsigned m_parameterSlots;
993     
994     HashSet<String> m_localStrings;
995     HashMap<const StringImpl*, String> m_copiedStrings;
996
997 #if USE(JSVALUE32_64)
998     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
999     std::unique_ptr<Bag<double>> m_doubleConstants;
1000 #endif
1001     
1002     OptimizationFixpointState m_fixpointState;
1003     StructureRegistrationState m_structureRegistrationState;
1004     GraphForm m_form;
1005     UnificationState m_unificationState;
1006     PlanStage m_planStage { PlanStage::Initial };
1007     RefCountState m_refCountState;
1008     bool m_hasDebuggerEnabled;
1009     bool m_hasExceptionHandlers { false };
1010     std::unique_ptr<FlowIndexing> m_indexingCache;
1011     std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
1012
1013     RegisteredStructure stringStructure;
1014     RegisteredStructure symbolStructure;
1015
1016 private:
1017     bool isStringPrototypeMethodSane(JSGlobalObject*, UniquedStringImpl*);
1018
1019     void handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock*, BasicBlock* successor);
1020     
1021     AddSpeculationMode addImmediateShouldSpeculateInt32(Node* add, bool variableShouldSpeculateInt32, Node* operand, Node*immediate, RareCaseProfilingSource source)
1022     {
1023         ASSERT(immediate->hasConstant());
1024         
1025         JSValue immediateValue = immediate->asJSValue();
1026         if (!immediateValue.isNumber() && !immediateValue.isBoolean())
1027             return DontSpeculateInt32;
1028         
1029         if (!variableShouldSpeculateInt32)
1030             return DontSpeculateInt32;
1031
1032         // Integer constants can be typed Double if they are written like a double in the source code (e.g. 42.0).
1033         // In that case, we stay conservative unless the other operand was explicitly typed as integer.
1034         NodeFlags operandResultType = operand->result();
1035         if (operandResultType != NodeResultInt32 && immediateValue.isDouble())
1036             return DontSpeculateInt32;
1037         
1038         if (immediateValue.isBoolean() || jsNumber(immediateValue.asNumber()).isInt32())
1039             return add->canSpeculateInt32(source) ? SpeculateInt32 : DontSpeculateInt32;
1040         
1041         double doubleImmediate = immediateValue.asDouble();
1042         const double twoToThe48 = 281474976710656.0;
1043         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
1044             return DontSpeculateInt32;
1045         
1046         return bytecodeCanTruncateInteger(add->arithNodeFlags()) ? SpeculateInt32AndTruncateConstants : DontSpeculateInt32;
1047     }
1048
1049     B3::SparseCollection<Node> m_nodes;
1050     SegmentedVector<RegisteredStructureSet, 16> m_structureSets;
1051 };
1052
1053 } } // namespace JSC::DFG
1054
1055 #endif