profile-utils.js 17.3 KB
Newer Older
1 2 3 4
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
"use strict";
6 7 8

let codeKinds = [
    "UNKNOWN",
9 10
    "CPPPARSE",
    "CPPCOMPBC",
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
    "CPPCOMP",
    "CPPGC",
    "CPPEXT",
    "CPP",
    "LIB",
    "IC",
    "BC",
    "STUB",
    "BUILTIN",
    "REGEXP",
    "JSOPT",
    "JSUNOPT"
];

function resolveCodeKind(code) {
  if (!code || !code.type) {
    return "UNKNOWN";
  } else if (code.type === "CPP") {
    return "CPP";
  } else if (code.type === "SHARED_LIB") {
    return "LIB";
  } else if (code.type === "CODE") {
    if (code.kind === "LoadIC" ||
        code.kind === "StoreIC" ||
        code.kind === "KeyedStoreIC" ||
        code.kind === "KeyedLoadIC" ||
        code.kind === "LoadGlobalIC" ||
        code.kind === "Handler") {
      return "IC";
    } else if (code.kind === "BytecodeHandler") {
      return "BC";
    } else if (code.kind === "Stub") {
      return "STUB";
    } else if (code.kind === "Builtin") {
      return "BUILTIN";
    } else if (code.kind === "RegExp") {
      return "REGEXP";
    }
    console.log("Unknown CODE: '" + code.kind + "'.");
    return "CODE";
  } else if (code.type === "JS") {
    if (code.kind === "Builtin") {
      return "JSUNOPT";
    } else if (code.kind === "Opt") {
      return "JSOPT";
    } else if (code.kind === "Unopt") {
      return "JSUNOPT";
    }
  }
  console.log("Unknown code type '" + type + "'.");
}

function resolveCodeKindAndVmState(code, vmState) {
  let kind = resolveCodeKind(code);
  if (kind === "CPP") {
    if (vmState === 1) {
      kind = "CPPGC";
    } else if (vmState === 2) {
69 70 71
      kind = "CPPPARSE";
    } else if (vmState === 3) {
      kind = "CPPCOMPBC";
72
    } else if (vmState === 4) {
73 74
      kind = "CPPCOMP";
    } else if (vmState === 6) {
75 76 77 78 79 80
      kind = "CPPEXT";
    }
  }
  return kind;
}

81 82
function codeEquals(code1, code2, allowDifferentKinds = false) {
  if (!code1 || !code2) return false;
83
  if (code1.name !== code2.name || code1.type !== code2.type) return false;
84

85 86 87 88 89
  if (code1.type === 'CODE') {
    if (!allowDifferentKinds && code1.kind !== code2.kind) return false;
  } else if (code1.type === 'JS') {
    if (!allowDifferentKinds && code1.kind !== code2.kind) return false;
    if (code1.func !== code2.func) return false;
90 91 92 93
  }
  return true;
}

94
function createNodeFromStackEntry(code, codeId, vmState) {
95
  let name = code ? code.name : "UNKNOWN";
96 97 98 99
  let node = createEmptyNode(name);
  node.codeId = codeId;
  node.type = resolveCodeKindAndVmState(code, vmState);
  return node;
100 101
}

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
function childIdFromCode(codeId, code) {
  // For JavaScript function, pretend there is one instance of optimized
  // function and one instance of unoptimized function per SFI.
  // Otherwise, just compute the id from code id.
  let type = resolveCodeKind(code);
  if (type === "JSOPT") {
    return code.func * 4 + 1;
  } else if (type === "JSUNOPT") {
    return code.func * 4 + 2;
  } else {
    return codeId * 4;
  }
}

// We store list of ticks and positions within the ticks stack by
// storing flattened triplets of { tickIndex, depth, count }.
// Triplet { 123, 2, 3 } encodes positions in ticks 123, 124, 125,
// all of them at depth 2. The flattened array is used to encode
// position within the call-tree.

// The following function helps to encode such triplets.
function addFrameToFrameList(paths, pathIndex, depth) {
  // Try to combine with the previous code run.
  if (paths.length > 0 &&
      paths[paths.length - 3] + 1 === pathIndex &&
      paths[paths.length - 2] === depth) {
    paths[paths.length - 1]++;
  } else {
    paths.push(pathIndex, depth, 1);
  }
}

134 135 136 137 138 139
function findNextFrame(file, stack, stackPos, step, filter) {
  let codeId = -1;
  let code = null;
  while (stackPos >= 0 && stackPos < stack.length) {
    codeId = stack[stackPos];
    code = codeId >= 0 ? file.code[codeId] : undefined;
140

141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
    if (filter) {
      let type = code ? code.type : undefined;
      let kind = code ? code.kind : undefined;
      if (filter(type, kind)) return stackPos;
    }
    stackPos += step;
  }
  return -1;
}

function addOrUpdateChildNode(parent, file, stackIndex, stackPos, ascending) {
  if (stackPos === -1) {
    // We reached the end without finding the next step.
    // If we are doing top-down call tree, update own ticks.
    if (!ascending) {
      parent.ownTicks++;
    }
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
    return;
  }

  let stack = file.ticks[stackIndex].s;
  console.assert(stackPos >= 0 && stackPos < stack.length);
  let codeId = stack[stackPos];
  let code = codeId >= 0 ? file.code[codeId] : undefined;
  // We found a child node.
  let childId = childIdFromCode(codeId, code);
  let child = parent.children[childId];
  if (!child) {
    let vmState = file.ticks[stackIndex].vm;
    child = createNodeFromStackEntry(code, codeId, vmState);
    child.delayedExpansion = { frameList : [], ascending };
    parent.children[childId] = child;
173
  }
174 175
  child.ticks++;
  addFrameToFrameList(child.delayedExpansion.frameList, stackIndex, stackPos);
176 177
}

178 179 180 181 182 183 184
// This expands a tree node (direct children only).
function expandTreeNode(file, node, filter) {
  let { frameList, ascending } = node.delayedExpansion;

  let step = ascending ? 2 : -2;

  for (let i = 0; i < frameList.length; i+= 3) {
185
    let firstStackIndex = frameList[i];
186 187 188
    let depth = frameList[i + 1];
    let count = frameList[i + 2];
    for (let j = 0; j < count; j++) {
189 190
      let stackIndex = firstStackIndex + j;
      let stack = file.ticks[stackIndex].s;
191 192

      // Get to the next frame that has not been filtered out.
193 194
      let stackPos = findNextFrame(file, stack, depth + step, step, filter);
      addOrUpdateChildNode(node, file, stackIndex, stackPos, ascending);
195 196 197 198 199
    }
  }
  node.delayedExpansion = null;
}

200 201 202
function createEmptyNode(name) {
  return {
      name : name,
203
      codeId: -1,
204 205 206 207 208 209 210
      type : "CAT",
      children : [],
      ownTicks : 0,
      ticks : 0
  };
}

211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
class RuntimeCallTreeProcessor {
  constructor() {
    this.tree = createEmptyNode("root");
    this.tree.delayedExpansion = { frameList : [], ascending : false };
  }

  addStack(file, tickIndex) {
    this.tree.ticks++;

    let stack = file.ticks[tickIndex].s;
    let i;
    for (i = 0; i < stack.length; i += 2) {
      let codeId = stack[i];
      if (codeId < 0) return;
      let code = file.code[codeId];
      if (code.type !== "CPP" && code.type !== "SHARED_LIB") {
        i -= 2;
        break;
      }
    }
    if (i < 0 || i >= stack.length) return;
    addOrUpdateChildNode(this.tree, file, tickIndex, i, false);
  }
}

236 237 238 239
class PlainCallTreeProcessor {
  constructor(filter, isBottomUp) {
    this.filter = filter;
    this.tree = createEmptyNode("root");
240
    this.tree.delayedExpansion = { frameList : [], ascending : isBottomUp };
241 242 243
    this.isBottomUp = isBottomUp;
  }

244 245
  addStack(file, tickIndex) {
    let stack = file.ticks[tickIndex].s;
246 247 248 249 250 251 252
    let step = this.isBottomUp ? 2 : -2;
    let start = this.isBottomUp ? 0 : stack.length - 2;

    let stackPos = findNextFrame(file, stack, start, step, this.filter);
    addOrUpdateChildNode(this.tree, file, tickIndex, stackPos, this.isBottomUp);

    this.tree.ticks++;
253 254 255
  }
}

256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
function buildCategoryTreeAndLookup() {
  let root = createEmptyNode("root");
  let categories = {};
  function addCategory(name, types) {
    let n = createEmptyNode(name);
    for (let i = 0; i < types.length; i++) {
      categories[types[i]] = n;
    }
    root.children.push(n);
  }
  addCategory("JS Optimized", [ "JSOPT" ]);
  addCategory("JS Unoptimized", [ "JSUNOPT", "BC" ]);
  addCategory("IC", [ "IC" ]);
  addCategory("RegExp", [ "REGEXP" ]);
  addCategory("Other generated", [ "STUB", "BUILTIN" ]);
  addCategory("C++", [ "CPP", "LIB" ]);
  addCategory("C++/GC", [ "CPPGC" ]);
273 274
  addCategory("C++/Parser", [ "CPPPARSE" ]);
  addCategory("C++/Bytecode compiler", [ "CPPCOMPBC" ]);
275 276 277 278 279 280 281
  addCategory("C++/Compiler", [ "CPPCOMP" ]);
  addCategory("C++/External", [ "CPPEXT" ]);
  addCategory("Unknown", [ "UNKNOWN" ]);

  return { categories, root };
}

282 283 284
class CategorizedCallTreeProcessor {
  constructor(filter, isBottomUp) {
    this.filter = filter;
285
    let { categories, root } = buildCategoryTreeAndLookup();
286 287 288 289 290 291

    this.tree = root;
    this.categories = categories;
    this.isBottomUp = isBottomUp;
  }

292 293 294
  addStack(file, tickIndex) {
    let stack = file.ticks[tickIndex].s;
    let vmState = file.ticks[tickIndex].vm;
295 296 297 298 299 300 301
    if (stack.length === 0) return;
    let codeId = stack[0];
    let code = codeId >= 0 ? file.code[codeId] : undefined;
    let kind = resolveCodeKindAndVmState(code, vmState);
    let node = this.categories[kind];

    this.tree.ticks++;
302
    node.ticks++;
303

304 305
    let step = this.isBottomUp ? 2 : -2;
    let start = this.isBottomUp ? 0 : stack.length - 2;
306

307 308
    let stackPos = findNextFrame(file, stack, start, step, this.filter);
    addOrUpdateChildNode(node, file, tickIndex, stackPos, this.isBottomUp);
309 310 311 312
  }
}

class FunctionListTree {
313 314 315 316 317 318
  constructor(filter, withCategories) {
    if (withCategories) {
      let { categories, root } = buildCategoryTreeAndLookup();
      this.tree = root;
      this.categories = categories;
    } else {
319
      this.tree = createEmptyNode("root");
320 321 322
      this.categories = null;
    }

323 324 325 326
    this.codeVisited = [];
    this.filter = filter;
  }

327 328 329 330
  addStack(file, tickIndex) {
    let stack = file.ticks[tickIndex].s;
    let vmState = file.ticks[tickIndex].vm;

331 332
    this.tree.ticks++;
    let child = null;
333
    let tree = null;
334 335 336 337
    for (let i = stack.length - 2; i >= 0; i -= 2) {
      let codeId = stack[i];
      if (codeId < 0 || this.codeVisited[codeId]) continue;

338
      let code = file.code[codeId];
339 340 341 342 343
      if (this.filter) {
        let type = code ? code.type : undefined;
        let kind = code ? code.kind : undefined;
        if (!this.filter(type, kind)) continue;
      }
344 345 346 347 348 349 350 351
      let childId = childIdFromCode(codeId, code);
      if (this.categories) {
        let kind = resolveCodeKindAndVmState(code, vmState);
        tree = this.categories[kind];
      } else {
        tree = this.tree;
      }
      child = tree.children[childId];
352
      if (!child) {
353
        child = createNodeFromStackEntry(code, codeId, vmState);
354 355 356 357 358 359 360
        child.children[0] = createEmptyNode("Top-down tree");
        child.children[0].delayedExpansion =
          { frameList : [], ascending : false };
        child.children[1] = createEmptyNode("Bottom-up tree");
        child.children[1].delayedExpansion =
          { frameList : [], ascending : true };
        tree.children[childId] = child;
361 362
      }
      child.ticks++;
363 364 365 366 367 368
      child.children[0].ticks++;
      addFrameToFrameList(
          child.children[0].delayedExpansion.frameList, tickIndex, i);
      child.children[1].ticks++;
      addFrameToFrameList(
          child.children[1].delayedExpansion.frameList, tickIndex, i);
369 370 371 372
      this.codeVisited[codeId] = true;
    }
    if (child) {
      child.ownTicks++;
373 374 375
      console.assert(tree !== null);
      tree.ticks++;
      console.assert(tree.type === "CAT");
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403
    }

    for (let i = 0; i < stack.length; i += 2) {
      let codeId = stack[i];
      if (codeId >= 0) this.codeVisited[codeId] = false;
    }
  }
}


class CategorySampler {
  constructor(file, bucketCount) {
    this.bucketCount = bucketCount;

    this.firstTime = file.ticks[0].tm;
    let lastTime = file.ticks[file.ticks.length - 1].tm;
    this.step = (lastTime - this.firstTime) / bucketCount;

    this.buckets = [];
    let bucket = {};
    for (let i = 0; i < codeKinds.length; i++) {
      bucket[codeKinds[i]] = 0;
    }
    for (let i = 0; i < bucketCount; i++) {
      this.buckets.push(Object.assign({ total : 0 }, bucket));
    }
  }

404 405 406
  addStack(file, tickIndex) {
    let { tm : timestamp, vm : vmState, s : stack } = file.ticks[tickIndex];

407
    let i = Math.floor((timestamp - this.firstTime) / this.step);
408
    if (i === this.buckets.length) i--;
409 410 411 412 413 414 415 416 417 418 419 420
    console.assert(i >= 0 && i < this.buckets.length);

    let bucket = this.buckets[i];
    bucket.total++;

    let codeId = (stack.length > 0) ? stack[0] : -1;
    let code = codeId >= 0 ? file.code[codeId] : undefined;
    let kind = resolveCodeKindAndVmState(code, vmState);
    bucket[kind]++;
  }
}

421 422 423 424 425 426 427 428 429
class FunctionTimelineProcessor {
  constructor(functionCodeId, filter) {
    this.functionCodeId = functionCodeId;
    this.filter = filter;
    this.blocks = [];
    this.currentBlock = null;
  }

  addStack(file, tickIndex) {
430
    if (!this.functionCodeId) return;
431

432 433 434 435 436 437 438
    let { tm : timestamp, vm : vmState, s : stack } = file.ticks[tickIndex];
    let functionCode = file.code[this.functionCodeId];

    // Find if the function is on the stack, and its position on the stack,
    // ignoring any filtered entries.
    let stackCode = undefined;
    let functionPosInStack = -1;
439
    let filteredI = 0;
440 441 442 443 444 445
    for (let i = 0; i < stack.length - 1; i += 2) {
      let codeId = stack[i];
      let code = codeId >= 0 ? file.code[codeId] : undefined;
      let type = code ? code.type : undefined;
      let kind = code ? code.kind : undefined;
      if (!this.filter(type, kind)) continue;
446

447 448 449 450 451
      // Match other instances of the same function (e.g. unoptimised, various
      // different optimised versions).
      if (codeEquals(code, functionCode, true)) {
        functionPosInStack = filteredI;
        stackCode = code;
452 453
        break;
      }
454 455 456 457 458
      filteredI++;
    }

    if (functionPosInStack >= 0) {
      let stackKind = resolveCodeKindAndVmState(stackCode, vmState);
459

460
      let codeIsTopOfStack = (functionPosInStack === 0);
461 462 463 464

      if (this.currentBlock !== null) {
        this.currentBlock.end = timestamp;

465 466 467 468 469
        if (codeIsTopOfStack === this.currentBlock.topOfStack
          && stackKind === this.currentBlock.kind) {
          // If we haven't changed the stack top or the function kind, then
          // we're happy just extending the current block and not starting
          // a new one.
470 471 472 473
          return;
        }
      }

474
      // Start a new block at the current timestamp.
475 476 477
      this.currentBlock = {
        start: timestamp,
        end: timestamp,
478 479
        code: stackCode,
        kind: stackKind,
480 481 482 483 484 485 486 487 488
        topOfStack: codeIsTopOfStack
      };
      this.blocks.push(this.currentBlock);
    } else {
      this.currentBlock = null;
    }
  }
}

489 490 491 492 493 494 495 496 497 498 499 500 501 502
// Generates a tree out of a ticks sequence.
// {file} is the JSON files with the ticks and code objects.
// {startTime}, {endTime} is the interval.
// {tree} is the processor of stacks.
function generateTree(
    file, startTime, endTime, tree) {
  let ticks = file.ticks;
  let i = 0;
  while (i < ticks.length && ticks[i].tm < startTime) {
    i++;
  }

  let tickCount = 0;
  while (i < ticks.length && ticks[i].tm < endTime) {
503
    tree.addStack(file, i);
504 505 506 507 508 509
    i++;
    tickCount++;
  }

  return tickCount;
}
510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599

function computeOptimizationStats(file,
    timeStart = -Infinity, timeEnd = Infinity) {
  function newCollection() {
    return { count : 0, functions : [], functionTable : [] };
  }
  function addToCollection(collection, code) {
    collection.count++;
    let funcData = collection.functionTable[code.func];
    if (!funcData) {
      funcData = { f : file.functions[code.func], instances : [] };
      collection.functionTable[code.func] = funcData;
      collection.functions.push(funcData);
    }
    funcData.instances.push(code);
  }

  let functionCount = 0;
  let optimizedFunctionCount = 0;
  let deoptimizedFunctionCount = 0;
  let optimizations = newCollection();
  let eagerDeoptimizations = newCollection();
  let softDeoptimizations = newCollection();
  let lazyDeoptimizations = newCollection();

  for (let i = 0; i < file.functions.length; i++) {
    let f = file.functions[i];

    // Skip special SFIs that do not correspond to JS functions.
    if (f.codes.length === 0) continue;
    if (file.code[f.codes[0]].type !== "JS") continue;

    functionCount++;
    let optimized = false;
    let deoptimized = false;

    for (let j = 0; j < f.codes.length; j++) {
      let code = file.code[f.codes[j]];
      console.assert(code.type === "JS");
      if (code.kind === "Opt") {
        optimized = true;
        if (code.tm >= timeStart && code.tm <= timeEnd) {
          addToCollection(optimizations, code);
        }
      }
      if (code.deopt) {
        deoptimized = true;
        if (code.deopt.tm >= timeStart && code.deopt.tm <= timeEnd) {
          switch (code.deopt.bailoutType) {
            case "lazy":
              addToCollection(lazyDeoptimizations, code);
              break;
            case "eager":
              addToCollection(eagerDeoptimizations, code);
              break;
            case "soft":
              addToCollection(softDeoptimizations, code);
              break;
          }
        }
      }
    }
    if (optimized) {
      optimizedFunctionCount++;
    }
    if (deoptimized) {
      deoptimizedFunctionCount++;
    }
  }

  function sortCollection(collection) {
    collection.functions.sort(
        (a, b) => a.instances.length - b.instances.length);
  }

  sortCollection(eagerDeoptimizations);
  sortCollection(lazyDeoptimizations);
  sortCollection(softDeoptimizations);
  sortCollection(optimizations);

  return {
    functionCount,
    optimizedFunctionCount,
    deoptimizedFunctionCount,
    optimizations,
    eagerDeoptimizations,
    lazyDeoptimizations,
    softDeoptimizations,
  };
}
600 601 602 603 604 605 606 607 608 609 610 611

function normalizeLeadingWhitespace(lines) {
  let regex = /^\s*/;
  let minimumLeadingWhitespaceChars = Infinity;
  for (let line of lines) {
    minimumLeadingWhitespaceChars =
        Math.min(minimumLeadingWhitespaceChars, regex.exec(line)[0].length);
  }
  for (let i = 0; i < lines.length; i++) {
    lines[i] = lines[i].substring(minimumLeadingWhitespaceChars);
  }
}