1// Copyright 2017 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5"use strict";
6
7let codeKinds = [
8    "UNKNOWN",
9    "CPPPARSE",
10    "CPPCOMPBC",
11    "CPPCOMP",
12    "CPPGC",
13    "CPPEXT",
14    "CPP",
15    "LIB",
16    "IC",
17    "BC",
18    "STUB",
19    "BUILTIN",
20    "REGEXP",
21    "JSOPT",
22    "JSUNOPT"
23];
24
25function resolveCodeKind(code) {
26  if (!code || !code.type) {
27    return "UNKNOWN";
28  } else if (code.type === "CPP") {
29    return "CPP";
30  } else if (code.type === "SHARED_LIB") {
31    return "LIB";
32  } else if (code.type === "CODE") {
33    if (code.kind === "LoadIC" ||
34        code.kind === "StoreIC" ||
35        code.kind === "KeyedStoreIC" ||
36        code.kind === "KeyedLoadIC" ||
37        code.kind === "LoadGlobalIC" ||
38        code.kind === "Handler") {
39      return "IC";
40    } else if (code.kind === "BytecodeHandler") {
41      return "BC";
42    } else if (code.kind === "Stub") {
43      return "STUB";
44    } else if (code.kind === "Builtin") {
45      return "BUILTIN";
46    } else if (code.kind === "RegExp") {
47      return "REGEXP";
48    }
49    console.log("Unknown CODE: '" + code.kind + "'.");
50    return "CODE";
51  } else if (code.type === "JS") {
52    if (code.kind === "Builtin") {
53      return "JSUNOPT";
54    } else if (code.kind === "Opt") {
55      return "JSOPT";
56    } else if (code.kind === "Unopt") {
57      return "JSUNOPT";
58    }
59  }
60  console.log("Unknown code type '" + type + "'.");
61}
62
63function resolveCodeKindAndVmState(code, vmState) {
64  let kind = resolveCodeKind(code);
65  if (kind === "CPP") {
66    if (vmState === 1) {
67      kind = "CPPGC";
68    } else if (vmState === 2) {
69      kind = "CPPPARSE";
70    } else if (vmState === 3) {
71      kind = "CPPCOMPBC";
72    } else if (vmState === 4) {
73      kind = "CPPCOMP";
74    } else if (vmState === 6) {
75      kind = "CPPEXT";
76    }
77  }
78  return kind;
79}
80
81function codeEquals(code1, code2, allowDifferentKinds = false) {
82  if (!code1 || !code2) return false;
83  if (code1.name !== code2.name || code1.type !== code2.type) return false;
84
85  if (code1.type === 'CODE') {
86    if (!allowDifferentKinds && code1.kind !== code2.kind) return false;
87  } else if (code1.type === 'JS') {
88    if (!allowDifferentKinds && code1.kind !== code2.kind) return false;
89    if (code1.func !== code2.func) return false;
90  }
91  return true;
92}
93
94function createNodeFromStackEntry(code, codeId, vmState) {
95  let name = code ? code.name : "UNKNOWN";
96
97  return { name, codeId, type : resolveCodeKindAndVmState(code, vmState),
98           children : [], ownTicks : 0, ticks : 0 };
99}
100
101function childIdFromCode(codeId, code) {
102  // For JavaScript function, pretend there is one instance of optimized
103  // function and one instance of unoptimized function per SFI.
104  // Otherwise, just compute the id from code id.
105  let type = resolveCodeKind(code);
106  if (type === "JSOPT") {
107    return code.func * 4 + 1;
108  } else if (type === "JSUNOPT") {
109    return code.func * 4 + 2;
110  } else {
111    return codeId * 4;
112  }
113}
114
115// We store list of ticks and positions within the ticks stack by
116// storing flattened triplets of { tickIndex, depth, count }.
117// Triplet { 123, 2, 3 } encodes positions in ticks 123, 124, 125,
118// all of them at depth 2. The flattened array is used to encode
119// position within the call-tree.
120
121// The following function helps to encode such triplets.
122function addFrameToFrameList(paths, pathIndex, depth) {
123  // Try to combine with the previous code run.
124  if (paths.length > 0 &&
125      paths[paths.length - 3] + 1 === pathIndex &&
126      paths[paths.length - 2] === depth) {
127    paths[paths.length - 1]++;
128  } else {
129    paths.push(pathIndex, depth, 1);
130  }
131}
132
133function findNextFrame(file, stack, stackPos, step, filter) {
134  let codeId = -1;
135  let code = null;
136  while (stackPos >= 0 && stackPos < stack.length) {
137    codeId = stack[stackPos];
138    code = codeId >= 0 ? file.code[codeId] : undefined;
139
140    if (filter) {
141      let type = code ? code.type : undefined;
142      let kind = code ? code.kind : undefined;
143      if (filter(type, kind)) return stackPos;
144    }
145    stackPos += step;
146  }
147  return -1;
148}
149
150function addOrUpdateChildNode(parent, file, stackIndex, stackPos, ascending) {
151  let stack = file.ticks[stackIndex].s;
152  let vmState = file.ticks[stackIndex].vm;
153  let codeId = stack[stackPos];
154  let code = codeId >= 0 ? file.code[codeId] : undefined;
155  if (stackPos === -1) {
156    // We reached the end without finding the next step.
157    // If we are doing top-down call tree, update own ticks.
158    if (!ascending) {
159      parent.ownTicks++;
160    }
161  } else {
162    console.assert(stackPos >= 0 && stackPos < stack.length);
163    // We found a child node.
164    let childId = childIdFromCode(codeId, code);
165    let child = parent.children[childId];
166    if (!child) {
167      child = createNodeFromStackEntry(code, codeId, vmState);
168      child.delayedExpansion = { frameList : [], ascending };
169      parent.children[childId] = child;
170    }
171    child.ticks++;
172    addFrameToFrameList(child.delayedExpansion.frameList, stackIndex, stackPos);
173  }
174}
175
176// This expands a tree node (direct children only).
177function expandTreeNode(file, node, filter) {
178  let { frameList, ascending } = node.delayedExpansion;
179
180  let step = ascending ? 2 : -2;
181
182  for (let i = 0; i < frameList.length; i+= 3) {
183    let firstStackIndex = frameList[i];
184    let depth = frameList[i + 1];
185    let count = frameList[i + 2];
186    for (let j = 0; j < count; j++) {
187      let stackIndex = firstStackIndex + j;
188      let stack = file.ticks[stackIndex].s;
189
190      // Get to the next frame that has not been filtered out.
191      let stackPos = findNextFrame(file, stack, depth + step, step, filter);
192      addOrUpdateChildNode(node, file, stackIndex, stackPos, ascending);
193    }
194  }
195  node.delayedExpansion = null;
196}
197
198function createEmptyNode(name) {
199  return {
200      name : name,
201      codeId: -1,
202      type : "CAT",
203      children : [],
204      ownTicks : 0,
205      ticks : 0
206  };
207}
208
209class RuntimeCallTreeProcessor {
210  constructor() {
211    this.tree = createEmptyNode("root");
212    this.tree.delayedExpansion = { frameList : [], ascending : false };
213  }
214
215  addStack(file, tickIndex) {
216    this.tree.ticks++;
217
218    let stack = file.ticks[tickIndex].s;
219    let i;
220    for (i = 0; i < stack.length; i += 2) {
221      let codeId = stack[i];
222      if (codeId < 0) return;
223      let code = file.code[codeId];
224      if (code.type !== "CPP" && code.type !== "SHARED_LIB") {
225        i -= 2;
226        break;
227      }
228    }
229    if (i < 0 || i >= stack.length) return;
230    addOrUpdateChildNode(this.tree, file, tickIndex, i, false);
231  }
232}
233
234class PlainCallTreeProcessor {
235  constructor(filter, isBottomUp) {
236    this.filter = filter;
237    this.tree = createEmptyNode("root");
238    this.tree.delayedExpansion = { frameList : [], ascending : isBottomUp };
239    this.isBottomUp = isBottomUp;
240  }
241
242  addStack(file, tickIndex) {
243    let stack = file.ticks[tickIndex].s;
244    let step = this.isBottomUp ? 2 : -2;
245    let start = this.isBottomUp ? 0 : stack.length - 2;
246
247    let stackPos = findNextFrame(file, stack, start, step, this.filter);
248    addOrUpdateChildNode(this.tree, file, tickIndex, stackPos, this.isBottomUp);
249
250    this.tree.ticks++;
251  }
252}
253
254function buildCategoryTreeAndLookup() {
255  let root = createEmptyNode("root");
256  let categories = {};
257  function addCategory(name, types) {
258    let n = createEmptyNode(name);
259    for (let i = 0; i < types.length; i++) {
260      categories[types[i]] = n;
261    }
262    root.children.push(n);
263  }
264  addCategory("JS Optimized", [ "JSOPT" ]);
265  addCategory("JS Unoptimized", [ "JSUNOPT", "BC" ]);
266  addCategory("IC", [ "IC" ]);
267  addCategory("RegExp", [ "REGEXP" ]);
268  addCategory("Other generated", [ "STUB", "BUILTIN" ]);
269  addCategory("C++", [ "CPP", "LIB" ]);
270  addCategory("C++/GC", [ "CPPGC" ]);
271  addCategory("C++/Parser", [ "CPPPARSE" ]);
272  addCategory("C++/Bytecode compiler", [ "CPPCOMPBC" ]);
273  addCategory("C++/Compiler", [ "CPPCOMP" ]);
274  addCategory("C++/External", [ "CPPEXT" ]);
275  addCategory("Unknown", [ "UNKNOWN" ]);
276
277  return { categories, root };
278}
279
280class CategorizedCallTreeProcessor {
281  constructor(filter, isBottomUp) {
282    this.filter = filter;
283    let { categories, root } = buildCategoryTreeAndLookup();
284
285    this.tree = root;
286    this.categories = categories;
287    this.isBottomUp = isBottomUp;
288  }
289
290  addStack(file, tickIndex) {
291    let stack = file.ticks[tickIndex].s;
292    let vmState = file.ticks[tickIndex].vm;
293    if (stack.length === 0) return;
294    let codeId = stack[0];
295    let code = codeId >= 0 ? file.code[codeId] : undefined;
296    let kind = resolveCodeKindAndVmState(code, vmState);
297    let node = this.categories[kind];
298
299    this.tree.ticks++;
300    node.ticks++;
301
302    let step = this.isBottomUp ? 2 : -2;
303    let start = this.isBottomUp ? 0 : stack.length - 2;
304
305    let stackPos = findNextFrame(file, stack, start, step, this.filter);
306    addOrUpdateChildNode(node, file, tickIndex, stackPos, this.isBottomUp);
307  }
308}
309
310class FunctionListTree {
311  constructor(filter, withCategories) {
312    if (withCategories) {
313      let { categories, root } = buildCategoryTreeAndLookup();
314      this.tree = root;
315      this.categories = categories;
316    } else {
317      this.tree = {
318        name : "root",
319        codeId: -1,
320        children : [],
321        ownTicks : 0,
322        ticks : 0
323      };
324      this.categories = null;
325    }
326
327    this.codeVisited = [];
328    this.filter = filter;
329  }
330
331  addStack(file, tickIndex) {
332    let stack = file.ticks[tickIndex].s;
333    let vmState = file.ticks[tickIndex].vm;
334
335    this.tree.ticks++;
336    let child = null;
337    let tree = null;
338    for (let i = stack.length - 2; i >= 0; i -= 2) {
339      let codeId = stack[i];
340      if (codeId < 0 || this.codeVisited[codeId]) continue;
341
342      let code = codeId >= 0 ? file.code[codeId] : undefined;
343      if (this.filter) {
344        let type = code ? code.type : undefined;
345        let kind = code ? code.kind : undefined;
346        if (!this.filter(type, kind)) continue;
347      }
348      let childId = childIdFromCode(codeId, code);
349      if (this.categories) {
350        let kind = resolveCodeKindAndVmState(code, vmState);
351        tree = this.categories[kind];
352      } else {
353        tree = this.tree;
354      }
355      child = tree.children[childId];
356      if (!child) {
357        child = createNodeFromStackEntry(code, codeId, vmState);
358        child.children[0] = createEmptyNode("Top-down tree");
359        child.children[0].delayedExpansion =
360          { frameList : [], ascending : false };
361        child.children[1] = createEmptyNode("Bottom-up tree");
362        child.children[1].delayedExpansion =
363          { frameList : [], ascending : true };
364        tree.children[childId] = child;
365      }
366      child.ticks++;
367      child.children[0].ticks++;
368      addFrameToFrameList(
369          child.children[0].delayedExpansion.frameList, tickIndex, i);
370      child.children[1].ticks++;
371      addFrameToFrameList(
372          child.children[1].delayedExpansion.frameList, tickIndex, i);
373      this.codeVisited[codeId] = true;
374    }
375    if (child) {
376      child.ownTicks++;
377      console.assert(tree !== null);
378      tree.ticks++;
379      console.assert(tree.type === "CAT");
380    }
381
382    for (let i = 0; i < stack.length; i += 2) {
383      let codeId = stack[i];
384      if (codeId >= 0) this.codeVisited[codeId] = false;
385    }
386  }
387}
388
389
390class CategorySampler {
391  constructor(file, bucketCount) {
392    this.bucketCount = bucketCount;
393
394    this.firstTime = file.ticks[0].tm;
395    let lastTime = file.ticks[file.ticks.length - 1].tm;
396    this.step = (lastTime - this.firstTime) / bucketCount;
397
398    this.buckets = [];
399    let bucket = {};
400    for (let i = 0; i < codeKinds.length; i++) {
401      bucket[codeKinds[i]] = 0;
402    }
403    for (let i = 0; i < bucketCount; i++) {
404      this.buckets.push(Object.assign({ total : 0 }, bucket));
405    }
406  }
407
408  addStack(file, tickIndex) {
409    let { tm : timestamp, vm : vmState, s : stack } = file.ticks[tickIndex];
410
411    let i = Math.floor((timestamp - this.firstTime) / this.step);
412    if (i === this.buckets.length) i--;
413    console.assert(i >= 0 && i < this.buckets.length);
414
415    let bucket = this.buckets[i];
416    bucket.total++;
417
418    let codeId = (stack.length > 0) ? stack[0] : -1;
419    let code = codeId >= 0 ? file.code[codeId] : undefined;
420    let kind = resolveCodeKindAndVmState(code, vmState);
421    bucket[kind]++;
422  }
423}
424
425class FunctionTimelineProcessor {
426  constructor(functionCodeId, filter) {
427    this.functionCodeId = functionCodeId;
428    this.filter = filter;
429    this.blocks = [];
430    this.currentBlock = null;
431  }
432
433  addStack(file, tickIndex) {
434    if (!this.functionCodeId) return;
435
436    let { tm : timestamp, vm : vmState, s : stack } = file.ticks[tickIndex];
437    let functionCode = file.code[this.functionCodeId];
438
439    // Find if the function is on the stack, and its position on the stack,
440    // ignoring any filtered entries.
441    let stackCode = undefined;
442    let functionPosInStack = -1;
443    let filteredI = 0;
444    for (let i = 0; i < stack.length - 1; i += 2) {
445      let codeId = stack[i];
446      let code = codeId >= 0 ? file.code[codeId] : undefined;
447      let type = code ? code.type : undefined;
448      let kind = code ? code.kind : undefined;
449      if (!this.filter(type, kind)) continue;
450
451      // Match other instances of the same function (e.g. unoptimised, various
452      // different optimised versions).
453      if (codeEquals(code, functionCode, true)) {
454        functionPosInStack = filteredI;
455        stackCode = code;
456        break;
457      }
458      filteredI++;
459    }
460
461    if (functionPosInStack >= 0) {
462      let stackKind = resolveCodeKindAndVmState(stackCode, vmState);
463
464      let codeIsTopOfStack = (functionPosInStack === 0);
465
466      if (this.currentBlock !== null) {
467        this.currentBlock.end = timestamp;
468
469        if (codeIsTopOfStack === this.currentBlock.topOfStack
470          && stackKind === this.currentBlock.kind) {
471          // If we haven't changed the stack top or the function kind, then
472          // we're happy just extending the current block and not starting
473          // a new one.
474          return;
475        }
476      }
477
478      // Start a new block at the current timestamp.
479      this.currentBlock = {
480        start: timestamp,
481        end: timestamp,
482        code: stackCode,
483        kind: stackKind,
484        topOfStack: codeIsTopOfStack
485      };
486      this.blocks.push(this.currentBlock);
487    } else {
488      this.currentBlock = null;
489    }
490  }
491}
492
493// Generates a tree out of a ticks sequence.
494// {file} is the JSON files with the ticks and code objects.
495// {startTime}, {endTime} is the interval.
496// {tree} is the processor of stacks.
497function generateTree(
498    file, startTime, endTime, tree) {
499  let ticks = file.ticks;
500  let i = 0;
501  while (i < ticks.length && ticks[i].tm < startTime) {
502    i++;
503  }
504
505  let tickCount = 0;
506  while (i < ticks.length && ticks[i].tm < endTime) {
507    tree.addStack(file, i);
508    i++;
509    tickCount++;
510  }
511
512  return tickCount;
513}
514
515function computeOptimizationStats(file,
516    timeStart = -Infinity, timeEnd = Infinity) {
517  function newCollection() {
518    return { count : 0, functions : [], functionTable : [] };
519  }
520  function addToCollection(collection, code) {
521    collection.count++;
522    let funcData = collection.functionTable[code.func];
523    if (!funcData) {
524      funcData = { f : file.functions[code.func], instances : [] };
525      collection.functionTable[code.func] = funcData;
526      collection.functions.push(funcData);
527    }
528    funcData.instances.push(code);
529  }
530
531  let functionCount = 0;
532  let optimizedFunctionCount = 0;
533  let deoptimizedFunctionCount = 0;
534  let optimizations = newCollection();
535  let eagerDeoptimizations = newCollection();
536  let softDeoptimizations = newCollection();
537  let lazyDeoptimizations = newCollection();
538
539  for (let i = 0; i < file.functions.length; i++) {
540    let f = file.functions[i];
541
542    // Skip special SFIs that do not correspond to JS functions.
543    if (f.codes.length === 0) continue;
544    if (file.code[f.codes[0]].type !== "JS") continue;
545
546    functionCount++;
547    let optimized = false;
548    let deoptimized = false;
549
550    for (let j = 0; j < f.codes.length; j++) {
551      let code = file.code[f.codes[j]];
552      console.assert(code.type === "JS");
553      if (code.kind === "Opt") {
554        optimized = true;
555        if (code.tm >= timeStart && code.tm <= timeEnd) {
556          addToCollection(optimizations, code);
557        }
558      }
559      if (code.deopt) {
560        deoptimized = true;
561        if (code.deopt.tm >= timeStart && code.deopt.tm <= timeEnd) {
562          switch (code.deopt.bailoutType) {
563            case "lazy":
564              addToCollection(lazyDeoptimizations, code);
565              break;
566            case "eager":
567              addToCollection(eagerDeoptimizations, code);
568              break;
569            case "soft":
570              addToCollection(softDeoptimizations, code);
571              break;
572          }
573        }
574      }
575    }
576    if (optimized) {
577      optimizedFunctionCount++;
578    }
579    if (deoptimized) {
580      deoptimizedFunctionCount++;
581    }
582  }
583
584  function sortCollection(collection) {
585    collection.functions.sort(
586        (a, b) => a.instances.length - b.instances.length);
587  }
588
589  sortCollection(eagerDeoptimizations);
590  sortCollection(lazyDeoptimizations);
591  sortCollection(softDeoptimizations);
592  sortCollection(optimizations);
593
594  return {
595    functionCount,
596    optimizedFunctionCount,
597    deoptimizedFunctionCount,
598    optimizations,
599    eagerDeoptimizations,
600    lazyDeoptimizations,
601    softDeoptimizations,
602  };
603}
604