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