ValueRecovery should be moved out of the DFG JIT
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSpeculativeJIT.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 DFGSpeculativeJIT_h
27 #define DFGSpeculativeJIT_h
28
29 #if ENABLE(DFG_JIT)
30
31 #include "ValueRecovery.h"
32 #include <dfg/DFGAbstractState.h>
33 #include <dfg/DFGJITCodeGenerator.h>
34
35 namespace JSC { namespace DFG {
36
37 class SpeculativeJIT;
38
39 // This enum describes the types of additional recovery that
40 // may need be performed should a speculation check fail.
41 enum SpeculationRecoveryType {
42     SpeculativeAdd,
43     BooleanSpeculationCheck
44 };
45
46 // === SpeculationRecovery ===
47 //
48 // This class provides additional information that may be associated with a
49 // speculation check - for example 
50 class SpeculationRecovery {
51 public:
52     SpeculationRecovery(SpeculationRecoveryType type, GPRReg dest, GPRReg src)
53         : m_type(type)
54         , m_dest(dest)
55         , m_src(src)
56     {
57     }
58
59     SpeculationRecoveryType type() { return m_type; }
60     GPRReg dest() { return m_dest; }
61     GPRReg src() { return m_src; }
62
63 private:
64     // Indicates the type of additional recovery to be performed.
65     SpeculationRecoveryType m_type;
66     // different recovery types may required different additional information here.
67     GPRReg m_dest;
68     GPRReg m_src;
69 };
70
71 enum ValueSourceKind {
72     SourceNotSet,
73     ValueInRegisterFile,
74     Int32InRegisterFile,
75     CellInRegisterFile,
76     BooleanInRegisterFile,
77     HaveNode
78 };
79
80 class ValueSource {
81 public:
82     ValueSource()
83         : m_nodeIndex(nodeIndexFromKind(SourceNotSet))
84     {
85     }
86     
87     explicit ValueSource(ValueSourceKind valueSourceKind)
88         : m_nodeIndex(nodeIndexFromKind(valueSourceKind))
89     {
90         ASSERT(kind() != SourceNotSet);
91         ASSERT(kind() != HaveNode);
92     }
93     
94     explicit ValueSource(NodeIndex nodeIndex)
95         : m_nodeIndex(nodeIndex)
96     {
97         ASSERT(kind() == HaveNode);
98     }
99     
100     static ValueSource forPrediction(PredictedType prediction)
101     {
102         if (isInt32Prediction(prediction))
103             return ValueSource(Int32InRegisterFile);
104         if (isArrayPrediction(prediction) || isByteArrayPrediction(prediction))
105             return ValueSource(CellInRegisterFile);
106         if (isBooleanPrediction(prediction))
107             return ValueSource(BooleanInRegisterFile);
108         return ValueSource(ValueInRegisterFile);
109     }
110     
111     bool isSet() const
112     {
113         return kindFromNodeIndex(m_nodeIndex) != SourceNotSet;
114     }
115     
116     ValueSourceKind kind() const
117     {
118         return kindFromNodeIndex(m_nodeIndex);
119     }
120     
121     NodeIndex nodeIndex() const
122     {
123         ASSERT(kind() == HaveNode);
124         return m_nodeIndex;
125     }
126     
127 #ifndef NDEBUG
128     void dump(FILE* out) const;
129 #endif
130     
131 private:
132     static NodeIndex nodeIndexFromKind(ValueSourceKind kind)
133     {
134         ASSERT(kind >= SourceNotSet && kind < HaveNode);
135         return NoNode - kind;
136     }
137     
138     static ValueSourceKind kindFromNodeIndex(NodeIndex nodeIndex)
139     {
140         unsigned kind = static_cast<unsigned>(NoNode - nodeIndex);
141         if (kind >= static_cast<unsigned>(HaveNode))
142             return HaveNode;
143         return static_cast<ValueSourceKind>(kind);
144     }
145     
146     NodeIndex m_nodeIndex;
147 };
148     
149 // === OSRExit ===
150 //
151 // This structure describes how to exit the speculative path by
152 // going into baseline code.
153 struct OSRExit {
154     OSRExit(JSValueSource, ValueProfile*, MacroAssembler::Jump, SpeculativeJIT*, unsigned recoveryIndex = 0);
155     
156     JSValueSource m_jsValueSource;
157     ValueProfile* m_valueProfile;
158     
159     MacroAssembler::Jump m_check;
160     NodeIndex m_nodeIndex;
161     CodeOrigin m_codeOrigin;
162     
163     unsigned m_recoveryIndex;
164     
165     // Convenient way of iterating over ValueRecoveries while being
166     // generic over argument versus variable.
167     int numberOfRecoveries() const { return m_arguments.size() + m_variables.size(); }
168     const ValueRecovery& valueRecovery(int index) const
169     {
170         if (index < (int)m_arguments.size())
171             return m_arguments[index];
172         return m_variables[index - m_arguments.size()];
173     }
174     bool isArgument(int index) const { return index < (int)m_arguments.size(); }
175     bool isVariable(int index) const { return !isArgument(index); }
176     int argumentForIndex(int index) const
177     {
178         return index;
179     }
180     int variableForIndex(int index) const
181     {
182         return index - m_arguments.size();
183     }
184     int operandForArgument(int argument) const
185     {
186         return argument - m_arguments.size() - RegisterFile::CallFrameHeaderSize;
187     }
188     int operandForIndex(int index) const
189     {
190         if (index < (int)m_arguments.size())
191             return operandForArgument(index);
192         return index - m_arguments.size();
193     }
194     
195 #ifndef NDEBUG
196     void dump(FILE* out) const;
197 #endif
198     
199     Vector<ValueRecovery, 0> m_arguments;
200     Vector<ValueRecovery, 0> m_variables;
201     int m_lastSetOperand;
202 };
203 typedef SegmentedVector<OSRExit, 16> OSRExitVector;
204
205 // === SpeculativeJIT ===
206 //
207 // The SpeculativeJIT is used to generate a fast, but potentially
208 // incomplete code path for the dataflow. When code generating
209 // we may make assumptions about operand types, dynamically check,
210 // and bail-out to an alternate code path if these checks fail.
211 // Importantly, the speculative code path cannot be reentered once
212 // a speculative check has failed. This allows the SpeculativeJIT
213 // to propagate type information (including information that has
214 // only speculatively been asserted) through the dataflow.
215 class SpeculativeJIT : public JITCodeGenerator {
216     friend struct OSRExit;
217 public:
218     SpeculativeJIT(JITCompiler&);
219
220     bool compile();
221
222     // Retrieve the list of bail-outs from the speculative path,
223     // and additional recovery information.
224     OSRExitVector& osrExits()
225     {
226         return m_osrExits;
227     }
228     SpeculationRecovery* speculationRecovery(size_t index)
229     {
230         // OSRExit::m_recoveryIndex is offset by 1,
231         // 0 means no recovery.
232         return index ? &m_speculationRecoveryList[index - 1] : 0;
233     }
234
235     // Called by the speculative operand types, below, to fill operand to
236     // machine registers, implicitly generating speculation checks as needed.
237     GPRReg fillSpeculateInt(NodeIndex, DataFormat& returnFormat);
238     GPRReg fillSpeculateIntStrict(NodeIndex);
239     FPRReg fillSpeculateDouble(NodeIndex);
240     GPRReg fillSpeculateCell(NodeIndex);
241     GPRReg fillSpeculateBoolean(NodeIndex);
242
243 private:
244     friend class JITCodeGenerator;
245     
246     void compile(Node&);
247     void compileMovHint(Node&);
248     void compile(BasicBlock&);
249
250     void checkArgumentTypes();
251
252     bool isInteger(NodeIndex nodeIndex)
253     {
254         Node& node = at(nodeIndex);
255         if (node.hasInt32Result())
256             return true;
257
258         if (isInt32Constant(nodeIndex))
259             return true;
260
261         VirtualRegister virtualRegister = node.virtualRegister();
262         GenerationInfo& info = m_generationInfo[virtualRegister];
263         
264         return info.isJSInteger();
265     }
266     
267     bool compare(Node&, MacroAssembler::RelationalCondition, MacroAssembler::DoubleCondition, S_DFGOperation_EJJ);
268     bool compilePeepHoleBranch(Node&, MacroAssembler::RelationalCondition, MacroAssembler::DoubleCondition, S_DFGOperation_EJJ);
269     void compilePeepHoleIntegerBranch(Node&, NodeIndex branchNodeIndex, JITCompiler::RelationalCondition);
270     void compilePeepHoleDoubleBranch(Node&, NodeIndex branchNodeIndex, JITCompiler::DoubleCondition);
271     void compilePeepHoleObjectEquality(Node&, NodeIndex branchNodeIndex, void* vptr, PredictionChecker);
272     void compileObjectEquality(Node&, void* vptr, PredictionChecker);
273     void compileValueAdd(Node&);
274     void compileObjectOrOtherLogicalNot(NodeIndex value, void* vptr, bool needSpeculationCheck);
275     void compileLogicalNot(Node&);
276     void emitObjectOrOtherBranch(NodeIndex value, BlockIndex taken, BlockIndex notTaken, void *vptr, bool needSpeculationCheck);
277     void emitBranch(Node&);
278     
279     void compileGetCharCodeAt(Node&);
280     void compileGetByValOnString(Node&);
281     void compileValueToInt32(Node&);
282     void compileGetByValOnByteArray(Node&);
283     void compilePutByValForByteArray(GPRReg base, GPRReg property, Node&);
284     
285     // It is acceptable to have structure be equal to scratch, so long as you're fine
286     // with the structure GPR being clobbered.
287     template<typename T>
288     void emitAllocateJSFinalObject(T structure, GPRReg resultGPR, GPRReg scratchGPR, MacroAssembler::JumpList& slowPath)
289     {
290         MarkedSpace::SizeClass* sizeClass = &m_jit.globalData()->heap.sizeClassForObject(sizeof(JSFinalObject));
291         
292         m_jit.loadPtr(&sizeClass->firstFreeCell, resultGPR);
293         slowPath.append(m_jit.branchTestPtr(MacroAssembler::Zero, resultGPR));
294         
295         // The object is half-allocated: we have what we know is a fresh object, but
296         // it's still on the GC's free list.
297         
298         // Ditch the structure by placing it into the structure slot, so that we can reuse
299         // scratchGPR.
300         m_jit.storePtr(structure, MacroAssembler::Address(resultGPR, JSObject::structureOffset()));
301         
302         // Now that we have scratchGPR back, remove the object from the free list
303         m_jit.loadPtr(MacroAssembler::Address(resultGPR), scratchGPR);
304         m_jit.storePtr(scratchGPR, &sizeClass->firstFreeCell);
305         
306         // Initialize the object's vtable
307         m_jit.storePtr(MacroAssembler::TrustedImmPtr(m_jit.globalData()->jsFinalObjectVPtr), MacroAssembler::Address(resultGPR));
308         
309         // Initialize the object's inheritorID.
310         m_jit.storePtr(MacroAssembler::TrustedImmPtr(0), MacroAssembler::Address(resultGPR, JSObject::offsetOfInheritorID()));
311         
312         // Initialize the object's property storage pointer.
313         m_jit.addPtr(MacroAssembler::TrustedImm32(sizeof(JSObject)), resultGPR, scratchGPR);
314         m_jit.storePtr(scratchGPR, MacroAssembler::Address(resultGPR, JSFinalObject::offsetOfPropertyStorage()));
315     }
316
317 #if USE(JSVALUE64) 
318     JITCompiler::Jump convertToDouble(GPRReg value, FPRReg result, GPRReg tmp);
319 #elif USE(JSVALUE32_64)
320     JITCompiler::Jump convertToDouble(JSValueOperand&, FPRReg result);
321 #endif
322
323     // Add a speculation check without additional recovery.
324     void speculationCheck(JSValueSource jsValueSource, NodeIndex nodeIndex, MacroAssembler::Jump jumpToFail)
325     {
326         if (!m_compileOkay)
327             return;
328         m_osrExits.append(OSRExit(jsValueSource, m_jit.valueProfileFor(nodeIndex), jumpToFail, this));
329     }
330     // Add a speculation check with additional recovery.
331     void speculationCheck(JSValueSource jsValueSource, NodeIndex nodeIndex, MacroAssembler::Jump jumpToFail, const SpeculationRecovery& recovery)
332     {
333         if (!m_compileOkay)
334             return;
335         m_speculationRecoveryList.append(recovery);
336         m_osrExits.append(OSRExit(jsValueSource, m_jit.valueProfileFor(nodeIndex), jumpToFail, this, m_speculationRecoveryList.size()));
337     }
338
339     // Called when we statically determine that a speculation will fail.
340     void terminateSpeculativeExecution(JSValueRegs jsValueRegs, NodeIndex nodeIndex)
341     {
342 #if DFG_ENABLE(DEBUG_VERBOSE)
343         fprintf(stderr, "SpeculativeJIT was terminated.\n");
344 #endif
345         if (!m_compileOkay)
346             return;
347         speculationCheck(jsValueRegs, nodeIndex, m_jit.jump());
348         m_compileOkay = false;
349     }
350
351     template<bool strict>
352     GPRReg fillSpeculateIntInternal(NodeIndex, DataFormat& returnFormat);
353     
354     // It is possible, during speculative generation, to reach a situation in which we
355     // can statically determine a speculation will fail (for example, when two nodes
356     // will make conflicting speculations about the same operand). In such cases this
357     // flag is cleared, indicating no further code generation should take place.
358     bool m_compileOkay;
359     // This vector tracks bail-outs from the speculative path to the old JIT.
360     OSRExitVector m_osrExits;
361     // Some bail-outs need to record additional information recording specific recovery
362     // to be performed (for example, on detected overflow from an add, we may need to
363     // reverse the addition if an operand is being overwritten).
364     Vector<SpeculationRecovery, 16> m_speculationRecoveryList;
365     
366     // Tracking for which nodes are currently holding the values of arguments and bytecode
367     // operand-indexed variables.
368     
369     ValueSource valueSourceForOperand(int operand)
370     {
371         return valueSourceReferenceForOperand(operand);
372     }
373     
374     void setNodeIndexForOperand(NodeIndex nodeIndex, int operand)
375     {
376         valueSourceReferenceForOperand(operand) = ValueSource(nodeIndex);
377     }
378     
379     // Call this with care, since it both returns a reference into an array
380     // and potentially resizes the array. So it would not be right to call this
381     // twice and then perform operands on both references, since the one from
382     // the first call may no longer be valid.
383     ValueSource& valueSourceReferenceForOperand(int operand)
384     {
385         if (operandIsArgument(operand)) {
386             int argument = operand + m_arguments.size() + RegisterFile::CallFrameHeaderSize;
387             return m_arguments[argument];
388         }
389         
390         if ((unsigned)operand >= m_variables.size())
391             m_variables.resize(operand + 1);
392         
393         return m_variables[operand];
394     }
395     
396     Vector<ValueSource, 0> m_arguments;
397     Vector<ValueSource, 0> m_variables;
398     int m_lastSetOperand;
399     CodeOrigin m_codeOriginForOSR;
400     
401     AbstractState m_state;
402     
403     ValueRecovery computeValueRecoveryFor(const ValueSource&);
404
405     ValueRecovery computeValueRecoveryFor(int operand)
406     {
407         return computeValueRecoveryFor(valueSourceForOperand(operand));
408     }
409 };
410
411
412 // === Speculative Operand types ===
413 //
414 // SpeculateIntegerOperand, SpeculateStrictInt32Operand and SpeculateCellOperand.
415 //
416 // These are used to lock the operands to a node into machine registers within the
417 // SpeculativeJIT. The classes operate like those provided by the JITCodeGenerator,
418 // however these will perform a speculative check for a more restrictive type than
419 // we can statically determine the operand to have. If the operand does not have
420 // the requested type, a bail-out to the non-speculative path will be taken.
421
422 class SpeculateIntegerOperand {
423 public:
424     explicit SpeculateIntegerOperand(SpeculativeJIT* jit, NodeIndex index)
425         : m_jit(jit)
426         , m_index(index)
427         , m_gprOrInvalid(InvalidGPRReg)
428 #ifndef NDEBUG
429         , m_format(DataFormatNone)
430 #endif
431     {
432         ASSERT(m_jit);
433         if (jit->isFilled(index))
434             gpr();
435     }
436
437     ~SpeculateIntegerOperand()
438     {
439         ASSERT(m_gprOrInvalid != InvalidGPRReg);
440         m_jit->unlock(m_gprOrInvalid);
441     }
442
443     NodeIndex index() const
444     {
445         return m_index;
446     }
447
448     DataFormat format()
449     {
450         gpr(); // m_format is set when m_gpr is locked.
451         ASSERT(m_format == DataFormatInteger || m_format == DataFormatJSInteger);
452         return m_format;
453     }
454
455     GPRReg gpr()
456     {
457         if (m_gprOrInvalid == InvalidGPRReg)
458             m_gprOrInvalid = m_jit->fillSpeculateInt(index(), m_format);
459         return m_gprOrInvalid;
460     }
461
462 private:
463     SpeculativeJIT* m_jit;
464     NodeIndex m_index;
465     GPRReg m_gprOrInvalid;
466     DataFormat m_format;
467 };
468
469 class SpeculateStrictInt32Operand {
470 public:
471     explicit SpeculateStrictInt32Operand(SpeculativeJIT* jit, NodeIndex index)
472         : m_jit(jit)
473         , m_index(index)
474         , m_gprOrInvalid(InvalidGPRReg)
475     {
476         ASSERT(m_jit);
477         if (jit->isFilled(index))
478             gpr();
479     }
480
481     ~SpeculateStrictInt32Operand()
482     {
483         ASSERT(m_gprOrInvalid != InvalidGPRReg);
484         m_jit->unlock(m_gprOrInvalid);
485     }
486
487     NodeIndex index() const
488     {
489         return m_index;
490     }
491
492     GPRReg gpr()
493     {
494         if (m_gprOrInvalid == InvalidGPRReg)
495             m_gprOrInvalid = m_jit->fillSpeculateIntStrict(index());
496         return m_gprOrInvalid;
497     }
498     
499     void use()
500     {
501         m_jit->use(m_index);
502     }
503
504 private:
505     SpeculativeJIT* m_jit;
506     NodeIndex m_index;
507     GPRReg m_gprOrInvalid;
508 };
509
510 class SpeculateDoubleOperand {
511 public:
512     explicit SpeculateDoubleOperand(SpeculativeJIT* jit, NodeIndex index)
513         : m_jit(jit)
514         , m_index(index)
515         , m_fprOrInvalid(InvalidFPRReg)
516     {
517         ASSERT(m_jit);
518         if (jit->isFilled(index))
519             fpr();
520     }
521
522     ~SpeculateDoubleOperand()
523     {
524         ASSERT(m_fprOrInvalid != InvalidFPRReg);
525         m_jit->unlock(m_fprOrInvalid);
526     }
527
528     NodeIndex index() const
529     {
530         return m_index;
531     }
532
533     FPRReg fpr()
534     {
535         if (m_fprOrInvalid == InvalidFPRReg)
536             m_fprOrInvalid = m_jit->fillSpeculateDouble(index());
537         return m_fprOrInvalid;
538     }
539
540 private:
541     SpeculativeJIT* m_jit;
542     NodeIndex m_index;
543     FPRReg m_fprOrInvalid;
544 };
545
546 class SpeculateCellOperand {
547 public:
548     explicit SpeculateCellOperand(SpeculativeJIT* jit, NodeIndex index)
549         : m_jit(jit)
550         , m_index(index)
551         , m_gprOrInvalid(InvalidGPRReg)
552     {
553         ASSERT(m_jit);
554         if (jit->isFilled(index))
555             gpr();
556     }
557
558     ~SpeculateCellOperand()
559     {
560         ASSERT(m_gprOrInvalid != InvalidGPRReg);
561         m_jit->unlock(m_gprOrInvalid);
562     }
563
564     NodeIndex index() const
565     {
566         return m_index;
567     }
568
569     GPRReg gpr()
570     {
571         if (m_gprOrInvalid == InvalidGPRReg)
572             m_gprOrInvalid = m_jit->fillSpeculateCell(index());
573         return m_gprOrInvalid;
574     }
575     
576     void use()
577     {
578         m_jit->use(m_index);
579     }
580
581 private:
582     SpeculativeJIT* m_jit;
583     NodeIndex m_index;
584     GPRReg m_gprOrInvalid;
585 };
586
587 class SpeculateBooleanOperand {
588 public:
589     explicit SpeculateBooleanOperand(SpeculativeJIT* jit, NodeIndex index)
590         : m_jit(jit)
591         , m_index(index)
592         , m_gprOrInvalid(InvalidGPRReg)
593     {
594         ASSERT(m_jit);
595         if (jit->isFilled(index))
596             gpr();
597     }
598     
599     ~SpeculateBooleanOperand()
600     {
601         ASSERT(m_gprOrInvalid != InvalidGPRReg);
602         m_jit->unlock(m_gprOrInvalid);
603     }
604     
605     NodeIndex index() const
606     {
607         return m_index;
608     }
609     
610     GPRReg gpr()
611     {
612         if (m_gprOrInvalid == InvalidGPRReg)
613             m_gprOrInvalid = m_jit->fillSpeculateBoolean(index());
614         return m_gprOrInvalid;
615     }
616     
617     void use()
618     {
619         m_jit->use(m_index);
620     }
621
622 private:
623     SpeculativeJIT* m_jit;
624     NodeIndex m_index;
625     GPRReg m_gprOrInvalid;
626 };
627
628 inline SpeculativeJIT::SpeculativeJIT(JITCompiler& jit)
629     : JITCodeGenerator(jit)
630     , m_compileOkay(true)
631     , m_arguments(jit.codeBlock()->m_numParameters)
632     , m_variables(jit.graph().m_localVars)
633     , m_lastSetOperand(std::numeric_limits<int>::max())
634     , m_state(m_jit.codeBlock(), m_jit.graph())
635 {
636 }
637
638 } } // namespace JSC::DFG
639
640 #endif
641 #endif
642