PredictedType should be called SpeculatedType
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGGraph.h
1 /*
2  * Copyright (C) 2011 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 #include <wtf/Platform.h>
30
31 #if ENABLE(DFG_JIT)
32
33 #include "CodeBlock.h"
34 #include "DFGArgumentPosition.h"
35 #include "DFGAssemblyHelpers.h"
36 #include "DFGBasicBlock.h"
37 #include "DFGDominators.h"
38 #include "DFGNode.h"
39 #include "MethodOfGettingAValueProfile.h"
40 #include "RegisterFile.h"
41 #include <wtf/BitVector.h>
42 #include <wtf/HashMap.h>
43 #include <wtf/Vector.h>
44 #include <wtf/StdLibExtras.h>
45
46 namespace JSC {
47
48 class CodeBlock;
49 class ExecState;
50
51 namespace DFG {
52
53 struct StorageAccessData {
54     size_t offset;
55     unsigned identifierNumber;
56     
57     // NOTE: the offset and identifierNumber do not by themselves
58     // uniquely identify a property. The identifierNumber and a
59     // Structure* do. If those two match, then the offset should
60     // be the same, as well. For any Node that has a StorageAccessData,
61     // it is possible to retrieve the Structure* by looking at the
62     // first child. It should be a CheckStructure, which has the
63     // Structure*.
64 };
65
66 struct ResolveGlobalData {
67     unsigned identifierNumber;
68     unsigned resolveInfoIndex;
69 };
70
71 // 
72 // === Graph ===
73 //
74 // The dataflow graph is an ordered vector of nodes.
75 // The order may be significant for nodes with side-effects (property accesses, value conversions).
76 // Nodes that are 'dead' remain in the vector with refCount 0.
77 class Graph : public Vector<Node, 64> {
78 public:
79     Graph(JSGlobalData& globalData, CodeBlock* codeBlock)
80         : m_globalData(globalData)
81         , m_codeBlock(codeBlock)
82         , m_profiledBlock(codeBlock->alternative())
83         , m_hasArguments(false)
84     {
85         ASSERT(m_profiledBlock);
86     }
87     
88     using Vector<Node, 64>::operator[];
89     using Vector<Node, 64>::at;
90     
91     Node& operator[](Edge nodeUse) { return at(nodeUse.index()); }
92     const Node& operator[](Edge nodeUse) const { return at(nodeUse.index()); }
93     
94     Node& at(Edge nodeUse) { return at(nodeUse.index()); }
95     const Node& at(Edge nodeUse) const { return at(nodeUse.index()); }
96     
97     // Mark a node as being referenced.
98     void ref(NodeIndex nodeIndex)
99     {
100         Node& node = at(nodeIndex);
101         // If the value (before incrementing) was at refCount zero then we need to ref its children.
102         if (node.ref())
103             refChildren(nodeIndex);
104     }
105     void ref(Edge nodeUse)
106     {
107         ref(nodeUse.index());
108     }
109     
110     void deref(NodeIndex nodeIndex)
111     {
112         if (!at(nodeIndex).refCount())
113             dump();
114         if (at(nodeIndex).deref())
115             derefChildren(nodeIndex);
116     }
117     void deref(Edge nodeUse)
118     {
119         deref(nodeUse.index());
120     }
121     
122     void changeIndex(Edge& edge, NodeIndex newIndex, bool changeRef = true)
123     {
124         if (changeRef) {
125             ref(newIndex);
126             deref(edge.index());
127         }
128         edge.setIndex(newIndex);
129     }
130     
131     void changeEdge(Edge& edge, Edge newEdge, bool changeRef = true)
132     {
133         if (changeRef) {
134             ref(newEdge);
135             deref(edge);
136         }
137         edge = newEdge;
138     }
139     
140     void clearAndDerefChild1(Node& node)
141     {
142         if (!node.child1())
143             return;
144         deref(node.child1());
145         node.children.child1() = Edge();
146     }
147
148     void clearAndDerefChild2(Node& node)
149     {
150         if (!node.child2())
151             return;
152         deref(node.child2());
153         node.children.child2() = Edge();
154     }
155
156     void clearAndDerefChild3(Node& node)
157     {
158         if (!node.child3())
159             return;
160         deref(node.child3());
161         node.children.child3() = Edge();
162     }
163     
164     // Call this if you've modified the reference counts of nodes that deal with
165     // local variables. This is necessary because local variable references can form
166     // cycles, and hence reference counting is not enough. This will reset the
167     // reference counts according to reachability.
168     void collectGarbage();
169     
170     void convertToConstant(NodeIndex nodeIndex, unsigned constantNumber)
171     {
172         at(nodeIndex).convertToConstant(constantNumber);
173     }
174     
175     void convertToConstant(NodeIndex nodeIndex, JSValue value)
176     {
177         convertToConstant(nodeIndex, m_codeBlock->addOrFindConstant(value));
178     }
179
180     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
181     void dump();
182     void dump(NodeIndex);
183
184     // Dump the code origin of the given node as a diff from the code origin of the
185     // preceding node.
186     void dumpCodeOrigin(NodeIndex, NodeIndex);
187
188     BlockIndex blockIndexForBytecodeOffset(Vector<BlockIndex>& blocks, unsigned bytecodeBegin);
189
190     SpeculatedType getJSConstantSpeculation(Node& node)
191     {
192         return speculationFromValue(node.valueOfJSConstant(m_codeBlock));
193     }
194     
195     bool addShouldSpeculateInteger(Node& add)
196     {
197         ASSERT(add.op() == ValueAdd || add.op() == ArithAdd || add.op() == ArithSub);
198         
199         Node& left = at(add.child1());
200         Node& right = at(add.child2());
201         
202         if (left.hasConstant())
203             return addImmediateShouldSpeculateInteger(add, right, left);
204         if (right.hasConstant())
205             return addImmediateShouldSpeculateInteger(add, left, right);
206         
207         return Node::shouldSpeculateInteger(left, right) && add.canSpeculateInteger();
208     }
209     
210     bool mulShouldSpeculateInteger(Node& mul)
211     {
212         ASSERT(mul.op() == ArithMul);
213         
214         Node& left = at(mul.child1());
215         Node& right = at(mul.child2());
216         
217         if (left.hasConstant())
218             return mulImmediateShouldSpeculateInteger(mul, right, left);
219         if (right.hasConstant())
220             return mulImmediateShouldSpeculateInteger(mul, left, right);
221         
222         return Node::shouldSpeculateInteger(left, right) && mul.canSpeculateInteger() && !nodeMayOverflow(mul.arithNodeFlags());
223     }
224     
225     bool negateShouldSpeculateInteger(Node& negate)
226     {
227         ASSERT(negate.op() == ArithNegate);
228         return at(negate.child1()).shouldSpeculateInteger() && negate.canSpeculateInteger();
229     }
230     
231     bool addShouldSpeculateInteger(NodeIndex nodeIndex)
232     {
233         return addShouldSpeculateInteger(at(nodeIndex));
234     }
235     
236     // Helper methods to check nodes for constants.
237     bool isConstant(NodeIndex nodeIndex)
238     {
239         return at(nodeIndex).hasConstant();
240     }
241     bool isJSConstant(NodeIndex nodeIndex)
242     {
243         return at(nodeIndex).hasConstant();
244     }
245     bool isInt32Constant(NodeIndex nodeIndex)
246     {
247         return at(nodeIndex).isInt32Constant(m_codeBlock);
248     }
249     bool isDoubleConstant(NodeIndex nodeIndex)
250     {
251         return at(nodeIndex).isDoubleConstant(m_codeBlock);
252     }
253     bool isNumberConstant(NodeIndex nodeIndex)
254     {
255         return at(nodeIndex).isNumberConstant(m_codeBlock);
256     }
257     bool isBooleanConstant(NodeIndex nodeIndex)
258     {
259         return at(nodeIndex).isBooleanConstant(m_codeBlock);
260     }
261     bool isFunctionConstant(NodeIndex nodeIndex)
262     {
263         if (!isJSConstant(nodeIndex))
264             return false;
265         if (!getJSFunction(valueOfJSConstant(nodeIndex)))
266             return false;
267         return true;
268     }
269     // Helper methods get constant values from nodes.
270     JSValue valueOfJSConstant(NodeIndex nodeIndex)
271     {
272         return at(nodeIndex).valueOfJSConstant(m_codeBlock);
273     }
274     int32_t valueOfInt32Constant(NodeIndex nodeIndex)
275     {
276         return valueOfJSConstant(nodeIndex).asInt32();
277     }
278     double valueOfNumberConstant(NodeIndex nodeIndex)
279     {
280         return valueOfJSConstant(nodeIndex).asNumber();
281     }
282     bool valueOfBooleanConstant(NodeIndex nodeIndex)
283     {
284         return valueOfJSConstant(nodeIndex).asBoolean();
285     }
286     JSFunction* valueOfFunctionConstant(NodeIndex nodeIndex)
287     {
288         JSCell* function = getJSFunction(valueOfJSConstant(nodeIndex));
289         ASSERT(function);
290         return jsCast<JSFunction*>(function);
291     }
292
293     static const char *opName(NodeType);
294     
295     // This is O(n), and should only be used for verbose dumps.
296     const char* nameOfVariableAccessData(VariableAccessData*);
297
298     void predictArgumentTypes();
299     
300     StructureSet* addStructureSet(const StructureSet& structureSet)
301     {
302         ASSERT(structureSet.size());
303         m_structureSet.append(structureSet);
304         return &m_structureSet.last();
305     }
306     
307     StructureTransitionData* addStructureTransitionData(const StructureTransitionData& structureTransitionData)
308     {
309         m_structureTransitionData.append(structureTransitionData);
310         return &m_structureTransitionData.last();
311     }
312     
313     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
314     {
315         return m_codeBlock->globalObjectFor(codeOrigin);
316     }
317     
318     ExecutableBase* executableFor(InlineCallFrame* inlineCallFrame)
319     {
320         if (!inlineCallFrame)
321             return m_codeBlock->ownerExecutable();
322         
323         return inlineCallFrame->executable.get();
324     }
325     
326     ExecutableBase* executableFor(const CodeOrigin& codeOrigin)
327     {
328         return executableFor(codeOrigin.inlineCallFrame);
329     }
330     
331     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
332     {
333         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
334     }
335     
336     int argumentsRegisterFor(const CodeOrigin& codeOrigin)
337     {
338         if (!codeOrigin.inlineCallFrame)
339             return m_codeBlock->argumentsRegister();
340         
341         return baselineCodeBlockForInlineCallFrame(
342             codeOrigin.inlineCallFrame)->argumentsRegister() +
343             codeOrigin.inlineCallFrame->stackOffset;
344     }
345     
346     int uncheckedArgumentsRegisterFor(const CodeOrigin& codeOrigin)
347     {
348         if (!codeOrigin.inlineCallFrame)
349             return m_codeBlock->uncheckedArgumentsRegister();
350         
351         CodeBlock* codeBlock = baselineCodeBlockForInlineCallFrame(
352             codeOrigin.inlineCallFrame);
353         if (!codeBlock->usesArguments())
354             return InvalidVirtualRegister;
355         
356         return codeBlock->argumentsRegister() +
357             codeOrigin.inlineCallFrame->stackOffset;
358     }
359     
360     int uncheckedActivationRegisterFor(const CodeOrigin& codeOrigin)
361     {
362         ASSERT_UNUSED(codeOrigin, !codeOrigin.inlineCallFrame);
363         return m_codeBlock->uncheckedActivationRegister();
364     }
365     
366     ValueProfile* valueProfileFor(NodeIndex nodeIndex)
367     {
368         if (nodeIndex == NoNode)
369             return 0;
370         
371         Node& node = at(nodeIndex);
372         CodeBlock* profiledBlock = baselineCodeBlockFor(node.codeOrigin);
373         
374         if (node.hasLocal()) {
375             if (!operandIsArgument(node.local()))
376                 return 0;
377             int argument = operandToArgument(node.local());
378             if (node.variableAccessData() != at(m_arguments[argument]).variableAccessData())
379                 return 0;
380             return profiledBlock->valueProfileForArgument(argument);
381         }
382         
383         if (node.hasHeapPrediction())
384             return profiledBlock->valueProfileForBytecodeOffset(node.codeOrigin.bytecodeIndexForValueProfile());
385         
386         return 0;
387     }
388     
389     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(NodeIndex nodeIndex)
390     {
391         if (nodeIndex == NoNode)
392             return MethodOfGettingAValueProfile();
393         
394         Node& node = at(nodeIndex);
395         CodeBlock* profiledBlock = baselineCodeBlockFor(node.codeOrigin);
396         
397         if (node.op() == GetLocal) {
398             return MethodOfGettingAValueProfile::fromLazyOperand(
399                 profiledBlock,
400                 LazyOperandValueProfileKey(
401                     node.codeOrigin.bytecodeIndex, node.local()));
402         }
403         
404         return MethodOfGettingAValueProfile(valueProfileFor(nodeIndex));
405     }
406     
407     bool needsActivation() const
408     {
409         return m_codeBlock->needsFullScopeChain() && m_codeBlock->codeType() != GlobalCode;
410     }
411     
412     bool usesArguments() const
413     {
414         return m_codeBlock->usesArguments();
415     }
416     
417     unsigned numSuccessors(BasicBlock* block)
418     {
419         return at(block->last()).numSuccessors();
420     }
421     BlockIndex successor(BasicBlock* block, unsigned index)
422     {
423         return at(block->last()).successor(index);
424     }
425     BlockIndex successorForCondition(BasicBlock* block, bool condition)
426     {
427         return at(block->last()).successorForCondition(condition);
428     }
429     
430     bool isPredictedNumerical(Node& node)
431     {
432         SpeculatedType left = at(node.child1()).prediction();
433         SpeculatedType right = at(node.child2()).prediction();
434         return isNumberSpeculation(left) && isNumberSpeculation(right);
435     }
436     
437     bool byValIsPure(Node& node)
438     {
439         return at(node.child2()).shouldSpeculateInteger()
440             && ((node.op() == PutByVal || node.op() == PutByValAlias)
441                 ? isActionableMutableArraySpeculation(at(node.child1()).prediction())
442                 : isActionableArraySpeculation(at(node.child1()).prediction()));
443     }
444     
445     bool clobbersWorld(Node& node)
446     {
447         if (node.flags() & NodeClobbersWorld)
448             return true;
449         if (!(node.flags() & NodeMightClobber))
450             return false;
451         switch (node.op()) {
452         case ValueAdd:
453         case CompareLess:
454         case CompareLessEq:
455         case CompareGreater:
456         case CompareGreaterEq:
457         case CompareEq:
458             return !isPredictedNumerical(node);
459         case GetByVal:
460             return !byValIsPure(node);
461         default:
462             ASSERT_NOT_REACHED();
463             return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
464         }
465     }
466     
467     bool clobbersWorld(NodeIndex nodeIndex)
468     {
469         return clobbersWorld(at(nodeIndex));
470     }
471     
472     void determineReachability();
473     void resetReachability();
474     
475     void resetExitStates();
476     
477     unsigned numChildren(Node& node)
478     {
479         if (node.flags() & NodeHasVarArgs)
480             return node.numChildren();
481         return AdjacencyList::Size;
482     }
483     
484     Edge child(Node& node, unsigned index)
485     {
486         if (node.flags() & NodeHasVarArgs)
487             return m_varArgChildren[node.firstChild() + index];
488         return node.children.child(index);
489     }
490     
491     JSGlobalData& m_globalData;
492     CodeBlock* m_codeBlock;
493     CodeBlock* m_profiledBlock;
494
495     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
496     Vector<Edge, 16> m_varArgChildren;
497     Vector<StorageAccessData> m_storageAccessData;
498     Vector<ResolveGlobalData> m_resolveGlobalData;
499     Vector<NodeIndex, 8> m_arguments;
500     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
501     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
502     SegmentedVector<StructureSet, 16> m_structureSet;
503     SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
504     bool m_hasArguments;
505     HashSet<ExecutableBase*> m_executablesWhoseArgumentsEscaped;
506     BitVector m_preservedVars;
507     Dominators m_dominators;
508     unsigned m_localVars;
509     unsigned m_parameterSlots;
510 private:
511     
512     void handleSuccessor(Vector<BlockIndex, 16>& worklist, BlockIndex blockIndex, BlockIndex successorIndex);
513     
514     bool addImmediateShouldSpeculateInteger(Node& add, Node& variable, Node& immediate)
515     {
516         ASSERT(immediate.hasConstant());
517         
518         JSValue immediateValue = immediate.valueOfJSConstant(m_codeBlock);
519         if (!immediateValue.isNumber())
520             return false;
521         
522         if (!variable.shouldSpeculateInteger())
523             return false;
524         
525         if (immediateValue.isInt32())
526             return add.canSpeculateInteger();
527         
528         double doubleImmediate = immediateValue.asDouble();
529         const double twoToThe48 = 281474976710656.0;
530         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
531             return false;
532         
533         return nodeCanTruncateInteger(add.arithNodeFlags());
534     }
535     
536     bool mulImmediateShouldSpeculateInteger(Node& mul, Node& variable, Node& immediate)
537     {
538         ASSERT(immediate.hasConstant());
539         
540         JSValue immediateValue = immediate.valueOfJSConstant(m_codeBlock);
541         if (!immediateValue.isInt32())
542             return false;
543         
544         if (!variable.shouldSpeculateInteger())
545             return false;
546         
547         int32_t intImmediate = immediateValue.asInt32();
548         // Doubles have a 53 bit mantissa so we expect a multiplication of 2^31 (the highest
549         // magnitude possible int32 value) and any value less than 2^22 to not result in any
550         // rounding in a double multiplication - hence it will be equivalent to an integer
551         // multiplication, if we are doing int32 truncation afterwards (which is what
552         // canSpeculateInteger() implies).
553         const int32_t twoToThe22 = 1 << 22;
554         if (intImmediate <= -twoToThe22 || intImmediate >= twoToThe22)
555             return mul.canSpeculateInteger() && !nodeMayOverflow(mul.arithNodeFlags());
556
557         return mul.canSpeculateInteger();
558     }
559     
560     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
561     void refChildren(NodeIndex);
562     void derefChildren(NodeIndex);
563 };
564
565 class GetBytecodeBeginForBlock {
566 public:
567     GetBytecodeBeginForBlock(Graph& graph)
568         : m_graph(graph)
569     {
570     }
571     
572     unsigned operator()(BlockIndex* blockIndex) const
573     {
574         return m_graph.m_blocks[*blockIndex]->bytecodeBegin;
575     }
576
577 private:
578     Graph& m_graph;
579 };
580
581 inline BlockIndex Graph::blockIndexForBytecodeOffset(Vector<BlockIndex>& linkingTargets, unsigned bytecodeBegin)
582 {
583     return *WTF::binarySearchWithFunctor<BlockIndex, unsigned>(linkingTargets.begin(), linkingTargets.size(), bytecodeBegin, WTF::KeyMustBePresentInArray, GetBytecodeBeginForBlock(*this));
584 }
585
586 } } // namespace JSC::DFG
587
588 #endif
589 #endif