7ca0ac79ddc9dbd7d770eb65d534fe677e031a3d
[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 mulShouldSpeculateInt32(Node* mul, PredictionPass pass)
279     {
280         ASSERT(mul->op() == ArithMul);
281         
282         Node* left = mul->child1().node();
283         Node* right = mul->child2().node();
284         
285         return Node::shouldSpeculateInt32OrBooleanForArithmetic(left, right)
286             && mul->canSpeculateInt32(mul->sourceFor(pass));
287     }
288     
289     bool mulShouldSpeculateMachineInt(Node* mul, PredictionPass pass)
290     {
291         ASSERT(mul->op() == ArithMul);
292         
293         if (!enableInt52())
294             return false;
295         
296         Node* left = mul->child1().node();
297         Node* right = mul->child2().node();
298
299         return Node::shouldSpeculateMachineInt(left, right)
300             && mul->canSpeculateInt52(pass)
301             && !hasExitSite(mul, Int52Overflow);
302     }
303     
304     bool negateShouldSpeculateInt32(Node* negate, PredictionPass pass)
305     {
306         ASSERT(negate->op() == ArithNegate);
307         return negate->child1()->shouldSpeculateInt32OrBooleanForArithmetic()
308             && negate->canSpeculateInt32(pass);
309     }
310     
311     bool negateShouldSpeculateMachineInt(Node* negate, PredictionPass pass)
312     {
313         ASSERT(negate->op() == ArithNegate);
314         if (!enableInt52())
315             return false;
316         return negate->child1()->shouldSpeculateMachineInt()
317             && !hasExitSite(negate, Int52Overflow)
318             && negate->canSpeculateInt52(pass);
319     }
320
321     bool roundShouldSpeculateInt32(Node* arithRound, PredictionPass pass)
322     {
323         ASSERT(arithRound->op() == ArithRound);
324         return arithRound->canSpeculateInt32(pass) && !hasExitSite(arithRound->origin.semantic, Overflow) && !hasExitSite(arithRound->origin.semantic, NegativeZero);
325     }
326     
327     static const char *opName(NodeType);
328     
329     StructureSet* addStructureSet(const StructureSet& structureSet)
330     {
331         for (Structure* structure : structureSet)
332             registerStructure(structure);
333         m_structureSet.append(structureSet);
334         return &m_structureSet.last();
335     }
336     
337     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
338     {
339         return m_codeBlock->globalObjectFor(codeOrigin);
340     }
341     
342     JSObject* globalThisObjectFor(CodeOrigin codeOrigin)
343     {
344         JSGlobalObject* object = globalObjectFor(codeOrigin);
345         return jsCast<JSObject*>(object->methodTable()->toThis(object, object->globalExec(), NotStrictMode));
346     }
347     
348     ScriptExecutable* executableFor(InlineCallFrame* inlineCallFrame)
349     {
350         if (!inlineCallFrame)
351             return m_codeBlock->ownerScriptExecutable();
352         
353         return inlineCallFrame->baselineCodeBlock->ownerScriptExecutable();
354     }
355     
356     ScriptExecutable* executableFor(const CodeOrigin& codeOrigin)
357     {
358         return executableFor(codeOrigin.inlineCallFrame);
359     }
360     
361     CodeBlock* baselineCodeBlockFor(InlineCallFrame* inlineCallFrame)
362     {
363         if (!inlineCallFrame)
364             return m_profiledBlock;
365         return baselineCodeBlockForInlineCallFrame(inlineCallFrame);
366     }
367     
368     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
369     {
370         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
371     }
372     
373     bool isStrictModeFor(CodeOrigin codeOrigin)
374     {
375         if (!codeOrigin.inlineCallFrame)
376             return m_codeBlock->isStrictMode();
377         return codeOrigin.inlineCallFrame->isStrictMode();
378     }
379     
380     ECMAMode ecmaModeFor(CodeOrigin codeOrigin)
381     {
382         return isStrictModeFor(codeOrigin) ? StrictMode : NotStrictMode;
383     }
384     
385     bool masqueradesAsUndefinedWatchpointIsStillValid(const CodeOrigin& codeOrigin)
386     {
387         return globalObjectFor(codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid();
388     }
389     
390     bool hasGlobalExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
391     {
392         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(exitKind));
393     }
394     
395     bool hasExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
396     {
397         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(codeOrigin.bytecodeIndex, exitKind));
398     }
399     
400     bool hasExitSite(Node* node, ExitKind exitKind)
401     {
402         return hasExitSite(node->origin.semantic, exitKind);
403     }
404     
405     VirtualRegister activationRegister()
406     {
407         return m_profiledBlock->activationRegister();
408     }
409     
410     VirtualRegister uncheckedActivationRegister()
411     {
412         return m_profiledBlock->uncheckedActivationRegister();
413     }
414     
415     VirtualRegister machineActivationRegister()
416     {
417         return m_profiledBlock->activationRegister();
418     }
419     
420     VirtualRegister uncheckedMachineActivationRegister()
421     {
422         return m_profiledBlock->uncheckedActivationRegister();
423     }
424     
425     ValueProfile* valueProfileFor(Node*);
426     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(Node*);
427     
428     BlockIndex numBlocks() const { return m_blocks.size(); }
429     BasicBlock* block(BlockIndex blockIndex) const { return m_blocks[blockIndex].get(); }
430     BasicBlock* lastBlock() const { return block(numBlocks() - 1); }
431
432     void appendBlock(PassRefPtr<BasicBlock> basicBlock)
433     {
434         basicBlock->index = m_blocks.size();
435         m_blocks.append(basicBlock);
436     }
437     
438     void killBlock(BlockIndex blockIndex)
439     {
440         m_blocks[blockIndex] = nullptr;
441     }
442     
443     void killBlock(BasicBlock* basicBlock)
444     {
445         killBlock(basicBlock->index);
446     }
447     
448     void killBlockAndItsContents(BasicBlock*);
449     
450     void killUnreachableBlocks();
451     
452     void determineReachability();
453     void resetReachability();
454     
455     void computeRefCounts();
456     
457     unsigned varArgNumChildren(Node* node)
458     {
459         ASSERT(node->flags() & NodeHasVarArgs);
460         return node->numChildren();
461     }
462     
463     unsigned numChildren(Node* node)
464     {
465         if (node->flags() & NodeHasVarArgs)
466             return varArgNumChildren(node);
467         return AdjacencyList::Size;
468     }
469     
470     Edge& varArgChild(Node* node, unsigned index)
471     {
472         ASSERT(node->flags() & NodeHasVarArgs);
473         return m_varArgChildren[node->firstChild() + index];
474     }
475     
476     Edge& child(Node* node, unsigned index)
477     {
478         if (node->flags() & NodeHasVarArgs)
479             return varArgChild(node, index);
480         return node->children.child(index);
481     }
482     
483     void voteNode(Node* node, unsigned ballot, float weight = 1)
484     {
485         switch (node->op()) {
486         case ValueToInt32:
487         case UInt32ToNumber:
488             node = node->child1().node();
489             break;
490         default:
491             break;
492         }
493         
494         if (node->op() == GetLocal)
495             node->variableAccessData()->vote(ballot, weight);
496     }
497     
498     void voteNode(Edge edge, unsigned ballot, float weight = 1)
499     {
500         voteNode(edge.node(), ballot, weight);
501     }
502     
503     void voteChildren(Node* node, unsigned ballot, float weight = 1)
504     {
505         if (node->flags() & NodeHasVarArgs) {
506             for (unsigned childIdx = node->firstChild();
507                 childIdx < node->firstChild() + node->numChildren();
508                 childIdx++) {
509                 if (!!m_varArgChildren[childIdx])
510                     voteNode(m_varArgChildren[childIdx], ballot, weight);
511             }
512             return;
513         }
514         
515         if (!node->child1())
516             return;
517         voteNode(node->child1(), ballot, weight);
518         if (!node->child2())
519             return;
520         voteNode(node->child2(), ballot, weight);
521         if (!node->child3())
522             return;
523         voteNode(node->child3(), ballot, weight);
524     }
525     
526     template<typename T> // T = Node* or Edge
527     void substitute(BasicBlock& block, unsigned startIndexInBlock, T oldThing, T newThing)
528     {
529         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
530             Node* node = block[indexInBlock];
531             if (node->flags() & NodeHasVarArgs) {
532                 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); ++childIdx) {
533                     if (!!m_varArgChildren[childIdx])
534                         compareAndSwap(m_varArgChildren[childIdx], oldThing, newThing);
535                 }
536                 continue;
537             }
538             if (!node->child1())
539                 continue;
540             compareAndSwap(node->children.child1(), oldThing, newThing);
541             if (!node->child2())
542                 continue;
543             compareAndSwap(node->children.child2(), oldThing, newThing);
544             if (!node->child3())
545                 continue;
546             compareAndSwap(node->children.child3(), oldThing, newThing);
547         }
548     }
549     
550     // Use this if you introduce a new GetLocal and you know that you introduced it *before*
551     // any GetLocals in the basic block.
552     // FIXME: it may be appropriate, in the future, to generalize this to handle GetLocals
553     // introduced anywhere in the basic block.
554     void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal);
555     
556     void invalidateCFG();
557     
558     void clearFlagsOnAllNodes(NodeFlags);
559     
560     void clearReplacements();
561     void clearEpochs();
562     void initializeNodeOwners();
563     
564     BlockList blocksInPreOrder();
565     BlockList blocksInPostOrder();
566     
567     class NaturalBlockIterable {
568     public:
569         NaturalBlockIterable()
570             : m_graph(nullptr)
571         {
572         }
573         
574         NaturalBlockIterable(Graph& graph)
575             : m_graph(&graph)
576         {
577         }
578         
579         class iterator {
580         public:
581             iterator()
582                 : m_graph(nullptr)
583                 , m_index(0)
584             {
585             }
586             
587             iterator(Graph& graph, BlockIndex index)
588                 : m_graph(&graph)
589                 , m_index(findNext(index))
590             {
591             }
592             
593             BasicBlock *operator*()
594             {
595                 return m_graph->block(m_index);
596             }
597             
598             iterator& operator++()
599             {
600                 m_index = findNext(m_index + 1);
601                 return *this;
602             }
603             
604             bool operator==(const iterator& other) const
605             {
606                 return m_index == other.m_index;
607             }
608             
609             bool operator!=(const iterator& other) const
610             {
611                 return !(*this == other);
612             }
613             
614         private:
615             BlockIndex findNext(BlockIndex index)
616             {
617                 while (index < m_graph->numBlocks() && !m_graph->block(index))
618                     index++;
619                 return index;
620             }
621             
622             Graph* m_graph;
623             BlockIndex m_index;
624         };
625         
626         iterator begin()
627         {
628             return iterator(*m_graph, 0);
629         }
630         
631         iterator end()
632         {
633             return iterator(*m_graph, m_graph->numBlocks());
634         }
635         
636     private:
637         Graph* m_graph;
638     };
639     
640     NaturalBlockIterable blocksInNaturalOrder()
641     {
642         return NaturalBlockIterable(*this);
643     }
644     
645     template<typename ChildFunctor>
646     void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
647     {
648         DFG_NODE_DO_TO_CHILDREN(*this, node, functor);
649     }
650     
651     template<typename ChildFunctor>
652     void doToChildren(Node* node, const ChildFunctor& functor)
653     {
654         doToChildrenWithNode(
655             node,
656             [&functor] (Node*, Edge& edge) {
657                 functor(edge);
658             });
659     }
660     
661     bool uses(Node* node, Node* child)
662     {
663         bool result = false;
664         doToChildren(node, [&] (Edge edge) { result |= edge == child; });
665         return result;
666     }
667     
668     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
669     
670     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
671     DesiredWatchpoints& watchpoints() { return m_plan.watchpoints; }
672     
673     // Returns false if the key is already invalid or unwatchable. If this is a Presence condition,
674     // this also makes it cheap to query if the condition holds. Also makes sure that the GC knows
675     // what's going on.
676     bool watchCondition(const ObjectPropertyCondition&);
677
678     // Checks if it's known that loading from the given object at the given offset is fine. This is
679     // computed by tracking which conditions we track with watchCondition().
680     bool isSafeToLoad(JSObject* base, PropertyOffset);
681
682     void registerInferredType(const InferredType::Descriptor& type)
683     {
684         if (type.structure())
685             registerStructure(type.structure());
686     }
687
688     // Tells us what inferred type we are able to prove the property to have now and in the future.
689     InferredType::Descriptor inferredTypeFor(const PropertyTypeKey&);
690     InferredType::Descriptor inferredTypeForProperty(Structure* structure, UniquedStringImpl* uid)
691     {
692         return inferredTypeFor(PropertyTypeKey(structure, uid));
693     }
694
695     AbstractValue inferredValueForProperty(
696         const StructureSet& base, UniquedStringImpl* uid, StructureClobberState = StructuresAreWatched);
697
698     // This uses either constant property inference or property type inference to derive a good abstract
699     // value for some property accessed with the given abstract value base.
700     AbstractValue inferredValueForProperty(
701         const AbstractValue& base, UniquedStringImpl* uid, PropertyOffset, StructureClobberState);
702     
703     FullBytecodeLiveness& livenessFor(CodeBlock*);
704     FullBytecodeLiveness& livenessFor(InlineCallFrame*);
705     
706     // Quickly query if a single local is live at the given point. This is faster than calling
707     // forAllLiveInBytecode() if you will only query one local. But, if you want to know all of the
708     // locals live, then calling this for each local is much slower than forAllLiveInBytecode().
709     bool isLiveInBytecode(VirtualRegister, CodeOrigin);
710     
711     // Quickly get all of the non-argument locals live at the given point. This doesn't give you
712     // any arguments because those are all presumed live. You can call forAllLiveInBytecode() to
713     // also get the arguments. This is much faster than calling isLiveInBytecode() for each local.
714     template<typename Functor>
715     void forAllLocalsLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
716     {
717         // Support for not redundantly reporting arguments. Necessary because in case of a varargs
718         // call, only the callee knows that arguments are live while in the case of a non-varargs
719         // call, both callee and caller will see the variables live.
720         VirtualRegister exclusionStart;
721         VirtualRegister exclusionEnd;
722
723         CodeOrigin* codeOriginPtr = &codeOrigin;
724         
725         for (;;) {
726             InlineCallFrame* inlineCallFrame = codeOriginPtr->inlineCallFrame;
727             VirtualRegister stackOffset(inlineCallFrame ? inlineCallFrame->stackOffset : 0);
728             
729             if (inlineCallFrame) {
730                 if (inlineCallFrame->isClosureCall)
731                     functor(stackOffset + JSStack::Callee);
732                 if (inlineCallFrame->isVarargs())
733                     functor(stackOffset + JSStack::ArgumentCount);
734             }
735             
736             CodeBlock* codeBlock = baselineCodeBlockFor(inlineCallFrame);
737             FullBytecodeLiveness& fullLiveness = livenessFor(codeBlock);
738             const FastBitVector& liveness = fullLiveness.getLiveness(codeOriginPtr->bytecodeIndex);
739             for (unsigned relativeLocal = codeBlock->m_numCalleeRegisters; relativeLocal--;) {
740                 VirtualRegister reg = stackOffset + virtualRegisterForLocal(relativeLocal);
741                 
742                 // Don't report if our callee already reported.
743                 if (reg >= exclusionStart && reg < exclusionEnd)
744                     continue;
745                 
746                 if (liveness.get(relativeLocal))
747                     functor(reg);
748             }
749             
750             if (!inlineCallFrame)
751                 break;
752
753             // Arguments are always live. This would be redundant if it wasn't for our
754             // op_call_varargs inlining. See the comment above.
755             exclusionStart = stackOffset + CallFrame::argumentOffsetIncludingThis(0);
756             exclusionEnd = stackOffset + CallFrame::argumentOffsetIncludingThis(inlineCallFrame->arguments.size());
757             
758             // We will always have a "this" argument and exclusionStart should be a smaller stack
759             // offset than exclusionEnd.
760             ASSERT(exclusionStart < exclusionEnd);
761
762             for (VirtualRegister reg = exclusionStart; reg < exclusionEnd; reg += 1)
763                 functor(reg);
764             
765             codeOriginPtr = inlineCallFrame->getCallerSkippingTailCalls();
766
767             // The first inline call frame could be an inline tail call
768             if (!codeOriginPtr)
769                 break;
770         }
771     }
772     
773     // Get a BitVector of all of the non-argument locals live right now. This is mostly useful if
774     // you want to compare two sets of live locals from two different CodeOrigins.
775     BitVector localsLiveInBytecode(CodeOrigin);
776     
777     // Tells you all of the arguments and locals live at the given CodeOrigin. This is a small
778     // extension to forAllLocalsLiveInBytecode(), since all arguments are always presumed live.
779     template<typename Functor>
780     void forAllLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
781     {
782         forAllLocalsLiveInBytecode(codeOrigin, functor);
783         
784         // Report all arguments as being live.
785         for (unsigned argument = block(0)->variablesAtHead.numberOfArguments(); argument--;)
786             functor(virtualRegisterForArgument(argument));
787     }
788     
789     BytecodeKills& killsFor(CodeBlock*);
790     BytecodeKills& killsFor(InlineCallFrame*);
791     
792     unsigned frameRegisterCount();
793     unsigned stackPointerOffset();
794     unsigned requiredRegisterCountForExit();
795     unsigned requiredRegisterCountForExecutionAndExit();
796     
797     JSValue tryGetConstantProperty(JSValue base, const StructureSet&, PropertyOffset);
798     JSValue tryGetConstantProperty(JSValue base, Structure*, PropertyOffset);
799     JSValue tryGetConstantProperty(JSValue base, const StructureAbstractValue&, PropertyOffset);
800     JSValue tryGetConstantProperty(const AbstractValue&, PropertyOffset);
801     
802     JSValue tryGetConstantClosureVar(JSValue base, ScopeOffset);
803     JSValue tryGetConstantClosureVar(const AbstractValue&, ScopeOffset);
804     JSValue tryGetConstantClosureVar(Node*, ScopeOffset);
805     
806     JSArrayBufferView* tryGetFoldableView(JSValue);
807     JSArrayBufferView* tryGetFoldableView(JSValue, ArrayMode arrayMode);
808     
809     void registerFrozenValues();
810     
811     virtual void visitChildren(SlotVisitor&) override;
812     
813     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
814         std::nullptr_t, const char* file, int line, const char* function,
815         const char* assertion);
816     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
817         Node*, const char* file, int line, const char* function,
818         const char* assertion);
819     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
820         BasicBlock*, const char* file, int line, const char* function,
821         const char* assertion);
822
823     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
824
825     void ensureDominators();
826     void ensurePrePostNumbering();
827     void ensureNaturalLoops();
828
829     VM& m_vm;
830     Plan& m_plan;
831     CodeBlock* m_codeBlock;
832     CodeBlock* m_profiledBlock;
833     
834     NodeAllocator& m_allocator;
835
836     Vector< RefPtr<BasicBlock> , 8> m_blocks;
837     Vector<Edge, 16> m_varArgChildren;
838
839     HashMap<EncodedJSValue, FrozenValue*, EncodedJSValueHash, EncodedJSValueHashTraits> m_frozenValueMap;
840     Bag<FrozenValue> m_frozenValues;
841
842     Vector<uint32_t> m_uint32ValuesInUse;
843     
844     Bag<StorageAccessData> m_storageAccessData;
845     
846     // In CPS, this is all of the SetArgument nodes for the arguments in the machine code block
847     // that survived DCE. All of them except maybe "this" will survive DCE, because of the Flush
848     // nodes.
849     //
850     // In SSA, this is all of the GetStack nodes for the arguments in the machine code block that
851     // may have some speculation in the prologue and survived DCE. Note that to get the speculation
852     // for an argument in SSA, you must use m_argumentFormats, since we still have to speculate
853     // even if the argument got killed. For example:
854     //
855     //     function foo(x) {
856     //        var tmp = x + 1;
857     //     }
858     //
859     // Assume that x is always int during profiling. The ArithAdd for "x + 1" will be dead and will
860     // have a proven check for the edge to "x". So, we will not insert a Check node and we will
861     // kill the GetStack for "x". But, we must do the int check in the progolue, because that's the
862     // thing we used to allow DCE of ArithAdd. Otherwise the add could be impure:
863     //
864     //     var o = {
865     //         valueOf: function() { do side effects; }
866     //     };
867     //     foo(o);
868     //
869     // If we DCE the ArithAdd and we remove the int check on x, then this won't do the side
870     // effects.
871     Vector<Node*, 8> m_arguments;
872     
873     // In CPS, this is meaningless. In SSA, this is the argument speculation that we've locked in.
874     Vector<FlushFormat> m_argumentFormats;
875     
876     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
877     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
878     SegmentedVector<StructureSet, 16> m_structureSet;
879     Bag<Transition> m_transitions;
880     SegmentedVector<NewArrayBufferData, 4> m_newArrayBufferData;
881     Bag<BranchData> m_branchData;
882     Bag<SwitchData> m_switchData;
883     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
884     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
885     Bag<ObjectMaterializationData> m_objectMaterializationData;
886     Bag<CallVarargsData> m_callVarargsData;
887     Bag<LoadVarargsData> m_loadVarargsData;
888     Bag<StackAccessData> m_stackAccessData;
889     Vector<InlineVariableData, 4> m_inlineVariableData;
890     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
891     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
892     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
893     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
894     std::unique_ptr<Dominators> m_dominators;
895     std::unique_ptr<PrePostNumbering> m_prePostNumbering;
896     std::unique_ptr<NaturalLoops> m_naturalLoops;
897     std::unique_ptr<CFG> m_cfg;
898     unsigned m_localVars;
899     unsigned m_nextMachineLocal;
900     unsigned m_parameterSlots;
901
902 #if USE(JSVALUE32_64)
903     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
904     std::unique_ptr<Bag<double>> m_doubleConstants;
905 #endif
906     
907     OptimizationFixpointState m_fixpointState;
908     StructureRegistrationState m_structureRegistrationState;
909     GraphForm m_form;
910     UnificationState m_unificationState;
911     PlanStage m_planStage { PlanStage::Initial };
912     RefCountState m_refCountState;
913     bool m_hasDebuggerEnabled;
914     bool m_hasExceptionHandlers { false };
915 private:
916     
917     void handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock*, BasicBlock* successor);
918     
919     AddSpeculationMode addImmediateShouldSpeculateInt32(Node* add, bool variableShouldSpeculateInt32, Node* operand, Node*immediate, RareCaseProfilingSource source)
920     {
921         ASSERT(immediate->hasConstant());
922         
923         JSValue immediateValue = immediate->asJSValue();
924         if (!immediateValue.isNumber() && !immediateValue.isBoolean())
925             return DontSpeculateInt32;
926         
927         if (!variableShouldSpeculateInt32)
928             return DontSpeculateInt32;
929
930         // Integer constants can be typed Double if they are written like a double in the source code (e.g. 42.0).
931         // In that case, we stay conservative unless the other operand was explicitly typed as integer.
932         NodeFlags operandResultType = operand->result();
933         if (operandResultType != NodeResultInt32 && immediateValue.isDouble())
934             return DontSpeculateInt32;
935         
936         if (immediateValue.isBoolean() || jsNumber(immediateValue.asNumber()).isInt32())
937             return add->canSpeculateInt32(source) ? SpeculateInt32 : DontSpeculateInt32;
938         
939         double doubleImmediate = immediateValue.asDouble();
940         const double twoToThe48 = 281474976710656.0;
941         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
942             return DontSpeculateInt32;
943         
944         return bytecodeCanTruncateInteger(add->arithNodeFlags()) ? SpeculateInt32AndTruncateConstants : DontSpeculateInt32;
945     }
946 };
947
948 } } // namespace JSC::DFG
949
950 #endif
951 #endif