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