profile.mjs 35.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
// Copyright 2009 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

28
import { CodeMap, CodeEntry } from "./codemap.mjs";
29 30
import { ConsArray } from "./consarray.mjs";

31
// Used to associate log entries with source positions in scripts.
32 33 34 35 36 37 38
// TODO: move to separate modules
export class SourcePosition {
  constructor(script, line, column) {
    this.script = script;
    this.line = line;
    this.column = column;
    this.entries = [];
39
    this.isFunction = false;
40
  }
41

42 43 44
  addEntry(entry) {
    this.entries.push(entry);
  }
45 46

  toString() {
47
    return `${this.script.name}:${this.line}:${this.column}`;
48
  }
49 50 51 52 53 54 55 56 57 58 59

  get functionPosition() {
    // TODO(cbruni)
    return undefined;
  }

  get toolTipDict() {
    return {
      title: this.toString(),
      __this__: this,
      script: this.script,
60
      entries: this.entries,
61 62
    }
  }
63 64 65
}

export class Script {
66
  url;
67
  source;
68
  name;
69 70
  // Map<line, Map<column, SourcePosition>>
  lineToColumn = new Map();
71
  _entries = [];
72 73

  constructor(id) {
74
    this.id = id;
75 76 77
    this.sourcePositions = [];
  }

78 79 80
  update(url, source) {
    this.url = url;
    this.name = Script.getShortestUniqueName(url, this);
81 82 83
    this.source = source;
  }

84 85 86 87
  get length() {
    return this.source.length;
  }

88 89 90 91
  get entries() {
    return this._entries;
  }

92 93 94 95 96
  findFunctionSourcePosition(sourcePosition) {
    // TODO(cbruni) implmenent
    return undefined;
  }

97 98 99
  addSourcePosition(line, column, entry) {
    let sourcePosition = this.lineToColumn.get(line)?.get(column);
    if (sourcePosition === undefined) {
100
      sourcePosition = new SourcePosition(this, line, column,)
101
      this._addSourcePosition(line, column, sourcePosition);
102 103
    }
    sourcePosition.addEntry(entry);
104
    this._entries.push(entry);
105 106 107
    return sourcePosition;
  }

108
  _addSourcePosition(line, column, sourcePosition) {
109 110 111 112 113 114 115 116 117 118
    let columnToSourcePosition;
    if (this.lineToColumn.has(line)) {
      columnToSourcePosition = this.lineToColumn.get(line);
    } else {
      columnToSourcePosition = new Map();
      this.lineToColumn.set(line, columnToSourcePosition);
    }
    this.sourcePositions.push(sourcePosition);
    columnToSourcePosition.set(column, sourcePosition);
  }
119

120
  toString() {
121
    return `Script(${this.id}): ${this.name}`;
122
  }
123

124 125 126 127 128 129 130
  get toolTipDict() {
    return {
      title: this.toString(),
      __this__: this,
      id: this.id,
      url: this.url,
      source: this.source,
131
      sourcePositions: this.sourcePositions
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
    }
  }

  static getShortestUniqueName(url, script) {
    const parts = url.split('/');
    const filename = parts[parts.length -1];
    const dict = this._dict ?? (this._dict = new Map());
    const matchingScripts = dict.get(filename);
    if (matchingScripts == undefined) {
      dict.set(filename, [script]);
      return filename;
    }
    // TODO: find shortest unique substring
    // Update all matching scripts to have a unique filename again.
    for (let matchingScript of matchingScripts) {
      matchingScript.name = script.url
    }
    matchingScripts.push(script);
    return url;
151
  }
152 153
}

154

155
class SourceInfo {
156 157 158 159 160 161 162
  script;
  start;
  end;
  positions;
  inlined;
  fns;
  disassemble;
163 164

  setSourcePositionInfo(script, startPos, endPos, sourcePositionTable, inliningPositions, inlinedFunctions) {
165 166 167 168 169 170 171
    this.script = script;
    this.start = startPos;
    this.end = endPos;
    this.positions = sourcePositionTable;
    this.inlined = inliningPositions;
    this.fns = inlinedFunctions;
  }
172 173 174 175

  setDisassemble(code) {
    this.disassemble = code;
  }
176 177 178 179

  getSourceCode() {
    return this.script.source?.substring(this.start, this.end);
  }
180 181
}

182 183 184 185 186 187
/**
 * Creates a profile object for processing profiling-related events
 * and calculating function execution times.
 *
 * @constructor
 */
188 189 190 191 192 193 194 195
export class Profile {
  codeMap_ = new CodeMap();
  topDownTree_ = new CallTree();
  bottomUpTree_ = new CallTree();
  c_entries_ = {};
  scripts_ = [];
  urlToScript_ = new Map();

196 197 198 199 200 201 202 203
  serializeVMSymbols() {
    let result = this.codeMap_.getAllStaticEntriesWithAddresses();
    result.concat(this.codeMap_.getAllLibraryEntriesWithAddresses())
    return result.map(([startAddress, codeEntry]) => {
      return [codeEntry.getName(), startAddress, startAddress + codeEntry.size]
    });
  }

204 205
  /**
   * Returns whether a function with the specified name must be skipped.
206
   * Should be overridden by subclasses.
207 208 209 210 211 212
   *
   * @param {string} name Function name.
   */
  skipThisFunction(name) {
    return false;
  }
213

214 215 216 217 218 219 220 221 222 223 224
  /**
   * Enum for profiler operations that involve looking up existing
   * code entries.
   *
   * @enum {number}
   */
  static Operation = {
    MOVE: 0,
    DELETE: 1,
    TICK: 2
  }
225

226 227 228 229 230 231 232
  /**
   * Enum for code state regarding its dynamic optimization.
   *
   * @enum {number}
   */
  static CodeState = {
    COMPILED: 0,
233
    IGNITION: 1,
234
    BASELINE: 2,
235 236
    TURBOPROP: 4,
    TURBOFAN: 5,
237 238
  }

239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
  static VMState = {
    JS: 0,
    GC: 1,
    PARSER: 2,
    BYTECODE_COMPILER: 3,
    // TODO(cbruni): add BASELINE_COMPILER
    COMPILER: 4,
    OTHER: 5,
    EXTERNAL: 6,
    IDLE: 7,
  }

  static CodeType = {
    CPP: 0,
    SHARED_LIB: 1
  }

256 257 258 259 260 261 262 263 264
  /**
   * Parser for dynamic code optimization state.
   */
  static parseState(s) {
    switch (s) {
      case '':
        return this.CodeState.COMPILED;
      case '~':
        return this.CodeState.IGNITION;
265
      case '^':
266
        return this.CodeState.BASELINE;
267
      case '+':
268 269 270 271 272
        return this.CodeState.TURBOPROP;
      case '*':
        return this.CodeState.TURBOFAN;
    }
    throw new Error(`unknown code state: ${s}`);
273
  }
274

275 276 277 278 279
  static getKindFromState(state) {
    if (state === this.CodeState.COMPILED) {
      return "Builtin";
    } else if (state === this.CodeState.IGNITION) {
      return "Unopt";
280 281
    } else if (state === this.CodeState.BASELINE) {
      return "Baseline";
282 283 284 285 286 287 288 289
    } else if (state === this.CodeState.TURBOPROP) {
      return "Turboprop";
    } else if (state === this.CodeState.TURBOFAN) {
      return "Opt";
    }
    throw new Error(`unknown code state: ${state}`);
  }

290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
  static vmStateString(state) {
    switch (state) {
      case this.VMState.JS:
        return 'JS';
      case this.VMState.GC:
        return 'GC';
      case this.VMState.PARSER:
        return 'Parse';
      case this.VMState.BYTECODE_COMPILER:
        return 'Compile Bytecode';
      case this.VMState.COMPILER:
        return 'Compile';
      case this.VMState.OTHER:
        return 'Other';
      case this.VMState.EXTERNAL:
        return 'External';
      case this.VMState.IDLE:
        return 'Idle';
    }
    return 'unknown';
  }

312 313 314 315 316 317 318 319 320 321 322 323
  /**
   * Called whenever the specified operation has failed finding a function
   * containing the specified address. Should be overriden by subclasses.
   * See the Profile.Operation enum for the list of
   * possible operations.
   *
   * @param {number} operation Operation.
   * @param {number} addr Address of the unknown code.
   * @param {number} opt_stackPos If an unknown address is encountered
   *     during stack strace processing, specifies a position of the frame
   *     containing the address.
   */
324
  handleUnknownCode(operation, addr, opt_stackPos) { }
325 326 327 328 329 330 331 332 333

  /**
   * Registers a library.
   *
   * @param {string} name Code entry name.
   * @param {number} startAddr Starting address.
   * @param {number} endAddr Ending address.
   */
  addLibrary(name, startAddr, endAddr) {
334
    const entry = new CodeEntry(endAddr - startAddr, name, 'SHARED_LIB');
335 336 337
    this.codeMap_.addLibrary(startAddr, entry);
    return entry;
  }
338

339 340 341 342 343 344 345 346
  /**
   * Registers statically compiled code entry.
   *
   * @param {string} name Code entry name.
   * @param {number} startAddr Starting address.
   * @param {number} endAddr Ending address.
   */
  addStaticCode(name, startAddr, endAddr) {
347
    const entry = new CodeEntry(endAddr - startAddr, name, 'CPP');
348 349 350
    this.codeMap_.addStaticCode(startAddr, entry);
    return entry;
  }
351

352 353 354 355 356 357 358 359 360
  /**
   * Registers dynamic (JIT-compiled) code entry.
   *
   * @param {string} type Code entry type.
   * @param {string} name Code entry name.
   * @param {number} start Starting address.
   * @param {number} size Code entry size.
   */
  addCode(type, name, timestamp, start, size) {
361
    const entry = new DynamicCodeEntry(size, type, name);
362 363 364
    this.codeMap_.addCode(start, entry);
    return entry;
  }
365

366 367 368 369 370 371 372 373 374 375 376 377 378
  /**
   * Registers dynamic (JIT-compiled) code entry.
   *
   * @param {string} type Code entry type.
   * @param {string} name Code entry name.
   * @param {number} start Starting address.
   * @param {number} size Code entry size.
   * @param {number} funcAddr Shared function object address.
   * @param {Profile.CodeState} state Optimization state.
   */
  addFuncCode(type, name, timestamp, start, size, funcAddr, state) {
    // As code and functions are in the same address space,
    // it is safe to put them in a single code map.
379
    let func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
380 381 382 383 384 385 386
    if (!func) {
      func = new FunctionEntry(name);
      this.codeMap_.addCode(funcAddr, func);
    } else if (func.name !== name) {
      // Function object has been overwritten with a new one.
      func.name = name;
    }
387
    let entry = this.codeMap_.findDynamicEntryByStartAddress(start);
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
    if (entry) {
      if (entry.size === size && entry.func === func) {
        // Entry state has changed.
        entry.state = state;
      } else {
        this.codeMap_.deleteCode(start);
        entry = null;
      }
    }
    if (!entry) {
      entry = new DynamicFuncCodeEntry(size, type, func, state);
      this.codeMap_.addCode(start, entry);
    }
    return entry;
  }
403

404 405 406 407 408 409 410 411 412 413 414 415 416
  /**
   * Reports about moving of a dynamic code entry.
   *
   * @param {number} from Current code entry address.
   * @param {number} to New code entry address.
   */
  moveCode(from, to) {
    try {
      this.codeMap_.moveCode(from, to);
    } catch (e) {
      this.handleUnknownCode(Profile.Operation.MOVE, from);
    }
  }
417

418
  deoptCode(timestamp, code, inliningId, scriptOffset, bailoutType,
419
    sourcePositionText, deoptReasonText) {
420
  }
421 422 423 424 425 426 427 428

  /**
   * Reports about deletion of a dynamic code entry.
   *
   * @param {number} start Starting address.
   */
  deleteCode(start) {
    try {
429
      this.codeMap_.deleteCode(start);
430 431
    } catch (e) {
      this.handleUnknownCode(Profile.Operation.DELETE, start);
432 433 434
    }
  }

435 436 437
  /**
   * Adds source positions for given code.
   */
438
  addSourcePositions(start, scriptId, startPos, endPos, sourcePositionTable,
439
        inliningPositions, inlinedFunctions) {
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
    const script = this.getOrCreateScript(scriptId);
    const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
    if (!entry) return;
    // Resolve the inlined functions list.
    if (inlinedFunctions.length > 0) {
      inlinedFunctions = inlinedFunctions.substring(1).split("S");
      for (let i = 0; i < inlinedFunctions.length; i++) {
        const funcAddr = parseInt(inlinedFunctions[i]);
        const func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
        if (!func || func.funcId === undefined) {
          // TODO: fix
          console.warn(`Could not find function ${inlinedFunctions[i]}`);
          inlinedFunctions[i] = null;
        } else {
          inlinedFunctions[i] = func.funcId;
        }
      }
    } else {
      inlinedFunctions = [];
    }

461
    this.getOrCreateSourceInfo(entry).setSourcePositionInfo(
462 463
      script, startPos, endPos, sourcePositionTable, inliningPositions,
      inlinedFunctions);
464 465
  }

466 467 468 469 470 471 472 473 474 475
  addDisassemble(start, kind, disassemble) {
    const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
    if (!entry) return;
    this.getOrCreateSourceInfo(entry).setDisassemble(disassemble);
  }

  getOrCreateSourceInfo(entry) {
    return entry.source ?? (entry.source = new SourceInfo());
  }

476
  addScriptSource(id, url, source) {
477 478
    const script = this.getOrCreateScript(id);
    script.update(url, source);
479
    this.urlToScript_.set(url, script);
480 481
  }

482 483 484 485 486 487 488 489 490
  getOrCreateScript(id) {
    let script = this.scripts_[id];
    if (!script) {
      script = new Script(id);
      this.scripts_[id] = script;
    }
    return script;
  }

491 492
  getScript(url) {
    return this.urlToScript_.get(url);
493 494
  }

495 496 497 498 499 500 501 502 503 504 505
  /**
   * Reports about moving of a dynamic code entry.
   *
   * @param {number} from Current code entry address.
   * @param {number} to New code entry address.
   */
  moveFunc(from, to) {
    if (this.codeMap_.findDynamicEntryByStartAddress(from)) {
      this.codeMap_.moveCode(from, to);
    }
  }
506

507 508 509 510 511 512 513 514
  /**
   * Retrieves a code entry by an address.
   *
   * @param {number} addr Entry address.
   */
  findEntry(addr) {
    return this.codeMap_.findEntry(addr);
  }
515

516 517 518 519 520 521 522
  /**
   * Records a tick event. Stack must contain a sequence of
   * addresses starting with the program counter value.
   *
   * @param {Array<number>} stack Stack sample.
   */
  recordTick(time_ns, vmState, stack) {
523 524 525 526
    const {nameStack, entryStack} = this.resolveAndFilterFuncs_(stack);
    this.bottomUpTree_.addPath(nameStack);
    nameStack.reverse();
    this.topDownTree_.addPath(nameStack);
527
    return entryStack;
528
  }
529

530 531 532 533 534 535 536
  /**
   * Translates addresses into function names and filters unneeded
   * functions.
   *
   * @param {Array<number>} stack Stack sample.
   */
  resolveAndFilterFuncs_(stack) {
537 538
    const nameStack = [];
    const entryStack = [];
539 540 541
    let last_seen_c_function = '';
    let look_for_first_c_function = false;
    for (let i = 0; i < stack.length; ++i) {
542 543
      const pc = stack[i];
      const entry = this.codeMap_.findEntry(pc);
544
      if (entry) {
545
        entryStack.push(entry);
546
        const name = entry.getName();
547 548 549 550 551 552 553
        if (i === 0 && (entry.type === 'CPP' || entry.type === 'SHARED_LIB')) {
          look_for_first_c_function = true;
        }
        if (look_for_first_c_function && entry.type === 'CPP') {
          last_seen_c_function = name;
        }
        if (!this.skipThisFunction(name)) {
554
          nameStack.push(name);
555 556
        }
      } else {
557 558 559
        this.handleUnknownCode(Profile.Operation.TICK, pc, i);
        if (i === 0) nameStack.push("UNKNOWN");
        entryStack.push(pc);
560
      }
561 562
      if (look_for_first_c_function && i > 0 &&
          (!entry || entry.type !== 'CPP') && last_seen_c_function !== '') {
563 564 565 566 567
        if (this.c_entries_[last_seen_c_function] === undefined) {
          this.c_entries_[last_seen_c_function] = 0;
        }
        this.c_entries_[last_seen_c_function]++;
        look_for_first_c_function = false;  // Found it, we're done.
568 569
      }
    }
570
    return {nameStack, entryStack};
571 572
  }

573 574 575 576 577 578 579 580
  /**
   * Performs a BF traversal of the top down call graph.
   *
   * @param {function(CallTreeNode)} f Visitor function.
   */
  traverseTopDownTree(f) {
    this.topDownTree_.traverse(f);
  }
581

582 583 584 585 586 587 588 589
  /**
   * Performs a BF traversal of the bottom up call graph.
   *
   * @param {function(CallTreeNode)} f Visitor function.
   */
  traverseBottomUpTree(f) {
    this.bottomUpTree_.traverse(f);
  }
590

591 592 593 594 595 596 597 598 599
  /**
   * Calculates a top down profile for a node with the specified label.
   * If no name specified, returns the whole top down calls tree.
   *
   * @param {string} opt_label Node label.
   */
  getTopDownProfile(opt_label) {
    return this.getTreeProfile_(this.topDownTree_, opt_label);
  }
600

601 602 603 604 605 606 607 608
  /**
   * Calculates a bottom up profile for a node with the specified label.
   * If no name specified, returns the whole bottom up calls tree.
   *
   * @param {string} opt_label Node label.
   */
  getBottomUpProfile(opt_label) {
    return this.getTreeProfile_(this.bottomUpTree_, opt_label);
609 610
  }

611 612 613 614 615 616 617 618 619 620 621
  /**
   * Helper function for calculating a tree profile.
   *
   * @param {Profile.CallTree} tree Call tree.
   * @param {string} opt_label Node label.
   */
  getTreeProfile_(tree, opt_label) {
    if (!opt_label) {
      tree.computeTotalWeights();
      return tree;
    } else {
622
      const subTree = tree.cloneSubtree(opt_label);
623 624 625 626
      subTree.computeTotalWeights();
      return subTree;
    }
  }
627

628 629 630 631 632 633 634
  /**
   * Calculates a flat profile of callees starting from a node with
   * the specified label. If no name specified, starts from the root.
   *
   * @param {string} opt_label Starting node label.
   */
  getFlatProfile(opt_label) {
635 636 637
    const counters = new CallTree();
    const rootLabel = opt_label || CallTree.ROOT_NODE_LABEL;
    const precs = {};
638
    precs[rootLabel] = 0;
639
    const root = counters.findOrAddChild(rootLabel);
640 641 642 643 644 645 646

    this.topDownTree_.computeTotalWeights();
    this.topDownTree_.traverseInDepth(
      function onEnter(node) {
        if (!(node.label in precs)) {
          precs[node.label] = 0;
        }
647
        const nodeLabelIsRootLabel = node.label == rootLabel;
648 649 650 651 652
        if (nodeLabelIsRootLabel || precs[rootLabel] > 0) {
          if (precs[rootLabel] == 0) {
            root.selfWeight += node.selfWeight;
            root.totalWeight += node.totalWeight;
          } else {
653
            const rec = root.findOrAddChild(node.label);
654 655 656 657
            rec.selfWeight += node.selfWeight;
            if (nodeLabelIsRootLabel || precs[node.label] == 0) {
              rec.totalWeight += node.totalWeight;
            }
658
          }
659
          precs[node.label]++;
660
        }
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679
      },
      function onExit(node) {
        if (node.label == rootLabel || precs[rootLabel] > 0) {
          precs[node.label]--;
        }
      },
      null);

    if (!opt_label) {
      // If we have created a flat profile for the whole program, we don't
      // need an explicit root in it. Thus, replace the counters tree
      // root with the node corresponding to the whole program.
      counters.root_ = root;
    } else {
      // Propagate weights so percents can be calculated correctly.
      counters.getRoot().selfWeight = root.selfWeight;
      counters.getRoot().totalWeight = root.totalWeight;
    }
    return counters;
680 681
  }

682
  getCEntryProfile() {
683 684 685 686
    const result = [new CEntryNode("TOTAL", 0)];
    let total_ticks = 0;
    for (let f in this.c_entries_) {
      const ticks = this.c_entries_[f];
687 688 689 690
      total_ticks += ticks;
      result.push(new CEntryNode(f, ticks));
    }
    result[0].ticks = total_ticks;  // Sorting will keep this at index 0.
691
    result.sort((n1, n2) => n2.ticks - n1.ticks || (n2.name < n1.name ? -1 : 1));
692
    return result;
693 694 695
  }


696 697 698 699
  /**
   * Cleans up function entries that are not referenced by code entries.
   */
  cleanUpFuncEntries() {
700 701 702
    const referencedFuncEntries = [];
    const entries = this.codeMap_.getAllDynamicEntriesWithAddresses();
    for (let i = 0, l = entries.length; i < l; ++i) {
703 704 705
      if (entries[i][1].constructor === FunctionEntry) {
        entries[i][1].used = false;
      }
706
    }
707
    for (let i = 0, l = entries.length; i < l; ++i) {
708 709 710
      if ("func" in entries[i][1]) {
        entries[i][1].func.used = true;
      }
711
    }
712
    for (let i = 0, l = entries.length; i < l; ++i) {
713 714 715 716
      if (entries[i][1].constructor === FunctionEntry &&
        !entries[i][1].used) {
        this.codeMap_.deleteCode(entries[i][0]);
      }
717 718
    }
  }
719 720 721 722 723 724 725 726
}

class CEntryNode {
  constructor(name, ticks) {
    this.name = name;
    this.ticks = ticks;
  }
}
727 728 729 730 731 732 733 734 735 736


/**
 * Creates a dynamic code entry.
 *
 * @param {number} size Code size.
 * @param {string} type Code type.
 * @param {string} name Function name.
 * @constructor
 */
737 738 739 740
class DynamicCodeEntry extends CodeEntry {
  constructor(size, type, name) {
    super(size, name, type);
  }
741

742 743 744
  getName() {
    return this.type + ': ' + this.name;
  }
745

746 747 748 749 750 751
  /**
   * Returns raw node name (without type decoration).
   */
  getRawName() {
    return this.name;
  }
752

753 754 755
  isJSFunction() {
    return false;
  }
756

757 758 759 760
  toString() {
    return this.getName() + ': ' + this.size.toString(16);
  }
}
761 762 763 764 765 766 767


/**
 * Creates a dynamic code entry.
 *
 * @param {number} size Code size.
 * @param {string} type Code type.
768
 * @param {FunctionEntry} func Shared function entry.
769 770 771
 * @param {Profile.CodeState} state Code optimization state.
 * @constructor
 */
772 773 774 775
class DynamicFuncCodeEntry extends CodeEntry {
  constructor(size, type, func, state) {
    super(size, '', type);
    this.func = func;
776
    func.addDynamicCode(this);
777 778
    this.state = state;
  }
779

780 781 782 783
  get functionName() {
    return this.func.functionName;
  }

784 785 786 787
  getSourceCode() {
    return this.source?.getSourceCode();
  }

788
  static STATE_PREFIX = ["", "~", "^", "-", "+", "*"];
789 790 791
  getState() {
    return DynamicFuncCodeEntry.STATE_PREFIX[this.state];
  }
792

793
  getName() {
794
    const name = this.func.getName();
795 796
    return this.type + ': ' + this.getState() + name;
  }
797

798 799 800 801 802 803
  /**
   * Returns raw node name (without type decoration).
   */
  getRawName() {
    return this.func.getName();
  }
804

805 806 807
  isJSFunction() {
    return true;
  }
808

809 810 811 812
  toString() {
    return this.getName() + ': ' + this.size.toString(16);
  }
}
813 814 815 816 817 818 819

/**
 * Creates a shared function object entry.
 *
 * @param {string} name Function name.
 * @constructor
 */
820
class FunctionEntry extends CodeEntry {
821

822 823 824
  // Contains the list of generated code for this function.
  _codeEntries = new Set();

825 826
  constructor(name) {
    super(0, name);
827 828
    const index = name.lastIndexOf(' ');
    this.functionName = 1 <= index ? name.substring(0, index) : '<anonymous>';
829
  }
830

831 832 833 834 835 836 837 838 839 840 841 842
  addDynamicCode(code) {
    if (code.func != this) {
      throw new Error("Adding dynamic code to wrong function");
    }
    this._codeEntries.add(code);
  }

  getSourceCode() {
    // All code entries should map to the same source positions.
    return this._codeEntries.values().next().value.getSourceCode();
  }

843 844 845 846
  get codeEntries() {
    return this._codeEntries;
  }

847 848 849 850
  /**
   * Returns node name.
   */
  getName() {
851
    let name = this.name;
852
    if (name.length == 0) {
853
      return '<anonymous>';
854 855
    } else if (name.charAt(0) == ' ') {
      // An anonymous function with location: " aaa.js:10".
856
      return `<anonymous>${name}`;
857 858 859 860
    }
    return name;
  }
}
861 862 863 864 865 866

/**
 * Constructs a call graph.
 *
 * @constructor
 */
867 868 869 870 871 872 873 874 875 876 877 878 879 880
class CallTree {
  root_ = new CallTreeNode(CallTree.ROOT_NODE_LABEL);
  totalsComputed_ = false;

  /**
   * The label of the root node.
   */
  static ROOT_NODE_LABEL = '';

  /**
   * Returns the tree root.
   */
  getRoot() {
    return this.root_;
881 882
  }

883 884 885 886 887 888 889 890
  /**
   * Adds the specified call path, constructing nodes as necessary.
   *
   * @param {Array<string>} path Call path.
   */
  addPath(path) {
    if (path.length == 0) {
      return;
891
    }
892 893
    let curr = this.root_;
    for (let i = 0; i < path.length; ++i) {
894 895 896 897
      curr = curr.findOrAddChild(path[i]);
    }
    curr.selfWeight++;
    this.totalsComputed_ = false;
898 899
  }

900 901 902 903 904 905 906 907 908 909
  /**
   * Finds an immediate child of the specified parent with the specified
   * label, creates a child node if necessary. If a parent node isn't
   * specified, uses tree root.
   *
   * @param {string} label Child node label.
   */
  findOrAddChild(label) {
    return this.root_.findOrAddChild(label);
  }
910

911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927
  /**
   * Creates a subtree by cloning and merging all subtrees rooted at nodes
   * with a given label. E.g. cloning the following call tree on label 'A'
   * will give the following result:
   *
   *           <A>--<B>                                     <B>
   *          /                                            /
   *     <root>             == clone on 'A' ==>  <root>--<A>
   *          \                                            \
   *           <C>--<A>--<D>                                <D>
   *
   * And <A>'s selfWeight will be the sum of selfWeights of <A>'s from the
   * source call tree.
   *
   * @param {string} label The label of the new root node.
   */
  cloneSubtree(label) {
928
    const subTree = new CallTree();
929 930 931 932
    this.traverse((node, parent) => {
      if (!parent && node.label != label) {
        return null;
      }
933
      const child = (parent ? parent : subTree).findOrAddChild(node.label);
934 935
      child.selfWeight += node.selfWeight;
      return child;
936
    });
937
    return subTree;
938 939
  }

940 941 942 943 944 945 946 947
  /**
   * Computes total weights in the call graph.
   */
  computeTotalWeights() {
    if (this.totalsComputed_) return;
    this.root_.computeTotalWeight();
    this.totalsComputed_ = true;
  }
948

949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964
  /**
   * Traverses the call graph in preorder. This function can be used for
   * building optionally modified tree clones. This is the boilerplate code
   * for this scenario:
   *
   * callTree.traverse(function(node, parentClone) {
   *   var nodeClone = cloneNode(node);
   *   if (parentClone)
   *     parentClone.addChild(nodeClone);
   *   return nodeClone;
   * });
   *
   * @param {function(CallTreeNode, *)} f Visitor function.
   *    The second parameter is the result of calling 'f' on the parent node.
   */
  traverse(f) {
965
    const pairsToProcess = new ConsArray();
966 967
    pairsToProcess.concat([{ node: this.root_, param: null }]);
    while (!pairsToProcess.atEnd()) {
968 969 970 971
      const pair = pairsToProcess.next();
      const node = pair.node;
      const newParam = f(node, pair.param);
      const morePairsToProcess = [];
972 973 974 975 976
      node.forEachChild((child) => {
        morePairsToProcess.push({ node: child, param: newParam });
      });
      pairsToProcess.concat(morePairsToProcess);
    }
977
  }
978 979 980 981 982 983 984 985 986

  /**
   * Performs an indepth call graph traversal.
   *
   * @param {function(CallTreeNode)} enter A function called
   *     prior to visiting node's children.
   * @param {function(CallTreeNode)} exit A function called
   *     after visiting node's children.
   */
987
  traverseInDepth(enter, exit) {
988 989 990 991 992 993 994 995
    function traverse(node) {
      enter(node);
      node.forEachChild(traverse);
      exit(node);
    }
    traverse(this.root_);
  }
}
996 997 998 999 1000 1001


/**
 * Constructs a call graph node.
 *
 * @param {string} label Node label.
1002
 * @param {CallTreeNode} opt_parent Node parent.
1003
 */
1004
class CallTreeNode {
1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022
  /**
   * Node self weight (how many times this node was the last node in
   * a call path).
   * @type {number}
   */
  selfWeight = 0;

  /**
   * Node total weight (includes weights of all children).
   * @type {number}
   */
  totalWeight = 0;
  children = {};

  constructor(label, opt_parent) {
    this.label = label;
    this.parent = opt_parent;
  }
1023 1024


1025 1026 1027 1028 1029 1030
  /**
   * Adds a child node.
   *
   * @param {string} label Child node label.
   */
  addChild(label) {
1031
    const child = new CallTreeNode(label, this);
1032 1033 1034
    this.children[label] = child;
    return child;
  }
1035

1036 1037 1038 1039
  /**
   * Computes node's total weight.
   */
  computeTotalWeight() {
1040
    let totalWeight = this.selfWeight;
1041 1042 1043 1044
    this.forEachChild(function (child) {
      totalWeight += child.computeTotalWeight();
    });
    return this.totalWeight = totalWeight;
1045
  }
1046

1047 1048 1049 1050
  /**
   * Returns all node's children as an array.
   */
  exportChildren() {
1051
    const result = [];
1052 1053 1054
    this.forEachChild(function (node) { result.push(node); });
    return result;
  }
1055

1056 1057 1058 1059 1060 1061 1062
  /**
   * Finds an immediate child with the specified label.
   *
   * @param {string} label Child node label.
   */
  findChild(label) {
    return this.children[label] || null;
1063 1064
  }

1065 1066 1067 1068 1069 1070 1071 1072 1073
  /**
   * Finds an immediate child with the specified label, creates a child
   * node if necessary.
   *
   * @param {string} label Child node label.
   */
  findOrAddChild(label) {
    return this.findChild(label) || this.addChild(label);
  }
1074

1075 1076 1077 1078 1079 1080
  /**
   * Calls the specified function for every child.
   *
   * @param {function(CallTreeNode)} f Visitor function.
   */
  forEachChild(f) {
1081
    for (let c in this.children) {
1082 1083
      f(this.children[c]);
    }
1084 1085
  }

1086 1087 1088 1089 1090 1091
  /**
   * Walks up from the current node up to the call tree root.
   *
   * @param {function(CallTreeNode)} f Visitor function.
   */
  walkUpToRoot(f) {
1092
    for (let curr = this; curr != null; curr = curr.parent) {
1093 1094 1095
      f(curr);
    }
  }
1096

1097 1098 1099 1100 1101 1102 1103
  /**
   * Tries to find a node with the specified path.
   *
   * @param {Array<string>} labels The path.
   * @param {function(CallTreeNode)} opt_f Visitor function.
   */
  descendToChild(labels, opt_f) {
1104 1105 1106
    let curr = this;
    for (let pos = 0; pos < labels.length && curr != null; pos++) {
      const child = curr.findChild(labels[pos]);
1107 1108 1109 1110
      if (opt_f) {
        opt_f(child, pos);
      }
      curr = child;
1111
    }
1112
    return curr;
1113
  }
1114
}
1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125

export function JsonProfile() {
  this.codeMap_ = new CodeMap();
  this.codeEntries_ = [];
  this.functionEntries_ = [];
  this.ticks_ = [];
  this.scripts_ = [];
}

JsonProfile.prototype.addLibrary = function (
  name, startAddr, endAddr) {
1126
  const entry = new CodeEntry(
1127 1128 1129 1130 1131 1132 1133 1134 1135 1136
    endAddr - startAddr, name, 'SHARED_LIB');
  this.codeMap_.addLibrary(startAddr, entry);

  entry.codeId = this.codeEntries_.length;
  this.codeEntries_.push({ name: entry.name, type: entry.type });
  return entry;
};

JsonProfile.prototype.addStaticCode = function (
  name, startAddr, endAddr) {
1137
  const entry = new CodeEntry(
1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
    endAddr - startAddr, name, 'CPP');
  this.codeMap_.addStaticCode(startAddr, entry);

  entry.codeId = this.codeEntries_.length;
  this.codeEntries_.push({ name: entry.name, type: entry.type });
  return entry;
};

JsonProfile.prototype.addCode = function (
  kind, name, timestamp, start, size) {
  let codeId = this.codeEntries_.length;
  // Find out if we have a static code entry for the code. If yes, we will
  // make sure it is written to the JSON file just once.
  let staticEntry = this.codeMap_.findAddress(start);
  if (staticEntry && staticEntry.entry.type === 'CPP') {
    codeId = staticEntry.entry.codeId;
  }

1156
  const entry = new CodeEntry(size, name, 'CODE');
1157 1158 1159 1160 1161 1162 1163
  this.codeMap_.addCode(start, entry);

  entry.codeId = codeId;
  this.codeEntries_[codeId] = {
    name: entry.name,
    timestamp: timestamp,
    type: entry.type,
1164
    kind: kind,
1165 1166 1167 1168 1169 1170 1171 1172 1173
  };

  return entry;
};

JsonProfile.prototype.addFuncCode = function (
  kind, name, timestamp, start, size, funcAddr, state) {
  // As code and functions are in the same address space,
  // it is safe to put them in a single code map.
1174
  let func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
1175
  if (!func) {
1176
    func = new CodeEntry(0, name, 'SFI');
1177 1178 1179
    this.codeMap_.addCode(funcAddr, func);

    func.funcId = this.functionEntries_.length;
1180
    this.functionEntries_.push({ name, codes: [] });
1181 1182 1183 1184 1185
  } else if (func.name !== name) {
    // Function object has been overwritten with a new one.
    func.name = name;

    func.funcId = this.functionEntries_.length;
1186
    this.functionEntries_.push({ name, codes: [] });
1187 1188
  }
  // TODO(jarin): Insert the code object into the SFI's code list.
1189
  let entry = this.codeMap_.findDynamicEntryByStartAddress(start);
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
  if (entry) {
    if (entry.size === size && entry.func === func) {
      // Entry state has changed.
      entry.state = state;
    } else {
      this.codeMap_.deleteCode(start);
      entry = null;
    }
  }
  if (!entry) {
1200
    entry = new CodeEntry(size, name, 'JS');
1201 1202 1203 1204 1205 1206
    this.codeMap_.addCode(start, entry);

    entry.codeId = this.codeEntries_.length;

    this.functionEntries_[func.funcId].codes.push(entry.codeId);

1207
    kind = Profile.getKindFromState(state);
1208 1209 1210 1211 1212 1213

    this.codeEntries_.push({
      name: entry.name,
      type: entry.type,
      kind: kind,
      func: func.funcId,
1214
      tm: timestamp,
1215 1216 1217 1218 1219 1220 1221 1222 1223
    });
  }
  return entry;
};

JsonProfile.prototype.moveCode = function (from, to) {
  try {
    this.codeMap_.moveCode(from, to);
  } catch (e) {
1224
    printErr(`Move: unknown source ${from}`);
1225 1226 1227 1228 1229 1230
  }
};

JsonProfile.prototype.addSourcePositions = function (
  start, script, startPos, endPos, sourcePositions, inliningPositions,
  inlinedFunctions) {
1231
  const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
1232
  if (!entry) return;
1233
  const codeId = entry.codeId;
1234 1235 1236 1237

  // Resolve the inlined functions list.
  if (inlinedFunctions.length > 0) {
    inlinedFunctions = inlinedFunctions.substring(1).split("S");
1238 1239 1240
    for (let i = 0; i < inlinedFunctions.length; i++) {
      const funcAddr = parseInt(inlinedFunctions[i]);
      const func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
1241
      if (!func || func.funcId === undefined) {
1242
        printErr(`Could not find function ${inlinedFunctions[i]}`);
1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262
        inlinedFunctions[i] = null;
      } else {
        inlinedFunctions[i] = func.funcId;
      }
    }
  } else {
    inlinedFunctions = [];
  }

  this.codeEntries_[entry.codeId].source = {
    script: script,
    start: startPos,
    end: endPos,
    positions: sourcePositions,
    inlined: inliningPositions,
    fns: inlinedFunctions
  };
};

JsonProfile.prototype.addScriptSource = function (id, url, source) {
1263 1264 1265
  const script = new Script(id);
  script.update(url, source);
  this.scripts_[id] = script;
1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
};

JsonProfile.prototype.deoptCode = function (
  timestamp, code, inliningId, scriptOffset, bailoutType,
  sourcePositionText, deoptReasonText) {
  let entry = this.codeMap_.findDynamicEntryByStartAddress(code);
  if (entry) {
    let codeId = entry.codeId;
    if (!this.codeEntries_[codeId].deopt) {
      // Only add the deopt if there was no deopt before.
      // The subsequent deoptimizations should be lazy deopts for
      // other on-stack activations.
      this.codeEntries_[codeId].deopt = {
        tm: timestamp,
        inliningId: inliningId,
        scriptOffset: scriptOffset,
        posText: sourcePositionText,
        reason: deoptReasonText,
1284
        bailoutType: bailoutType,
1285 1286 1287 1288 1289 1290 1291 1292 1293
      };
    }
  }
};

JsonProfile.prototype.deleteCode = function (start) {
  try {
    this.codeMap_.deleteCode(start);
  } catch (e) {
1294
    printErr(`Delete: unknown address ${start}`);
1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310
  }
};

JsonProfile.prototype.moveFunc = function (from, to) {
  if (this.codeMap_.findDynamicEntryByStartAddress(from)) {
    this.codeMap_.moveCode(from, to);
  }
};

JsonProfile.prototype.findEntry = function (addr) {
  return this.codeMap_.findEntry(addr);
};

JsonProfile.prototype.recordTick = function (time_ns, vmState, stack) {
  // TODO(jarin) Resolve the frame-less case (when top of stack is
  // known code).
1311 1312 1313
  const processedStack = [];
  for (let i = 0; i < stack.length; i++) {
    const resolved = this.codeMap_.findAddress(stack[i]);
1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340
    if (resolved) {
      processedStack.push(resolved.entry.codeId, resolved.offset);
    } else {
      processedStack.push(-1, stack[i]);
    }
  }
  this.ticks_.push({ tm: time_ns, vm: vmState, s: processedStack });
};

function writeJson(s) {
  write(JSON.stringify(s, null, 2));
}

JsonProfile.prototype.writeJson = function () {
  // Write out the JSON in a partially manual way to avoid creating too-large
  // strings in one JSON.stringify call when there are a lot of ticks.
  write('{\n')

  write('  "code": ');
  writeJson(this.codeEntries_);
  write(',\n');

  write('  "functions": ');
  writeJson(this.functionEntries_);
  write(',\n');

  write('  "ticks": [\n');
1341
  for (let i = 0; i < this.ticks_.length; i++) {
1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356
    write('    ');
    writeJson(this.ticks_[i]);
    if (i < this.ticks_.length - 1) {
      write(',\n');
    } else {
      write('\n');
    }
  }
  write('  ],\n');

  write('  "scripts": ');
  writeJson(this.scripts_);

  write('}\n');
};