src/v8/tools/profile.js

   1 // Copyright 2009 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 /**
  30  * Creates a profile object for processing profiling-related events
  31  * and calculating function execution times.
  32  *
  33  * @constructor
  34  */
  35 function Profile() {
  36   this.codeMap_ = new CodeMap();
  37   this.topDownTree_ = new CallTree();
  38   this.bottomUpTree_ = new CallTree();
  39 };
  40
  41
  42 /**
  43  * Returns whether a function with the specified name must be skipped.
  44  * Should be overriden by subclasses.
  45  *
  46  * @param {string} name Function name.
  47  */
  48 Profile.prototype.skipThisFunction = function(name) {
  49   return false;
  50 };
  51
  52
  53 /**
  54  * Enum for profiler operations that involve looking up existing
  55  * code entries.
  56  *
  57  * @enum {number}
  58  */
  59 Profile.Operation = {
  60   MOVE: 0,
  61   DELETE: 1,
  62   TICK: 2
  63 };
  64
  65
  66 /**
  67  * Enum for code state regarding its dynamic optimization.
  68  *
  69  * @enum {number}
  70  */
  71 Profile.CodeState = {
  72   COMPILED: 0,
  73   OPTIMIZABLE: 1,
  74   OPTIMIZED: 2
  75 };
  76
  77
  78 /**
  79  * Called whenever the specified operation has failed finding a function
  80  * containing the specified address. Should be overriden by subclasses.
  81  * See the Profile.Operation enum for the list of
  82  * possible operations.
  83  *
  84  * @param {number} operation Operation.
  85  * @param {number} addr Address of the unknown code.
  86  * @param {number} opt_stackPos If an unknown address is encountered
  87  *     during stack strace processing, specifies a position of the frame
  88  *     containing the address.
  89  */
  90 Profile.prototype.handleUnknownCode = function(
  91     operation, addr, opt_stackPos) {
  92 };
  93
  94
  95 /**
  96  * Registers a library.
  97  *
  98  * @param {string} name Code entry name.
  99  * @param {number} startAddr Starting address.
 100  * @param {number} endAddr Ending address.
 101  */
 102 Profile.prototype.addLibrary = function(
 103     name, startAddr, endAddr) {
 104   var entry = new CodeMap.CodeEntry(
 105       endAddr - startAddr, name);
 106   this.codeMap_.addLibrary(startAddr, entry);
 107   return entry;
 108 };
 109
 110
 111 /**
 112  * Registers statically compiled code entry.
 113  *
 114  * @param {string} name Code entry name.
 115  * @param {number} startAddr Starting address.
 116  * @param {number} endAddr Ending address.
 117  */
 118 Profile.prototype.addStaticCode = function(
 119     name, startAddr, endAddr) {
 120   var entry = new CodeMap.CodeEntry(
 121       endAddr - startAddr, name);
 122   this.codeMap_.addStaticCode(startAddr, entry);
 123   return entry;
 124 };
 125
 126
 127 /**
 128  * Registers dynamic (JIT-compiled) code entry.
 129  *
 130  * @param {string} type Code entry type.
 131  * @param {string} name Code entry name.
 132  * @param {number} start Starting address.
 133  * @param {number} size Code entry size.
 134  */
 135 Profile.prototype.addCode = function(
 136     type, name, start, size) {
 137   var entry = new Profile.DynamicCodeEntry(size, type, name);
 138   this.codeMap_.addCode(start, entry);
 139   return entry;
 140 };
 141
 142
 143 /**
 144  * Registers dynamic (JIT-compiled) code entry.
 145  *
 146  * @param {string} type Code entry type.
 147  * @param {string} name Code entry name.
 148  * @param {number} start Starting address.
 149  * @param {number} size Code entry size.
 150  * @param {number} funcAddr Shared function object address.
 151  * @param {Profile.CodeState} state Optimization state.
 152  */
 153 Profile.prototype.addFuncCode = function(
 154     type, name, start, size, funcAddr, state) {
 155   // As code and functions are in the same address space,
 156   // it is safe to put them in a single code map.
 157   var func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
 158   if (!func) {
 159     func = new Profile.FunctionEntry(name);
 160     this.codeMap_.addCode(funcAddr, func);
 161   } else if (func.name !== name) {
 162     // Function object has been overwritten with a new one.
 163     func.name = name;
 164   }
 165   var entry = this.codeMap_.findDynamicEntryByStartAddress(start);
 166   if (entry) {
 167     if (entry.size === size && entry.func === func) {
 168       // Entry state has changed.
 169       entry.state = state;
 170     }
 171   } else {
 172     entry = new Profile.DynamicFuncCodeEntry(size, type, func, state);
 173     this.codeMap_.addCode(start, entry);
 174   }
 175   return entry;
 176 };
 177
 178
 179 /**
 180  * Reports about moving of a dynamic code entry.
 181  *
 182  * @param {number} from Current code entry address.
 183  * @param {number} to New code entry address.
 184  */
 185 Profile.prototype.moveCode = function(from, to) {
 186   try {
 187     this.codeMap_.moveCode(from, to);
 188   } catch (e) {
 189     this.handleUnknownCode(Profile.Operation.MOVE, from);
 190   }
 191 };
 192
 193
 194 /**
 195  * Reports about deletion of a dynamic code entry.
 196  *
 197  * @param {number} start Starting address.
 198  */
 199 Profile.prototype.deleteCode = function(start) {
 200   try {
 201     this.codeMap_.deleteCode(start);
 202   } catch (e) {
 203     this.handleUnknownCode(Profile.Operation.DELETE, start);
 204   }
 205 };
 206
 207
 208 /**
 209  * Reports about moving of a dynamic code entry.
 210  *
 211  * @param {number} from Current code entry address.
 212  * @param {number} to New code entry address.
 213  */
 214 Profile.prototype.moveFunc = function(from, to) {
 215   if (this.codeMap_.findDynamicEntryByStartAddress(from)) {
 216     this.codeMap_.moveCode(from, to);
 217   }
 218 };
 219
 220
 221 /**
 222  * Retrieves a code entry by an address.
 223  *
 224  * @param {number} addr Entry address.
 225  */
 226 Profile.prototype.findEntry = function(addr) {
 227   return this.codeMap_.findEntry(addr);
 228 };
 229
 230
 231 /**
 232  * Records a tick event. Stack must contain a sequence of
 233  * addresses starting with the program counter value.
 234  *
 235  * @param {Array<number>} stack Stack sample.
 236  */
 237 Profile.prototype.recordTick = function(stack) {
 238   var processedStack = this.resolveAndFilterFuncs_(stack);
 239   this.bottomUpTree_.addPath(processedStack);
 240   processedStack.reverse();
 241   this.topDownTree_.addPath(processedStack);
 242 };
 243
 244
 245 /**
 246  * Translates addresses into function names and filters unneeded
 247  * functions.
 248  *
 249  * @param {Array<number>} stack Stack sample.
 250  */
 251 Profile.prototype.resolveAndFilterFuncs_ = function(stack) {
 252   var result = [];
 253   for (var i = 0; i < stack.length; ++i) {
 254     var entry = this.codeMap_.findEntry(stack[i]);
 255     if (entry) {
 256       var name = entry.getName();
 257       if (!this.skipThisFunction(name)) {
 258         result.push(name);
 259       }
 260     } else {
 261       this.handleUnknownCode(
 262           Profile.Operation.TICK, stack[i], i);
 263     }
 264   }
 265   return result;
 266 };
 267
 268
 269 /**
 270  * Performs a BF traversal of the top down call graph.
 271  *
 272  * @param {function(CallTree.Node)} f Visitor function.
 273  */
 274 Profile.prototype.traverseTopDownTree = function(f) {
 275   this.topDownTree_.traverse(f);
 276 };
 277
 278
 279 /**
 280  * Performs a BF traversal of the bottom up call graph.
 281  *
 282  * @param {function(CallTree.Node)} f Visitor function.
 283  */
 284 Profile.prototype.traverseBottomUpTree = function(f) {
 285   this.bottomUpTree_.traverse(f);
 286 };
 287
 288
 289 /**
 290  * Calculates a top down profile for a node with the specified label.
 291  * If no name specified, returns the whole top down calls tree.
 292  *
 293  * @param {string} opt_label Node label.
 294  */
 295 Profile.prototype.getTopDownProfile = function(opt_label) {
 296   return this.getTreeProfile_(this.topDownTree_, opt_label);
 297 };
 298
 299
 300 /**
 301  * Calculates a bottom up profile for a node with the specified label.
 302  * If no name specified, returns the whole bottom up calls tree.
 303  *
 304  * @param {string} opt_label Node label.
 305  */
 306 Profile.prototype.getBottomUpProfile = function(opt_label) {
 307   return this.getTreeProfile_(this.bottomUpTree_, opt_label);
 308 };
 309
 310
 311 /**
 312  * Helper function for calculating a tree profile.
 313  *
 314  * @param {Profile.CallTree} tree Call tree.
 315  * @param {string} opt_label Node label.
 316  */
 317 Profile.prototype.getTreeProfile_ = function(tree, opt_label) {
 318   if (!opt_label) {
 319     tree.computeTotalWeights();
 320     return tree;
 321   } else {
 322     var subTree = tree.cloneSubtree(opt_label);
 323     subTree.computeTotalWeights();
 324     return subTree;
 325   }
 326 };
 327
 328
 329 /**
 330  * Calculates a flat profile of callees starting from a node with
 331  * the specified label. If no name specified, starts from the root.
 332  *
 333  * @param {string} opt_label Starting node label.
 334  */
 335 Profile.prototype.getFlatProfile = function(opt_label) {
 336   var counters = new CallTree();
 337   var rootLabel = opt_label || CallTree.ROOT_NODE_LABEL;
 338   var precs = {};
 339   precs[rootLabel] = 0;
 340   var root = counters.findOrAddChild(rootLabel);
 341
 342   this.topDownTree_.computeTotalWeights();
 343   this.topDownTree_.traverseInDepth(
 344     function onEnter(node) {
 345       if (!(node.label in precs)) {
 346         precs[node.label] = 0;
 347       }
 348       var nodeLabelIsRootLabel = node.label == rootLabel;
 349       if (nodeLabelIsRootLabel || precs[rootLabel] > 0) {
 350         if (precs[rootLabel] == 0) {
 351           root.selfWeight += node.selfWeight;
 352           root.totalWeight += node.totalWeight;
 353         } else {
 354           var rec = root.findOrAddChild(node.label);
 355           rec.selfWeight += node.selfWeight;
 356           if (nodeLabelIsRootLabel || precs[node.label] == 0) {
 357             rec.totalWeight += node.totalWeight;
 358           }
 359         }
 360         precs[node.label]++;
 361       }
 362     },
 363     function onExit(node) {
 364       if (node.label == rootLabel || precs[rootLabel] > 0) {
 365         precs[node.label]--;
 366       }
 367     },
 368     null);
 369
 370   if (!opt_label) {
 371     // If we have created a flat profile for the whole program, we don't
 372     // need an explicit root in it. Thus, replace the counters tree
 373     // root with the node corresponding to the whole program.
 374     counters.root_ = root;
 375   } else {
 376     // Propagate weights so percents can be calculated correctly.
 377     counters.getRoot().selfWeight = root.selfWeight;
 378     counters.getRoot().totalWeight = root.totalWeight;
 379   }
 380   return counters;
 381 };
 382
 383
 384 /**
 385  * Cleans up function entries that are not referenced by code entries.
 386  */
 387 Profile.prototype.cleanUpFuncEntries = function() {
 388   var referencedFuncEntries = [];
 389   var entries = this.codeMap_.getAllDynamicEntriesWithAddresses();
 390   for (var i = 0, l = entries.length; i < l; ++i) {
 391     if (entries[i][1].constructor === Profile.FunctionEntry) {
 392       entries[i][1].used = false;
 393     }
 394   }
 395   for (var i = 0, l = entries.length; i < l; ++i) {
 396     if ("func" in entries[i][1]) {
 397       entries[i][1].func.used = true;
 398     }
 399   }
 400   for (var i = 0, l = entries.length; i < l; ++i) {
 401     if (entries[i][1].constructor === Profile.FunctionEntry &&
 402         !entries[i][1].used) {
 403       this.codeMap_.deleteCode(entries[i][0]);
 404     }
 405   }
 406 };
 407
 408
 409 /**
 410  * Creates a dynamic code entry.
 411  *
 412  * @param {number} size Code size.
 413  * @param {string} type Code type.
 414  * @param {string} name Function name.
 415  * @constructor
 416  */
 417 Profile.DynamicCodeEntry = function(size, type, name) {
 418   CodeMap.CodeEntry.call(this, size, name);
 419   this.type = type;
 420 };
 421
 422
 423 /**
 424  * Returns node name.
 425  */
 426 Profile.DynamicCodeEntry.prototype.getName = function() {
 427   return this.type + ': ' + this.name;
 428 };
 429
 430
 431 /**
 432  * Returns raw node name (without type decoration).
 433  */
 434 Profile.DynamicCodeEntry.prototype.getRawName = function() {
 435   return this.name;
 436 };
 437
 438
 439 Profile.DynamicCodeEntry.prototype.isJSFunction = function() {
 440   return false;
 441 };
 442
 443
 444 Profile.DynamicCodeEntry.prototype.toString = function() {
 445   return this.getName() + ': ' + this.size.toString(16);
 446 };
 447
 448
 449 /**
 450  * Creates a dynamic code entry.
 451  *
 452  * @param {number} size Code size.
 453  * @param {string} type Code type.
 454  * @param {Profile.FunctionEntry} func Shared function entry.
 455  * @param {Profile.CodeState} state Code optimization state.
 456  * @constructor
 457  */
 458 Profile.DynamicFuncCodeEntry = function(size, type, func, state) {
 459   CodeMap.CodeEntry.call(this, size);
 460   this.type = type;
 461   this.func = func;
 462   this.state = state;
 463 };
 464
 465 Profile.DynamicFuncCodeEntry.STATE_PREFIX = ["", "~", "*"];
 466
 467 /**
 468  * Returns node name.
 469  */
 470 Profile.DynamicFuncCodeEntry.prototype.getName = function() {
 471   var name = this.func.getName();
 472   return this.type + ': ' + Profile.DynamicFuncCodeEntry.STATE_PREFIX[this.state] + name;
 473 };
 474
 475
 476 /**
 477  * Returns raw node name (without type decoration).
 478  */
 479 Profile.DynamicFuncCodeEntry.prototype.getRawName = function() {
 480   return this.func.getName();
 481 };
 482
 483
 484 Profile.DynamicFuncCodeEntry.prototype.isJSFunction = function() {
 485   return true;
 486 };
 487
 488
 489 Profile.DynamicFuncCodeEntry.prototype.toString = function() {
 490   return this.getName() + ': ' + this.size.toString(16);
 491 };
 492
 493
 494 /**
 495  * Creates a shared function object entry.
 496  *
 497  * @param {string} name Function name.
 498  * @constructor
 499  */
 500 Profile.FunctionEntry = function(name) {
 501   CodeMap.CodeEntry.call(this, 0, name);
 502 };
 503
 504
 505 /**
 506  * Returns node name.
 507  */
 508 Profile.FunctionEntry.prototype.getName = function() {
 509   var name = this.name;
 510   if (name.length == 0) {
 511     name = '<anonymous>';
 512   } else if (name.charAt(0) == ' ') {
 513     // An anonymous function with location: " aaa.js:10".
 514     name = '<anonymous>' + name;
 515   }
 516   return name;
 517 };
 518
 519 Profile.FunctionEntry.prototype.toString = CodeMap.CodeEntry.prototype.toString;
 520
 521 /**
 522  * Constructs a call graph.
 523  *
 524  * @constructor
 525  */
 526 function CallTree() {
 527   this.root_ = new CallTree.Node(
 528       CallTree.ROOT_NODE_LABEL);
 529 };
 530
 531
 532 /**
 533  * The label of the root node.
 534  */
 535 CallTree.ROOT_NODE_LABEL = '';
 536
 537
 538 /**
 539  * @private
 540  */
 541 CallTree.prototype.totalsComputed_ = false;
 542
 543
 544 /**
 545  * Returns the tree root.
 546  */
 547 CallTree.prototype.getRoot = function() {
 548   return this.root_;
 549 };
 550
 551
 552 /**
 553  * Adds the specified call path, constructing nodes as necessary.
 554  *
 555  * @param {Array<string>} path Call path.
 556  */
 557 CallTree.prototype.addPath = function(path) {
 558   if (path.length == 0) {
 559     return;
 560   }
 561   var curr = this.root_;
 562   for (var i = 0; i < path.length; ++i) {
 563     curr = curr.findOrAddChild(path[i]);
 564   }
 565   curr.selfWeight++;
 566   this.totalsComputed_ = false;
 567 };
 568
 569
 570 /**
 571  * Finds an immediate child of the specified parent with the specified
 572  * label, creates a child node if necessary. If a parent node isn't
 573  * specified, uses tree root.
 574  *
 575  * @param {string} label Child node label.
 576  */
 577 CallTree.prototype.findOrAddChild = function(label) {
 578   return this.root_.findOrAddChild(label);
 579 };
 580
 581
 582 /**
 583  * Creates a subtree by cloning and merging all subtrees rooted at nodes
 584  * with a given label. E.g. cloning the following call tree on label 'A'
 585  * will give the following result:
 586  *
 587  *           <A>--<B>                                     <B>
 588  *          /                                            /
 589  *     <root>             == clone on 'A' ==>  <root>--<A>
 590  *          \                                            \
 591  *           <C>--<A>--<D>                                <D>
 592  *
 593  * And <A>'s selfWeight will be the sum of selfWeights of <A>'s from the
 594  * source call tree.
 595  *
 596  * @param {string} label The label of the new root node.
 597  */
 598 CallTree.prototype.cloneSubtree = function(label) {
 599   var subTree = new CallTree();
 600   this.traverse(function(node, parent) {
 601     if (!parent && node.label != label) {
 602       return null;
 603     }
 604     var child = (parent ? parent : subTree).findOrAddChild(node.label);
 605     child.selfWeight += node.selfWeight;
 606     return child;
 607   });
 608   return subTree;
 609 };
 610
 611
 612 /**
 613  * Computes total weights in the call graph.
 614  */
 615 CallTree.prototype.computeTotalWeights = function() {
 616   if (this.totalsComputed_) {
 617     return;
 618   }
 619   this.root_.computeTotalWeight();
 620   this.totalsComputed_ = true;
 621 };
 622
 623
 624 /**
 625  * Traverses the call graph in preorder. This function can be used for
 626  * building optionally modified tree clones. This is the boilerplate code
 627  * for this scenario:
 628  *
 629  * callTree.traverse(function(node, parentClone) {
 630  *   var nodeClone = cloneNode(node);
 631  *   if (parentClone)
 632  *     parentClone.addChild(nodeClone);
 633  *   return nodeClone;
 634  * });
 635  *
 636  * @param {function(CallTree.Node, *)} f Visitor function.
 637  *    The second parameter is the result of calling 'f' on the parent node.
 638  */
 639 CallTree.prototype.traverse = function(f) {
 640   var pairsToProcess = new ConsArray();
 641   pairsToProcess.concat([{node: this.root_, param: null}]);
 642   while (!pairsToProcess.atEnd()) {
 643     var pair = pairsToProcess.next();
 644     var node = pair.node;
 645     var newParam = f(node, pair.param);
 646     var morePairsToProcess = [];
 647     node.forEachChild(function (child) {
 648         morePairsToProcess.push({node: child, param: newParam}); });
 649     pairsToProcess.concat(morePairsToProcess);
 650   }
 651 };
 652
 653
 654 /**
 655  * Performs an indepth call graph traversal.
 656  *
 657  * @param {function(CallTree.Node)} enter A function called
 658  *     prior to visiting node's children.
 659  * @param {function(CallTree.Node)} exit A function called
 660  *     after visiting node's children.
 661  */
 662 CallTree.prototype.traverseInDepth = function(enter, exit) {
 663   function traverse(node) {
 664     enter(node);
 665     node.forEachChild(traverse);
 666     exit(node);
 667   }
 668   traverse(this.root_);
 669 };
 670
 671
 672 /**
 673  * Constructs a call graph node.
 674  *
 675  * @param {string} label Node label.
 676  * @param {CallTree.Node} opt_parent Node parent.
 677  */
 678 CallTree.Node = function(label, opt_parent) {
 679   this.label = label;
 680   this.parent = opt_parent;
 681   this.children = {};
 682 };
 683
 684
 685 /**
 686  * Node self weight (how many times this node was the last node in
 687  * a call path).
 688  * @type {number}
 689  */
 690 CallTree.Node.prototype.selfWeight = 0;
 691
 692
 693 /**
 694  * Node total weight (includes weights of all children).
 695  * @type {number}
 696  */
 697 CallTree.Node.prototype.totalWeight = 0;
 698
 699
 700 /**
 701  * Adds a child node.
 702  *
 703  * @param {string} label Child node label.
 704  */
 705 CallTree.Node.prototype.addChild = function(label) {
 706   var child = new CallTree.Node(label, this);
 707   this.children[label] = child;
 708   return child;
 709 };
 710
 711
 712 /**
 713  * Computes node's total weight.
 714  */
 715 CallTree.Node.prototype.computeTotalWeight =
 716     function() {
 717   var totalWeight = this.selfWeight;
 718   this.forEachChild(function(child) {
 719       totalWeight += child.computeTotalWeight(); });
 720   return this.totalWeight = totalWeight;
 721 };
 722
 723
 724 /**
 725  * Returns all node's children as an array.
 726  */
 727 CallTree.Node.prototype.exportChildren = function() {
 728   var result = [];
 729   this.forEachChild(function (node) { result.push(node); });
 730   return result;
 731 };
 732
 733
 734 /**
 735  * Finds an immediate child with the specified label.
 736  *
 737  * @param {string} label Child node label.
 738  */
 739 CallTree.Node.prototype.findChild = function(label) {
 740   return this.children[label] || null;
 741 };
 742
 743
 744 /**
 745  * Finds an immediate child with the specified label, creates a child
 746  * node if necessary.
 747  *
 748  * @param {string} label Child node label.
 749  */
 750 CallTree.Node.prototype.findOrAddChild = function(label) {
 751   return this.findChild(label) || this.addChild(label);
 752 };
 753
 754
 755 /**
 756  * Calls the specified function for every child.
 757  *
 758  * @param {function(CallTree.Node)} f Visitor function.
 759  */
 760 CallTree.Node.prototype.forEachChild = function(f) {
 761   for (var c in this.children) {
 762     f(this.children[c]);
 763   }
 764 };
 765
 766
 767 /**
 768  * Walks up from the current node up to the call tree root.
 769  *
 770  * @param {function(CallTree.Node)} f Visitor function.
 771  */
 772 CallTree.Node.prototype.walkUpToRoot = function(f) {
 773   for (var curr = this; curr != null; curr = curr.parent) {
 774     f(curr);
 775   }
 776 };
 777
 778
 779 /**
 780  * Tries to find a node with the specified path.
 781  *
 782  * @param {Array<string>} labels The path.
 783  * @param {function(CallTree.Node)} opt_f Visitor function.
 784  */
 785 CallTree.Node.prototype.descendToChild = function(
 786     labels, opt_f) {
 787   for (var pos = 0, curr = this; pos < labels.length && curr != null; pos++) {
 788     var child = curr.findChild(labels[pos]);
 789     if (opt_f) {
 790       opt_f(child, pos);
 791     }
 792     curr = child;
 793   }
 794   return curr;
 795 };