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