JavaScriptCore:
[WebKit-https.git] / JavaScriptCore / VM / CodeBlock.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 CodeBlock_h
31 #define CodeBlock_h
32
33 #include "EvalCodeCache.h"
34 #include "Instruction.h"
35 #include "JSGlobalObject.h"
36 #include "Nodes.h"
37 #include "RegExp.h"
38 #include "UString.h"
39 #include <wtf/RefPtr.h>
40 #include <wtf/Vector.h>
41
42 namespace JSC {
43
44     class ExecState;
45
46     enum CodeType { GlobalCode, EvalCode, FunctionCode };
47
48     static ALWAYS_INLINE int missingThisObjectMarker() { return std::numeric_limits<int>::max(); }
49
50     struct HandlerInfo {
51         uint32_t start;
52         uint32_t end;
53         uint32_t target;
54         uint32_t scopeDepth;
55         void* nativeCode;
56     };
57
58     struct ExpressionRangeInfo {
59         enum {
60             MaxOffset = (1 << 7) - 1, 
61             MaxDivot = (1 << 25) - 1
62         };
63         uint32_t instructionOffset : 25;
64         uint32_t divotPoint : 25;
65         uint32_t startOffset : 7;
66         uint32_t endOffset : 7;
67     };
68
69     struct LineInfo {
70         uint32_t instructionOffset;
71         int32_t lineNumber;
72     };
73
74     struct OffsetLocation {
75         int32_t branchOffset;
76 #if ENABLE(CTI)
77         void* ctiOffset;
78 #endif
79     };
80
81     struct StructureStubInfo {
82         StructureStubInfo(unsigned bytecodeIndex)
83             : bytecodeIndex(bytecodeIndex)
84             , stubRoutine(0)
85             , callReturnLocation(0)
86             , hotPathBegin(0)
87         {
88         }
89     
90         unsigned bytecodeIndex;
91         void* stubRoutine;
92         void* callReturnLocation;
93         void* hotPathBegin;
94     };
95
96     struct CallLinkInfo {
97         CallLinkInfo()
98             : callReturnLocation(0)
99             , hotPathBegin(0)
100             , hotPathOther(0)
101             , coldPathOther(0)
102             , callee(0)
103         {
104         }
105     
106         unsigned bytecodeIndex;
107         void* callReturnLocation;
108         void* hotPathBegin;
109         void* hotPathOther;
110         void* coldPathOther;
111         CodeBlock* callee;
112         unsigned position;
113         
114         void setUnlinked() { callee = 0; }
115         bool isLinked() { return callee; }
116     };
117
118     inline void* getStructureStubInfoReturnLocation(StructureStubInfo* structureStubInfo)
119     {
120         return structureStubInfo->callReturnLocation;
121     }
122
123     inline void* getCallLinkInfoReturnLocation(CallLinkInfo* callLinkInfo)
124     {
125         return callLinkInfo->callReturnLocation;
126     }
127
128     // Binary chop algorithm, calls valueAtPosition on pre-sorted elements in array,
129     // compares result with key (KeyTypes should be comparable with '--', '<', '>').
130     // Optimized for cases where the array contains the key, checked by assertions.
131     template<typename ArrayType, typename KeyType, KeyType(*valueAtPosition)(ArrayType*)>
132     inline ArrayType* binaryChop(ArrayType* array, size_t size, KeyType key)
133     {
134         // The array must contain at least one element (pre-condition, array does conatin key).
135         // If the array only contains one element, no need to do the comparison.
136         while (size > 1) {
137             // Pick an element to check, half way through the array, and read the value.
138             int pos = (size - 1) >> 1;
139             KeyType val = valueAtPosition(&array[pos]);
140             
141             // If the key matches, success!
142             if (val == key)
143                 return &array[pos];
144             // The item we are looking for is smaller than the item being check; reduce the value of 'size',
145             // chopping off the right hand half of the array.
146             else if (key < val)
147                 size = pos;
148             // Discard all values in the left hand half of the array, up to and including the item at pos.
149             else {
150                 size -= (pos + 1);
151                 array += (pos + 1);
152             }
153
154             // 'size' should never reach zero.
155             ASSERT(size);
156         }
157         
158         // If we reach this point we've chopped down to one element, no need to check it matches
159         ASSERT(size == 1);
160         ASSERT(key == valueAtPosition(&array[0]));
161         return &array[0];
162     }
163
164     struct StringJumpTable {
165         typedef HashMap<RefPtr<UString::Rep>, OffsetLocation> StringOffsetTable;
166         StringOffsetTable offsetTable;
167 #if ENABLE(CTI)
168         void* ctiDefault; // FIXME: it should not be necessary to store this.
169 #endif
170
171         inline int32_t offsetForValue(UString::Rep* value, int32_t defaultOffset)
172         {
173             StringOffsetTable::const_iterator end = offsetTable.end();
174             StringOffsetTable::const_iterator loc = offsetTable.find(value);
175             if (loc == end)
176                 return defaultOffset;
177             return loc->second.branchOffset;
178         }
179
180 #if ENABLE(CTI)
181         inline void* ctiForValue(UString::Rep* value)
182         {
183             StringOffsetTable::const_iterator end = offsetTable.end();
184             StringOffsetTable::const_iterator loc = offsetTable.find(value);
185             if (loc == end)
186                 return ctiDefault;
187             return loc->second.ctiOffset;
188         }
189 #endif
190     };
191
192     struct SimpleJumpTable {
193         // FIXME: The two Vectors can be combind into one Vector<OffsetLocation>
194         Vector<int32_t> branchOffsets;
195         int32_t min;
196 #if ENABLE(CTI)
197         Vector<void*> ctiOffsets;
198         void* ctiDefault;
199 #endif
200
201         int32_t offsetForValue(int32_t value, int32_t defaultOffset);
202         void add(int32_t key, int32_t offset)
203         {
204             if (!branchOffsets[key])
205                 branchOffsets[key] = offset;
206         }
207
208 #if ENABLE(CTI)
209         inline void* ctiForValue(int32_t value)
210         {
211             if (value >= min && static_cast<uint32_t>(value - min) < ctiOffsets.size())
212                 return ctiOffsets[value - min];
213             return ctiDefault;
214         }
215 #endif
216     };
217
218     struct CodeBlock {
219         CodeBlock(ScopeNode* ownerNode, CodeType codeType, PassRefPtr<SourceProvider> sourceProvider, unsigned sourceOffset)
220             : ownerNode(ownerNode)
221             , globalData(0)
222 #if ENABLE(CTI)
223             , ctiCode(0)
224 #endif
225             , numCalleeRegisters(0)
226             , numConstants(0)
227             , numVars(0)
228             , numParameters(0)
229             , needsFullScopeChain(ownerNode->needsActivation())
230             , usesEval(ownerNode->usesEval())
231             , codeType(codeType)
232             , source(sourceProvider)
233             , sourceOffset(sourceOffset)
234         {
235             ASSERT(source);
236         }
237
238         ~CodeBlock();
239
240 #if ENABLE(CTI) 
241         void unlinkCallers();
242 #endif
243
244         void addCaller(CallLinkInfo* caller)
245         {
246             caller->callee = this;
247             caller->position = linkedCallerList.size();
248             linkedCallerList.append(caller);
249         }
250
251         void removeCaller(CallLinkInfo* caller)
252         {
253             unsigned pos = caller->position;
254             unsigned lastPos = linkedCallerList.size() - 1;
255
256             if (pos != lastPos) {
257                 linkedCallerList[pos] = linkedCallerList[lastPos];
258                 linkedCallerList[pos]->position = pos;
259             }
260             linkedCallerList.shrink(lastPos);
261         }
262
263         inline bool isKnownNotImmediate(int index)
264         {
265             if (index == thisRegister)
266                 return true;
267
268             if (isConstantRegisterIndex(index))
269                 return !JSImmediate::isImmediate(getConstant(index));
270
271             return false;
272         }
273
274         ALWAYS_INLINE bool isConstantRegisterIndex(int index)
275         {
276             return index >= numVars && index < numVars + numConstants;
277         }
278
279         ALWAYS_INLINE JSValue* getConstant(int index)
280         {
281             return constantRegisters[index - numVars].getJSValue();
282         }
283
284         ALWAYS_INLINE bool isTemporaryRegisterIndex(int index)
285         {
286             return index >= numVars + numConstants;
287         }
288
289 #if !defined(NDEBUG) || ENABLE_OPCODE_SAMPLING
290         void dump(ExecState*) const;
291         void printStructures(const Instruction*) const;
292         void printStructure(const char* name, const Instruction*, int operand) const;
293 #endif
294         int expressionRangeForVPC(const Instruction*, int& divot, int& startOffset, int& endOffset);
295         int lineNumberForVPC(const Instruction* vPC);
296         bool getHandlerForVPC(const Instruction* vPC, Instruction*& target, int& scopeDepth);
297         void* nativeExceptionCodeForHandlerVPC(const Instruction* handlerVPC);
298
299         void mark();
300         void refStructures(Instruction* vPC) const;
301         void derefStructures(Instruction* vPC) const;
302
303         StructureStubInfo& getStubInfo(void* returnAddress)
304         {
305             return *(binaryChop<StructureStubInfo, void*, getStructureStubInfoReturnLocation>(propertyAccessInstructions.begin(), propertyAccessInstructions.size(), returnAddress));
306         }
307
308         CallLinkInfo& getCallLinkInfo(void* returnAddress)
309         {
310             return *(binaryChop<CallLinkInfo, void*, getCallLinkInfoReturnLocation>(callLinkInfos.begin(), callLinkInfos.size(), returnAddress));
311         }
312
313         ScopeNode* ownerNode;
314         JSGlobalData* globalData;
315 #if ENABLE(CTI)
316         void* ctiCode;
317 #endif
318
319         int numCalleeRegisters;
320
321         // NOTE: numConstants holds the number of constant registers allocated
322         // by the code generator, not the number of constant registers used.
323         // (Duplicate constants are uniqued during code generation, and spare
324         // constant registers may be allocated.)
325         int numConstants;
326         int numVars;
327         int numParameters;
328         int thisRegister;
329         bool needsFullScopeChain;
330         bool usesEval;
331         bool usesArguments;
332         CodeType codeType;
333         RefPtr<SourceProvider> source;
334         unsigned sourceOffset;
335
336         Vector<Instruction> instructions;
337         Vector<unsigned> globalResolveInstructions;
338         Vector<StructureStubInfo> propertyAccessInstructions;
339         Vector<CallLinkInfo> callLinkInfos;
340         Vector<CallLinkInfo*> linkedCallerList;
341
342         // Constant pool
343         Vector<Identifier> identifiers;
344         Vector<RefPtr<FuncDeclNode> > functions;
345         Vector<RefPtr<FuncExprNode> > functionExpressions;
346         Vector<Register> constantRegisters;
347         Vector<JSValue*> unexpectedConstants;
348         Vector<RefPtr<RegExp> > regexps;
349         Vector<HandlerInfo> exceptionHandlers;
350         Vector<ExpressionRangeInfo> expressionInfo;
351         Vector<LineInfo> lineInfo;
352
353         Vector<SimpleJumpTable> immediateSwitchJumpTables;
354         Vector<SimpleJumpTable> characterSwitchJumpTables;
355         Vector<StringJumpTable> stringSwitchJumpTables;
356
357 #if ENABLE(CTI)
358         HashMap<void*, unsigned> ctiReturnAddressVPCMap;
359 #endif
360
361         Vector<unsigned> jumpTargets;
362
363         EvalCodeCache evalCodeCache;
364
365         SymbolTable symbolTable;
366     private:
367 #if !defined(NDEBUG) || ENABLE(OPCODE_SAMPLING)
368         void dump(ExecState*, const Vector<Instruction>::const_iterator& begin, Vector<Instruction>::const_iterator&) const;
369 #endif
370
371     };
372
373     // Program code is not marked by any function, so we make the global object
374     // responsible for marking it.
375
376     struct ProgramCodeBlock : public CodeBlock {
377         ProgramCodeBlock(ScopeNode* ownerNode, CodeType codeType, JSGlobalObject* globalObject, PassRefPtr<SourceProvider> sourceProvider)
378             : CodeBlock(ownerNode, codeType, sourceProvider, 0)
379             , globalObject(globalObject)
380         {
381             globalObject->codeBlocks().add(this);
382         }
383
384         ~ProgramCodeBlock()
385         {
386             if (globalObject)
387                 globalObject->codeBlocks().remove(this);
388         }
389
390         JSGlobalObject* globalObject; // For program and eval nodes, the global object that marks the constant pool.
391     };
392
393     struct EvalCodeBlock : public ProgramCodeBlock {
394         EvalCodeBlock(ScopeNode* ownerNode, JSGlobalObject* globalObject, PassRefPtr<SourceProvider> sourceProvider)
395             : ProgramCodeBlock(ownerNode, EvalCode, globalObject, sourceProvider)
396         {
397         }
398     };
399
400 } // namespace JSC
401
402 #endif // CodeBlock_h