f5733641d6a1cef2d42c82588c5f93fca0a1be45
[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(VirtualRegister())
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(VirtualRegister())
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(VirtualRegister())
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(VirtualRegister())
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(VirtualRegister())
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.offset();
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     bool hasUnlinkedLocal()
531     {
532         switch (op()) {
533         case GetLocalUnlinked:
534         case ExtractOSREntryLocal:
535             return true;
536         default:
537             return false;
538         }
539     }
540     
541     VirtualRegister unlinkedLocal()
542     {
543         ASSERT(hasUnlinkedLocal());
544         return static_cast<VirtualRegister>(m_opInfo);
545     }
546     
547     bool hasPhi()
548     {
549         return op() == Upsilon;
550     }
551     
552     Node* phi()
553     {
554         ASSERT(hasPhi());
555         return bitwise_cast<Node*>(m_opInfo);
556     }
557     
558     bool hasIdentifier()
559     {
560         switch (op()) {
561         case GetById:
562         case GetByIdFlush:
563         case PutById:
564         case PutByIdDirect:
565             return true;
566         default:
567             return false;
568         }
569     }
570
571     unsigned identifierNumber()
572     {
573         ASSERT(hasIdentifier());
574         return m_opInfo;
575     }
576     
577     bool hasArithNodeFlags()
578     {
579         switch (op()) {
580         case UInt32ToNumber:
581         case ArithAdd:
582         case ArithSub:
583         case ArithNegate:
584         case ArithMul:
585         case ArithAbs:
586         case ArithMin:
587         case ArithMax:
588         case ArithMod:
589         case ArithDiv:
590         case ValueAdd:
591             return true;
592         default:
593             return false;
594         }
595     }
596     
597     // This corrects the arithmetic node flags, so that irrelevant bits are
598     // ignored. In particular, anything other than ArithMul does not need
599     // to know if it can speculate on negative zero.
600     NodeFlags arithNodeFlags()
601     {
602         NodeFlags result = m_flags & NodeArithFlagsMask;
603         if (op() == ArithMul || op() == ArithDiv || op() == ArithMod || op() == ArithNegate || op() == DoubleAsInt32)
604             return result;
605         return result & ~NodeBytecodeNeedsNegZero;
606     }
607     
608     bool hasConstantBuffer()
609     {
610         return op() == NewArrayBuffer;
611     }
612     
613     NewArrayBufferData* newArrayBufferData()
614     {
615         ASSERT(hasConstantBuffer());
616         return reinterpret_cast<NewArrayBufferData*>(m_opInfo);
617     }
618     
619     unsigned startConstant()
620     {
621         return newArrayBufferData()->startConstant;
622     }
623     
624     unsigned numConstants()
625     {
626         return newArrayBufferData()->numConstants;
627     }
628     
629     bool hasIndexingType()
630     {
631         switch (op()) {
632         case NewArray:
633         case NewArrayWithSize:
634         case NewArrayBuffer:
635             return true;
636         default:
637             return false;
638         }
639     }
640     
641     IndexingType indexingType()
642     {
643         ASSERT(hasIndexingType());
644         if (op() == NewArrayBuffer)
645             return newArrayBufferData()->indexingType;
646         return m_opInfo;
647     }
648     
649     bool hasTypedArrayType()
650     {
651         switch (op()) {
652         case NewTypedArray:
653             return true;
654         default:
655             return false;
656         }
657     }
658     
659     TypedArrayType typedArrayType()
660     {
661         ASSERT(hasTypedArrayType());
662         TypedArrayType result = static_cast<TypedArrayType>(m_opInfo);
663         ASSERT(isTypedView(result));
664         return result;
665     }
666     
667     bool hasInlineCapacity()
668     {
669         return op() == CreateThis;
670     }
671
672     unsigned inlineCapacity()
673     {
674         ASSERT(hasInlineCapacity());
675         return m_opInfo;
676     }
677
678     void setIndexingType(IndexingType indexingType)
679     {
680         ASSERT(hasIndexingType());
681         m_opInfo = indexingType;
682     }
683     
684     bool hasRegexpIndex()
685     {
686         return op() == NewRegexp;
687     }
688     
689     unsigned regexpIndex()
690     {
691         ASSERT(hasRegexpIndex());
692         return m_opInfo;
693     }
694     
695     bool hasVarNumber()
696     {
697         return op() == GetClosureVar || op() == PutClosureVar;
698     }
699
700     unsigned varNumber()
701     {
702         ASSERT(hasVarNumber());
703         return m_opInfo;
704     }
705     
706     bool hasIdentifierNumberForCheck()
707     {
708         return op() == GlobalVarWatchpoint;
709     }
710     
711     unsigned identifierNumberForCheck()
712     {
713         ASSERT(hasIdentifierNumberForCheck());
714         return m_opInfo2;
715     }
716     
717     bool hasRegisterPointer()
718     {
719         return op() == GetGlobalVar || op() == PutGlobalVar || op() == GlobalVarWatchpoint;
720     }
721     
722     WriteBarrier<Unknown>* registerPointer()
723     {
724         return bitwise_cast<WriteBarrier<Unknown>*>(m_opInfo);
725     }
726
727     bool hasResult()
728     {
729         return m_flags & NodeResultMask;
730     }
731
732     bool hasInt32Result()
733     {
734         return (m_flags & NodeResultMask) == NodeResultInt32;
735     }
736     
737     bool hasNumberResult()
738     {
739         return (m_flags & NodeResultMask) == NodeResultNumber;
740     }
741     
742     bool hasJSResult()
743     {
744         return (m_flags & NodeResultMask) == NodeResultJS;
745     }
746     
747     bool hasBooleanResult()
748     {
749         return (m_flags & NodeResultMask) == NodeResultBoolean;
750     }
751
752     bool hasStorageResult()
753     {
754         return (m_flags & NodeResultMask) == NodeResultStorage;
755     }
756
757     bool isJump()
758     {
759         return op() == Jump;
760     }
761
762     bool isBranch()
763     {
764         return op() == Branch;
765     }
766     
767     bool isSwitch()
768     {
769         return op() == Switch;
770     }
771
772     bool isTerminal()
773     {
774         switch (op()) {
775         case Jump:
776         case Branch:
777         case Switch:
778         case Return:
779         case Unreachable:
780             return true;
781         default:
782             return false;
783         }
784     }
785
786     unsigned takenBytecodeOffsetDuringParsing()
787     {
788         ASSERT(isBranch() || isJump());
789         return m_opInfo;
790     }
791
792     unsigned notTakenBytecodeOffsetDuringParsing()
793     {
794         ASSERT(isBranch());
795         return m_opInfo2;
796     }
797     
798     void setTakenBlock(BasicBlock* block)
799     {
800         ASSERT(isBranch() || isJump());
801         m_opInfo = bitwise_cast<uintptr_t>(block);
802     }
803     
804     void setNotTakenBlock(BasicBlock* block)
805     {
806         ASSERT(isBranch());
807         m_opInfo2 = bitwise_cast<uintptr_t>(block);
808     }
809     
810     BasicBlock*& takenBlock()
811     {
812         ASSERT(isBranch() || isJump());
813         return *bitwise_cast<BasicBlock**>(&m_opInfo);
814     }
815     
816     BasicBlock*& notTakenBlock()
817     {
818         ASSERT(isBranch());
819         return *bitwise_cast<BasicBlock**>(&m_opInfo2);
820     }
821     
822     SwitchData* switchData()
823     {
824         ASSERT(isSwitch());
825         return bitwise_cast<SwitchData*>(m_opInfo);
826     }
827     
828     unsigned numSuccessors()
829     {
830         switch (op()) {
831         case Jump:
832             return 1;
833         case Branch:
834             return 2;
835         case Switch:
836             return switchData()->cases.size() + 1;
837         default:
838             return 0;
839         }
840     }
841     
842     BasicBlock*& successor(unsigned index)
843     {
844         if (isSwitch()) {
845             if (index < switchData()->cases.size())
846                 return switchData()->cases[index].target;
847             RELEASE_ASSERT(index == switchData()->cases.size());
848             return switchData()->fallThrough;
849         }
850         switch (index) {
851         case 0:
852             return takenBlock();
853         case 1:
854             return notTakenBlock();
855         default:
856             RELEASE_ASSERT_NOT_REACHED();
857             return takenBlock();
858         }
859     }
860     
861     BasicBlock*& successorForCondition(bool condition)
862     {
863         ASSERT(isBranch());
864         return condition ? takenBlock() : notTakenBlock();
865     }
866     
867     bool hasHeapPrediction()
868     {
869         switch (op()) {
870         case GetById:
871         case GetByIdFlush:
872         case GetByVal:
873         case GetMyArgumentByVal:
874         case GetMyArgumentByValSafe:
875         case Call:
876         case Construct:
877         case GetByOffset:
878         case GetClosureVar:
879         case ArrayPop:
880         case ArrayPush:
881         case RegExpExec:
882         case RegExpTest:
883         case GetGlobalVar:
884             return true;
885         default:
886             return false;
887         }
888     }
889     
890     SpeculatedType getHeapPrediction()
891     {
892         ASSERT(hasHeapPrediction());
893         return static_cast<SpeculatedType>(m_opInfo2);
894     }
895     
896     bool predictHeap(SpeculatedType prediction)
897     {
898         ASSERT(hasHeapPrediction());
899         
900         return mergeSpeculation(m_opInfo2, prediction);
901     }
902     
903     bool hasFunction()
904     {
905         switch (op()) {
906         case CheckFunction:
907         case AllocationProfileWatchpoint:
908             return true;
909         default:
910             return false;
911         }
912     }
913
914     JSCell* function()
915     {
916         ASSERT(hasFunction());
917         JSCell* result = reinterpret_cast<JSFunction*>(m_opInfo);
918         ASSERT(JSValue(result).isFunction());
919         return result;
920     }
921     
922     bool hasExecutable()
923     {
924         return op() == CheckExecutable;
925     }
926     
927     ExecutableBase* executable()
928     {
929         return jsCast<ExecutableBase*>(reinterpret_cast<JSCell*>(m_opInfo));
930     }
931
932     bool hasStructureTransitionData()
933     {
934         switch (op()) {
935         case PutStructure:
936         case PhantomPutStructure:
937         case AllocatePropertyStorage:
938         case ReallocatePropertyStorage:
939             return true;
940         default:
941             return false;
942         }
943     }
944     
945     StructureTransitionData& structureTransitionData()
946     {
947         ASSERT(hasStructureTransitionData());
948         return *reinterpret_cast<StructureTransitionData*>(m_opInfo);
949     }
950     
951     bool hasStructureSet()
952     {
953         switch (op()) {
954         case CheckStructure:
955             return true;
956         default:
957             return false;
958         }
959     }
960     
961     StructureSet& structureSet()
962     {
963         ASSERT(hasStructureSet());
964         return *reinterpret_cast<StructureSet*>(m_opInfo);
965     }
966     
967     bool hasStructure()
968     {
969         switch (op()) {
970         case StructureTransitionWatchpoint:
971         case ArrayifyToStructure:
972         case NewObject:
973         case NewStringObject:
974             return true;
975         default:
976             return false;
977         }
978     }
979     
980     Structure* structure()
981     {
982         ASSERT(hasStructure());
983         return reinterpret_cast<Structure*>(m_opInfo);
984     }
985     
986     bool hasStorageAccessData()
987     {
988         return op() == GetByOffset || op() == PutByOffset;
989     }
990     
991     unsigned storageAccessDataIndex()
992     {
993         ASSERT(hasStorageAccessData());
994         return m_opInfo;
995     }
996     
997     bool hasFunctionDeclIndex()
998     {
999         return op() == NewFunction
1000             || op() == NewFunctionNoCheck;
1001     }
1002     
1003     unsigned functionDeclIndex()
1004     {
1005         ASSERT(hasFunctionDeclIndex());
1006         return m_opInfo;
1007     }
1008     
1009     bool hasFunctionExprIndex()
1010     {
1011         return op() == NewFunctionExpression;
1012     }
1013     
1014     unsigned functionExprIndex()
1015     {
1016         ASSERT(hasFunctionExprIndex());
1017         return m_opInfo;
1018     }
1019     
1020     bool hasArrayMode()
1021     {
1022         switch (op()) {
1023         case GetIndexedPropertyStorage:
1024         case GetArrayLength:
1025         case PutByVal:
1026         case PutByValAlias:
1027         case GetByVal:
1028         case StringCharAt:
1029         case StringCharCodeAt:
1030         case CheckArray:
1031         case Arrayify:
1032         case ArrayifyToStructure:
1033         case ArrayPush:
1034         case ArrayPop:
1035             return true;
1036         default:
1037             return false;
1038         }
1039     }
1040     
1041     ArrayMode arrayMode()
1042     {
1043         ASSERT(hasArrayMode());
1044         if (op() == ArrayifyToStructure)
1045             return ArrayMode::fromWord(m_opInfo2);
1046         return ArrayMode::fromWord(m_opInfo);
1047     }
1048     
1049     bool setArrayMode(ArrayMode arrayMode)
1050     {
1051         ASSERT(hasArrayMode());
1052         if (this->arrayMode() == arrayMode)
1053             return false;
1054         m_opInfo = arrayMode.asWord();
1055         return true;
1056     }
1057     
1058     bool hasVirtualRegister()
1059     {
1060         return m_virtualRegister.isValid();
1061     }
1062     
1063     VirtualRegister virtualRegister()
1064     {
1065         ASSERT(hasResult());
1066         ASSERT(m_virtualRegister.isValid());
1067         return m_virtualRegister;
1068     }
1069     
1070     void setVirtualRegister(VirtualRegister virtualRegister)
1071     {
1072         ASSERT(hasResult());
1073         ASSERT(!m_virtualRegister.isValid());
1074         m_virtualRegister = virtualRegister;
1075     }
1076     
1077     bool hasArgumentPositionStart()
1078     {
1079         return op() == InlineStart;
1080     }
1081     
1082     unsigned argumentPositionStart()
1083     {
1084         ASSERT(hasArgumentPositionStart());
1085         return m_opInfo;
1086     }
1087     
1088     bool hasExecutionCounter()
1089     {
1090         return op() == CountExecution;
1091     }
1092     
1093     Profiler::ExecutionCounter* executionCounter()
1094     {
1095         return bitwise_cast<Profiler::ExecutionCounter*>(m_opInfo);
1096     }
1097
1098     bool shouldGenerate()
1099     {
1100         return m_refCount;
1101     }
1102     
1103     bool willHaveCodeGenOrOSR()
1104     {
1105         switch (op()) {
1106         case SetLocal:
1107         case MovHint:
1108         case ZombieHint:
1109         case MovHintAndCheck:
1110         case Int32ToDouble:
1111         case ValueToInt32:
1112         case UInt32ToNumber:
1113         case DoubleAsInt32:
1114         case PhantomArguments:
1115             return true;
1116         case Phantom:
1117             return child1().useKindUnchecked() != UntypedUse || child2().useKindUnchecked() != UntypedUse || child3().useKindUnchecked() != UntypedUse;
1118         default:
1119             return shouldGenerate();
1120         }
1121     }
1122
1123     unsigned refCount()
1124     {
1125         return m_refCount;
1126     }
1127
1128     unsigned postfixRef()
1129     {
1130         return m_refCount++;
1131     }
1132
1133     unsigned adjustedRefCount()
1134     {
1135         return mustGenerate() ? m_refCount - 1 : m_refCount;
1136     }
1137     
1138     void setRefCount(unsigned refCount)
1139     {
1140         m_refCount = refCount;
1141     }
1142     
1143     Edge& child1()
1144     {
1145         ASSERT(!(m_flags & NodeHasVarArgs));
1146         return children.child1();
1147     }
1148     
1149     // This is useful if you want to do a fast check on the first child
1150     // before also doing a check on the opcode. Use this with care and
1151     // avoid it if possible.
1152     Edge child1Unchecked()
1153     {
1154         return children.child1Unchecked();
1155     }
1156
1157     Edge& child2()
1158     {
1159         ASSERT(!(m_flags & NodeHasVarArgs));
1160         return children.child2();
1161     }
1162
1163     Edge& child3()
1164     {
1165         ASSERT(!(m_flags & NodeHasVarArgs));
1166         return children.child3();
1167     }
1168     
1169     unsigned firstChild()
1170     {
1171         ASSERT(m_flags & NodeHasVarArgs);
1172         return children.firstChild();
1173     }
1174     
1175     unsigned numChildren()
1176     {
1177         ASSERT(m_flags & NodeHasVarArgs);
1178         return children.numChildren();
1179     }
1180     
1181     UseKind binaryUseKind()
1182     {
1183         ASSERT(child1().useKind() == child2().useKind());
1184         return child1().useKind();
1185     }
1186     
1187     bool isBinaryUseKind(UseKind useKind)
1188     {
1189         return child1().useKind() == useKind && child2().useKind() == useKind;
1190     }
1191     
1192     SpeculatedType prediction()
1193     {
1194         return m_prediction;
1195     }
1196     
1197     bool predict(SpeculatedType prediction)
1198     {
1199         return mergeSpeculation(m_prediction, prediction);
1200     }
1201     
1202     bool shouldSpeculateInt32()
1203     {
1204         return isInt32Speculation(prediction());
1205     }
1206     
1207     bool shouldSpeculateInt32ForArithmetic()
1208     {
1209         return isInt32SpeculationForArithmetic(prediction());
1210     }
1211     
1212     bool shouldSpeculateInt32ExpectingDefined()
1213     {
1214         return isInt32SpeculationExpectingDefined(prediction());
1215     }
1216     
1217     bool shouldSpeculateMachineInt()
1218     {
1219         return isMachineIntSpeculation(prediction());
1220     }
1221     
1222     bool shouldSpeculateMachineIntForArithmetic()
1223     {
1224         return isMachineIntSpeculationForArithmetic(prediction());
1225     }
1226     
1227     bool shouldSpeculateMachineIntExpectingDefined()
1228     {
1229         return isMachineIntSpeculationExpectingDefined(prediction());
1230     }
1231     
1232     bool shouldSpeculateDouble()
1233     {
1234         return isDoubleSpeculation(prediction());
1235     }
1236     
1237     bool shouldSpeculateDoubleForArithmetic()
1238     {
1239         return isDoubleSpeculationForArithmetic(prediction());
1240     }
1241     
1242     bool shouldSpeculateNumber()
1243     {
1244         return isFullNumberSpeculation(prediction());
1245     }
1246     
1247     bool shouldSpeculateNumberExpectingDefined()
1248     {
1249         return isFullNumberSpeculationExpectingDefined(prediction());
1250     }
1251     
1252     bool shouldSpeculateBoolean()
1253     {
1254         return isBooleanSpeculation(prediction());
1255     }
1256    
1257     bool shouldSpeculateStringIdent()
1258     {
1259         return isStringIdentSpeculation(prediction());
1260     }
1261  
1262     bool shouldSpeculateString()
1263     {
1264         return isStringSpeculation(prediction());
1265     }
1266  
1267     bool shouldSpeculateStringObject()
1268     {
1269         return isStringObjectSpeculation(prediction());
1270     }
1271     
1272     bool shouldSpeculateStringOrStringObject()
1273     {
1274         return isStringOrStringObjectSpeculation(prediction());
1275     }
1276     
1277     bool shouldSpeculateFinalObject()
1278     {
1279         return isFinalObjectSpeculation(prediction());
1280     }
1281     
1282     bool shouldSpeculateFinalObjectOrOther()
1283     {
1284         return isFinalObjectOrOtherSpeculation(prediction());
1285     }
1286     
1287     bool shouldSpeculateArray()
1288     {
1289         return isArraySpeculation(prediction());
1290     }
1291     
1292     bool shouldSpeculateArguments()
1293     {
1294         return isArgumentsSpeculation(prediction());
1295     }
1296     
1297     bool shouldSpeculateInt8Array()
1298     {
1299         return isInt8ArraySpeculation(prediction());
1300     }
1301     
1302     bool shouldSpeculateInt16Array()
1303     {
1304         return isInt16ArraySpeculation(prediction());
1305     }
1306     
1307     bool shouldSpeculateInt32Array()
1308     {
1309         return isInt32ArraySpeculation(prediction());
1310     }
1311     
1312     bool shouldSpeculateUint8Array()
1313     {
1314         return isUint8ArraySpeculation(prediction());
1315     }
1316
1317     bool shouldSpeculateUint8ClampedArray()
1318     {
1319         return isUint8ClampedArraySpeculation(prediction());
1320     }
1321     
1322     bool shouldSpeculateUint16Array()
1323     {
1324         return isUint16ArraySpeculation(prediction());
1325     }
1326     
1327     bool shouldSpeculateUint32Array()
1328     {
1329         return isUint32ArraySpeculation(prediction());
1330     }
1331     
1332     bool shouldSpeculateFloat32Array()
1333     {
1334         return isFloat32ArraySpeculation(prediction());
1335     }
1336     
1337     bool shouldSpeculateFloat64Array()
1338     {
1339         return isFloat64ArraySpeculation(prediction());
1340     }
1341     
1342     bool shouldSpeculateArrayOrOther()
1343     {
1344         return isArrayOrOtherSpeculation(prediction());
1345     }
1346     
1347     bool shouldSpeculateObject()
1348     {
1349         return isObjectSpeculation(prediction());
1350     }
1351     
1352     bool shouldSpeculateObjectOrOther()
1353     {
1354         return isObjectOrOtherSpeculation(prediction());
1355     }
1356
1357     bool shouldSpeculateCell()
1358     {
1359         return isCellSpeculation(prediction());
1360     }
1361     
1362     static bool shouldSpeculateBoolean(Node* op1, Node* op2)
1363     {
1364         return op1->shouldSpeculateBoolean() && op2->shouldSpeculateBoolean();
1365     }
1366     
1367     static bool shouldSpeculateInt32(Node* op1, Node* op2)
1368     {
1369         return op1->shouldSpeculateInt32() && op2->shouldSpeculateInt32();
1370     }
1371     
1372     static bool shouldSpeculateInt32ForArithmetic(Node* op1, Node* op2)
1373     {
1374         return op1->shouldSpeculateInt32ForArithmetic() && op2->shouldSpeculateInt32ForArithmetic();
1375     }
1376     
1377     static bool shouldSpeculateInt32ExpectingDefined(Node* op1, Node* op2)
1378     {
1379         return op1->shouldSpeculateInt32ExpectingDefined() && op2->shouldSpeculateInt32ExpectingDefined();
1380     }
1381     
1382     static bool shouldSpeculateMachineInt(Node* op1, Node* op2)
1383     {
1384         return op1->shouldSpeculateMachineInt() && op2->shouldSpeculateMachineInt();
1385     }
1386     
1387     static bool shouldSpeculateMachineIntForArithmetic(Node* op1, Node* op2)
1388     {
1389         return op1->shouldSpeculateMachineIntForArithmetic() && op2->shouldSpeculateMachineIntForArithmetic();
1390     }
1391     
1392     static bool shouldSpeculateMachineIntExpectingDefined(Node* op1, Node* op2)
1393     {
1394         return op1->shouldSpeculateMachineIntExpectingDefined() && op2->shouldSpeculateMachineIntExpectingDefined();
1395     }
1396     
1397     static bool shouldSpeculateDoubleForArithmetic(Node* op1, Node* op2)
1398     {
1399         return op1->shouldSpeculateDoubleForArithmetic() && op2->shouldSpeculateDoubleForArithmetic();
1400     }
1401     
1402     static bool shouldSpeculateNumber(Node* op1, Node* op2)
1403     {
1404         return op1->shouldSpeculateNumber() && op2->shouldSpeculateNumber();
1405     }
1406     
1407     static bool shouldSpeculateNumberExpectingDefined(Node* op1, Node* op2)
1408     {
1409         return op1->shouldSpeculateNumberExpectingDefined() && op2->shouldSpeculateNumberExpectingDefined();
1410     }
1411     
1412     static bool shouldSpeculateFinalObject(Node* op1, Node* op2)
1413     {
1414         return op1->shouldSpeculateFinalObject() && op2->shouldSpeculateFinalObject();
1415     }
1416
1417     static bool shouldSpeculateArray(Node* op1, Node* op2)
1418     {
1419         return op1->shouldSpeculateArray() && op2->shouldSpeculateArray();
1420     }
1421     
1422     bool canSpeculateInt32()
1423     {
1424         return nodeCanSpeculateInt32(arithNodeFlags());
1425     }
1426     
1427     bool canSpeculateInt52()
1428     {
1429         return nodeCanSpeculateInt52(arithNodeFlags());
1430     }
1431     
1432     void dumpChildren(PrintStream& out)
1433     {
1434         if (!child1())
1435             return;
1436         out.printf("@%u", child1()->index());
1437         if (!child2())
1438             return;
1439         out.printf(", @%u", child2()->index());
1440         if (!child3())
1441             return;
1442         out.printf(", @%u", child3()->index());
1443     }
1444     
1445     // NB. This class must have a trivial destructor.
1446     
1447     // Used for determining what bytecode this came from. This is important for
1448     // debugging, exceptions, and even basic execution semantics.
1449     CodeOrigin codeOrigin;
1450     // Code origin for where the node exits to.
1451     CodeOrigin codeOriginForExitTarget;
1452     // References to up to 3 children, or links to a variable length set of children.
1453     AdjacencyList children;
1454
1455 private:
1456     unsigned m_op : 10; // real type is NodeType
1457     unsigned m_flags : 22;
1458     // The virtual register number (spill location) associated with this .
1459     VirtualRegister m_virtualRegister;
1460     // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
1461     unsigned m_refCount;
1462     // The prediction ascribed to this node after propagation.
1463     SpeculatedType m_prediction;
1464     // Immediate values, accesses type-checked via accessors above. The first one is
1465     // big enough to store a pointer.
1466     uintptr_t m_opInfo;
1467     uintptr_t m_opInfo2;
1468
1469 public:
1470     // Fields used by various analyses.
1471     AbstractValue value;
1472     
1473     // Miscellaneous data that is usually meaningless, but can hold some analysis results
1474     // if you ask right. For example, if you do Graph::initializeNodeOwners(), misc.owner
1475     // will tell you which basic block a node belongs to. You cannot rely on this persisting
1476     // across transformations unless you do the maintenance work yourself. Other phases use
1477     // misc.replacement, but they do so manually: first you do Graph::clearReplacements()
1478     // and then you set, and use, replacement's yourself.
1479     //
1480     // Bottom line: don't use these fields unless you initialize them yourself, or by
1481     // calling some appropriate methods that initialize them the way you want. Otherwise,
1482     // these fields are meaningless.
1483     union {
1484         Node* replacement;
1485         BasicBlock* owner;
1486     } misc;
1487 };
1488
1489 inline bool nodeComparator(Node* a, Node* b)
1490 {
1491     return a->index() < b->index();
1492 }
1493
1494 template<typename T>
1495 CString nodeListDump(const T& nodeList)
1496 {
1497     return sortedListDump(nodeList, nodeComparator);
1498 }
1499
1500 template<typename T>
1501 CString nodeMapDump(const T& nodeMap, DumpContext* context = 0)
1502 {
1503     Vector<typename T::KeyType> keys;
1504     for (
1505         typename T::const_iterator iter = nodeMap.begin();
1506         iter != nodeMap.end(); ++iter)
1507         keys.append(iter->key);
1508     std::sort(keys.begin(), keys.end(), nodeComparator);
1509     StringPrintStream out;
1510     CommaPrinter comma;
1511     for(unsigned i = 0; i < keys.size(); ++i)
1512         out.print(comma, keys[i], "=>", inContext(nodeMap.get(keys[i]), context));
1513     return out.toCString();
1514 }
1515
1516 } } // namespace JSC::DFG
1517
1518 namespace WTF {
1519
1520 void printInternal(PrintStream&, JSC::DFG::SwitchKind);
1521 void printInternal(PrintStream&, JSC::DFG::Node*);
1522
1523 inline JSC::DFG::Node* inContext(JSC::DFG::Node* node, JSC::DumpContext*) { return node; }
1524
1525 } // namespace WTF
1526
1527 using WTF::inContext;
1528
1529 #endif
1530 #endif