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