2008-12-02 Geoffrey Garen <ggaren@apple.com>
[WebKit-https.git] / JavaScriptCore / bytecompiler / BytecodeGenerator.h
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  * Copyright (C) 2008 Cameron Zwarich <cwzwarich@uwaterloo.ca>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer.
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution.
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #ifndef BytecodeGenerator_h
31 #define BytecodeGenerator_h
32
33 #include "CodeBlock.h"
34 #include "HashTraits.h"
35 #include "Instruction.h"
36 #include "Label.h"
37 #include "LabelScope.h"
38 #include "Interpreter.h"
39 #include "RegisterID.h"
40 #include "SegmentedVector.h"
41 #include "SymbolTable.h"
42 #include "Debugger.h"
43 #include "Nodes.h"
44 #include <wtf/PassRefPtr.h>
45 #include <wtf/Vector.h>
46
47 namespace JSC {
48
49     class Identifier;
50     class ScopeChain;
51     class ScopeNode;
52
53     struct FinallyContext {
54         Label* finallyAddr;
55         RegisterID* retAddrDst;
56     };
57
58     struct ControlFlowContext {
59         bool isFinallyBlock;
60         FinallyContext finallyContext;
61     };
62
63     class BytecodeGenerator {
64     public:
65         typedef DeclarationStacks::VarStack VarStack;
66         typedef DeclarationStacks::FunctionStack FunctionStack;
67
68         static void setDumpsGeneratedCode(bool dumpsGeneratedCode);
69
70         BytecodeGenerator(ProgramNode*, const Debugger*, const ScopeChain&, SymbolTable*, ProgramCodeBlock*);
71         BytecodeGenerator(FunctionBodyNode*, const Debugger*, const ScopeChain&, SymbolTable*, CodeBlock*);
72         BytecodeGenerator(EvalNode*, const Debugger*, const ScopeChain&, SymbolTable*, EvalCodeBlock*);
73
74         JSGlobalData* globalData() const { return m_globalData; }
75         const CommonIdentifiers& propertyNames() const { return *m_globalData->propertyNames; }
76
77         void generate();
78
79         // Returns the register corresponding to a local variable, or 0 if no
80         // such register exists. Registers returned by registerFor do not
81         // require explicit reference counting.
82         RegisterID* registerFor(const Identifier&);
83
84         // Behaves as registerFor does, but ignores dynamic scope as
85         // dynamic scope should not interfere with const initialisation
86         RegisterID* constRegisterFor(const Identifier&);
87
88         // Searches the scope chain in an attempt to  statically locate the requested
89         // property.  Returns false if for any reason the property cannot be safely
90         // optimised at all.  Otherwise it will return the index and depth of the
91         // VariableObject that defines the property.  If the property cannot be found
92         // statically, depth will contain the depth of the scope chain where dynamic
93         // lookup must begin.
94         //
95         // NB: depth does _not_ include the local scope.  eg. a depth of 0 refers
96         // to the scope containing this codeblock.
97         bool findScopedProperty(const Identifier&, int& index, size_t& depth, bool forWriting, JSObject*& globalObject);
98
99         // Returns the register storing "this"
100         RegisterID* thisRegister() { return &m_thisRegister; }
101
102         bool isLocal(const Identifier&);
103         bool isLocalConstant(const Identifier&);
104
105         // Returns the next available temporary register. Registers returned by
106         // newTemporary require a modified form of reference counting: any
107         // register with a refcount of 0 is considered "available", meaning that
108         // the next instruction may overwrite it.
109         RegisterID* newTemporary();
110
111         RegisterID* highestUsedRegister();
112
113         // The same as newTemporary(), but this function returns "suggestion" if
114         // "suggestion" is a temporary. This function is helpful in situations
115         // where you've put "suggestion" in a RefPtr, but you'd like to allow
116         // the next instruction to overwrite it anyway.
117         RegisterID* newTemporaryOr(RegisterID* suggestion) { return suggestion->isTemporary() ? suggestion : newTemporary(); }
118
119         // Functions for handling of dst register
120
121         // Returns a place to write intermediate values of an operation
122         // which reuses dst if it is safe to do so.
123         RegisterID* tempDestination(RegisterID* dst)
124         {
125             return (dst && dst != ignoredResult() && dst->isTemporary()) ? dst : newTemporary();
126         }
127
128         // Returns the place to write the final output of an operation.
129         RegisterID* finalDestination(RegisterID* originalDst, RegisterID* tempDst = 0)
130         {
131             if (originalDst && originalDst != ignoredResult())
132                 return originalDst;
133             ASSERT(tempDst != ignoredResult());
134             if (tempDst && tempDst->isTemporary())
135                 return tempDst;
136             return newTemporary();
137         }
138
139         RegisterID* destinationForAssignResult(RegisterID* dst)
140         {
141             if (dst && dst != ignoredResult() && m_codeBlock->needsFullScopeChain)
142                 return dst->isTemporary() ? dst : newTemporary();
143             return 0;
144         }
145
146         // Moves src to dst if dst is not null and is different from src, otherwise just returns src.
147         RegisterID* moveToDestinationIfNeeded(RegisterID* dst, RegisterID* src)
148         {
149             return dst == ignoredResult() ? 0 : (dst && dst != src) ? emitMove(dst, src) : src;
150         }
151
152         PassRefPtr<LabelScope> newLabelScope(LabelScope::Type, const Identifier* = 0);
153         PassRefPtr<Label> newLabel();
154
155         // The emitNode functions are just syntactic sugar for calling
156         // Node::emitCode. These functions accept a 0 for the register,
157         // meaning that the node should allocate a register, or ignoredResult(),
158         // meaning that the node need not put the result in a register.
159         // Other emit functions do not accept 0 or ignoredResult().
160         RegisterID* emitNode(RegisterID* dst, Node* n)
161         {
162             // Node::emitCode assumes that dst, if provided, is either a local or a referenced temporary.
163             ASSERT(!dst || dst == ignoredResult() || !dst->isTemporary() || dst->refCount());
164             if (!m_codeBlock->lineInfo.size() || m_codeBlock->lineInfo.last().lineNumber != n->lineNo()) {
165                 LineInfo info = { instructions().size(), n->lineNo() };
166                 m_codeBlock->lineInfo.append(info);
167             }
168             if (m_emitNodeDepth >= s_maxEmitNodeDepth)
169                 return emitThrowExpressionTooDeepException();
170             ++m_emitNodeDepth;
171             RegisterID* r = n->emitBytecode(*this, dst);
172             --m_emitNodeDepth;
173             return r;
174         }
175
176         RegisterID* emitNode(Node* n)
177         {
178             return emitNode(0, n);
179         }
180
181         void emitExpressionInfo(unsigned divot, unsigned startOffset, unsigned endOffset)
182         { 
183             divot -= m_codeBlock->sourceOffset;
184             if (divot > ExpressionRangeInfo::MaxDivot) {
185                 // Overflow has occurred, we can only give line number info for errors for this region
186                 divot = 0;
187                 startOffset = 0;
188                 endOffset = 0;
189             } else if (startOffset > ExpressionRangeInfo::MaxOffset) {
190                 // If the start offset is out of bounds we clear both offsets
191                 // so we only get the divot marker.  Error message will have to be reduced
192                 // to line and column number.
193                 startOffset = 0;
194                 endOffset = 0;
195             } else if (endOffset > ExpressionRangeInfo::MaxOffset) {
196                 // The end offset is only used for additional context, and is much more likely
197                 // to overflow (eg. function call arguments) so we are willing to drop it without
198                 // dropping the rest of the range.
199                 endOffset = 0;
200             }
201             
202             ExpressionRangeInfo info;
203             info.instructionOffset = instructions().size();
204             info.divotPoint = divot;
205             info.startOffset = startOffset;
206             info.endOffset = endOffset;
207             m_codeBlock->expressionInfo.append(info);
208         }
209         
210         ALWAYS_INLINE bool leftHandSideNeedsCopy(bool rightHasAssignments, bool rightIsPure)
211         {
212             return (m_codeType != FunctionCode || m_codeBlock->needsFullScopeChain || rightHasAssignments) && !rightIsPure;
213         }
214
215         ALWAYS_INLINE PassRefPtr<RegisterID> emitNodeForLeftHandSide(ExpressionNode* n, bool rightHasAssignments, bool rightIsPure)
216         {
217             if (leftHandSideNeedsCopy(rightHasAssignments, rightIsPure)) {
218                 PassRefPtr<RegisterID> dst = newTemporary();
219                 emitNode(dst.get(), n);
220                 return dst;
221             }
222
223             return PassRefPtr<RegisterID>(emitNode(n));
224         }
225
226         RegisterID* emitLoad(RegisterID* dst, bool);
227         RegisterID* emitLoad(RegisterID* dst, double);
228         RegisterID* emitLoad(RegisterID* dst, const Identifier&);
229         RegisterID* emitLoad(RegisterID* dst, JSValue*);
230         RegisterID* emitLoad(RegisterID* dst, JSCell*);
231         RegisterID* emitUnexpectedLoad(RegisterID* dst, bool);
232         RegisterID* emitUnexpectedLoad(RegisterID* dst, double);
233
234         RegisterID* emitUnaryOp(OpcodeID, RegisterID* dst, RegisterID* src);
235         RegisterID* emitBinaryOp(OpcodeID, RegisterID* dst, RegisterID* src1, RegisterID* src2, OperandTypes);
236         RegisterID* emitEqualityOp(OpcodeID, RegisterID* dst, RegisterID* src1, RegisterID* src2);
237         RegisterID* emitUnaryNoDstOp(OpcodeID, RegisterID* src);
238
239         RegisterID* emitNewObject(RegisterID* dst);
240         RegisterID* emitNewArray(RegisterID* dst, ElementNode*); // stops at first elision
241
242         RegisterID* emitNewFunction(RegisterID* dst, FuncDeclNode* func);
243         RegisterID* emitNewFunctionExpression(RegisterID* dst, FuncExprNode* func);
244         RegisterID* emitNewRegExp(RegisterID* dst, RegExp* regExp);
245
246         RegisterID* emitMove(RegisterID* dst, RegisterID* src);
247
248         RegisterID* emitToJSNumber(RegisterID* dst, RegisterID* src) { return emitUnaryOp(op_to_jsnumber, dst, src); }
249         RegisterID* emitPreInc(RegisterID* srcDst);
250         RegisterID* emitPreDec(RegisterID* srcDst);
251         RegisterID* emitPostInc(RegisterID* dst, RegisterID* srcDst);
252         RegisterID* emitPostDec(RegisterID* dst, RegisterID* srcDst);
253
254         RegisterID* emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base, RegisterID* basePrototype);
255         RegisterID* emitTypeOf(RegisterID* dst, RegisterID* src) { return emitUnaryOp(op_typeof, dst, src); }
256         RegisterID* emitIn(RegisterID* dst, RegisterID* property, RegisterID* base) { return emitBinaryOp(op_in, dst, property, base, OperandTypes()); }
257
258         RegisterID* emitResolve(RegisterID* dst, const Identifier& property);
259         RegisterID* emitGetScopedVar(RegisterID* dst, size_t skip, int index, JSValue* globalObject);
260         RegisterID* emitPutScopedVar(size_t skip, int index, RegisterID* value, JSValue* globalObject);
261
262         RegisterID* emitResolveBase(RegisterID* dst, const Identifier& property);
263         RegisterID* emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property);
264         RegisterID* emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property);
265
266         RegisterID* emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property);
267         RegisterID* emitPutById(RegisterID* base, const Identifier& property, RegisterID* value);
268         RegisterID* emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier&);
269         RegisterID* emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
270         RegisterID* emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value);
271         RegisterID* emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
272         RegisterID* emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value);
273         RegisterID* emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value);
274         RegisterID* emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value);
275
276         RegisterID* emitCall(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
277         RegisterID* emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
278
279         RegisterID* emitReturn(RegisterID* src);
280         RegisterID* emitEnd(RegisterID* src) { return emitUnaryNoDstOp(op_end, src); }
281
282         RegisterID* emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
283
284         PassRefPtr<Label> emitLabel(Label*);
285         PassRefPtr<Label> emitJump(Label* target);
286         PassRefPtr<Label> emitJumpIfTrue(RegisterID* cond, Label* target);
287         PassRefPtr<Label> emitJumpIfFalse(RegisterID* cond, Label* target);
288         PassRefPtr<Label> emitJumpScopes(Label* target, int targetScopeDepth);
289
290         PassRefPtr<Label> emitJumpSubroutine(RegisterID* retAddrDst, Label*);
291         void emitSubroutineReturn(RegisterID* retAddrSrc);
292
293         RegisterID* emitGetPropertyNames(RegisterID* dst, RegisterID* base) { return emitUnaryOp(op_get_pnames, dst, base); }
294         RegisterID* emitNextPropertyName(RegisterID* dst, RegisterID* iter, Label* target);
295
296         RegisterID* emitCatch(RegisterID*, Label* start, Label* end);
297         void emitThrow(RegisterID* exc) { emitUnaryNoDstOp(op_throw, exc); }
298         RegisterID* emitNewError(RegisterID* dst, ErrorType type, JSValue* message);
299         void emitPushNewScope(RegisterID* dst, Identifier& property, RegisterID* value);
300
301         RegisterID* emitPushScope(RegisterID* scope);
302         void emitPopScope();
303
304         void emitDebugHook(DebugHookID, int firstLine, int lastLine);
305
306         int scopeDepth() { return m_dynamicScopeDepth + m_finallyDepth; }
307
308         void pushFinallyContext(Label* target, RegisterID* returnAddrDst);
309         void popFinallyContext();
310
311         LabelScope* breakTarget(const Identifier&);
312         LabelScope* continueTarget(const Identifier&);
313
314         void beginSwitch(RegisterID*, SwitchInfo::SwitchType);
315         void endSwitch(uint32_t clauseCount, RefPtr<Label>*, ExpressionNode**, Label* defaultLabel, int32_t min, int32_t range);
316
317         CodeType codeType() const { return m_codeType; }
318
319     private:
320         void emitOpcode(OpcodeID);
321         void retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index);
322         void retrieveLastUnaryOp(int& dstIndex, int& srcIndex);
323         void rewindBinaryOp();
324         void rewindUnaryOp();
325
326         PassRefPtr<Label> emitComplexJumpScopes(Label* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope);
327
328         struct JSValueHashTraits : HashTraits<JSValue*> {
329             static void constructDeletedValue(JSValue*& slot) { slot = JSImmediate::impossibleValue(); }
330             static bool isDeletedValue(JSValue* value) { return value == JSImmediate::impossibleValue(); }
331         };
332
333         typedef HashMap<JSValue*, unsigned, PtrHash<JSValue*>, JSValueHashTraits> JSValueMap;
334
335         struct IdentifierMapIndexHashTraits {
336             typedef int TraitType;
337             typedef IdentifierMapIndexHashTraits StorageTraits;
338             static int emptyValue() { return std::numeric_limits<int>::max(); }
339             static const bool emptyValueIsZero = false;
340             static const bool needsDestruction = false;
341             static const bool needsRef = false;
342         };
343
344         typedef HashMap<RefPtr<UString::Rep>, int, IdentifierRepHash, HashTraits<RefPtr<UString::Rep> >, IdentifierMapIndexHashTraits> IdentifierMap;
345         typedef HashMap<double, JSValue*> NumberMap;
346         typedef HashMap<UString::Rep*, JSString*, IdentifierRepHash> IdentifierStringMap;
347
348         RegisterID* emitCall(OpcodeID, RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
349         
350         RegisterID* newRegister();
351
352         // Returns the RegisterID corresponding to ident.
353         RegisterID* addVar(const Identifier& ident, bool isConstant)
354         {
355             RegisterID* local;
356             addVar(ident, isConstant, local);
357             return local;
358         }
359         // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
360         bool addVar(const Identifier&, bool isConstant, RegisterID*&);
361
362         // Returns the RegisterID corresponding to ident.
363         RegisterID* addGlobalVar(const Identifier& ident, bool isConstant)
364         {
365             RegisterID* local;
366             addGlobalVar(ident, isConstant, local);
367             return local;
368         }
369         // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
370         bool addGlobalVar(const Identifier&, bool isConstant, RegisterID*&);
371
372         RegisterID* addParameter(const Identifier&);
373         
374         void allocateConstants(size_t);
375
376         RegisterID& registerFor(int index)
377         {
378             if (index >= 0)
379                 return m_calleeRegisters[index];
380
381             if (index == RegisterFile::OptionalCalleeArguments)
382                 return m_argumentsRegister;
383
384             if (m_parameters.size()) {
385                 ASSERT(!m_globals.size());
386                 return m_parameters[index + m_parameters.size() + RegisterFile::CallFrameHeaderSize];
387             }
388
389             return m_globals[-index - 1];
390         }
391
392         unsigned addConstant(FuncDeclNode*);
393         unsigned addConstant(FuncExprNode*);
394         unsigned addConstant(const Identifier&);
395         RegisterID* addConstant(JSValue*);
396         unsigned addUnexpectedConstant(JSValue*);
397         unsigned addRegExp(RegExp*);
398
399         Vector<Instruction>& instructions() { return m_codeBlock->instructions; }
400         SymbolTable& symbolTable() { return *m_symbolTable; }
401         Vector<HandlerInfo>& exceptionHandlers() { return m_codeBlock->exceptionHandlers; }
402
403         bool shouldOptimizeLocals() { return (m_codeType != EvalCode) && !m_dynamicScopeDepth; }
404         bool canOptimizeNonLocals() { return (m_codeType == FunctionCode) && !m_dynamicScopeDepth && !m_codeBlock->usesEval; }
405
406         RegisterID* emitThrowExpressionTooDeepException();
407
408         bool m_shouldEmitDebugHooks;
409         bool m_shouldEmitProfileHooks;
410
411         const ScopeChain* m_scopeChain;
412         SymbolTable* m_symbolTable;
413
414         ScopeNode* m_scopeNode;
415         CodeBlock* m_codeBlock;
416
417         HashSet<RefPtr<UString::Rep>, IdentifierRepHash> m_functions;
418         RegisterID m_thisRegister;
419         RegisterID m_argumentsRegister;
420         int m_activationRegisterIndex;
421         SegmentedVector<RegisterID, 512> m_calleeRegisters;
422         SegmentedVector<RegisterID, 512> m_parameters;
423         SegmentedVector<RegisterID, 512> m_globals;
424         SegmentedVector<LabelScope, 256> m_labelScopes;
425         SegmentedVector<Label, 256> m_labels;
426         RefPtr<RegisterID> m_lastConstant;
427         int m_finallyDepth;
428         int m_dynamicScopeDepth;
429         CodeType m_codeType;
430
431         Vector<ControlFlowContext> m_scopeContextStack;
432         Vector<SwitchInfo> m_switchContextStack;
433
434         int m_nextGlobalIndex;
435         int m_nextParameterIndex;
436         int m_nextConstantIndex;
437
438         int m_globalVarStorageOffset;
439
440         // Constant pool
441         IdentifierMap m_identifierMap;
442         JSValueMap m_jsValueMap;
443         NumberMap m_numberMap;
444         IdentifierStringMap m_stringMap;
445
446         JSGlobalData* m_globalData;
447
448         OpcodeID m_lastOpcodeID;
449
450 #ifndef NDEBUG
451         static bool s_dumpsGeneratedCode;
452 #endif
453
454         unsigned m_emitNodeDepth;
455
456         static const unsigned s_maxEmitNodeDepth = 10000;
457     };
458
459 }
460
461 #endif // BytecodeGenerator_h