]> git.saurik.com Git - apple/javascriptcore.git/blob - bytecompiler/BytecodeGenerator.h
JavaScriptCore-554.1.tar.gz
[apple/javascriptcore.git] / bytecompiler / BytecodeGenerator.h
1 /*
2 * Copyright (C) 2008, 2009 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 "SymbolTable.h"
41 #include "Debugger.h"
42 #include "Nodes.h"
43 #include <wtf/FastAllocBase.h>
44 #include <wtf/PassRefPtr.h>
45 #include <wtf/SegmentedVector.h>
46 #include <wtf/Vector.h>
47
48 namespace JSC {
49
50 class Identifier;
51 class ScopeChain;
52 class ScopeNode;
53
54 struct FinallyContext {
55 Label* finallyAddr;
56 RegisterID* retAddrDst;
57 };
58
59 struct ControlFlowContext {
60 bool isFinallyBlock;
61 FinallyContext finallyContext;
62 };
63
64 class BytecodeGenerator : public WTF::FastAllocBase {
65 public:
66 typedef DeclarationStacks::VarStack VarStack;
67 typedef DeclarationStacks::FunctionStack FunctionStack;
68
69 static void setDumpsGeneratedCode(bool dumpsGeneratedCode);
70 static bool dumpsGeneratedCode();
71
72 BytecodeGenerator(ProgramNode*, const Debugger*, const ScopeChain&, SymbolTable*, ProgramCodeBlock*);
73 BytecodeGenerator(FunctionBodyNode*, const Debugger*, const ScopeChain&, SymbolTable*, CodeBlock*);
74 BytecodeGenerator(EvalNode*, const Debugger*, const ScopeChain&, SymbolTable*, EvalCodeBlock*);
75
76 JSGlobalData* globalData() const { return m_globalData; }
77 const CommonIdentifiers& propertyNames() const { return *m_globalData->propertyNames; }
78
79 void generate();
80
81 // Returns the register corresponding to a local variable, or 0 if no
82 // such register exists. Registers returned by registerFor do not
83 // require explicit reference counting.
84 RegisterID* registerFor(const Identifier&);
85
86 bool willResolveToArguments(const Identifier&);
87 RegisterID* uncheckedRegisterForArguments();
88
89 // Behaves as registerFor does, but ignores dynamic scope as
90 // dynamic scope should not interfere with const initialisation
91 RegisterID* constRegisterFor(const Identifier&);
92
93 // Searches the scope chain in an attempt to statically locate the requested
94 // property. Returns false if for any reason the property cannot be safely
95 // optimised at all. Otherwise it will return the index and depth of the
96 // VariableObject that defines the property. If the property cannot be found
97 // statically, depth will contain the depth of the scope chain where dynamic
98 // lookup must begin.
99 //
100 // NB: depth does _not_ include the local scope. eg. a depth of 0 refers
101 // to the scope containing this codeblock.
102 bool findScopedProperty(const Identifier&, int& index, size_t& depth, bool forWriting, JSObject*& globalObject);
103
104 // Returns the register storing "this"
105 RegisterID* thisRegister() { return &m_thisRegister; }
106
107 bool isLocal(const Identifier&);
108 bool isLocalConstant(const Identifier&);
109
110 // Returns the next available temporary register. Registers returned by
111 // newTemporary require a modified form of reference counting: any
112 // register with a refcount of 0 is considered "available", meaning that
113 // the next instruction may overwrite it.
114 RegisterID* newTemporary();
115
116 RegisterID* highestUsedRegister();
117
118 // The same as newTemporary(), but this function returns "suggestion" if
119 // "suggestion" is a temporary. This function is helpful in situations
120 // where you've put "suggestion" in a RefPtr, but you'd like to allow
121 // the next instruction to overwrite it anyway.
122 RegisterID* newTemporaryOr(RegisterID* suggestion) { return suggestion->isTemporary() ? suggestion : newTemporary(); }
123
124 // Functions for handling of dst register
125
126 RegisterID* ignoredResult() { return &m_ignoredResultRegister; }
127
128 // Returns a place to write intermediate values of an operation
129 // which reuses dst if it is safe to do so.
130 RegisterID* tempDestination(RegisterID* dst)
131 {
132 return (dst && dst != ignoredResult() && dst->isTemporary()) ? dst : newTemporary();
133 }
134
135 // Returns the place to write the final output of an operation.
136 RegisterID* finalDestination(RegisterID* originalDst, RegisterID* tempDst = 0)
137 {
138 if (originalDst && originalDst != ignoredResult())
139 return originalDst;
140 ASSERT(tempDst != ignoredResult());
141 if (tempDst && tempDst->isTemporary())
142 return tempDst;
143 return newTemporary();
144 }
145
146 RegisterID* destinationForAssignResult(RegisterID* dst)
147 {
148 if (dst && dst != ignoredResult() && m_codeBlock->needsFullScopeChain())
149 return dst->isTemporary() ? dst : newTemporary();
150 return 0;
151 }
152
153 // Moves src to dst if dst is not null and is different from src, otherwise just returns src.
154 RegisterID* moveToDestinationIfNeeded(RegisterID* dst, RegisterID* src)
155 {
156 return dst == ignoredResult() ? 0 : (dst && dst != src) ? emitMove(dst, src) : src;
157 }
158
159 PassRefPtr<LabelScope> newLabelScope(LabelScope::Type, const Identifier* = 0);
160 PassRefPtr<Label> newLabel();
161
162 // The emitNode functions are just syntactic sugar for calling
163 // Node::emitCode. These functions accept a 0 for the register,
164 // meaning that the node should allocate a register, or ignoredResult(),
165 // meaning that the node need not put the result in a register.
166 // Other emit functions do not accept 0 or ignoredResult().
167 RegisterID* emitNode(RegisterID* dst, Node* n)
168 {
169 // Node::emitCode assumes that dst, if provided, is either a local or a referenced temporary.
170 ASSERT(!dst || dst == ignoredResult() || !dst->isTemporary() || dst->refCount());
171 if (!m_codeBlock->numberOfLineInfos() || m_codeBlock->lastLineInfo().lineNumber != n->lineNo()) {
172 LineInfo info = { instructions().size(), n->lineNo() };
173 m_codeBlock->addLineInfo(info);
174 }
175 if (m_emitNodeDepth >= s_maxEmitNodeDepth)
176 return emitThrowExpressionTooDeepException();
177 ++m_emitNodeDepth;
178 RegisterID* r = n->emitBytecode(*this, dst);
179 --m_emitNodeDepth;
180 return r;
181 }
182
183 RegisterID* emitNode(Node* n)
184 {
185 return emitNode(0, n);
186 }
187
188 void emitExpressionInfo(unsigned divot, unsigned startOffset, unsigned endOffset)
189 {
190 divot -= m_codeBlock->sourceOffset();
191 if (divot > ExpressionRangeInfo::MaxDivot) {
192 // Overflow has occurred, we can only give line number info for errors for this region
193 divot = 0;
194 startOffset = 0;
195 endOffset = 0;
196 } else if (startOffset > ExpressionRangeInfo::MaxOffset) {
197 // If the start offset is out of bounds we clear both offsets
198 // so we only get the divot marker. Error message will have to be reduced
199 // to line and column number.
200 startOffset = 0;
201 endOffset = 0;
202 } else if (endOffset > ExpressionRangeInfo::MaxOffset) {
203 // The end offset is only used for additional context, and is much more likely
204 // to overflow (eg. function call arguments) so we are willing to drop it without
205 // dropping the rest of the range.
206 endOffset = 0;
207 }
208
209 ExpressionRangeInfo info;
210 info.instructionOffset = instructions().size();
211 info.divotPoint = divot;
212 info.startOffset = startOffset;
213 info.endOffset = endOffset;
214 m_codeBlock->addExpressionInfo(info);
215 }
216
217 void emitGetByIdExceptionInfo(OpcodeID opcodeID)
218 {
219 // Only op_construct and op_instanceof need exception info for
220 // a preceding op_get_by_id.
221 ASSERT(opcodeID == op_construct || opcodeID == op_instanceof);
222 GetByIdExceptionInfo info;
223 info.bytecodeOffset = instructions().size();
224 info.isOpConstruct = (opcodeID == op_construct);
225 m_codeBlock->addGetByIdExceptionInfo(info);
226 }
227
228 ALWAYS_INLINE bool leftHandSideNeedsCopy(bool rightHasAssignments, bool rightIsPure)
229 {
230 return (m_codeType != FunctionCode || m_codeBlock->needsFullScopeChain() || rightHasAssignments) && !rightIsPure;
231 }
232
233 ALWAYS_INLINE PassRefPtr<RegisterID> emitNodeForLeftHandSide(ExpressionNode* n, bool rightHasAssignments, bool rightIsPure)
234 {
235 if (leftHandSideNeedsCopy(rightHasAssignments, rightIsPure)) {
236 PassRefPtr<RegisterID> dst = newTemporary();
237 emitNode(dst.get(), n);
238 return dst;
239 }
240
241 return PassRefPtr<RegisterID>(emitNode(n));
242 }
243
244 RegisterID* emitLoad(RegisterID* dst, bool);
245 RegisterID* emitLoad(RegisterID* dst, double);
246 RegisterID* emitLoad(RegisterID* dst, const Identifier&);
247 RegisterID* emitLoad(RegisterID* dst, JSValue);
248
249 RegisterID* emitUnaryOp(OpcodeID, RegisterID* dst, RegisterID* src);
250 RegisterID* emitBinaryOp(OpcodeID, RegisterID* dst, RegisterID* src1, RegisterID* src2, OperandTypes);
251 RegisterID* emitEqualityOp(OpcodeID, RegisterID* dst, RegisterID* src1, RegisterID* src2);
252 RegisterID* emitUnaryNoDstOp(OpcodeID, RegisterID* src);
253
254 RegisterID* emitNewObject(RegisterID* dst);
255 RegisterID* emitNewArray(RegisterID* dst, ElementNode*); // stops at first elision
256
257 RegisterID* emitNewFunction(RegisterID* dst, FuncDeclNode* func);
258 RegisterID* emitNewFunctionExpression(RegisterID* dst, FuncExprNode* func);
259 RegisterID* emitNewRegExp(RegisterID* dst, RegExp* regExp);
260
261 RegisterID* emitMove(RegisterID* dst, RegisterID* src);
262
263 RegisterID* emitToJSNumber(RegisterID* dst, RegisterID* src) { return emitUnaryOp(op_to_jsnumber, dst, src); }
264 RegisterID* emitPreInc(RegisterID* srcDst);
265 RegisterID* emitPreDec(RegisterID* srcDst);
266 RegisterID* emitPostInc(RegisterID* dst, RegisterID* srcDst);
267 RegisterID* emitPostDec(RegisterID* dst, RegisterID* srcDst);
268
269 RegisterID* emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base, RegisterID* basePrototype);
270 RegisterID* emitTypeOf(RegisterID* dst, RegisterID* src) { return emitUnaryOp(op_typeof, dst, src); }
271 RegisterID* emitIn(RegisterID* dst, RegisterID* property, RegisterID* base) { return emitBinaryOp(op_in, dst, property, base, OperandTypes()); }
272
273 RegisterID* emitResolve(RegisterID* dst, const Identifier& property);
274 RegisterID* emitGetScopedVar(RegisterID* dst, size_t skip, int index, JSValue globalObject);
275 RegisterID* emitPutScopedVar(size_t skip, int index, RegisterID* value, JSValue globalObject);
276
277 RegisterID* emitResolveBase(RegisterID* dst, const Identifier& property);
278 RegisterID* emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property);
279
280 void emitMethodCheck();
281
282 RegisterID* emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property);
283 RegisterID* emitPutById(RegisterID* base, const Identifier& property, RegisterID* value);
284 RegisterID* emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier&);
285 RegisterID* emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
286 RegisterID* emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value);
287 RegisterID* emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property);
288 RegisterID* emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value);
289 RegisterID* emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value);
290 RegisterID* emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value);
291
292 RegisterID* emitCall(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
293 RegisterID* emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
294 RegisterID* emitCallVarargs(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, RegisterID* argCount, unsigned divot, unsigned startOffset, unsigned endOffset);
295 RegisterID* emitLoadVarargs(RegisterID* argCountDst, RegisterID* args);
296
297 RegisterID* emitReturn(RegisterID* src);
298 RegisterID* emitEnd(RegisterID* src) { return emitUnaryNoDstOp(op_end, src); }
299
300 RegisterID* emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
301 RegisterID* emitStrcat(RegisterID* dst, RegisterID* src, int count);
302 void emitToPrimitive(RegisterID* dst, RegisterID* src);
303
304 PassRefPtr<Label> emitLabel(Label*);
305 PassRefPtr<Label> emitJump(Label* target);
306 PassRefPtr<Label> emitJumpIfTrue(RegisterID* cond, Label* target);
307 PassRefPtr<Label> emitJumpIfFalse(RegisterID* cond, Label* target);
308 PassRefPtr<Label> emitJumpIfNotFunctionCall(RegisterID* cond, Label* target);
309 PassRefPtr<Label> emitJumpIfNotFunctionApply(RegisterID* cond, Label* target);
310 PassRefPtr<Label> emitJumpScopes(Label* target, int targetScopeDepth);
311
312 PassRefPtr<Label> emitJumpSubroutine(RegisterID* retAddrDst, Label*);
313 void emitSubroutineReturn(RegisterID* retAddrSrc);
314
315 RegisterID* emitGetPropertyNames(RegisterID* dst, RegisterID* base) { return emitUnaryOp(op_get_pnames, dst, base); }
316 RegisterID* emitNextPropertyName(RegisterID* dst, RegisterID* iter, Label* target);
317
318 RegisterID* emitCatch(RegisterID*, Label* start, Label* end);
319 void emitThrow(RegisterID* exc) { emitUnaryNoDstOp(op_throw, exc); }
320 RegisterID* emitNewError(RegisterID* dst, ErrorType type, JSValue message);
321 void emitPushNewScope(RegisterID* dst, Identifier& property, RegisterID* value);
322
323 RegisterID* emitPushScope(RegisterID* scope);
324 void emitPopScope();
325
326 void emitDebugHook(DebugHookID, int firstLine, int lastLine);
327
328 int scopeDepth() { return m_dynamicScopeDepth + m_finallyDepth; }
329 bool hasFinaliser() { return m_finallyDepth != 0; }
330
331 void pushFinallyContext(Label* target, RegisterID* returnAddrDst);
332 void popFinallyContext();
333
334 LabelScope* breakTarget(const Identifier&);
335 LabelScope* continueTarget(const Identifier&);
336
337 void beginSwitch(RegisterID*, SwitchInfo::SwitchType);
338 void endSwitch(uint32_t clauseCount, RefPtr<Label>*, ExpressionNode**, Label* defaultLabel, int32_t min, int32_t range);
339
340 CodeType codeType() const { return m_codeType; }
341
342 void setRegeneratingForExceptionInfo(CodeBlock* originalCodeBlock)
343 {
344 m_regeneratingForExceptionInfo = true;
345 m_codeBlockBeingRegeneratedFrom = originalCodeBlock;
346 }
347
348 private:
349 void emitOpcode(OpcodeID);
350 void retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index);
351 void retrieveLastUnaryOp(int& dstIndex, int& srcIndex);
352 void rewindBinaryOp();
353 void rewindUnaryOp();
354
355 PassRefPtr<Label> emitComplexJumpScopes(Label* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope);
356
357 typedef HashMap<EncodedJSValue, unsigned, EncodedJSValueHash, EncodedJSValueHashTraits> JSValueMap;
358
359 struct IdentifierMapIndexHashTraits {
360 typedef int TraitType;
361 typedef IdentifierMapIndexHashTraits StorageTraits;
362 static int emptyValue() { return std::numeric_limits<int>::max(); }
363 static const bool emptyValueIsZero = false;
364 static const bool needsDestruction = false;
365 static const bool needsRef = false;
366 };
367
368 typedef HashMap<RefPtr<UString::Rep>, int, IdentifierRepHash, HashTraits<RefPtr<UString::Rep> >, IdentifierMapIndexHashTraits> IdentifierMap;
369 typedef HashMap<double, JSValue> NumberMap;
370 typedef HashMap<UString::Rep*, JSString*, IdentifierRepHash> IdentifierStringMap;
371
372 RegisterID* emitCall(OpcodeID, RegisterID* dst, RegisterID* func, RegisterID* thisRegister, ArgumentsNode*, unsigned divot, unsigned startOffset, unsigned endOffset);
373
374 RegisterID* newRegister();
375
376 // Returns the RegisterID corresponding to ident.
377 RegisterID* addVar(const Identifier& ident, bool isConstant)
378 {
379 RegisterID* local;
380 addVar(ident, isConstant, local);
381 return local;
382 }
383 // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
384 bool addVar(const Identifier&, bool isConstant, RegisterID*&);
385
386 // Returns the RegisterID corresponding to ident.
387 RegisterID* addGlobalVar(const Identifier& ident, bool isConstant)
388 {
389 RegisterID* local;
390 addGlobalVar(ident, isConstant, local);
391 return local;
392 }
393 // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
394 bool addGlobalVar(const Identifier&, bool isConstant, RegisterID*&);
395
396 RegisterID* addParameter(const Identifier&);
397
398 void preserveLastVar();
399
400 RegisterID& registerFor(int index)
401 {
402 if (index >= 0)
403 return m_calleeRegisters[index];
404
405 if (index == RegisterFile::OptionalCalleeArguments)
406 return m_argumentsRegister;
407
408 if (m_parameters.size()) {
409 ASSERT(!m_globals.size());
410 return m_parameters[index + m_parameters.size() + RegisterFile::CallFrameHeaderSize];
411 }
412
413 return m_globals[-index - 1];
414 }
415
416 unsigned addConstant(FuncDeclNode*);
417 unsigned addConstant(FuncExprNode*);
418 unsigned addConstant(const Identifier&);
419 RegisterID* addConstantValue(JSValue);
420 unsigned addRegExp(RegExp*);
421
422 Vector<Instruction>& instructions() { return m_codeBlock->instructions(); }
423 SymbolTable& symbolTable() { return *m_symbolTable; }
424
425 bool shouldOptimizeLocals() { return (m_codeType != EvalCode) && !m_dynamicScopeDepth; }
426 bool canOptimizeNonLocals() { return (m_codeType == FunctionCode) && !m_dynamicScopeDepth && !m_codeBlock->usesEval(); }
427
428 RegisterID* emitThrowExpressionTooDeepException();
429
430 void createArgumentsIfNecessary();
431
432 bool m_shouldEmitDebugHooks;
433 bool m_shouldEmitProfileHooks;
434
435 const ScopeChain* m_scopeChain;
436 SymbolTable* m_symbolTable;
437
438 ScopeNode* m_scopeNode;
439 CodeBlock* m_codeBlock;
440
441 // Some of these objects keep pointers to one another. They are arranged
442 // to ensure a sane destruction order that avoids references to freed memory.
443 HashSet<RefPtr<UString::Rep>, IdentifierRepHash> m_functions;
444 RegisterID m_ignoredResultRegister;
445 RegisterID m_thisRegister;
446 RegisterID m_argumentsRegister;
447 int m_activationRegisterIndex;
448 WTF::SegmentedVector<RegisterID, 32> m_constantPoolRegisters;
449 WTF::SegmentedVector<RegisterID, 32> m_calleeRegisters;
450 WTF::SegmentedVector<RegisterID, 32> m_parameters;
451 WTF::SegmentedVector<RegisterID, 32> m_globals;
452 WTF::SegmentedVector<Label, 32> m_labels;
453 WTF::SegmentedVector<LabelScope, 8> m_labelScopes;
454 RefPtr<RegisterID> m_lastVar;
455 int m_finallyDepth;
456 int m_dynamicScopeDepth;
457 int m_baseScopeDepth;
458 CodeType m_codeType;
459
460 Vector<ControlFlowContext> m_scopeContextStack;
461 Vector<SwitchInfo> m_switchContextStack;
462
463 int m_nextGlobalIndex;
464 int m_nextParameterIndex;
465 int m_firstConstantIndex;
466 int m_nextConstantOffset;
467 unsigned m_globalConstantIndex;
468
469 int m_globalVarStorageOffset;
470
471 // Constant pool
472 IdentifierMap m_identifierMap;
473 JSValueMap m_jsValueMap;
474 NumberMap m_numberMap;
475 IdentifierStringMap m_stringMap;
476
477 JSGlobalData* m_globalData;
478
479 OpcodeID m_lastOpcodeID;
480
481 unsigned m_emitNodeDepth;
482
483 bool m_regeneratingForExceptionInfo;
484 CodeBlock* m_codeBlockBeingRegeneratedFrom;
485
486 static const unsigned s_maxEmitNodeDepth = 5000;
487 };
488
489 }
490
491 #endif // BytecodeGenerator_h