Bug 1259850 - Switch to using a Map for visited points within a function, and heavily comment, r=terrence
authorSteve Fink <sfink@mozilla.com>
Tue, 29 Sep 2015 13:39:38 -0700
changeset 340799 0ae7a62636034a998d782ee64d2854d1ca613397
parent 340798 b780d702673a1bd061f28d2cb9c00e3d3c38305b
child 340800 b9f523c94cf0dbbfc07e67188bb78d6c57a799f3
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;
             }
         }
     }