d898b70853493a8d06453291167cf9f51839ffed
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGNode.h
1 /*
2  * Copyright (C) 2011, 2012, 2013 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 DFGNode_h
27 #define DFGNode_h
28
29 #include <wtf/Platform.h>
30
31 #if ENABLE(DFG_JIT)
32
33 #include "CodeBlock.h"
34 #include "CodeOrigin.h"
35 #include "DFGAbstractValue.h"
36 #include "DFGAdjacencyList.h"
37 #include "DFGArrayMode.h"
38 #include "DFGCommon.h"
39 #include "DFGLazyJSValue.h"
40 #include "DFGNodeFlags.h"
41 #include "DFGNodeType.h"
42 #include "DFGVariableAccessData.h"
43 #include "JSCJSValue.h"
44 #include "Operands.h"
45 #include "SpeculatedType.h"
46 #include "StructureSet.h"
47 #include "ValueProfile.h"
48 #include <wtf/ListDump.h>
49
50 namespace JSC { namespace DFG {
51
52 class Graph;
53 struct BasicBlock;
54
55 struct StructureTransitionData {
56     Structure* previousStructure;
57     Structure* newStructure;
58     
59     StructureTransitionData() { }
60     
61     StructureTransitionData(Structure* previousStructure, Structure* newStructure)
62         : previousStructure(previousStructure)
63         , newStructure(newStructure)
64     {
65     }
66 };
67
68 struct NewArrayBufferData {
69     unsigned startConstant;
70     unsigned numConstants;
71     IndexingType indexingType;
72 };
73
74 // The SwitchData and associated data structures duplicate the information in
75 // JumpTable. The DFG may ultimately end up using the JumpTable, though it may
76 // instead decide to do something different - this is entirely up to the DFG.
77 // These data structures give the DFG a higher-level semantic description of
78 // what is going on, which will allow it to make the right decision.
79 //
80 // Note that there will never be multiple SwitchCases in SwitchData::cases that
81 // have the same SwitchCase::value, since the bytecode's JumpTables never have
82 // duplicates - since the JumpTable maps a value to a target. It's a
83 // one-to-many mapping. So we may have duplicate targets, but never duplicate
84 // values.
85 struct SwitchCase {
86     SwitchCase()
87         : target(0)
88     {
89     }
90     
91     SwitchCase(LazyJSValue value, BasicBlock* target)
92         : value(value)
93         , target(target)
94     {
95     }
96     
97     static SwitchCase withBytecodeIndex(LazyJSValue value, unsigned bytecodeIndex)
98     {
99         SwitchCase result;
100         result.value = value;
101         result.target = bitwise_cast<BasicBlock*>(static_cast<uintptr_t>(bytecodeIndex));
102         return result;
103     }
104     
105     unsigned targetBytecodeIndex() const { return bitwise_cast<uintptr_t>(target); }
106     
107     LazyJSValue value;
108     BasicBlock* target;
109 };
110
111 enum SwitchKind {
112     SwitchImm,
113     SwitchChar,
114     SwitchString
115 };
116
117 struct SwitchData {
118     // Initializes most fields to obviously invalid values. Anyone
119     // constructing this should make sure to initialize everything they
120     // care about manually.
121     SwitchData()
122         : fallThrough(0)
123         , kind(static_cast<SwitchKind>(-1))
124         , switchTableIndex(UINT_MAX)
125         , didUseJumpTable(false)
126     {
127     }
128     
129     void setFallThroughBytecodeIndex(unsigned bytecodeIndex)
130     {
131         fallThrough = bitwise_cast<BasicBlock*>(static_cast<uintptr_t>(bytecodeIndex));
132     }
133     unsigned fallThroughBytecodeIndex() const { return bitwise_cast<uintptr_t>(fallThrough); }
134     
135     Vector<SwitchCase> cases;
136     BasicBlock* fallThrough;
137     SwitchKind kind;
138     unsigned switchTableIndex;
139     bool didUseJumpTable;
140 };
141
142 // This type used in passing an immediate argument to Node constructor;
143 // distinguishes an immediate value (typically an index into a CodeBlock data structure - 
144 // a constant index, argument, or identifier) from a Node*.
145 struct OpInfo {
146     explicit OpInfo(int32_t value) : m_value(static_cast<uintptr_t>(value)) { }
147     explicit OpInfo(uint32_t value) : m_value(static_cast<uintptr_t>(value)) { }
148 #if OS(DARWIN) || USE(JSVALUE64)
149     explicit OpInfo(size_t value) : m_value(static_cast<uintptr_t>(value)) { }
150 #endif
151     explicit OpInfo(void* value) : m_value(reinterpret_cast<uintptr_t>(value)) { }
152     uintptr_t m_value;
153 };
154
155 // === Node ===
156 //
157 // Node represents a single operation in the data flow graph.
158 struct Node {
159     enum VarArgTag { VarArg };
160     
161     Node() { }
162     
163     Node(NodeType op, CodeOrigin codeOrigin, const AdjacencyList& children)
164         : codeOrigin(codeOrigin)
165         , codeOriginForExitTarget(codeOrigin)
166         , children(children)
167         , m_virtualRegister(InvalidVirtualRegister)
168         , m_refCount(1)
169         , m_prediction(SpecNone)
170     {
171         misc.replacement = 0;
172         setOpAndDefaultFlags(op);
173     }
174     
175     // Construct a node with up to 3 children, no immediate value.
176     Node(NodeType op, CodeOrigin codeOrigin, Edge child1 = Edge(), Edge child2 = Edge(), Edge child3 = Edge())
177         : codeOrigin(codeOrigin)
178         , codeOriginForExitTarget(codeOrigin)
179         , children(AdjacencyList::Fixed, child1, child2, child3)
180         , m_virtualRegister(InvalidVirtualRegister)
181         , m_refCount(1)
182         , m_prediction(SpecNone)
183     {
184         misc.replacement = 0;
185         setOpAndDefaultFlags(op);
186         ASSERT(!(m_flags & NodeHasVarArgs));
187     }
188
189     // Construct a node with up to 3 children and an immediate value.
190     Node(NodeType op, CodeOrigin codeOrigin, OpInfo imm, Edge child1 = Edge(), Edge child2 = Edge(), Edge child3 = Edge())
191         : codeOrigin(codeOrigin)
192         , codeOriginForExitTarget(codeOrigin)
193         , children(AdjacencyList::Fixed, child1, child2, child3)
194         , m_virtualRegister(InvalidVirtualRegister)
195         , m_refCount(1)
196         , m_prediction(SpecNone)
197         , m_opInfo(imm.m_value)
198     {
199         misc.replacement = 0;
200         setOpAndDefaultFlags(op);
201         ASSERT(!(m_flags & NodeHasVarArgs));
202     }
203
204     // Construct a node with up to 3 children and two immediate values.
205     Node(NodeType op, CodeOrigin codeOrigin, OpInfo imm1, OpInfo imm2, Edge child1 = Edge(), Edge child2 = Edge(), Edge child3 = Edge())
206         : codeOrigin(codeOrigin)
207         , codeOriginForExitTarget(codeOrigin)
208         , children(AdjacencyList::Fixed, child1, child2, child3)
209         , m_virtualRegister(InvalidVirtualRegister)
210         , m_refCount(1)
211         , m_prediction(SpecNone)
212         , m_opInfo(imm1.m_value)
213         , m_opInfo2(imm2.m_value)
214     {
215         misc.replacement = 0;
216         setOpAndDefaultFlags(op);
217         ASSERT(!(m_flags & NodeHasVarArgs));
218     }
219     
220     // Construct a node with a variable number of children and two immediate values.
221     Node(VarArgTag, NodeType op, CodeOrigin codeOrigin, OpInfo imm1, OpInfo imm2, unsigned firstChild, unsigned numChildren)
222         : codeOrigin(codeOrigin)
223         , codeOriginForExitTarget(codeOrigin)
224         , children(AdjacencyList::Variable, firstChild, numChildren)
225         , m_virtualRegister(InvalidVirtualRegister)
226         , m_refCount(1)
227         , m_prediction(SpecNone)
228         , m_opInfo(imm1.m_value)
229         , m_opInfo2(imm2.m_value)
230     {
231         misc.replacement = 0;
232         setOpAndDefaultFlags(op);
233         ASSERT(m_flags & NodeHasVarArgs);
234     }
235     
236     NodeType op() const { return static_cast<NodeType>(m_op); }
237     NodeFlags flags() const { return m_flags; }
238     
239     // This is not a fast method.
240     unsigned index() const;
241     
242     void setOp(NodeType op)
243     {
244         m_op = op;
245     }
246     
247     void setFlags(NodeFlags flags)
248     {
249         m_flags = flags;
250     }
251     
252     bool mergeFlags(NodeFlags flags)
253     {
254         ASSERT(!(flags & NodeDoesNotExit));
255         NodeFlags newFlags = m_flags | flags;
256         if (newFlags == m_flags)
257             return false;
258         m_flags = newFlags;
259         return true;
260     }
261     
262     bool filterFlags(NodeFlags flags)
263     {
264         ASSERT(flags & NodeDoesNotExit);
265         NodeFlags newFlags = m_flags & flags;
266         if (newFlags == m_flags)
267             return false;
268         m_flags = newFlags;
269         return true;
270     }
271     
272     bool clearFlags(NodeFlags flags)
273     {
274         return filterFlags(~flags);
275     }
276     
277     void setOpAndDefaultFlags(NodeType op)
278     {
279         m_op = op;
280         m_flags = defaultFlags(op);
281     }
282
283     void setOpAndDefaultNonExitFlags(NodeType op)
284     {
285         ASSERT(!(m_flags & NodeHasVarArgs));
286         setOpAndDefaultNonExitFlagsUnchecked(op);
287     }
288
289     void setOpAndDefaultNonExitFlagsUnchecked(NodeType op)
290     {
291         m_op = op;
292         m_flags = (defaultFlags(op) & ~NodeExitsForward) | (m_flags & NodeExitsForward);
293     }
294
295     void convertToPhantom()
296     {
297         setOpAndDefaultNonExitFlags(Phantom);
298     }
299
300     void convertToPhantomUnchecked()
301     {
302         setOpAndDefaultNonExitFlagsUnchecked(Phantom);
303     }
304
305     void convertToIdentity()
306     {
307         RELEASE_ASSERT(child1());
308         RELEASE_ASSERT(!child2());
309         setOpAndDefaultNonExitFlags(Identity);
310     }
311
312     bool mustGenerate()
313     {
314         return m_flags & NodeMustGenerate;
315     }
316     
317     void setCanExit(bool exits)
318     {
319         if (exits)
320             m_flags &= ~NodeDoesNotExit;
321         else
322             m_flags |= NodeDoesNotExit;
323     }
324     
325     bool canExit()
326     {
327         return !(m_flags & NodeDoesNotExit);
328     }
329     
330     bool isConstant()
331     {
332         return op() == JSConstant;
333     }
334     
335     bool isWeakConstant()
336     {
337         return op() == WeakJSConstant;
338     }
339     
340     bool isStronglyProvedConstantIn(InlineCallFrame* inlineCallFrame)
341     {
342         return isConstant() && codeOrigin.inlineCallFrame == inlineCallFrame;
343     }
344     
345     bool isStronglyProvedConstantIn(const CodeOrigin& codeOrigin)
346     {
347         return isStronglyProvedConstantIn(codeOrigin.inlineCallFrame);
348     }
349     
350     bool isPhantomArguments()
351     {
352         return op() == PhantomArguments;
353     }
354     
355     bool hasConstant()
356     {
357         switch (op()) {
358         case JSConstant:
359         case WeakJSConstant:
360         case PhantomArguments:
361             return true;
362         default:
363             return false;
364         }
365     }
366
367     unsigned constantNumber()
368     {
369         ASSERT(isConstant());
370         return m_opInfo;
371     }
372     
373     void convertToConstant(unsigned constantNumber)
374     {
375         m_op = JSConstant;
376         m_flags &= ~(NodeMustGenerate | NodeMightClobber | NodeClobbersWorld);
377         m_opInfo = constantNumber;
378         children.reset();
379     }
380     
381     void convertToWeakConstant(JSCell* cell)
382     {
383         m_op = WeakJSConstant;
384         m_flags &= ~(NodeMustGenerate | NodeMightClobber | NodeClobbersWorld);
385         m_opInfo = bitwise_cast<uintptr_t>(cell);
386         children.reset();
387     }
388     
389     void convertToGetLocalUnlinked(VirtualRegister local)
390     {
391         m_op = GetLocalUnlinked;
392         m_flags &= ~(NodeMustGenerate | NodeMightClobber | NodeClobbersWorld);
393         m_opInfo = local;
394         children.reset();
395     }
396     
397     void convertToStructureTransitionWatchpoint(Structure* structure)
398     {
399         ASSERT(m_op == CheckStructure || m_op == ArrayifyToStructure);
400         ASSERT(!child2());
401         ASSERT(!child3());
402         m_opInfo = bitwise_cast<uintptr_t>(structure);
403         m_op = StructureTransitionWatchpoint;
404     }
405     
406     void convertToStructureTransitionWatchpoint()
407     {
408         convertToStructureTransitionWatchpoint(structureSet().singletonStructure());
409     }
410     
411     void convertToGetByOffset(unsigned storageAccessDataIndex, Edge storage)
412     {
413         ASSERT(m_op == GetById || m_op == GetByIdFlush);
414         m_opInfo = storageAccessDataIndex;
415         children.setChild2(children.child1());
416         children.child2().setUseKind(KnownCellUse);
417         children.setChild1(storage);
418         m_op = GetByOffset;
419         m_flags &= ~NodeClobbersWorld;
420     }
421     
422     void convertToPutByOffset(unsigned storageAccessDataIndex, Edge storage)
423     {
424         ASSERT(m_op == PutById || m_op == PutByIdDirect);
425         m_opInfo = storageAccessDataIndex;
426         children.setChild3(children.child2());
427         children.setChild2(children.child1());
428         children.setChild1(storage);
429         m_op = PutByOffset;
430         m_flags &= ~NodeClobbersWorld;
431     }
432     
433     void convertToPhantomLocal()
434     {
435         ASSERT(m_op == Phantom && (child1()->op() == Phi || child1()->op() == SetLocal || child1()->op() == SetArgument));
436         m_op = PhantomLocal;
437         m_opInfo = child1()->m_opInfo; // Copy the variableAccessData.
438         children.setChild1(Edge());
439     }
440     
441     void convertToGetLocal(VariableAccessData* variable, Node* phi)
442     {
443         ASSERT(m_op == GetLocalUnlinked);
444         m_op = GetLocal;
445         m_opInfo = bitwise_cast<uintptr_t>(variable);
446         children.setChild1(Edge(phi));
447     }
448     
449     void convertToToString()
450     {
451         ASSERT(m_op == ToPrimitive);
452         m_op = ToString;
453     }
454     
455     JSCell* weakConstant()
456     {
457         ASSERT(op() == WeakJSConstant);
458         return bitwise_cast<JSCell*>(m_opInfo);
459     }
460     
461     JSValue valueOfJSConstant(CodeBlock* codeBlock)
462     {
463         switch (op()) {
464         case WeakJSConstant:
465             return JSValue(weakConstant());
466         case JSConstant:
467             return codeBlock->constantRegister(FirstConstantRegisterIndex + constantNumber()).get();
468         case PhantomArguments:
469             return JSValue();
470         default:
471             RELEASE_ASSERT_NOT_REACHED();
472             return JSValue(); // Have to return something in release mode.
473         }
474     }
475
476     bool isInt32Constant(CodeBlock* codeBlock)
477     {
478         return isConstant() && valueOfJSConstant(codeBlock).isInt32();
479     }
480     
481     bool isDoubleConstant(CodeBlock* codeBlock)
482     {
483         bool result = isConstant() && valueOfJSConstant(codeBlock).isDouble();
484         if (result)
485             ASSERT(!isInt32Constant(codeBlock));
486         return result;
487     }
488     
489     bool isNumberConstant(CodeBlock* codeBlock)
490     {
491         bool result = isConstant() && valueOfJSConstant(codeBlock).isNumber();
492         ASSERT(result == (isInt32Constant(codeBlock) || isDoubleConstant(codeBlock)));
493         return result;
494     }
495     
496     bool isBooleanConstant(CodeBlock* codeBlock)
497     {
498         return isConstant() && valueOfJSConstant(codeBlock).isBoolean();
499     }
500     
501     bool containsMovHint()
502     {
503         switch (op()) {
504         case SetLocal:
505         case MovHint:
506         case MovHintAndCheck:
507         case ZombieHint:
508             return true;
509         default:
510             return false;
511         }
512     }
513     
514     bool hasVariableAccessData(Graph&);
515     bool hasLocal(Graph& graph)
516     {
517         return hasVariableAccessData(graph);
518     }
519     
520     VariableAccessData* variableAccessData()
521     {
522         return reinterpret_cast<VariableAccessData*>(m_opInfo)->find();
523     }
524     
525     VirtualRegister local()
526     {
527         return variableAccessData()->local();
528     }
529     
530     VirtualRegister unlinkedLocal()
531     {
532         ASSERT(op() == GetLocalUnlinked);
533         return static_cast<VirtualRegister>(m_opInfo);
534     }
535     
536     bool hasPhi()
537     {
538         return op() == Upsilon;
539     }
540     
541     Node* phi()
542     {
543         ASSERT(hasPhi());
544         return bitwise_cast<Node*>(m_opInfo);
545     }
546     
547     bool hasIdentifier()
548     {
549         switch (op()) {
550         case GetById:
551         case GetByIdFlush:
552         case PutById:
553         case PutByIdDirect:
554             return true;
555         default:
556             return false;
557         }
558     }
559
560     unsigned identifierNumber()
561     {
562         ASSERT(hasIdentifier());
563         return m_opInfo;
564     }
565     
566     bool hasArithNodeFlags()
567     {
568         switch (op()) {
569         case UInt32ToNumber:
570         case ArithAdd:
571         case ArithSub:
572         case ArithNegate:
573         case ArithMul:
574         case ArithAbs:
575         case ArithMin:
576         case ArithMax:
577         case ArithMod:
578         case ArithDiv:
579         case ValueAdd:
580             return true;
581         default:
582             return false;
583         }
584     }
585     
586     // This corrects the arithmetic node flags, so that irrelevant bits are
587     // ignored. In particular, anything other than ArithMul does not need
588     // to know if it can speculate on negative zero.
589     NodeFlags arithNodeFlags()
590     {
591         NodeFlags result = m_flags & NodeArithFlagsMask;
592         if (op() == ArithMul || op() == ArithDiv || op() == ArithMod || op() == ArithNegate || op() == DoubleAsInt32)
593             return result;
594         return result & ~NodeNeedsNegZero;
595     }
596     
597     bool hasConstantBuffer()
598     {
599         return op() == NewArrayBuffer;
600     }
601     
602     NewArrayBufferData* newArrayBufferData()
603     {
604         ASSERT(hasConstantBuffer());
605         return reinterpret_cast<NewArrayBufferData*>(m_opInfo);
606     }
607     
608     unsigned startConstant()
609     {
610         return newArrayBufferData()->startConstant;
611     }
612     
613     unsigned numConstants()
614     {
615         return newArrayBufferData()->numConstants;
616     }
617     
618     bool hasIndexingType()
619     {
620         switch (op()) {
621         case NewArray:
622         case NewArrayWithSize:
623         case NewArrayBuffer:
624             return true;
625         default:
626             return false;
627         }
628     }
629     
630     IndexingType indexingType()
631     {
632         ASSERT(hasIndexingType());
633         if (op() == NewArrayBuffer)
634             return newArrayBufferData()->indexingType;
635         return m_opInfo;
636     }
637     
638     bool hasTypedArrayType()
639     {
640         switch (op()) {
641         case NewTypedArray:
642             return true;
643         default:
644             return false;
645         }
646     }
647     
648     TypedArrayType typedArrayType()
649     {
650         ASSERT(hasTypedArrayType());
651         TypedArrayType result = static_cast<TypedArrayType>(m_opInfo);
652         ASSERT(isTypedView(result));
653         return result;
654     }
655     
656     bool hasInlineCapacity()
657     {
658         return op() == CreateThis;
659     }
660
661     unsigned inlineCapacity()
662     {
663         ASSERT(hasInlineCapacity());
664         return m_opInfo;
665     }
666
667     void setIndexingType(IndexingType indexingType)
668     {
669         ASSERT(hasIndexingType());
670         m_opInfo = indexingType;
671     }
672     
673     bool hasRegexpIndex()
674     {
675         return op() == NewRegexp;
676     }
677     
678     unsigned regexpIndex()
679     {
680         ASSERT(hasRegexpIndex());
681         return m_opInfo;
682     }
683     
684     bool hasVarNumber()
685     {
686         return op() == GetClosureVar || op() == PutClosureVar;
687     }
688
689     unsigned varNumber()
690     {
691         ASSERT(hasVarNumber());
692         return m_opInfo;
693     }
694     
695     bool hasIdentifierNumberForCheck()
696     {
697         return op() == GlobalVarWatchpoint;
698     }
699     
700     unsigned identifierNumberForCheck()
701     {
702         ASSERT(hasIdentifierNumberForCheck());
703         return m_opInfo2;
704     }
705     
706     bool hasRegisterPointer()
707     {
708         return op() == GetGlobalVar || op() == PutGlobalVar || op() == GlobalVarWatchpoint;
709     }
710     
711     WriteBarrier<Unknown>* registerPointer()
712     {
713         return bitwise_cast<WriteBarrier<Unknown>*>(m_opInfo);
714     }
715
716     bool hasResult()
717     {
718         return m_flags & NodeResultMask;
719     }
720
721     bool hasInt32Result()
722     {
723         return (m_flags & NodeResultMask) == NodeResultInt32;
724     }
725     
726     bool hasNumberResult()
727     {
728         return (m_flags & NodeResultMask) == NodeResultNumber;
729     }
730     
731     bool hasJSResult()
732     {
733         return (m_flags & NodeResultMask) == NodeResultJS;
734     }
735     
736     bool hasBooleanResult()
737     {
738         return (m_flags & NodeResultMask) == NodeResultBoolean;
739     }
740
741     bool hasStorageResult()
742     {
743         return (m_flags & NodeResultMask) == NodeResultStorage;
744     }
745
746     bool isJump()
747     {
748         return op() == Jump;
749     }
750
751     bool isBranch()
752     {
753         return op() == Branch;
754     }
755     
756     bool isSwitch()
757     {
758         return op() == Switch;
759     }
760
761     bool isTerminal()
762     {
763         switch (op()) {
764         case Jump:
765         case Branch:
766         case Switch:
767         case Return:
768         case Unreachable:
769             return true;
770         default:
771             return false;
772         }
773     }
774
775     unsigned takenBytecodeOffsetDuringParsing()
776     {
777         ASSERT(isBranch() || isJump());
778         return m_opInfo;
779     }
780
781     unsigned notTakenBytecodeOffsetDuringParsing()
782     {
783         ASSERT(isBranch());
784         return m_opInfo2;
785     }
786     
787     void setTakenBlock(BasicBlock* block)
788     {
789         ASSERT(isBranch() || isJump());
790         m_opInfo = bitwise_cast<uintptr_t>(block);
791     }
792     
793     void setNotTakenBlock(BasicBlock* block)
794     {
795         ASSERT(isBranch());
796         m_opInfo2 = bitwise_cast<uintptr_t>(block);
797     }
798     
799     BasicBlock*& takenBlock()
800     {
801         ASSERT(isBranch() || isJump());
802         return *bitwise_cast<BasicBlock**>(&m_opInfo);
803     }
804     
805     BasicBlock*& notTakenBlock()
806     {
807         ASSERT(isBranch());
808         return *bitwise_cast<BasicBlock**>(&m_opInfo2);
809     }
810     
811     SwitchData* switchData()
812     {
813         ASSERT(isSwitch());
814         return bitwise_cast<SwitchData*>(m_opInfo);
815     }
816     
817     unsigned numSuccessors()
818     {
819         switch (op()) {
820         case Jump:
821             return 1;
822         case Branch:
823             return 2;
824         case Switch:
825             return switchData()->cases.size() + 1;
826         default:
827             return 0;
828         }
829     }
830     
831     BasicBlock*& successor(unsigned index)
832     {
833         if (isSwitch()) {
834             if (index < switchData()->cases.size())
835                 return switchData()->cases[index].target;
836             RELEASE_ASSERT(index == switchData()->cases.size());
837             return switchData()->fallThrough;
838         }
839         switch (index) {
840         case 0:
841             return takenBlock();
842         case 1:
843             return notTakenBlock();
844         default:
845             RELEASE_ASSERT_NOT_REACHED();
846             return takenBlock();
847         }
848     }
849     
850     BasicBlock*& successorForCondition(bool condition)
851     {
852         ASSERT(isBranch());
853         return condition ? takenBlock() : notTakenBlock();
854     }
855     
856     bool hasHeapPrediction()
857     {
858         switch (op()) {
859         case GetById:
860         case GetByIdFlush:
861         case GetByVal:
862         case GetMyArgumentByVal:
863         case GetMyArgumentByValSafe:
864         case Call:
865         case Construct:
866         case GetByOffset:
867         case GetClosureVar:
868         case ArrayPop:
869         case ArrayPush:
870         case RegExpExec:
871         case RegExpTest:
872         case GetGlobalVar:
873             return true;
874         default:
875             return false;
876         }
877     }
878     
879     SpeculatedType getHeapPrediction()
880     {
881         ASSERT(hasHeapPrediction());
882         return static_cast<SpeculatedType>(m_opInfo2);
883     }
884     
885     bool predictHeap(SpeculatedType prediction)
886     {
887         ASSERT(hasHeapPrediction());
888         
889         return mergeSpeculation(m_opInfo2, prediction);
890     }
891     
892     bool hasFunction()
893     {
894         switch (op()) {
895         case CheckFunction:
896         case AllocationProfileWatchpoint:
897             return true;
898         default:
899             return false;
900         }
901     }
902
903     JSCell* function()
904     {
905         ASSERT(hasFunction());
906         JSCell* result = reinterpret_cast<JSFunction*>(m_opInfo);
907         ASSERT(JSValue(result).isFunction());
908         return result;
909     }
910     
911     bool hasExecutable()
912     {
913         return op() == CheckExecutable;
914     }
915     
916     ExecutableBase* executable()
917     {
918         return jsCast<ExecutableBase*>(reinterpret_cast<JSCell*>(m_opInfo));
919     }
920
921     bool hasStructureTransitionData()
922     {
923         switch (op()) {
924         case PutStructure:
925         case PhantomPutStructure:
926         case AllocatePropertyStorage:
927         case ReallocatePropertyStorage:
928             return true;
929         default:
930             return false;
931         }
932     }
933     
934     StructureTransitionData& structureTransitionData()
935     {
936         ASSERT(hasStructureTransitionData());
937         return *reinterpret_cast<StructureTransitionData*>(m_opInfo);
938     }
939     
940     bool hasStructureSet()
941     {
942         switch (op()) {
943         case CheckStructure:
944             return true;
945         default:
946             return false;
947         }
948     }
949     
950     StructureSet& structureSet()
951     {
952         ASSERT(hasStructureSet());
953         return *reinterpret_cast<StructureSet*>(m_opInfo);
954     }
955     
956     bool hasStructure()
957     {
958         switch (op()) {
959         case StructureTransitionWatchpoint:
960         case ArrayifyToStructure:
961         case NewObject:
962         case NewStringObject:
963             return true;
964         default:
965             return false;
966         }
967     }
968     
969     Structure* structure()
970     {
971         ASSERT(hasStructure());
972         return reinterpret_cast<Structure*>(m_opInfo);
973     }
974     
975     bool hasStorageAccessData()
976     {
977         return op() == GetByOffset || op() == PutByOffset;
978     }
979     
980     unsigned storageAccessDataIndex()
981     {
982         ASSERT(hasStorageAccessData());
983         return m_opInfo;
984     }
985     
986     bool hasFunctionDeclIndex()
987     {
988         return op() == NewFunction
989             || op() == NewFunctionNoCheck;
990     }
991     
992     unsigned functionDeclIndex()
993     {
994         ASSERT(hasFunctionDeclIndex());
995         return m_opInfo;
996     }
997     
998     bool hasFunctionExprIndex()
999     {
1000         return op() == NewFunctionExpression;
1001     }
1002     
1003     unsigned functionExprIndex()
1004     {
1005         ASSERT(hasFunctionExprIndex());
1006         return m_opInfo;
1007     }
1008     
1009     bool hasArrayMode()
1010     {
1011         switch (op()) {
1012         case GetIndexedPropertyStorage:
1013         case GetArrayLength:
1014         case PutByVal:
1015         case PutByValAlias:
1016         case GetByVal:
1017         case StringCharAt:
1018         case StringCharCodeAt:
1019         case CheckArray:
1020         case Arrayify:
1021         case ArrayifyToStructure:
1022         case ArrayPush:
1023         case ArrayPop:
1024             return true;
1025         default:
1026             return false;
1027         }
1028     }
1029     
1030     ArrayMode arrayMode()
1031     {
1032         ASSERT(hasArrayMode());
1033         if (op() == ArrayifyToStructure)
1034             return ArrayMode::fromWord(m_opInfo2);
1035         return ArrayMode::fromWord(m_opInfo);
1036     }
1037     
1038     bool setArrayMode(ArrayMode arrayMode)
1039     {
1040         ASSERT(hasArrayMode());
1041         if (this->arrayMode() == arrayMode)
1042             return false;
1043         m_opInfo = arrayMode.asWord();
1044         return true;
1045     }
1046     
1047     bool hasVirtualRegister()
1048     {
1049         return m_virtualRegister != InvalidVirtualRegister;
1050     }
1051     
1052     VirtualRegister virtualRegister()
1053     {
1054         ASSERT(hasResult());
1055         ASSERT(m_virtualRegister != InvalidVirtualRegister);
1056         return m_virtualRegister;
1057     }
1058     
1059     void setVirtualRegister(VirtualRegister virtualRegister)
1060     {
1061         ASSERT(hasResult());
1062         ASSERT(m_virtualRegister == InvalidVirtualRegister);
1063         m_virtualRegister = virtualRegister;
1064     }
1065     
1066     bool hasArgumentPositionStart()
1067     {
1068         return op() == InlineStart;
1069     }
1070     
1071     unsigned argumentPositionStart()
1072     {
1073         ASSERT(hasArgumentPositionStart());
1074         return m_opInfo;
1075     }
1076     
1077     bool hasExecutionCounter()
1078     {
1079         return op() == CountExecution;
1080     }
1081     
1082     Profiler::ExecutionCounter* executionCounter()
1083     {
1084         return bitwise_cast<Profiler::ExecutionCounter*>(m_opInfo);
1085     }
1086
1087     bool shouldGenerate()
1088     {
1089         return m_refCount;
1090     }
1091     
1092     bool willHaveCodeGenOrOSR()
1093     {
1094         switch (op()) {
1095         case SetLocal:
1096         case MovHint:
1097         case ZombieHint:
1098         case MovHintAndCheck:
1099         case Int32ToDouble:
1100         case ValueToInt32:
1101         case UInt32ToNumber:
1102         case DoubleAsInt32:
1103         case PhantomArguments:
1104             return true;
1105         case Phantom:
1106             return child1().useKindUnchecked() != UntypedUse || child2().useKindUnchecked() != UntypedUse || child3().useKindUnchecked() != UntypedUse;
1107         default:
1108             return shouldGenerate();
1109         }
1110     }
1111
1112     unsigned refCount()
1113     {
1114         return m_refCount;
1115     }
1116
1117     unsigned postfixRef()
1118     {
1119         return m_refCount++;
1120     }
1121
1122     unsigned adjustedRefCount()
1123     {
1124         return mustGenerate() ? m_refCount - 1 : m_refCount;
1125     }
1126     
1127     void setRefCount(unsigned refCount)
1128     {
1129         m_refCount = refCount;
1130     }
1131     
1132     Edge& child1()
1133     {
1134         ASSERT(!(m_flags & NodeHasVarArgs));
1135         return children.child1();
1136     }
1137     
1138     // This is useful if you want to do a fast check on the first child
1139     // before also doing a check on the opcode. Use this with care and
1140     // avoid it if possible.
1141     Edge child1Unchecked()
1142     {
1143         return children.child1Unchecked();
1144     }
1145
1146     Edge& child2()
1147     {
1148         ASSERT(!(m_flags & NodeHasVarArgs));
1149         return children.child2();
1150     }
1151
1152     Edge& child3()
1153     {
1154         ASSERT(!(m_flags & NodeHasVarArgs));
1155         return children.child3();
1156     }
1157     
1158     unsigned firstChild()
1159     {
1160         ASSERT(m_flags & NodeHasVarArgs);
1161         return children.firstChild();
1162     }
1163     
1164     unsigned numChildren()
1165     {
1166         ASSERT(m_flags & NodeHasVarArgs);
1167         return children.numChildren();
1168     }
1169     
1170     UseKind binaryUseKind()
1171     {
1172         ASSERT(child1().useKind() == child2().useKind());
1173         return child1().useKind();
1174     }
1175     
1176     bool isBinaryUseKind(UseKind useKind)
1177     {
1178         return child1().useKind() == useKind && child2().useKind() == useKind;
1179     }
1180     
1181     SpeculatedType prediction()
1182     {
1183         return m_prediction;
1184     }
1185     
1186     bool predict(SpeculatedType prediction)
1187     {
1188         return mergeSpeculation(m_prediction, prediction);
1189     }
1190     
1191     bool shouldSpeculateInteger()
1192     {
1193         return isInt32Speculation(prediction());
1194     }
1195     
1196     bool shouldSpeculateIntegerForArithmetic()
1197     {
1198         return isInt32SpeculationForArithmetic(prediction());
1199     }
1200     
1201     bool shouldSpeculateIntegerExpectingDefined()
1202     {
1203         return isInt32SpeculationExpectingDefined(prediction());
1204     }
1205     
1206     bool shouldSpeculateDouble()
1207     {
1208         return isDoubleSpeculation(prediction());
1209     }
1210     
1211     bool shouldSpeculateDoubleForArithmetic()
1212     {
1213         return isDoubleSpeculationForArithmetic(prediction());
1214     }
1215     
1216     bool shouldSpeculateNumber()
1217     {
1218         return isNumberSpeculation(prediction());
1219     }
1220     
1221     bool shouldSpeculateNumberExpectingDefined()
1222     {
1223         return isNumberSpeculationExpectingDefined(prediction());
1224     }
1225     
1226     bool shouldSpeculateBoolean()
1227     {
1228         return isBooleanSpeculation(prediction());
1229     }
1230    
1231     bool shouldSpeculateStringIdent()
1232     {
1233         return isStringIdentSpeculation(prediction());
1234     }
1235  
1236     bool shouldSpeculateString()
1237     {
1238         return isStringSpeculation(prediction());
1239     }
1240  
1241     bool shouldSpeculateStringObject()
1242     {
1243         return isStringObjectSpeculation(prediction());
1244     }
1245     
1246     bool shouldSpeculateStringOrStringObject()
1247     {
1248         return isStringOrStringObjectSpeculation(prediction());
1249     }
1250     
1251     bool shouldSpeculateFinalObject()
1252     {
1253         return isFinalObjectSpeculation(prediction());
1254     }
1255     
1256     bool shouldSpeculateFinalObjectOrOther()
1257     {
1258         return isFinalObjectOrOtherSpeculation(prediction());
1259     }
1260     
1261     bool shouldSpeculateArray()
1262     {
1263         return isArraySpeculation(prediction());
1264     }
1265     
1266     bool shouldSpeculateArguments()
1267     {
1268         return isArgumentsSpeculation(prediction());
1269     }
1270     
1271     bool shouldSpeculateInt8Array()
1272     {
1273         return isInt8ArraySpeculation(prediction());
1274     }
1275     
1276     bool shouldSpeculateInt16Array()
1277     {
1278         return isInt16ArraySpeculation(prediction());
1279     }
1280     
1281     bool shouldSpeculateInt32Array()
1282     {
1283         return isInt32ArraySpeculation(prediction());
1284     }
1285     
1286     bool shouldSpeculateUint8Array()
1287     {
1288         return isUint8ArraySpeculation(prediction());
1289     }
1290
1291     bool shouldSpeculateUint8ClampedArray()
1292     {
1293         return isUint8ClampedArraySpeculation(prediction());
1294     }
1295     
1296     bool shouldSpeculateUint16Array()
1297     {
1298         return isUint16ArraySpeculation(prediction());
1299     }
1300     
1301     bool shouldSpeculateUint32Array()
1302     {
1303         return isUint32ArraySpeculation(prediction());
1304     }
1305     
1306     bool shouldSpeculateFloat32Array()
1307     {
1308         return isFloat32ArraySpeculation(prediction());
1309     }
1310     
1311     bool shouldSpeculateFloat64Array()
1312     {
1313         return isFloat64ArraySpeculation(prediction());
1314     }
1315     
1316     bool shouldSpeculateArrayOrOther()
1317     {
1318         return isArrayOrOtherSpeculation(prediction());
1319     }
1320     
1321     bool shouldSpeculateObject()
1322     {
1323         return isObjectSpeculation(prediction());
1324     }
1325     
1326     bool shouldSpeculateObjectOrOther()
1327     {
1328         return isObjectOrOtherSpeculation(prediction());
1329     }
1330
1331     bool shouldSpeculateCell()
1332     {
1333         return isCellSpeculation(prediction());
1334     }
1335     
1336     static bool shouldSpeculateBoolean(Node* op1, Node* op2)
1337     {
1338         return op1->shouldSpeculateBoolean() && op2->shouldSpeculateBoolean();
1339     }
1340     
1341     static bool shouldSpeculateInteger(Node* op1, Node* op2)
1342     {
1343         return op1->shouldSpeculateInteger() && op2->shouldSpeculateInteger();
1344     }
1345     
1346     static bool shouldSpeculateIntegerForArithmetic(Node* op1, Node* op2)
1347     {
1348         return op1->shouldSpeculateIntegerForArithmetic() && op2->shouldSpeculateIntegerForArithmetic();
1349     }
1350     
1351     static bool shouldSpeculateIntegerExpectingDefined(Node* op1, Node* op2)
1352     {
1353         return op1->shouldSpeculateIntegerExpectingDefined() && op2->shouldSpeculateIntegerExpectingDefined();
1354     }
1355     
1356     static bool shouldSpeculateDoubleForArithmetic(Node* op1, Node* op2)
1357     {
1358         return op1->shouldSpeculateDoubleForArithmetic() && op2->shouldSpeculateDoubleForArithmetic();
1359     }
1360     
1361     static bool shouldSpeculateNumber(Node* op1, Node* op2)
1362     {
1363         return op1->shouldSpeculateNumber() && op2->shouldSpeculateNumber();
1364     }
1365     
1366     static bool shouldSpeculateNumberExpectingDefined(Node* op1, Node* op2)
1367     {
1368         return op1->shouldSpeculateNumberExpectingDefined() && op2->shouldSpeculateNumberExpectingDefined();
1369     }
1370     
1371     static bool shouldSpeculateFinalObject(Node* op1, Node* op2)
1372     {
1373         return op1->shouldSpeculateFinalObject() && op2->shouldSpeculateFinalObject();
1374     }
1375
1376     static bool shouldSpeculateArray(Node* op1, Node* op2)
1377     {
1378         return op1->shouldSpeculateArray() && op2->shouldSpeculateArray();
1379     }
1380     
1381     bool canSpeculateInteger()
1382     {
1383         return nodeCanSpeculateInteger(arithNodeFlags());
1384     }
1385     
1386     void dumpChildren(PrintStream& out)
1387     {
1388         if (!child1())
1389             return;
1390         out.printf("@%u", child1()->index());
1391         if (!child2())
1392             return;
1393         out.printf(", @%u", child2()->index());
1394         if (!child3())
1395             return;
1396         out.printf(", @%u", child3()->index());
1397     }
1398     
1399     // NB. This class must have a trivial destructor.
1400     
1401     // Used for determining what bytecode this came from. This is important for
1402     // debugging, exceptions, and even basic execution semantics.
1403     CodeOrigin codeOrigin;
1404     // Code origin for where the node exits to.
1405     CodeOrigin codeOriginForExitTarget;
1406     // References to up to 3 children, or links to a variable length set of children.
1407     AdjacencyList children;
1408
1409 private:
1410     unsigned m_op : 10; // real type is NodeType
1411     unsigned m_flags : 22;
1412     // The virtual register number (spill location) associated with this .
1413     VirtualRegister m_virtualRegister;
1414     // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
1415     unsigned m_refCount;
1416     // The prediction ascribed to this node after propagation.
1417     SpeculatedType m_prediction;
1418     // Immediate values, accesses type-checked via accessors above. The first one is
1419     // big enough to store a pointer.
1420     uintptr_t m_opInfo;
1421     uintptr_t m_opInfo2;
1422
1423 public:
1424     // Fields used by various analyses.
1425     AbstractValue value;
1426     
1427     // Miscellaneous data that is usually meaningless, but can hold some analysis results
1428     // if you ask right. For example, if you do Graph::initializeNodeOwners(), misc.owner
1429     // will tell you which basic block a node belongs to. You cannot rely on this persisting
1430     // across transformations unless you do the maintenance work yourself. Other phases use
1431     // misc.replacement, but they do so manually: first you do Graph::clearReplacements()
1432     // and then you set, and use, replacement's yourself.
1433     //
1434     // Bottom line: don't use these fields unless you initialize them yourself, or by
1435     // calling some appropriate methods that initialize them the way you want. Otherwise,
1436     // these fields are meaningless.
1437     union {
1438         Node* replacement;
1439         BasicBlock* owner;
1440     } misc;
1441 };
1442
1443 inline bool nodeComparator(Node* a, Node* b)
1444 {
1445     return a->index() < b->index();
1446 }
1447
1448 template<typename T>
1449 CString nodeListDump(const T& nodeList)
1450 {
1451     return sortedListDump(nodeList, nodeComparator);
1452 }
1453
1454 template<typename T>
1455 CString nodeMapDump(const T& nodeMap, DumpContext* context = 0)
1456 {
1457     Vector<typename T::KeyType> keys;
1458     for (
1459         typename T::const_iterator iter = nodeMap.begin();
1460         iter != nodeMap.end(); ++iter)
1461         keys.append(iter->key);
1462     std::sort(keys.begin(), keys.end(), nodeComparator);
1463     StringPrintStream out;
1464     CommaPrinter comma;
1465     for(unsigned i = 0; i < keys.size(); ++i)
1466         out.print(comma, keys[i], "=>", inContext(nodeMap.get(keys[i]), context));
1467     return out.toCString();
1468 }
1469
1470 } } // namespace JSC::DFG
1471
1472 namespace WTF {
1473
1474 void printInternal(PrintStream&, JSC::DFG::SwitchKind);
1475 void printInternal(PrintStream&, JSC::DFG::Node*);
1476
1477 inline JSC::DFG::Node* inContext(JSC::DFG::Node* node, JSC::DumpContext*) { return node; }
1478
1479 } // namespace WTF
1480
1481 using WTF::inContext;
1482
1483 #endif
1484 #endif