Bug 1479828 - Handle self-recursive roots, r=me
authorSteve Fink <sfink@mozilla.com>
Tue, 26 Sep 2017 18:22:13 -0700
changeset 500014 4ddc76989782be51553a2fb904c7c6284908fa72
parent 500013 3a02fd73f28641c2150ebe8d8e4529769e871b96
child 500015 d05f029a29ad2adc1d2d952d91f440a3f571e679
push id1864
push userffxbld-merge
push dateMon, 03 Dec 2018 15:51:40 +0000
treeherdermozilla-release@f040763d99ad [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersme
bugs1479828
milestone64.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1479828 - Handle self-recursive roots, r=me
js/src/devtools/rootAnalysis/loadCallgraph.js
--- a/js/src/devtools/rootAnalysis/loadCallgraph.js
+++ b/js/src/devtools/rootAnalysis/loadCallgraph.js
@@ -211,64 +211,40 @@ function loadCallgraph(file)
     for (var func of extraGCFunctions()) {
         addGCFunction(mangledToId[func], "annotation", functionLimits);
     }
 
     // Compute functionLimits: it should contain the set of functions that
     // are *always* called within some sort of limited context (eg GC
     // suppression).
 
-    // Initialize functionLimits to the set of all functions, where each one
-    // is maximally limited, and initialize the worklist to all toplevel
-    // callers with dummy unlimited edges.
-    var worklist = [];
-    for (let callee in callersOf)
-        functionLimits[callee] = LIMIT_UNVISITED;
-    for (var caller in calleesOf) {
-        if (!(caller in callersOf)) {
-            functionLimits[caller] = LIMIT_UNVISITED;
-            worklist.push([caller, LIMIT_NONE, 'root']);
-        }
-    }
-
-    // Add in limited field calls.
+    // Initialize to limited field calls.
     for (var [name, limits] of Object.entries(fieldCallLimits)) {
         if (limits)
             functionLimits[name] = limits;
     }
 
-    // Recursively traverse the callgraph from the roots. Recurse through every
-    // edge that weakens the limits. (Limits that entirely disappear, aka go to
-    // a zero intset, will be removed from functionLimits.)
-    while (worklist.length > 0) {
-        // Consider caller where (graph) -> caller -> (0 or more callees)
-        // 'callercaller' is for debugging.
-        const [caller, edge_limits, callercaller] = worklist.pop();
-        const prev_limits = functionLimits[caller];
-        if (prev_limits & ~edge_limits) {
-            // Turning off a limit (or unvisited marker). Must recurse to the
-            // children. But first, update this caller's limits: we just found
-            // out it is reachable by an unlimited path, so it must be treated
-            // as unlimited (with respect to that bit).
-            const new_limits = prev_limits & edge_limits;
-            if (new_limits)
-                functionLimits[caller] = new_limits;
-            else
-                delete functionLimits[caller];
-            for (const {callee, limits} of (calleesOf[caller] || []))
-                worklist.push([callee, limits | edge_limits, caller]);
-        }
-    }
+    // Initialize functionLimits to the set of all functions, where each one is
+    // maximally limited, and return a worklist containing all simple roots
+    // (nodes with no callers).
+    var roots = gather_simple_roots(functionLimits, callersOf);
+
+    // Traverse the graph, spreading the limits down from the roots.
+    propagate_limits(roots, functionLimits, calleesOf);
 
-    // Not all functions are reachable by searching backwards from GC
-    // functions, so some functions will be LIMIT_UNVISITED. Remove them.
-    for (var func in functionLimits) {
-        if (functionLimits[func] == LIMIT_UNVISITED)
-            delete functionLimits[func];
-    }
+    // There are a surprising number of "recursive roots", where there is a
+    // cycle of functions calling each other but not called by anything else,
+    // and these roots may also have descendants. Now that the above traversal
+    // has eliminated everything reachable from simple roots, traverse the
+    // remaining graph to gather up a representative function from each root
+    // cycle.
+    roots = gather_recursive_roots(roots, functionLimits, callersOf);
+
+    // And do a final traversal starting with the recursive roots.
+    propagate_limits(roots, functionLimits, calleesOf);
 
     // Eliminate GC-limited functions from the set of functions known to GC.
     for (var name in gcFunctions) {
         if (functionLimits[name] & LIMIT_CANNOT_GC)
             delete gcFunctions[name];
     }
 
     // functionLimits should now contain all functions that are always called
@@ -318,16 +294,116 @@ function loadCallgraph(file)
         limitedFunctions[idToMangled[id]] = limits;
 
     // The above code uses integer ids for efficiency. External code uses
     // mangled names. Rewrite the various data structures to convert ids to
     // mangled names.
     remap_ids_to_mangled_names();
 }
 
+// Return a worklist of functions with no callers, and also initialize
+// functionLimits to the set of all functions, each mapped to LIMIT_UNVISTED.
+function gather_simple_roots(functionLimits, callersOf) {
+    const roots = [];
+    for (let callee in callersOf)
+        functionLimits[callee] = LIMIT_UNVISITED;
+    for (let caller in calleesOf) {
+        if (!(caller in callersOf)) {
+            functionLimits[caller] = LIMIT_UNVISITED;
+            roots.push([caller, LIMIT_NONE, 'root']);
+        }
+    }
+
+    return roots;
+}
+
+// Recursively traverse the callgraph from the roots. Recurse through every
+// edge that weakens the limits. (Limits that entirely disappear, aka go to a
+// zero intset, will be removed from functionLimits.)
+function propagate_limits(worklist, functionLimits, calleesOf) {
+    let top = worklist.length;
+    while (top > 0) {
+        // Consider caller where (graph) -> caller -> (0 or more callees)
+        // 'callercaller' is for debugging.
+        const [caller, edge_limits, callercaller] = worklist[--top];
+        const prev_limits = functionLimits[caller];
+        if (prev_limits & ~edge_limits) {
+            // Turning off a limit (or unvisited marker). Must recurse to the
+            // children. But first, update this caller's limits: we just found
+            // out it is reachable by an unlimited path, so it must be treated
+            // as unlimited (with respect to that bit).
+            const new_limits = prev_limits & edge_limits;
+            if (new_limits)
+                functionLimits[caller] = new_limits;
+            else
+                delete functionLimits[caller];
+            for (const {callee, limits} of (calleesOf[caller] || []))
+                worklist[top++] = [callee, limits | edge_limits, caller];
+        }
+    }
+}
+
+// Mutually-recursive roots and their descendants will not have been visited,
+// and will still be set to LIMIT_UNVISITED. Scan through and gather them.
+function gather_recursive_roots(functionLimits, callersOf) {
+    const roots = [];
+
+    // 'seen' maps functions to the most recent starting function that each was
+    // first reachable from, to distinguish between the current pass and passes
+    // for preceding functions.
+    //
+    // Consider:
+    //
+    //   A <--> B --> C <-- D <--> E
+    //                C --> F
+    //                C --> G
+    //
+    // So there are two root cycles AB and DE, both calling C that in turn
+    // calls F and G. If we start at F and scan up through callers, we will
+    // keep going until A loops back to B and E loops back to D, and will add B
+    // and D as roots. Then if we scan from G, we encounter C and see that it
+    // was already been seen on an earlier pass. So C and everything reachable
+    // from it is already reachable by some root. (We need to label nodes with
+    // their pass because otherwise we couldn't distinguish "already seen C,
+    // done" from "already seen B, must be a root".)
+    //
+    const seen = new Map();
+    for (var func in functionLimits) {
+        if (functionLimits[func] != LIMIT_UNVISITED)
+            continue;
+
+        // We should only be looking at nodes with callers, since otherwise
+        // they would have been handled in the previous pass!
+        assert(callersOf[func].length > 0);
+
+        const work = [func];
+        while (work.length > 0) {
+            const f = work.pop();
+            if (seen.has(f)) {
+                if (seen.get(f) == func) {
+                    // We have traversed a cycle and reached an already-seen
+                    // node. Treat it as a root.
+                    roots.push([f, LIMIT_NONE, 'root']);
+                    print(`recursive root? ${f} = ${functionNames[f]}`);
+                } else {
+                    // Otherwise we hit the portion of the graph that is
+                    // reachable from a past root.
+                    seen.set(f, func);
+                }
+            } else {
+                print(`retained by recursive root? ${f} = ${functionNames[f]}`);
+                work.push(...callersOf[f]);
+                seen.set(f, func);
+            }
+        }
+    }
+
+    return roots;
+}
+
 function remap_ids_to_mangled_names() {
     var tmp = gcFunctions;
     gcFunctions = {};
     for (const [caller, reason] of Object.entries(tmp))
         gcFunctions[idToMangled[caller]] = idToMangled[reason] || reason;
 
     tmp = calleesOf;
     calleesOf = {};