Windows build fixes
[WebKit-https.git] / JavaScriptCore / VM / Opcode.cpp
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 #include "config.h"
31 #include "Opcode.h"
32
33 #include <stdlib.h>
34 #include "CodeBlock.h"
35 #include "Machine.h"
36
37 using namespace std;
38
39 namespace KJS {
40
41 #if SAMPLING_TOOL_ENABLED || DUMP_OPCODE_STATS
42
43 static const char* opcodeNames[] = {
44     "load             ",
45     "new_object       ",
46     "new_array        ",
47     "new_regexp       ",
48     "mov              ",
49     
50     "not              ",
51     "eq               ",
52     "neq              ",
53     "stricteq         ",
54     "nstricteq        ",
55     "less             ",
56     "lesseq           ",
57     
58     "pre_inc          ",
59     "pre_dec          ",
60     "post_inc         ",
61     "post_dec         ",
62     "to_jsnumber      ",
63     "negate           ",
64     "add              ",
65     "mul              ",
66     "div              ",
67     "mod              ",
68     "sub              ",
69     
70     "lshift           ",
71     "rshift           ",
72     "urshift          ",
73     "bitand           ",
74     "bitxor           ",
75     "bitor            ",
76     "bitnot           ",
77     
78     "instanceof       ",
79     "typeof           ",
80     "in               ",
81
82     "resolve          ",
83     "resolve_skip     ",
84     "get_scoped_var   ",
85     "put_scoped_var   ",
86     "resolve_base     ",
87     "resolve_with_base",
88     "resolve_func     ",
89     "get_by_id        ",
90     "put_by_id        ",
91     "del_by_id        ",
92     "get_by_val       ",
93     "put_by_val       ",
94     "del_by_val       ",
95     "put_by_index     ",
96     "put_getter       ",
97     "put_setter       ",
98
99     "jmp              ",
100     "jtrue            ",
101     "jfalse           ",
102     "jless            ",
103     "jnless           ",
104     "jmp_scopes       ",
105     "loop             ",
106     "loop_if_true     ",
107     "loop_if_less     ",
108     "switch_imm       ",
109     "switch_char      ",
110     "switch_string    ",
111
112     "new_func         ",
113     "new_func_exp     ",
114     "call             ",
115     "call_eval        ",
116     "ret              ",
117
118     "construct        ",
119
120     "get_pnames       ",
121     "next_pname       ",
122
123     "push_scope       ",
124     "pop_scope        ",
125
126     "catch            ",
127     "throw            ",
128     "new_error        ",
129
130     "jsr              ",
131     "sret             ",
132
133     "debug            ",
134
135     "end              "
136 };
137
138 #endif
139
140 #if SAMPLING_TOOL_ENABLED
141
142 void ScopeSampleRecord::sample(CodeBlock* codeBlock, Instruction* vPC)
143 {
144     m_totalCount++;
145
146     if (!m_vpcCounts) {
147         m_size = codeBlock->instructions.size();
148         m_vpcCounts = static_cast<int*>(calloc(m_size, sizeof(int)));
149         m_codeBlock = codeBlock;
150     }
151
152     unsigned codeOffset = static_cast<unsigned>(reinterpret_cast<ptrdiff_t>(vPC) - reinterpret_cast<ptrdiff_t>(codeBlock->instructions.begin())) / sizeof(Instruction*);
153     // This could occur if codeBlock & vPC are not consistent - e.g. sample mid op_call/op_ret.
154     if (codeOffset < m_size)
155         m_vpcCounts[codeOffset]++;
156 }
157
158 static inline unsigned hertz2us(unsigned hertz)
159 {
160     return 1000000 / hertz;
161 }
162
163 void SamplingTool::run()
164 {
165     while (m_running) {
166         usleep(hertz2us(m_hertz));
167
168         m_totalSamples++;
169
170         CodeBlock* codeBlock = m_recordedCodeBlock;
171         Instruction* vPC = m_recordedVPC;
172
173         if (codeBlock && vPC) {
174             ScopeSampleRecord* record = m_scopeSampleMap->get(codeBlock->ownerNode);
175             if (record)
176                 record->sample(codeBlock, vPC);
177         }
178     }
179 }
180
181 void* SamplingTool::threadStartFunc(void* samplingTool)
182 {
183     reinterpret_cast<SamplingTool*>(samplingTool)->run();
184     return 0;
185 }
186
187 void SamplingTool::notifyOfScope(ScopeNode* scope)
188 {
189     m_scopeSampleMap->set(scope, new ScopeSampleRecord(scope));
190 }
191
192 void SamplingTool::start(unsigned hertz)
193 {
194     ASSERT(!m_running);
195     m_running = true;
196     m_hertz = hertz;
197     pthread_create(&m_samplingThread, 0, threadStartFunc, this);
198 }
199
200 void SamplingTool::stop()
201 {
202     ASSERT(m_running);
203     m_running = false;
204     pthread_join(m_samplingThread, 0);
205 }
206
207 struct OpcodeSampleInfo
208 {
209     OpcodeID opcode;
210     long long count;
211 };
212
213 struct LineCountInfo
214 {
215     unsigned line;
216     unsigned count;
217 };
218
219 static int compareLineCountInfoSampling(const void* left, const void* right)
220 {
221     const LineCountInfo *leftLineCount = reinterpret_cast<const LineCountInfo *>(left);
222     const LineCountInfo *rightLineCount = reinterpret_cast<const LineCountInfo *>(right);
223
224     return (leftLineCount->line > rightLineCount->line) ? 1 : (leftLineCount->line < rightLineCount->line) ? -1 : 0;
225 }
226
227 static int compareOpcodeIndicesSampling(const void* left, const void* right)
228 {
229     const OpcodeSampleInfo *leftSampleInfo = reinterpret_cast<const OpcodeSampleInfo *>(left);
230     const OpcodeSampleInfo *rightSampleInfo = reinterpret_cast<const OpcodeSampleInfo *>(right);
231
232     return (leftSampleInfo->count < rightSampleInfo->count) ? 1 : (leftSampleInfo->count > rightSampleInfo->count) ? -1 : 0;
233 }
234
235 static int compareScopeSampleRecords(const void* left, const void* right)
236 {
237     const ScopeSampleRecord* const leftValue = *static_cast<const ScopeSampleRecord* const *>(left);
238     const ScopeSampleRecord* const rightValue = *static_cast<const ScopeSampleRecord* const *>(right);
239
240     return (leftValue->m_totalCount < rightValue->m_totalCount) ? 1 : (leftValue->m_totalCount > rightValue->m_totalCount) ? -1 : 0;
241 }
242
243 void SamplingTool::dump(ExecState* exec)
244 {
245     // Tidies up SunSpider output by removing short scripts - such a small number of samples would likely not be useful anyhow.
246     if (m_totalSamples < 10)
247         return;
248     
249     // (1) Calculate 'totalCodeBlockSamples', build and sort 'codeBlockSamples' array.
250
251     int scopeCount = m_scopeSampleMap->size();
252     long long totalCodeBlockSamples = 0;
253     ScopeSampleRecord* codeBlockSamples[scopeCount];
254     ScopeSampleRecordMap::iterator iter = m_scopeSampleMap->begin();
255     for (int i=0; i < scopeCount; ++i, ++iter) {
256         codeBlockSamples[i] = iter->second;
257         totalCodeBlockSamples += codeBlockSamples[i]->m_totalCount;
258     }
259     mergesort(codeBlockSamples, scopeCount, sizeof(ScopeSampleRecord*), compareScopeSampleRecords);
260
261     // (2) Print data from 'codeBlockSamples' array, calculate 'totalOpcodeSamples', populate 'opcodeSampleCounts' array.
262
263     long long totalOpcodeSamples = 0;
264     long long opcodeSampleCounts[numOpcodeIDs] = { 0 };
265
266     fprintf(stdout, "\nBlock sampling results\n\n"); 
267     fprintf(stdout, "Total blocks sampled (total samples): %lld (%lld)\n\n", totalCodeBlockSamples, m_totalSamples);
268
269     for (int i=0; i < scopeCount; i++) {
270         ScopeSampleRecord *record = codeBlockSamples[i];
271         CodeBlock* codeBlock = record->m_codeBlock;
272
273         double totalPercent = (record->m_totalCount * 100.0)/m_totalSamples;
274         double blockPercent = (record->m_totalCount * 100.0)/totalCodeBlockSamples;
275
276         if ((blockPercent >= 1) && codeBlock) {
277             Instruction* code = codeBlock->instructions.begin();
278             fprintf(stdout, "#%d: %s:%d: sampled %d times - %.3f%% (%.3f%%)\n", i+1, record->m_scope->sourceURL().UTF8String().c_str(), codeBlock->lineNumberForVPC(code), record->m_totalCount, blockPercent, totalPercent);
279             if (i < 10) {
280                 HashMap<unsigned,unsigned> lineCounts;
281                 codeBlock->dump(exec);
282                 for (unsigned op = 0; op < record->m_size; ++op) {
283                     int count = record->m_vpcCounts[op];
284                     if (count) {
285                         printf("    [% 4d] has sample count: % 4d\n", op, count);
286                         unsigned line = codeBlock->lineNumberForVPC(code+op);
287                         lineCounts.set(line, (lineCounts.contains(line) ? lineCounts.get(line) : 0) + count);
288                     }
289                 }
290                 printf("\n");
291                 int linesCount = lineCounts.size();
292                 LineCountInfo lineCountInfo[linesCount];
293                 int lineno = 0;
294                 for (HashMap<unsigned,unsigned>::iterator iter = lineCounts.begin(); iter != lineCounts.end(); ++iter, ++lineno) {
295                     lineCountInfo[lineno].line = iter->first;
296                     lineCountInfo[lineno].count = iter->second;
297                 }
298                 mergesort(lineCountInfo, linesCount, sizeof(LineCountInfo), compareLineCountInfoSampling);
299                 for (lineno = 0; lineno < linesCount; ++lineno) {
300                     printf("    Line #%d has sample count %d.\n", lineCountInfo[lineno].line, lineCountInfo[lineno].count);
301                 }
302                 printf("\n");
303             }
304         }
305         
306         if (record->m_vpcCounts && codeBlock) {
307             Instruction* instructions = codeBlock->instructions.begin();
308             for (unsigned op = 0; op < record->m_size; ++op) {
309                 Opcode opcode = instructions[op].u.opcode;
310                 if (exec->machine()->isOpcode(opcode)) {
311                     totalOpcodeSamples += record->m_vpcCounts[op];
312                     opcodeSampleCounts[exec->machine()->getOpcodeID(opcode)] += record->m_vpcCounts[op];
313                 }
314             }
315         }
316     }
317     printf("\n");
318
319     // (3) Build and sort 'opcodeSampleInfo' array.
320
321     OpcodeSampleInfo opcodeSampleInfo[numOpcodeIDs];
322     for (int i = 0; i < numOpcodeIDs; ++i) {
323         opcodeSampleInfo[i].opcode = (OpcodeID)i;
324         opcodeSampleInfo[i].count = opcodeSampleCounts[i];
325     }
326     mergesort(opcodeSampleInfo, numOpcodeIDs, sizeof(OpcodeSampleInfo), compareOpcodeIndicesSampling);
327
328     // (4) Print Opcode sampling results.
329     
330     fprintf(stdout, "\nOpcode sampling results\n\n"); 
331     
332     fprintf(stdout, "Total opcodes sampled (total samples): %lld (%lld)\n\n", totalOpcodeSamples, m_totalSamples);
333     fprintf(stdout, "Opcodes in order:\n\n");
334     for (int i = 0; i < numOpcodeIDs; ++i) {
335         long long count = opcodeSampleCounts[i];
336         fprintf(stdout, "%s:\t%6lld\t%.3f%%\t(%.3f%%)\n", opcodeNames[i], count, ((double)count * 100)/totalOpcodeSamples, ((double)count * 100)/m_totalSamples);    
337     }
338     fprintf(stdout, "\n");
339     fprintf(stdout, "Opcodes by sample count:\n\n");
340     for (int i = 0; i < numOpcodeIDs; ++i) {
341         OpcodeID opcode = opcodeSampleInfo[i].opcode;
342         long long count = opcodeSampleInfo[i].count;
343         fprintf(stdout, "%s:\t%6lld\t%.3f%%\t(%.3f%%)\n", opcodeNames[opcode], count, ((double)count * 100)/totalOpcodeSamples, ((double)count * 100)/m_totalSamples);    
344     }
345     fprintf(stdout, "\n");
346 }
347
348 #endif
349
350
351 #if DUMP_OPCODE_STATS
352
353 long long OpcodeStats::opcodeCounts[numOpcodeIDs];
354 long long OpcodeStats::opcodePairCounts[numOpcodeIDs][numOpcodeIDs];
355 int OpcodeStats::lastOpcode = -1;
356
357 static OpcodeStats logger;
358
359 OpcodeStats::OpcodeStats()
360 {
361     for (int i = 0; i < numOpcodeIDs; ++i)
362         opcodeCounts[i] = 0;
363     
364     for (int i = 0; i < numOpcodeIDs; ++i)
365         for (int j = 0; j < numOpcodeIDs; ++j)
366             opcodePairCounts[i][j] = 0;
367 }
368
369 static int compareOpcodeIndices(const void* left, const void* right)
370 {
371     long long leftValue = OpcodeStats::opcodeCounts[*(int*) left];
372     long long rightValue = OpcodeStats::opcodeCounts[*(int*) right];
373     
374     if (leftValue < rightValue)
375         return 1;
376     else if (leftValue > rightValue)
377         return -1;
378     else
379         return 0;
380 }
381
382 static int compareOpcodePairIndices(const void* left, const void* right)
383 {
384     pair<int, int> leftPair = *(pair<int, int>*) left;
385     long long leftValue = OpcodeStats::opcodePairCounts[leftPair.first][leftPair.second];
386     pair<int, int> rightPair = *(pair<int, int>*) right;
387     long long rightValue = OpcodeStats::opcodePairCounts[rightPair.first][rightPair.second];
388     
389     if (leftValue < rightValue)
390         return 1;
391     else if (leftValue > rightValue)
392         return -1;
393     else
394         return 0;
395 }
396
397 OpcodeStats::~OpcodeStats()
398 {
399     long long totalInstructions = 0;
400     for (int i = 0; i < numOpcodeIDs; ++i)
401         totalInstructions += opcodeCounts[i];
402     
403     long long totalInstructionPairs = 0;
404     for (int i = 0; i < numOpcodeIDs; ++i)
405         for (int j = 0; j < numOpcodeIDs; ++j)
406             totalInstructionPairs += opcodePairCounts[i][j];
407
408     int sortedIndices[numOpcodeIDs];    
409     for (int i = 0; i < numOpcodeIDs; ++i)
410         sortedIndices[i] = i;
411     mergesort(sortedIndices, numOpcodeIDs, sizeof(int), compareOpcodeIndices);
412     
413     pair<int, int> sortedPairIndices[numOpcodeIDs * numOpcodeIDs];
414     pair<int, int>* currentPairIndex = sortedPairIndices;
415     for (int i = 0; i < numOpcodeIDs; ++i)
416         for (int j = 0; j < numOpcodeIDs; ++j)
417             *(currentPairIndex++) = make_pair(i, j);
418     mergesort(sortedPairIndices, numOpcodeIDs * numOpcodeIDs, sizeof(pair<int, int>), compareOpcodePairIndices);
419     
420     printf("\nExecuted opcode statistics\n"); 
421     
422     printf("Total instructions executed: %lld\n\n", totalInstructions);
423
424     printf("All opcodes by frequency:\n\n");
425
426     for (int i = 0; i < numOpcodeIDs; ++i) {
427         int index = sortedIndices[i];
428         printf("%s: %lld - %.2f%%\n", opcodeNames[index], opcodeCounts[index], ((double) opcodeCounts[index]) / ((double) totalInstructions) * 100.0);    
429     }
430     
431     printf("\n");
432     printf("2-opcode sequences by frequency: %lld\n\n", totalInstructions);
433     
434     for (int i = 0; i < numOpcodeIDs * numOpcodeIDs; ++i) {
435         pair<int, int> indexPair = sortedPairIndices[i];
436         long long count = opcodePairCounts[indexPair.first][indexPair.second];
437         
438         if (!count)
439             break;
440         
441         printf("%s %s: %lld %.2f%%\n", opcodeNames[indexPair.first], opcodeNames[indexPair.second], count, ((double) count) / ((double) totalInstructionPairs) * 100.0);
442     }
443     
444     printf("\n");
445     printf("Most common opcodes and sequences:\n");
446
447     for (int i = 0; i < numOpcodeIDs; ++i) {
448         int index = sortedIndices[i];
449         long long opcodeCount = opcodeCounts[index];
450         double opcodeProportion = ((double) opcodeCount) / ((double) totalInstructions);
451         if (opcodeProportion < 0.0001)
452             break;
453         printf("\n%s: %lld - %.2f%%\n", opcodeNames[index], opcodeCount, opcodeProportion * 100.0);
454
455         for (int j = 0; j < numOpcodeIDs * numOpcodeIDs; ++j) {
456             pair<int, int> indexPair = sortedPairIndices[j];
457             long long pairCount = opcodePairCounts[indexPair.first][indexPair.second];
458             double pairProportion = ((double) pairCount) / ((double) totalInstructionPairs);
459         
460             if (!pairCount || pairProportion < 0.0001 || pairProportion < opcodeProportion / 100)
461                 break;
462
463             if (indexPair.first != index && indexPair.second != index)
464                 continue;
465
466             printf("    %s %s: %lld - %.2f%%\n", opcodeNames[indexPair.first], opcodeNames[indexPair.second], pairCount, pairProportion * 100.0);
467         }
468         
469     }
470     printf("\n");
471 }
472
473 void OpcodeStats::recordInstruction(int opcode)
474 {
475     opcodeCounts[opcode]++;
476     
477     if (lastOpcode != -1)
478         opcodePairCounts[lastOpcode][opcode]++;
479     
480     lastOpcode = opcode;
481 }
482
483 void OpcodeStats::resetLastInstruction()
484 {
485     lastOpcode = -1;
486 }
487
488 #endif
489
490 } // namespace WTF