ac61d3c88460cfce2188c9b2b76c645bfa0f858f
[WebKit-https.git] / JavaScriptCore / VM / CodeGenerator.h
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  * Copyright (C) 2008 Apple Inc. All rights reserved.
4  * Copyright (C) 2008 Cameron Zwarich <cwzwarich@uwaterloo.ca>
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1.  Redistributions of source code must retain the above copyright
11  *     notice, this list of conditions and the following disclaimer.
12  * 2.  Redistributions in binary form must reproduce the above copyright
13  *     notice, this list of conditions and the following disclaimer in the
14  *     documentation and/or other materials provided with the distribution.
15  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
16  *     its contributors may be used to endorse or promote products derived
17  *     from this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
20  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
23  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31 #ifndef CodeGenerator_h
32 #define CodeGenerator_h
33
34 #include "CodeBlock.h"
35 #include "HashTraits.h"
36 #include "Instruction.h"
37 #include "LabelID.h"
38 #include "Machine.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 KJS {
48
49     class Identifier;
50     class ScopeChain;
51     class ScopeNode;
52
53     // JumpContexts are used to track entry and exit points for javascript loops and switch statements
54     struct JumpContext {
55         LabelStack* labels;
56         LabelID* continueTarget;
57         LabelID* breakTarget;
58         int scopeDepth;
59         bool isValidUnlabeledBreakTarget;
60     };
61
62     struct FinallyContext {
63         LabelID* finallyAddr;
64         RegisterID* retAddrDst;
65     };
66
67     struct ControlFlowContext {
68         bool isFinallyBlock;
69         FinallyContext finallyContext;
70     };
71
72     class CodeGenerator {
73     public:
74         typedef DeclarationStacks::VarStack VarStack;
75         typedef DeclarationStacks::FunctionStack FunctionStack;
76
77         static void setDumpsGeneratedCode(bool dumpsGeneratedCode);
78
79         CodeGenerator(ProgramNode*, const Debugger*, const ScopeChain&, SymbolTable*, CodeBlock*, VarStack&, FunctionStack&, bool canCreateGlobals);
80         CodeGenerator(FunctionBodyNode*, const Debugger*, const ScopeChain&, SymbolTable*, CodeBlock*);
81         CodeGenerator(EvalNode*, const Debugger*, const ScopeChain&, SymbolTable*, EvalCodeBlock*);
82
83         ~CodeGenerator();
84
85         const CommonIdentifiers& propertyNames() const { return *m_propertyNames; }
86
87         void generate();
88
89         // Returns the register corresponding to a local variable, or 0 if no
90         // such register exists. Registers returned by registerForLocal do not
91         // require explicit reference counting.
92         RegisterID* registerForLocal(const Identifier&);
93         // Behaves as registerForLocal does, but ignores dynamic scope as
94         // dynamic scope should not interfere with const initialisation
95         RegisterID* registerForLocalConstInit(const Identifier&);
96
97         // Searches the scope chain in an attempt to  statically locate the requested
98         // property.  Returns false if for any reason the property cannot be safely
99         // optimised at all.  Otherwise it will return the index and depth of the
100         // VariableObject that defines the property.  If the property cannot be found
101         // statically, depth will contain the depth of the scope chain where dynamic
102         // lookup must begin.
103         //
104         // NB: depth does _not_ include the local scope.  eg. a depth of 0 refers
105         // to the scope containing this codeblock.
106         bool findScopedProperty(const Identifier&, int& index, size_t& depth);
107
108         // Returns the register storing "this"
109         RegisterID* thisRegister() { return &m_thisRegister; }
110
111         bool isLocalConstant(const Identifier&);
112
113         // Returns the next available temporary register. Registers returned by
114         // newTemporary require a modified form of reference counting: any
115         // register with a refcount of 0 is considered "available", meaning that
116         // the next instruction may overwrite it.
117         RegisterID* newTemporary();
118
119         RegisterID* highestUsedRegister();
120
121         // The same as newTemporary(), but this function returns "suggestion" if
122         // "suggestion" is a temporary. This function is helpful in situations
123         // where you've put "suggestion" in a RefPtr, but you'd like to allow
124         // the next instruction to overwrite it anyway.
125         RegisterID* newTemporaryOr(RegisterID* suggestion) { return suggestion->isTemporary() ? suggestion : newTemporary(); }
126
127         // Functions for handling of dst register
128
129         // Returns  a place to write intermediate values of an operation
130         // which reuses dst if it is safe to do so.
131
132         RegisterID* tempDestination(RegisterID* dst) { return (dst && dst->isTemporary()) ? dst : newTemporary(); }
133
134         // Returns the place to write the final output of an operation.
135         RegisterID* finalDestination(RegisterID* originalDst, RegisterID* tempDst = 0)
136         {
137             if (originalDst)
138                 return originalDst;
139             if (tempDst && tempDst->isTemporary())
140                 return tempDst;
141             return newTemporary();
142         }
143
144         RegisterID* destinationForAssignResult(RegisterID* dst)
145         {
146             if (dst && m_codeBlock->needsFullScopeChain)
147                 return dst->isTemporary() ? dst : newTemporary();
148             return 0;
149         }
150
151         // moves src to dst if dst is not null and is different from src, otherwise just returns src
152         RegisterID* moveToDestinationIfNeeded(RegisterID* dst, RegisterID* src) { return (dst && dst != src) ? emitMove(dst, src) : src; }
153
154         PassRefPtr<LabelID> newLabel();
155
156         // The emitNode functions are just syntactic sugar for calling
157         // Node::emitCode. They're the only functions that accept a NULL register.
158         RegisterID* emitNode(RegisterID* dst, Node* n)
159         {
160             // Node::emitCode assumes that dst, if provided, is either a local or a referenced temporary.
161             ASSERT(!dst || !dst->isTemporary() || dst->refCount());
162             if (!m_codeBlock->lineInfo.size() || m_codeBlock->lineInfo.last().lineNumber != n->lineNo()) {
163                 LineInfo info = { instructions().size(), n->lineNo() };
164                 m_codeBlock->lineInfo.append(info);
165             }
166             return n->emitCode(*this, dst);
167         }
168
169         RegisterID* emitNode(Node* n)
170         {
171             return emitNode(0, n);
172         }
173
174         ALWAYS_INLINE bool leftHandSideNeedsCopy(bool rightHasAssignments, bool rightIsConstant)
175         {
176             return (m_codeType != FunctionCode || m_codeBlock->needsFullScopeChain || rightHasAssignments) && !rightIsConstant;
177         }
178
179         ALWAYS_INLINE PassRefPtr<RegisterID> emitNodeForLeftHandSide(ExpressionNode* n, bool rightHasAssignments, bool rightIsConstant)
180         {
181             if (leftHandSideNeedsCopy(rightHasAssignments, rightIsConstant)) {
182                 PassRefPtr<RegisterID> dst = newTemporary();
183                 emitNode(dst.get(), n);
184                 return dst;
185             }
186
187             return PassRefPtr<RegisterID>(emitNode(n));
188         }
189
190         RegisterID* emitLoad(RegisterID* dst, bool);
191         RegisterID* emitLoad(RegisterID* dst, double);
192         RegisterID* emitLoad(RegisterID* dst, JSValue*);
193
194         RegisterID* emitNewObject(RegisterID* dst);
195         RegisterID* emitNewArray(RegisterID* dst);
196
197         RegisterID* emitNewFunction(RegisterID* dst, FuncDeclNode* func);
198         RegisterID* emitNewFunctionExpression(RegisterID* dst, FuncExprNode* func);
199         RegisterID* emitNewRegExp(RegisterID* dst, RegExp* regExp);
200
201         RegisterID* emitMove(RegisterID* dst, RegisterID* src);
202
203         RegisterID* emitNot(RegisterID* dst, RegisterID* src);
204         RegisterID* emitEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2);
205         RegisterID* emitNotEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2);
206         RegisterID* emitStrictEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2);
207         RegisterID* emitNotStrictEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2);
208         RegisterID* emitLess(RegisterID* dst, RegisterID* src1, RegisterID* src2);
209         RegisterID* emitLessEq(RegisterID* dst, RegisterID* src1, RegisterID* src2);
210
211         RegisterID* emitToJSNumber(RegisterID* dst, RegisterID* src);
212         RegisterID* emitNegate(RegisterID* dst, RegisterID* src);
213         RegisterID* emitPreInc(RegisterID* srcDst);
214         RegisterID* emitPreDec(RegisterID* srcDst);
215         RegisterID* emitPostInc(RegisterID* dst, RegisterID* srcDst);
216         RegisterID* emitPostDec(RegisterID* dst, RegisterID* srcDst);
217         RegisterID* emitAdd(RegisterID* dst, RegisterID* src1, RegisterID* src2);
218         RegisterID* emitMul(RegisterID* dst, RegisterID* src1, RegisterID* src2);
219         RegisterID* emitDiv(RegisterID* dst, RegisterID* dividend, RegisterID* divisor);
220         RegisterID* emitMod(RegisterID* dst, RegisterID* dividend, RegisterID* divisor);
221         RegisterID* emitSub(RegisterID* dst, RegisterID* src1, RegisterID* src2);
222
223         RegisterID* emitLeftShift(RegisterID* dst, RegisterID* val, RegisterID* shift);
224         RegisterID* emitRightShift(RegisterID* dst, RegisterID* val, RegisterID* shift);
225         RegisterID* emitUnsignedRightShift(RegisterID* dst, RegisterID* val, RegisterID* shift);
226
227         RegisterID* emitBitAnd(RegisterID* dst, RegisterID* src1, RegisterID* src2);
228         RegisterID* emitBitXOr(RegisterID* dst, RegisterID* src1, RegisterID* src2);
229         RegisterID* emitBitOr(RegisterID* dst, RegisterID* src1, RegisterID* src2);
230         RegisterID* emitBitNot(RegisterID* dst, RegisterID* src);
231
232         RegisterID* emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base);
233         RegisterID* emitTypeOf(RegisterID* dst, RegisterID* src);
234         RegisterID* emitIn(RegisterID* dst, RegisterID* property, RegisterID* base);
235
236         RegisterID* emitResolve(RegisterID* dst, const Identifier& property);
237         RegisterID* emitGetScopedVar(RegisterID* dst, size_t skip, int index);
238         RegisterID* emitPutScopedVar(size_t skip, int index, RegisterID* value);
239
240         RegisterID* emitResolveBase(RegisterID* dst, const Identifier& property);
241         RegisterID* emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property);
242         RegisterID* emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property);
243
244         RegisterID* emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property);
245         RegisterID* emitPutById(RegisterID* base, const Identifier& property, RegisterID* value);
246         RegisterID* emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier&);
247         RegisterID* emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
248         RegisterID* emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value);
249         RegisterID* emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
250         RegisterID* emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value);
251         RegisterID* emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value);
252         RegisterID* emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value);
253
254         RegisterID* emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode*);
255         RegisterID* emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode*);
256         RegisterID* emitReturn(RegisterID*);
257         RegisterID* emitEnd(RegisterID* dst);
258
259         RegisterID* emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode*);
260
261         PassRefPtr<LabelID> emitLabel(LabelID*);
262         PassRefPtr<LabelID> emitJump(LabelID* target);
263         PassRefPtr<LabelID> emitJumpIfTrueMayCombine(RegisterID* cond, LabelID* target);
264         PassRefPtr<LabelID> emitJumpIfTrue(RegisterID* cond, LabelID* target);
265         PassRefPtr<LabelID> emitJumpIfFalse(RegisterID* cond, LabelID* target);
266         PassRefPtr<LabelID> emitJumpScopes(LabelID* target, int targetScopeDepth);
267
268         PassRefPtr<LabelID> emitJumpSubroutine(RegisterID* retAddrDst, LabelID*);
269         void emitSubroutineReturn(RegisterID* retAddrSrc);
270
271         RegisterID* emitGetPropertyNames(RegisterID* dst, RegisterID* base);
272         RegisterID* emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target);
273
274         RegisterID* emitCatch(RegisterID*, LabelID* start, LabelID* end);
275         void emitThrow(RegisterID*);
276         RegisterID* emitNewError(RegisterID* dst, ErrorType type, JSValue* message);
277
278         RegisterID* emitPushScope(RegisterID* scope);
279         void emitPopScope();
280
281         void emitDebugHook(DebugHookID, int firstLine, int lastLine);
282
283         int scopeDepth() { return m_dynamicScopeDepth + m_finallyDepth; }
284
285         void pushFinallyContext(LabelID* target, RegisterID* returnAddrDst);
286         void popFinallyContext();
287         bool inContinueContext() { return m_continueDepth > 0; };
288         bool inJumpContext() { return m_jumpContextStack.size() > 0; };
289         void pushJumpContext(LabelStack*, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget);
290         void popJumpContext();
291         JumpContext* jumpContextForContinue(const Identifier&);
292         JumpContext* jumpContextForBreak(const Identifier&);
293
294         CodeType codeType() const { return m_codeType; }
295
296     private:
297         void emitOpcode(OpcodeID);
298         void retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index);
299         void rewindBinaryOp();
300
301         PassRefPtr<LabelID> emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope);
302         struct JSValueHashTraits : HashTraits<JSValue*> {
303             static void constructDeletedValue(JSValue** slot) { *slot = JSImmediate::impossibleValue(); }
304             static bool isDeletedValue(JSValue* value) { return value == JSImmediate::impossibleValue(); }
305         };
306
307         typedef HashMap<JSValue*, unsigned, DefaultHash<JSValue*>::Hash, JSValueHashTraits> JSValueMap;
308
309         struct IdentifierMapIndexHashTraits {
310             typedef int TraitType;
311             typedef IdentifierMapIndexHashTraits StorageTraits;
312             static int emptyValue() { return std::numeric_limits<int>::max(); }
313             static const bool emptyValueIsZero = false;
314             static const bool needsDestruction = false;
315             static const bool needsRef = false;
316         };
317
318         typedef HashMap<RefPtr<UString::Rep>, int, IdentifierRepHash, HashTraits<RefPtr<UString::Rep> >, IdentifierMapIndexHashTraits> IdentifierMap;
319
320         RegisterID* emitCall(OpcodeID, RegisterID*, RegisterID*, RegisterID*, ArgumentsNode*);
321
322         // Maps a register index in the symbol table to a RegisterID index in m_locals.
323         int localsIndex(int registerIndex) { return -registerIndex - 1; }
324
325         // Returns the RegisterID corresponding to ident.
326         RegisterID* addVar(const Identifier& ident, bool isConstant)
327         {
328             RegisterID* local;
329             addVar(ident, local, isConstant);
330             return local;
331         }
332
333         // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
334         bool addVar(const Identifier&, RegisterID*&, bool isConstant);
335
336         RegisterID* addParameter(const Identifier&);
337
338         unsigned addConstant(FuncDeclNode*);
339         unsigned addConstant(FuncExprNode*);
340         unsigned addConstant(const Identifier&);
341         unsigned addConstant(JSValue*);
342         unsigned addRegExp(RegExp* r);
343
344         Vector<Instruction>& instructions() { return m_codeBlock->instructions; }
345         SymbolTable& symbolTable() { return *m_symbolTable; }
346         Vector<HandlerInfo>& exceptionHandlers() { return m_codeBlock->exceptionHandlers; }
347
348         bool shouldOptimizeLocals() { return (m_codeType != EvalCode) && !m_dynamicScopeDepth; }
349         bool canOptimizeNonLocals() { return (m_codeType == FunctionCode) && !m_dynamicScopeDepth && !m_codeBlock->usesEval; }
350
351         bool m_shouldEmitDebugHooks;
352
353         const ScopeChain* m_scopeChain;
354         SymbolTable* m_symbolTable;
355
356         ScopeNode* m_scopeNode;
357         CodeBlock* m_codeBlock;
358
359         HashSet<RefPtr<UString::Rep>, IdentifierRepHash> m_functions;
360         RegisterID m_thisRegister;
361         SegmentedVector<RegisterID, 512> m_locals;
362         SegmentedVector<RegisterID, 512> m_temporaries;
363         SegmentedVector<LabelID, 512> m_labels;
364         int m_finallyDepth;
365         int m_dynamicScopeDepth;
366         CodeType m_codeType;
367
368         Vector<JumpContext> m_jumpContextStack;
369         int m_continueDepth;
370         Vector<ControlFlowContext> m_scopeContextStack;
371
372         int m_nextVar;
373         int m_nextParameter;
374
375         // Constant pool
376         IdentifierMap m_identifierMap;
377         JSValueMap m_jsValueMap;
378
379         const CommonIdentifiers* m_propertyNames;
380
381         OpcodeID m_lastOpcodeID;
382
383 #ifndef NDEBUG
384         static bool s_dumpsGeneratedCode;
385 #endif
386     };
387
388 }
389
390 #endif // CodeGenerator_h