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
);
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
);
254 RegisterID
* emitNewObject(RegisterID
* dst
);
255 RegisterID
* emitNewArray(RegisterID
* dst
, ElementNode
*); // stops at first elision
257 RegisterID
* emitNewFunction(RegisterID
* dst
, FuncDeclNode
* func
);
258 RegisterID
* emitNewFunctionExpression(RegisterID
* dst
, FuncExprNode
* func
);
259 RegisterID
* emitNewRegExp(RegisterID
* dst
, RegExp
* regExp
);
261 RegisterID
* emitMove(RegisterID
* dst
, RegisterID
* src
);
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
);
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()); }
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
);
277 RegisterID
* emitResolveBase(RegisterID
* dst
, const Identifier
& property
);
278 RegisterID
* emitResolveWithBase(RegisterID
* baseDst
, RegisterID
* propDst
, const Identifier
& property
);
280 void emitMethodCheck();
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
);
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
);
297 RegisterID
* emitReturn(RegisterID
* src
);
298 RegisterID
* emitEnd(RegisterID
* src
) { return emitUnaryNoDstOp(op_end
, src
); }
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
);
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
);
312 PassRefPtr
<Label
> emitJumpSubroutine(RegisterID
* retAddrDst
, Label
*);
313 void emitSubroutineReturn(RegisterID
* retAddrSrc
);
315 RegisterID
* emitGetPropertyNames(RegisterID
* dst
, RegisterID
* base
) { return emitUnaryOp(op_get_pnames
, dst
, base
); }
316 RegisterID
* emitNextPropertyName(RegisterID
* dst
, RegisterID
* iter
, Label
* target
);
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
);
323 RegisterID
* emitPushScope(RegisterID
* scope
);
326 void emitDebugHook(DebugHookID
, int firstLine
, int lastLine
);
328 int scopeDepth() { return m_dynamicScopeDepth
+ m_finallyDepth
; }
329 bool hasFinaliser() { return m_finallyDepth
!= 0; }
331 void pushFinallyContext(Label
* target
, RegisterID
* returnAddrDst
);
332 void popFinallyContext();
334 LabelScope
* breakTarget(const Identifier
&);
335 LabelScope
* continueTarget(const Identifier
&);
337 void beginSwitch(RegisterID
*, SwitchInfo::SwitchType
);
338 void endSwitch(uint32_t clauseCount
, RefPtr
<Label
>*, ExpressionNode
**, Label
* defaultLabel
, int32_t min
, int32_t range
);
340 CodeType
codeType() const { return m_codeType
; }
342 void setRegeneratingForExceptionInfo(CodeBlock
* originalCodeBlock
)
344 m_regeneratingForExceptionInfo
= true;
345 m_codeBlockBeingRegeneratedFrom
= originalCodeBlock
;
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();
355 PassRefPtr
<Label
> emitComplexJumpScopes(Label
* target
, ControlFlowContext
* topScope
, ControlFlowContext
* bottomScope
);
357 typedef HashMap
<EncodedJSValue
, unsigned, EncodedJSValueHash
, EncodedJSValueHashTraits
> JSValueMap
;
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;
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
;
372 RegisterID
* emitCall(OpcodeID
, RegisterID
* dst
, RegisterID
* func
, RegisterID
* thisRegister
, ArgumentsNode
*, unsigned divot
, unsigned startOffset
, unsigned endOffset
);
374 RegisterID
* newRegister();
376 // Returns the RegisterID corresponding to ident.
377 RegisterID
* addVar(const Identifier
& ident
, bool isConstant
)
380 addVar(ident
, isConstant
, local
);
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
*&);
386 // Returns the RegisterID corresponding to ident.
387 RegisterID
* addGlobalVar(const Identifier
& ident
, bool isConstant
)
390 addGlobalVar(ident
, isConstant
, local
);
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
*&);
396 RegisterID
* addParameter(const Identifier
&);
398 void preserveLastVar();
400 RegisterID
& registerFor(int index
)
403 return m_calleeRegisters
[index
];
405 if (index
== RegisterFile::OptionalCalleeArguments
)
406 return m_argumentsRegister
;
408 if (m_parameters
.size()) {
409 ASSERT(!m_globals
.size());
410 return m_parameters
[index
+ m_parameters
.size() + RegisterFile::CallFrameHeaderSize
];
413 return m_globals
[-index
- 1];
416 unsigned addConstant(FuncDeclNode
*);
417 unsigned addConstant(FuncExprNode
*);
418 unsigned addConstant(const Identifier
&);
419 RegisterID
* addConstantValue(JSValue
);
420 unsigned addRegExp(RegExp
*);
422 Vector
<Instruction
>& instructions() { return m_codeBlock
->instructions(); }
423 SymbolTable
& symbolTable() { return *m_symbolTable
; }
425 bool shouldOptimizeLocals() { return (m_codeType
!= EvalCode
) && !m_dynamicScopeDepth
; }
426 bool canOptimizeNonLocals() { return (m_codeType
== FunctionCode
) && !m_dynamicScopeDepth
&& !m_codeBlock
->usesEval(); }
428 RegisterID
* emitThrowExpressionTooDeepException();
430 void createArgumentsIfNecessary();
432 bool m_shouldEmitDebugHooks
;
433 bool m_shouldEmitProfileHooks
;
435 const ScopeChain
* m_scopeChain
;
436 SymbolTable
* m_symbolTable
;
438 ScopeNode
* m_scopeNode
;
439 CodeBlock
* m_codeBlock
;
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
;
456 int m_dynamicScopeDepth
;
457 int m_baseScopeDepth
;
460 Vector
<ControlFlowContext
> m_scopeContextStack
;
461 Vector
<SwitchInfo
> m_switchContextStack
;
463 int m_nextGlobalIndex
;
464 int m_nextParameterIndex
;
465 int m_firstConstantIndex
;
466 int m_nextConstantOffset
;
467 unsigned m_globalConstantIndex
;
469 int m_globalVarStorageOffset
;
472 IdentifierMap m_identifierMap
;
473 JSValueMap m_jsValueMap
;
474 NumberMap m_numberMap
;
475 IdentifierStringMap m_stringMap
;
477 JSGlobalData
* m_globalData
;
479 OpcodeID m_lastOpcodeID
;
481 unsigned m_emitNodeDepth
;
483 bool m_regeneratingForExceptionInfo
;
484 CodeBlock
* m_codeBlockBeingRegeneratedFrom
;
486 static const unsigned s_maxEmitNodeDepth
= 5000;
491 #endif // BytecodeGenerator_h