Bug 1259850 - Switch to using a Map for visited points within a function, and heavily comment, r=terrence
☠☠ backed out by 69518db96a4d ☠ ☠
authorSteve Fink <sfink@mozilla.com>
Tue, 29 Sep 2015 13:39:38 -0700
changeset 340758 15de0d1d0b05457c18dcf70e4e81d9bfe5ad5f79
parent 340757 b7b7ea5b410ea4b02432d26fbd09a7d43bae4f2a
child 340759 e8544b072ee6b0055984ad7307216d61d4d3a26f
push id1183
push userraliiev@mozilla.com
push dateMon, 05 Sep 2016 20:01:49 +0000
treeherdermozilla-release@3148731bed45 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersterrence
bugs1259850
milestone49.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 1259850 - Switch to using a Map for visited points within a function, and heavily comment, r=terrence MozReview-Commit-ID: LvU4upaHt8b
js/src/devtools/rootAnalysis/analyzeRoots.js
--- a/js/src/devtools/rootAnalysis/analyzeRoots.js
+++ b/js/src/devtools/rootAnalysis/analyzeRoots.js
@@ -326,41 +326,67 @@ function edgeCanGC(edge)
 //
 // If so:
 //
 //  - 'why': a path from the GC call to a use of the variable after the GC
 //    call, chained through a 'why' field in the returned edge descriptor
 //
 //  - 'gcInfo': a direct pointer to the GC call edge
 //
-function findGCBeforeVariableUse(suppressed, variable, worklist)
+function findGCBeforeVariableUse(start_body, start_point, suppressed, variable)
 {
     // Scan through all edges preceding an unrooted variable use, using an
     // explicit worklist, looking for a GC call. A worklist contains an
     // incoming edge together with a description of where it or one of its
     // successors GC'd (if any).
 
+    var bodies_visited = new Map();
+
+    let worklist = [{body: start_body, ppoint: start_point, gcInfo: null, why: null}];
     while (worklist.length) {
+        // Grab an entry off of the worklist, representing a point within the
+        // CFG identified by <body,ppoint>. If this point has a descendant
+        // later in the CFG that can GC, gcInfo will be set to the information
+        // about that GC call.
+
         var entry = worklist.pop();
         var { body, ppoint, gcInfo } = entry;
 
-        if (body.seen) {
-            if (ppoint in body.seen) {
-                var seenEntry = body.seen[ppoint];
-                if (!gcInfo || seenEntry.gcInfo)
-                    continue;
-            }
-        } else {
-            body.seen = [];
+        // Handle the case where there are multiple ways to reach this point
+        // (traversing backwards).
+        var visited = bodies_visited.get(body);
+        if (!visited)
+            bodies_visited.set(body, visited = new Map());
+        if (visited.has(ppoint)) {
+            var seenEntry = visited.get(ppoint);
+
+            // This point already knows how to GC through some other path, so
+            // we have nothing new to learn. (The other path will consider the
+            // predecessors.)
+            if (seenEntry.gcInfo)
+                continue;
+
+            // If this worklist's entry doesn't know of any way to GC, then
+            // there's no point in continuing the traversal through it. Perhaps
+            // another edge will be found that *can* GC; otherwise, the first
+            // route to the point will traverse through predecessors.
+            //
+            // Note that this means we may visit a point more than once, if the
+            // first time we visit we don't have a known reachable GC call and
+            // the second time we do.
+            if (!gcInfo)
+                continue;
         }
-        body.seen[ppoint] = {body: body, gcInfo: gcInfo};
+        visited.set(ppoint, {body: body, gcInfo: gcInfo});
 
+        // Check for hitting the entry point of the current body (which may be
+        // the outer function or a loop within it.)
         if (ppoint == body.Index[0]) {
             if (body.BlockId.Kind == "Loop") {
-                // propagate to parents that enter the loop body.
+                // Propagate to outer body parents that enter the loop body.
                 if ("BlockPPoint" in body) {
                     for (var parent of body.BlockPPoint) {
                         var found = false;
                         for (var xbody of functionBodies) {
                             if (sameBlockId(xbody.BlockId, parent.BlockId)) {
                                 assert(!found);
                                 found = true;
                                 worklist.push({body: xbody, ppoint: parent.Index,
@@ -394,33 +420,35 @@ function findGCBeforeVariableUse(suppres
 
             if (edge_kills) {
                 // This is a beginning of the variable's live range. If we can
                 // reach a GC call from here, then we're done -- we have a path
                 // from the beginning of the live range, through the GC call,
                 // to a use after the GC call that proves its live range
                 // extends at least that far.
                 if (gcInfo)
-                    return {gcInfo: gcInfo, why: {body: body, ppoint: source, gcInfo: gcInfo, why: entry } }
+                    return {gcInfo: gcInfo, why: {body: body, ppoint: source, gcInfo: gcInfo, why: entry } };
 
-                // Otherwise, we want to continue searching for the true
-                // minimumUse, for use in reporting unnecessary rooting, but we
-                // truncate this particular branch of the search at this edge.
+                // Otherwise, keep searching through the graph, but truncate
+                // this particular branch of the search at this edge.
                 continue;
             }
 
             if (!gcInfo && !(source in body.suppressed) && !suppressed) {
                 var gcName = edgeCanGC(edge, body);
                 if (gcName)
                     gcInfo = {name:gcName, body:body, ppoint:source};
             }
 
             if (edge_uses) {
                 // The live range starts at least this far back, so we're done
-                // for the same reason as with edge_kills.
+                // for the same reason as with edge_kills. The only difference
+                // is that a GC on this edge indicates a hazard, whereas if
+                // we're killing a live range in the GC call then it's not live
+                // *across* the call.
                 if (gcInfo)
                     return {gcInfo:gcInfo, why:entry};
             }
 
             if (edge.Kind == "Loop") {
                 // Additionally propagate the search into a loop body, starting
                 // with the exit point.
                 var found = false;
@@ -441,39 +469,37 @@ function findGCBeforeVariableUse(suppres
         }
     }
 
     return null;
 }
 
 function variableLiveAcrossGC(suppressed, variable)
 {
-    // A variable is live across a GC if (1) it is used by an edge, and (2) it
-    // is used after a GC in a successor edge.
+    // A variable is live across a GC if (1) it is used by an edge (as in, it
+    // was at least initialized), and (2) it is used after a GC in a successor
+    // edge.
 
-    for (var body of functionBodies) {
-        body.seen = null;
+    for (var body of functionBodies)
         body.minimumUse = 0;
-    }
 
     for (var body of functionBodies) {
         if (!("PEdge" in body))
             continue;
         for (var edge of body.PEdge) {
             var usePoint = edgeUsesVariable(edge, variable, body);
             // Example for !edgeKillsVariable:
             //
             //   JSObject* obj = NewObject();
             //   cangc();
             //   obj = NewObject();    <-- uses 'obj', but kills previous value
             //
             if (usePoint && !edgeKillsVariable(edge, variable)) {
                 // Found a use, possibly after a GC.
-                var worklist = [{body:body, ppoint:usePoint, gcInfo:null, why:null}];
-                var call = findGCBeforeVariableUse(suppressed, variable, worklist);
+                var call = findGCBeforeVariableUse(body, usePoint, suppressed, variable);
                 if (!call)
                     continue;
 
                 call.afterGCUse = usePoint;
                 return call;
             }
         }
     }