2 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 Cameron Zwarich <cwzwarich@uwaterloo.ca>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
30 #ifndef BytecodeGenerator_h
31 #define BytecodeGenerator_h
33 #include "CodeBlock.h"
34 #include "HashTraits.h"
35 #include "Instruction.h"
37 #include "LabelScope.h"
38 #include "Interpreter.h"
39 #include "RegisterID.h"
40 #include "SymbolTable.h"
43 #include <wtf/FastAllocBase.h>
44 #include <wtf/PassRefPtr.h>
45 #include <wtf/SegmentedVector.h>
46 #include <wtf/Vector.h>
54 struct FinallyContext
{
56 RegisterID
* retAddrDst
;
59 struct ControlFlowContext
{
61 FinallyContext finallyContext
;
64 class BytecodeGenerator
: public WTF::FastAllocBase
{
66 typedef DeclarationStacks::VarStack VarStack
;
67 typedef DeclarationStacks::FunctionStack FunctionStack
;
69 static void setDumpsGeneratedCode(bool dumpsGeneratedCode
);
70 static bool dumpsGeneratedCode();
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
*);
76 JSGlobalData
* globalData() const { return m_globalData
; }
77 const CommonIdentifiers
& propertyNames() const { return *m_globalData
->propertyNames
; }
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
&);
86 bool willResolveToArguments(const Identifier
&);
87 RegisterID
* uncheckedRegisterForArguments();
89 // Behaves as registerFor does, but ignores dynamic scope as
90 // dynamic scope should not interfere with const initialisation
91 RegisterID
* constRegisterFor(const Identifier
&);
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
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
);
104 // Returns the register storing "this"
105 RegisterID
* thisRegister() { return &m_thisRegister
; }
107 bool isLocal(const Identifier
&);
108 bool isLocalConstant(const Identifier
&);
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();
116 RegisterID
* highestUsedRegister();
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(); }
124 // Functions for handling of dst register
126 RegisterID
* ignoredResult() { return &m_ignoredResultRegister
; }
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
)
132 return (dst
&& dst
!= ignoredResult() && dst
->isTemporary()) ? dst
: newTemporary();
135 // Returns the place to write the final output of an operation.
136 RegisterID
* finalDestination(RegisterID
* originalDst
, RegisterID
* tempDst
= 0)
138 if (originalDst
&& originalDst
!= ignoredResult())
140 ASSERT(tempDst
!= ignoredResult());
141 if (tempDst
&& tempDst
->isTemporary())
143 return newTemporary();
146 RegisterID
* destinationForAssignResult(RegisterID
* dst
)
148 if (dst
&& dst
!= ignoredResult() && m_codeBlock
->needsFullScopeChain())
149 return dst
->isTemporary() ? dst
: newTemporary();
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
)
156 return dst
== ignoredResult() ? 0 : (dst
&& dst
!= src
) ? emitMove(dst
, src
) : src
;
159 PassRefPtr
<LabelScope
> newLabelScope(LabelScope::Type
, const Identifier
* = 0);
160 PassRefPtr
<Label
> newLabel();
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
)
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
);
175 if (m_emitNodeDepth
>= s_maxEmitNodeDepth
)
176 return emitThrowExpressionTooDeepException();
178 RegisterID
* r
= n
->emitBytecode(*this, dst
);
183 RegisterID
* emitNode(Node
* n
)
185 return emitNode(0, n
);
188 void emitExpressionInfo(unsigned divot
, unsigned startOffset
, unsigned endOffset
)
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
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.
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.
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
);
217 void emitGetByIdExceptionInfo(OpcodeID opcodeID
)
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
);
228 ALWAYS_INLINE
bool leftHandSideNeedsCopy(bool rightHasAssignments
, bool rightIsPure
)
230 return (m_codeType
!= FunctionCode
|| m_codeBlock
->needsFullScopeChain() || rightHasAssignments
) && !rightIsPure
;
233 ALWAYS_INLINE PassRefPtr
<RegisterID
> emitNodeForLeftHandSide(ExpressionNode
* n
, bool rightHasAssignments
, bool rightIsPure
)
235 if (leftHandSideNeedsCopy(rightHasAssignments
, rightIsPure
)) {
236 PassRefPtr
<RegisterID
> dst
= newTemporary();
237 emitNode(dst
.get(), n
);
241 return PassRefPtr
<RegisterID
>(emitNode(n
));
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 RegisterID
* emitUnexpectedLoad(RegisterID
* dst
, bool);
249 RegisterID
* emitUnexpectedLoad(RegisterID
* dst
, double);
250 RegisterID
* emitLoadGlobalObject(RegisterID
* dst
, JSObject
* globalObject
);
252 RegisterID
* emitUnaryOp(OpcodeID
, RegisterID
* dst
, RegisterID
* src
);
253 RegisterID
* emitBinaryOp(OpcodeID
, RegisterID
* dst
, RegisterID
* src1
, RegisterID
* src2
, OperandTypes
);
254 RegisterID
* emitEqualityOp(OpcodeID
, RegisterID
* dst
, RegisterID
* src1
, RegisterID
* src2
);
255 RegisterID
* emitUnaryNoDstOp(OpcodeID
, RegisterID
* src
);
257 RegisterID
* emitNewObject(RegisterID
* dst
);
258 RegisterID
* emitNewArray(RegisterID
* dst
, ElementNode
*); // stops at first elision
260 RegisterID
* emitNewFunction(RegisterID
* dst
, FuncDeclNode
* func
);
261 RegisterID
* emitNewFunctionExpression(RegisterID
* dst
, FuncExprNode
* func
);
262 RegisterID
* emitNewRegExp(RegisterID
* dst
, RegExp
* regExp
);
264 RegisterID
* emitMove(RegisterID
* dst
, RegisterID
* src
);
266 RegisterID
* emitToJSNumber(RegisterID
* dst
, RegisterID
* src
) { return emitUnaryOp(op_to_jsnumber
, dst
, src
); }
267 RegisterID
* emitPreInc(RegisterID
* srcDst
);
268 RegisterID
* emitPreDec(RegisterID
* srcDst
);
269 RegisterID
* emitPostInc(RegisterID
* dst
, RegisterID
* srcDst
);
270 RegisterID
* emitPostDec(RegisterID
* dst
, RegisterID
* srcDst
);
272 RegisterID
* emitInstanceOf(RegisterID
* dst
, RegisterID
* value
, RegisterID
* base
, RegisterID
* basePrototype
);
273 RegisterID
* emitTypeOf(RegisterID
* dst
, RegisterID
* src
) { return emitUnaryOp(op_typeof
, dst
, src
); }
274 RegisterID
* emitIn(RegisterID
* dst
, RegisterID
* property
, RegisterID
* base
) { return emitBinaryOp(op_in
, dst
, property
, base
, OperandTypes()); }
276 RegisterID
* emitResolve(RegisterID
* dst
, const Identifier
& property
);
277 RegisterID
* emitGetScopedVar(RegisterID
* dst
, size_t skip
, int index
, JSValue globalObject
);
278 RegisterID
* emitPutScopedVar(size_t skip
, int index
, RegisterID
* value
, JSValue globalObject
);
280 RegisterID
* emitResolveBase(RegisterID
* dst
, const Identifier
& property
);
281 RegisterID
* emitResolveWithBase(RegisterID
* baseDst
, RegisterID
* propDst
, const Identifier
& property
);
282 RegisterID
* emitResolveFunction(RegisterID
* baseDst
, RegisterID
* funcDst
, const Identifier
& property
);
284 void emitMethodCheck();
286 RegisterID
* emitGetById(RegisterID
* dst
, RegisterID
* base
, const Identifier
& property
);
287 RegisterID
* emitPutById(RegisterID
* base
, const Identifier
& property
, RegisterID
* value
);
288 RegisterID
* emitDeleteById(RegisterID
* dst
, RegisterID
* base
, const Identifier
&);
289 RegisterID
* emitGetByVal(RegisterID
* dst
, RegisterID
* base
, RegisterID
* property
);
290 RegisterID
* emitPutByVal(RegisterID
* base
, RegisterID
* property
, RegisterID
* value
);
291 RegisterID
* emitDeleteByVal(RegisterID
* dst
, RegisterID
* base
, RegisterID
* property
);
292 RegisterID
* emitPutByIndex(RegisterID
* base
, unsigned index
, RegisterID
* value
);
293 RegisterID
* emitPutGetter(RegisterID
* base
, const Identifier
& property
, RegisterID
* value
);
294 RegisterID
* emitPutSetter(RegisterID
* base
, const Identifier
& property
, RegisterID
* value
);
296 RegisterID
* emitCall(RegisterID
* dst
, RegisterID
* func
, RegisterID
* thisRegister
, ArgumentsNode
*, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
297 RegisterID
* emitCallEval(RegisterID
* dst
, RegisterID
* func
, RegisterID
* thisRegister
, ArgumentsNode
*, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
298 RegisterID
* emitCallVarargs(RegisterID
* dst
, RegisterID
* func
, RegisterID
* thisRegister
, RegisterID
* argCount
, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
299 RegisterID
* emitLoadVarargs(RegisterID
* argCountDst
, RegisterID
* args
);
301 RegisterID
* emitReturn(RegisterID
* src
);
302 RegisterID
* emitEnd(RegisterID
* src
) { return emitUnaryNoDstOp(op_end
, src
); }
304 RegisterID
* emitConstruct(RegisterID
* dst
, RegisterID
* func
, ArgumentsNode
*, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
305 RegisterID
* emitStrcat(RegisterID
* dst
, RegisterID
* src
, int count
);
306 void emitToPrimitive(RegisterID
* dst
, RegisterID
* src
);
308 PassRefPtr
<Label
> emitLabel(Label
*);
309 PassRefPtr
<Label
> emitJump(Label
* target
);
310 PassRefPtr
<Label
> emitJumpIfTrue(RegisterID
* cond
, Label
* target
);
311 PassRefPtr
<Label
> emitJumpIfFalse(RegisterID
* cond
, Label
* target
);
312 PassRefPtr
<Label
> emitJumpIfNotFunctionCall(RegisterID
* cond
, Label
* target
);
313 PassRefPtr
<Label
> emitJumpIfNotFunctionApply(RegisterID
* cond
, Label
* target
);
314 PassRefPtr
<Label
> emitJumpScopes(Label
* target
, int targetScopeDepth
);
316 PassRefPtr
<Label
> emitJumpSubroutine(RegisterID
* retAddrDst
, Label
*);
317 void emitSubroutineReturn(RegisterID
* retAddrSrc
);
319 RegisterID
* emitGetPropertyNames(RegisterID
* dst
, RegisterID
* base
) { return emitUnaryOp(op_get_pnames
, dst
, base
); }
320 RegisterID
* emitNextPropertyName(RegisterID
* dst
, RegisterID
* iter
, Label
* target
);
322 RegisterID
* emitCatch(RegisterID
*, Label
* start
, Label
* end
);
323 void emitThrow(RegisterID
* exc
) { emitUnaryNoDstOp(op_throw
, exc
); }
324 RegisterID
* emitNewError(RegisterID
* dst
, ErrorType type
, JSValue message
);
325 void emitPushNewScope(RegisterID
* dst
, Identifier
& property
, RegisterID
* value
);
327 RegisterID
* emitPushScope(RegisterID
* scope
);
330 void emitDebugHook(DebugHookID
, int firstLine
, int lastLine
);
332 int scopeDepth() { return m_dynamicScopeDepth
+ m_finallyDepth
; }
333 bool hasFinaliser() { return m_finallyDepth
!= 0; }
335 void pushFinallyContext(Label
* target
, RegisterID
* returnAddrDst
);
336 void popFinallyContext();
338 LabelScope
* breakTarget(const Identifier
&);
339 LabelScope
* continueTarget(const Identifier
&);
341 void beginSwitch(RegisterID
*, SwitchInfo::SwitchType
);
342 void endSwitch(uint32_t clauseCount
, RefPtr
<Label
>*, ExpressionNode
**, Label
* defaultLabel
, int32_t min
, int32_t range
);
344 CodeType
codeType() const { return m_codeType
; }
346 void setRegeneratingForExceptionInfo(CodeBlock
* originalCodeBlock
)
348 m_regeneratingForExceptionInfo
= true;
349 m_codeBlockBeingRegeneratedFrom
= originalCodeBlock
;
353 void emitOpcode(OpcodeID
);
354 void retrieveLastBinaryOp(int& dstIndex
, int& src1Index
, int& src2Index
);
355 void retrieveLastUnaryOp(int& dstIndex
, int& srcIndex
);
356 void rewindBinaryOp();
357 void rewindUnaryOp();
359 PassRefPtr
<Label
> emitComplexJumpScopes(Label
* target
, ControlFlowContext
* topScope
, ControlFlowContext
* bottomScope
);
361 typedef HashMap
<EncodedJSValue
, unsigned, PtrHash
<EncodedJSValue
>, JSValueHashTraits
> JSValueMap
;
363 struct IdentifierMapIndexHashTraits
{
364 typedef int TraitType
;
365 typedef IdentifierMapIndexHashTraits StorageTraits
;
366 static int emptyValue() { return std::numeric_limits
<int>::max(); }
367 static const bool emptyValueIsZero
= false;
368 static const bool needsDestruction
= false;
369 static const bool needsRef
= false;
372 typedef HashMap
<RefPtr
<UString::Rep
>, int, IdentifierRepHash
, HashTraits
<RefPtr
<UString::Rep
> >, IdentifierMapIndexHashTraits
> IdentifierMap
;
373 typedef HashMap
<double, JSValue
> NumberMap
;
374 typedef HashMap
<UString::Rep
*, JSString
*, IdentifierRepHash
> IdentifierStringMap
;
376 RegisterID
* emitCall(OpcodeID
, RegisterID
* dst
, RegisterID
* func
, RegisterID
* thisRegister
, ArgumentsNode
*, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
378 RegisterID
* newRegister();
380 // Returns the RegisterID corresponding to ident.
381 RegisterID
* addVar(const Identifier
& ident
, bool isConstant
)
384 addVar(ident
, isConstant
, local
);
387 // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
388 bool addVar(const Identifier
&, bool isConstant
, RegisterID
*&);
390 // Returns the RegisterID corresponding to ident.
391 RegisterID
* addGlobalVar(const Identifier
& ident
, bool isConstant
)
394 addGlobalVar(ident
, isConstant
, local
);
397 // Returns true if a new RegisterID was added, false if a pre-existing RegisterID was re-used.
398 bool addGlobalVar(const Identifier
&, bool isConstant
, RegisterID
*&);
400 RegisterID
* addParameter(const Identifier
&);
402 void allocateConstants(size_t);
404 RegisterID
& registerFor(int index
)
407 return m_calleeRegisters
[index
];
409 if (index
== RegisterFile::OptionalCalleeArguments
)
410 return m_argumentsRegister
;
412 if (m_parameters
.size()) {
413 ASSERT(!m_globals
.size());
414 return m_parameters
[index
+ m_parameters
.size() + RegisterFile::CallFrameHeaderSize
];
417 return m_globals
[-index
- 1];
420 unsigned addConstant(FuncDeclNode
*);
421 unsigned addConstant(FuncExprNode
*);
422 unsigned addConstant(const Identifier
&);
423 RegisterID
* addConstant(JSValue
);
424 unsigned addUnexpectedConstant(JSValue
);
425 unsigned addRegExp(RegExp
*);
427 Vector
<Instruction
>& instructions() { return m_codeBlock
->instructions(); }
428 SymbolTable
& symbolTable() { return *m_symbolTable
; }
430 bool shouldOptimizeLocals() { return (m_codeType
!= EvalCode
) && !m_dynamicScopeDepth
; }
431 bool canOptimizeNonLocals() { return (m_codeType
== FunctionCode
) && !m_dynamicScopeDepth
&& !m_codeBlock
->usesEval(); }
433 RegisterID
* emitThrowExpressionTooDeepException();
435 void createArgumentsIfNecessary();
437 bool m_shouldEmitDebugHooks
;
438 bool m_shouldEmitProfileHooks
;
440 const ScopeChain
* m_scopeChain
;
441 SymbolTable
* m_symbolTable
;
443 ScopeNode
* m_scopeNode
;
444 CodeBlock
* m_codeBlock
;
446 // Some of these objects keep pointers to one another. They are arranged
447 // to ensure a sane destruction order that avoids references to freed memory.
448 HashSet
<RefPtr
<UString::Rep
>, IdentifierRepHash
> m_functions
;
449 RegisterID m_ignoredResultRegister
;
450 RegisterID m_thisRegister
;
451 RegisterID m_argumentsRegister
;
452 int m_activationRegisterIndex
;
453 WTF::SegmentedVector
<RegisterID
, 32> m_calleeRegisters
;
454 WTF::SegmentedVector
<RegisterID
, 32> m_parameters
;
455 WTF::SegmentedVector
<RegisterID
, 32> m_globals
;
456 WTF::SegmentedVector
<Label
, 32> m_labels
;
457 WTF::SegmentedVector
<LabelScope
, 8> m_labelScopes
;
458 RefPtr
<RegisterID
> m_lastConstant
;
460 int m_dynamicScopeDepth
;
461 int m_baseScopeDepth
;
464 Vector
<ControlFlowContext
> m_scopeContextStack
;
465 Vector
<SwitchInfo
> m_switchContextStack
;
467 int m_nextGlobalIndex
;
468 int m_nextParameterIndex
;
469 int m_nextConstantIndex
;
470 unsigned m_globalConstantIndex
;
472 int m_globalVarStorageOffset
;
475 IdentifierMap m_identifierMap
;
476 JSValueMap m_jsValueMap
;
477 NumberMap m_numberMap
;
478 IdentifierStringMap m_stringMap
;
480 JSGlobalData
* m_globalData
;
482 OpcodeID m_lastOpcodeID
;
484 unsigned m_emitNodeDepth
;
486 bool m_regeneratingForExceptionInfo
;
487 CodeBlock
* m_codeBlockBeingRegeneratedFrom
;
489 static const unsigned s_maxEmitNodeDepth
= 5000;
494 #endif // BytecodeGenerator_h