Bug 1389974 - Remove the implication that killing a value overrides using it, r=bhackett
authorSteve Fink <sfink@mozilla.com>
Fri, 01 Sep 2017 09:56:15 -0700
changeset 429587 2b18295208be6a616d959f4f00e944f279dcca3f
parent 429586 3c6ea99a33d94afaf7323696f39f73433ca1af04
child 429588 0e2f9e7b7fd7ab31640383e64c8b7bf4c602d828
push id7761
push userjlund@mozilla.com
push dateFri, 15 Sep 2017 00:19:52 +0000
treeherdermozilla-beta@c38455951db4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs1389974
milestone57.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 1389974 - Remove the implication that killing a value overrides using it, r=bhackett
js/src/devtools/rootAnalysis/analyzeRoots.js
js/src/devtools/rootAnalysis/t/hazards/source.cpp
js/src/devtools/rootAnalysis/t/hazards/test.py
--- a/js/src/devtools/rootAnalysis/analyzeRoots.js
+++ b/js/src/devtools/rootAnalysis/analyzeRoots.js
@@ -10,17 +10,17 @@ var sourceRoot = (os.getenv('SOURCE') ||
 
 var functionName;
 var functionBodies;
 
 if (typeof scriptArgs[0] != 'string' || typeof scriptArgs[1] != 'string')
     throw "Usage: analyzeRoots.js [-f function_name] <gcFunctions.lst> <gcEdges.txt> <suppressedFunctions.lst> <gcTypes.txt> <typeInfo.txt> [start end [tmpfile]]";
 
 var theFunctionNameToFind;
-if (scriptArgs[0] == '--function') {
+if (scriptArgs[0] == '--function' || scriptArgs[0] == '-f') {
     theFunctionNameToFind = scriptArgs[1];
     scriptArgs = scriptArgs.slice(2);
 }
 
 var gcFunctionsFile = scriptArgs[0] || "gcFunctions.lst";
 var gcEdgesFile = scriptArgs[1] || "gcEdges.txt";
 var suppressedFunctionsFile = scriptArgs[2] || "suppressedFunctions.lst";
 var gcTypesFile = scriptArgs[3] || "gcTypes.txt";
@@ -126,64 +126,97 @@ function isReturningImmobileValue(edge, 
             if (edge.Exp[1].Kind == "Int" && edge.Exp[1].String == "0") {
                 return true;
             }
         }
     }
     return false;
 }
 
-// If the edge uses the given variable, return the earliest point at which the
-// use is definite. Usually, that means the source of the edge (anything that
-// reaches that source point will end up using the variable, but there may be
-// other ways to reach the destination of the edge.)
+// If the edge uses the given variable's value, return the earliest point at
+// which the use is definite. Usually, that means the source of the edge
+// (anything that reaches that source point will end up using the variable, but
+// there may be other ways to reach the destination of the edge.)
 //
 // Return values are implicitly used at the very last point in the function.
 // This makes a difference: if an RAII class GCs in its destructor, we need to
 // start looking at the final point in the function, not one point back from
 // that, since that would skip over the GCing call.
 //
+// Note that this returns true only if the variable's incoming value is used.
+// So this would return false for 'obj':
+//
+//     obj = someFunction();
+//
+// but these would return true:
+//
+//     obj = someFunction(obj);
+//     obj->foo = someFunction();
+//
 function edgeUsesVariable(edge, variable, body)
 {
     if (ignoreEdgeUse(edge, variable, body))
         return 0;
 
     if (variable.Kind == "Return" && body.Index[1] == edge.Index[1] && body.BlockId.Kind == "Function")
         return edge.Index[1]; // Last point in function body uses the return value.
 
     var src = edge.Index[0];
 
     switch (edge.Kind) {
 
-    case "Assign":
+    case "Assign": {
         if (isReturningImmobileValue(edge, variable))
             return 0;
-        if (expressionUsesVariable(edge.Exp[0], variable))
+        const [lhs, rhs] = edge.Exp;
+        if (expressionUsesVariable(rhs, variable))
             return src;
-        return expressionUsesVariable(edge.Exp[1], variable) ? src : 0;
+        if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable))
+            return src;
+        return 0;
+    }
 
     case "Assume":
         return expressionUsesVariableContents(edge.Exp[0], variable) ? src : 0;
 
-    case "Call":
-        if (expressionUsesVariable(edge.Exp[0], variable))
-            return src;
-        if (1 in edge.Exp && expressionUsesVariable(edge.Exp[1], variable))
+    case "Call": {
+        const callee = edge.Exp[0];
+        if (expressionUsesVariable(callee, variable))
             return src;
         if ("PEdgeCallInstance" in edge) {
-            if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable))
-                return src;
+            if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable)) {
+                if (edgeKillsVariable(edge, variable)) {
+                    // If the variable is being constructed, then the incoming
+                    // value is not used here; it didn't exist before
+                    // construction. (The analysis doesn't get told where
+                    // variables are defined, so must infer it from
+                    // construction. If the variable does not have a
+                    // constructor, its live range may be larger than it really
+                    // ought to be if it is defined within a loop body, but
+                    // that is conservative.)
+                } else {
+                    return src;
+                }
+            }
         }
         if ("PEdgeCallArguments" in edge) {
             for (var exp of edge.PEdgeCallArguments.Exp) {
                 if (expressionUsesVariable(exp, variable))
                     return src;
             }
         }
+        if (edge.Exp.length == 1)
+            return 0;
+
+        // Assigning call result to a variable.
+        const lhs = edge.Exp[1];
+        if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable))
+            return src;
         return 0;
+    }
 
     case "Loop":
         return 0;
 
     default:
         assert(false);
     }
 }
@@ -212,73 +245,84 @@ function edgeTakesVariableAddress(edge, 
             }
         }
         return false;
     default:
         return false;
     }
 }
 
+function expressionIsVariable(exp, variable)
+{
+    return exp.Kind == "Var" && sameVariable(exp.Variable, variable);
+}
+
+// Return whether the edge kills (overwrites) the variable's incoming value.
+// Examples of killing 'obj':
+//
+//     obj = foo;
+//     obj = foo();
+//     obj = foo(obj);         // uses previous value but then kills it
+//     SomeClass obj(true, 1); // constructor
+//
 function edgeKillsVariable(edge, variable)
 {
     // Direct assignments kill their lhs: var = value
     if (edge.Kind == "Assign") {
-        var lhs = edge.Exp[0];
-        if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
-            return !isReturningImmobileValue(edge, variable);
+        const [lhs] = edge.Exp;
+        return (expressionIsVariable(lhs, variable) &&
+                !isReturningImmobileValue(edge, variable));
     }
 
     if (edge.Kind != "Call")
         return false;
 
     // Assignments of call results kill their lhs.
     if (1 in edge.Exp) {
         var lhs = edge.Exp[1];
-        if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
+        if (expressionIsVariable(lhs, variable))
             return true;
     }
 
     // Constructor calls kill their 'this' value.
     if ("PEdgeCallInstance" in edge) {
-        do {
-            var instance = edge.PEdgeCallInstance.Exp;
+        var instance = edge.PEdgeCallInstance.Exp;
 
-            // Kludge around incorrect dereference on some constructor calls.
-            if (instance.Kind == "Drf")
-                instance = instance.Exp[0];
+        // Kludge around incorrect dereference on some constructor calls.
+        if (instance.Kind == "Drf")
+            instance = instance.Exp[0];
 
-            if (instance.Kind != "Var" || !sameVariable(instance.Variable, variable))
-                break;
+        if (!expressionIsVariable(instance, variable))
+            return false;
 
-            var callee = edge.Exp[0];
-            if (callee.Kind != "Var")
-                break;
+        var callee = edge.Exp[0];
+        if (callee.Kind != "Var")
+            return false;
 
-            assert(callee.Variable.Kind == "Func");
-            var calleeName = readable(callee.Variable.Name[0]);
+        assert(callee.Variable.Kind == "Func");
+        var calleeName = readable(callee.Variable.Name[0]);
 
-            // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('.
-            var openParen = calleeName.indexOf('(');
-            if (openParen < 0)
-                break;
-            calleeName = calleeName.substring(0, openParen);
+        // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('.
+        var openParen = calleeName.indexOf('(');
+        if (openParen < 0)
+            return false;
+        calleeName = calleeName.substring(0, openParen);
 
-            var lastColon = calleeName.lastIndexOf('::');
-            if (lastColon < 0)
-                break;
-            var constructorName = calleeName.substr(lastColon + 2);
-            calleeName = calleeName.substr(0, lastColon);
+        var lastColon = calleeName.lastIndexOf('::');
+        if (lastColon < 0)
+            return false;
+        var constructorName = calleeName.substr(lastColon + 2);
+        calleeName = calleeName.substr(0, lastColon);
 
-            var lastTemplateOpen = calleeName.lastIndexOf('<');
-            if (lastTemplateOpen >= 0)
-                calleeName = calleeName.substr(0, lastTemplateOpen);
+        var lastTemplateOpen = calleeName.lastIndexOf('<');
+        if (lastTemplateOpen >= 0)
+            calleeName = calleeName.substr(0, lastTemplateOpen);
 
-            if (calleeName.endsWith(constructorName))
-                return true;
-        } while (false);
+        if (calleeName.endsWith(constructorName))
+            return true;
     }
 
     return false;
 }
 
 function edgeCanGC(edge)
 {
     if (edge.Kind != "Call")
@@ -308,38 +352,38 @@ function edgeCanGC(edge)
         var csuName = field.FieldCSU.Type.Name;
         var fullFieldName = csuName + "." + field.Name[0];
         if (fieldCallCannotGC(csuName, fullFieldName))
             return null;
         return (fullFieldName in suppressedFunctions) ? null : fullFieldName;
     }
 }
 
-// Search recursively through predecessors from a variable use, returning
-// whether a GC call is reachable (in the reverse direction; this means that
-// the variable use is reachable from the GC call, and therefore the variable
-// is live after the GC call), along with some additional information. What
-// info we want depends on whether the variable turns out to be live across any
-// GC call. We are looking for both hazards (unrooted variables live across GC
-// calls) and unnecessary roots (rooted variables that have no GC calls in
-// their live ranges.)
+// Search recursively through predecessors from the use of a variable's value,
+// returning whether a GC call is reachable (in the reverse direction; this
+// means that the variable use is reachable from the GC call, and therefore the
+// variable is live after the GC call), along with some additional information.
+// What info we want depends on whether the variable turns out to be live
+// across a GC call. We are looking for both hazards (unrooted variables live
+// across GC calls) and unnecessary roots (rooted variables that have no GC
+// calls in their live ranges.)
 //
 // If not:
 //
 //  - 'minimumUse': the earliest point in each body that uses the variable, for
 //    reporting on unnecessary roots.
 //
 // 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(start_body, start_point, suppressed, variable)
+function findGCBeforeValueUse(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();
 
@@ -394,16 +438,21 @@ function findGCBeforeVariableUse(start_b
                                 found = true;
                                 worklist.push({body: xbody, ppoint: parent.Index,
                                                gcInfo: gcInfo, why: entry});
                             }
                         }
                         assert(found);
                     }
                 }
+
+                // Also propagate to the *end* of this loop, for the previous
+                // iteration.
+                worklist.push({body: body, ppoint: body.Index[1],
+                               gcInfo: gcInfo, why: entry});
             } else if (variable.Kind == "Arg" && gcInfo) {
                 // The scope of arguments starts at the beginning of the
                 // function
                 return entry;
             } else if (entry.preGCLive) {
                 // We didn't find a "good" explanation beginning of the live
                 // range, but we do know the variable was live across the GC.
                 // This can happen if the live range started when a variable is
@@ -468,17 +517,18 @@ function findGCBeforeVariableUse(start_b
                 //
                 // The call to .isUndefined() is considered to be a use and
                 // therefore indicates that v must be live at that point. But
                 // it's more helpful to the user to continue the 'why' path to
                 // include the ancestor where the value was generated. So we
                 // will only return here if edge.Kind is Assign; otherwise,
                 // we'll pass a "preGCLive" value up through the worklist to
                 // remember that the variable *is* alive before the GC and so
-                // this function should be returning a true value.
+                // this function should be returning a true value even if we
+                // don't find an assignment.
 
                 if (src_gcInfo) {
                     src_preGCLive = true;
                     if (edge.Kind == 'Assign')
                         return {body:body, ppoint:source, gcInfo:src_gcInfo, why:entry};
                 }
             }
 
@@ -491,16 +541,19 @@ function findGCBeforeVariableUse(start_b
                         assert(!found);
                         found = true;
                         worklist.push({body:xbody, ppoint:xbody.Index[1],
                                        preGCLive: src_preGCLive, gcInfo:src_gcInfo,
                                        why:entry});
                     }
                 }
                 assert(found);
+                // Don't continue to predecessors here without going through
+                // the loop. (The points in this body that enter the loop will
+                // be traversed when we reach the entry point of the loop.)
                 break;
             }
 
             // Propagate the search to the predecessors of this edge.
             worklist.push({body:body, ppoint:source,
                            preGCLive: src_preGCLive, gcInfo:src_gcInfo,
                            why:entry});
         }
@@ -517,26 +570,43 @@ function variableLiveAcrossGC(suppressed
 
     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:
+            // Examples:
+            //
+            //   JSObject* obj = NewObject();
+            //   cangc();
+            //   obj = NewObject();     <-- mentions 'obj' but kills previous value
+            //
+            // This is not a hazard. Contrast this with:
             //
             //   JSObject* obj = NewObject();
             //   cangc();
-            //   obj = NewObject();    <-- uses 'obj', but kills previous value
+            //   obj = LookAt(obj);  <-- uses 'obj' and kills previous value
+            //
+            // This is a hazard; the initial value of obj is live across
+            // cangc(). And a third possibility:
+            //
+            //   JSObject* obj = NewObject();
+            //   obj = CopyObject(obj);
             //
-            if (usePoint && !edgeKillsVariable(edge, variable)) {
-                // Found a use, possibly after a GC.
-                var call = findGCBeforeVariableUse(body, usePoint, suppressed, variable);
+            // This is not a hazard, because even though CopyObject can GC, obj
+            // is not live across it. (obj is live before CopyObject, and
+            // probably after, but not across.) There may be a hazard within
+            // CopyObject, of course.
+            //
+
+            var usePoint = edgeUsesVariable(edge, variable, body);
+            if (usePoint) {
+                var call = findGCBeforeValueUse(body, usePoint, suppressed, variable);
                 if (!call)
                     continue;
 
                 call.afterGCUse = usePoint;
                 return call;
             }
         }
     }
@@ -640,19 +710,23 @@ function printEntryTrace(functionName, e
         if (entry.why && entry.why.body == entry.body) {
             // If the next point in the trace is in the same block, look for an edge between them.
             var next = entry.why.ppoint;
 
             if (!entry.body.edgeTable) {
                 var table = {};
                 entry.body.edgeTable = table;
                 for (var line of entry.body.lines) {
-                    if (match = /\((\d+,\d+),/.exec(line))
+                    if (match = /^\w+\((\d+,\d+),/.exec(line))
                         table[match[1]] = line; // May be multiple?
                 }
+                if (entry.body.BlockId.Kind == 'Loop') {
+                    const [startPoint, endPoint] = entry.body.Index;
+                    table[`${endPoint},${startPoint}`] = '(loop to next iteration)';
+                }
             }
 
             edgeText = entry.body.edgeTable[ppoint + "," + next];
             assert(edgeText);
             if (ppoint == gcPoint)
                 edgeText += " [[GC call]]";
         } else {
             // Look for any outgoing edge from the chosen point.
--- a/js/src/devtools/rootAnalysis/t/hazards/source.cpp
+++ b/js/src/devtools/rootAnalysis/t/hazards/source.cpp
@@ -1,12 +1,14 @@
 #define ANNOTATE(property) __attribute__((tag(property)))
 
 struct Cell { int f; } ANNOTATE("GC Thing");
 
+struct RootedCell { RootedCell(Cell*) {} } ANNOTATE("Rooted Pointer");
+
 class AutoSuppressGC_Base {
   public:
     AutoSuppressGC_Base() {}
     ~AutoSuppressGC_Base() {}
 } ANNOTATE("Suppress GC");
 
 class AutoSuppressGC_Child : public AutoSuppressGC_Base {
   public:
@@ -25,17 +27,17 @@ extern void invisible();
 
 void GC()
 {
     // If the implementation is too trivial, the function body won't be emitted at all.
     asm("");
     invisible();
 }
 
-extern void foo(Cell*);
+extern void usecell(Cell*);
 
 void suppressedFunction() {
     GC(); // Calls GC, but is always called within AutoSuppressGC
 }
 
 void halfSuppressedFunction() {
     GC(); // Calls GC, but is sometimes called within AutoSuppressGC
 }
@@ -65,25 +67,120 @@ f()
     Cell* cell2 = &cell;
     Cell* cell3 = &cell;
     Cell* cell4 = &cell;
     {
         AutoSuppressGC nogc;
         suppressedFunction();
         halfSuppressedFunction();
     }
-    foo(cell1);
+    usecell(cell1);
     halfSuppressedFunction();
-    foo(cell2);
+    usecell(cell2);
     unsuppressedFunction();
     {
         // Old bug: it would look from the first AutoSuppressGC constructor it
         // found to the last destructor. This statement *should* have no effect.
         AutoSuppressGC nogc;
     }
-    foo(cell3);
+    usecell(cell3);
     Cell* cell5 = &cell;
-    foo(cell5);
+    usecell(cell5);
 
     // Hazard in return value due to ~GCInDestructor
     Cell* cell6 = &cell;
     return cell6;
 }
+
+Cell* copy_and_gc(Cell* src)
+{
+    GC();
+    return reinterpret_cast<Cell*>(88);
+}
+
+void use(Cell* cell)
+{
+    static int x = 0;
+    if (cell)
+        x++;
+}
+
+struct CellContainer {
+    Cell* cell;
+    CellContainer() {
+        asm("");
+    }
+};
+
+void loopy()
+{
+    Cell cell;
+
+    // No hazard: haz1 is not live during call to copy_and_gc.
+    Cell* haz1;
+    for (int i = 0; i < 10; i++) {
+        haz1 = copy_and_gc(haz1);
+    }
+
+    // No hazard: haz2 is live up to just before the GC, and starting at the
+    // next statement after it, but not across the GC.
+    Cell* haz2 = &cell;
+    for (int j = 0; j < 10; j++) {
+        use(haz2);
+        GC();
+        haz2 = &cell;
+    }
+
+    // Hazard: haz3 is live from the final statement in one iteration, across
+    // the GC in the next, to the use in the 2nd statement.
+    Cell* haz3;
+    for (int k = 0; k < 10; k++) {
+        GC();
+        use(haz3);
+        haz3 = &cell;
+    }
+
+    // Hazard: haz4 is live across a GC hidden in a loop.
+    Cell* haz4 = &cell;
+    for (int i2 = 0; i2 < 10; i2++) {
+        GC();
+    }
+    use(haz4);
+
+    // Hazard: haz5 is live from within a loop across a GC.
+    Cell* haz5;
+    for (int i3 = 0; i3 < 10; i3++) {
+        haz5 = &cell;
+    }
+    GC();
+    use(haz5);
+
+    // No hazard: similar to the haz3 case, but verifying that we do not get
+    // into an infinite loop.
+    Cell* haz6;
+    for (int i4 = 0; i4 < 10; i4++) {
+        GC();
+        haz6 = &cell;
+    }
+
+    // No hazard: haz7 is constructed within the body, so it can't make a
+    // hazard across iterations. Note that this requires CellContainer to have
+    // a constructor, because otherwise the analysis doesn't see where
+    // variables are declared. (With the constructor, it knows that
+    // construction of haz7 obliterates any previous value it might have had.
+    // Not that that's possible given its scope, but the analysis doesn't get
+    // that information.)
+    for (int i5 = 0; i5 < 10; i5++) {
+        GC();
+        CellContainer haz7;
+        use(haz7.cell);
+        haz7.cell = &cell;
+    }
+
+    // Hazard: make sure we *can* see hazards across iterations involving
+    // CellContainer;
+    CellContainer haz8;
+    for (int i6 = 0; i6 < 10; i6++) {
+        GC();
+        use(haz8.cell);
+        haz8.cell = &cell;
+    }
+}
--- a/js/src/devtools/rootAnalysis/t/hazards/test.py
+++ b/js/src/devtools/rootAnalysis/t/hazards/test.py
@@ -15,22 +15,33 @@ hazmap = {haz.variable: haz for haz in h
 assert('cell1' not in hazmap)
 assert('cell2' in hazmap)
 assert('cell3' in hazmap)
 assert('cell4' not in hazmap)
 assert('cell5' not in hazmap)
 assert('cell6' not in hazmap)
 assert('<returnvalue>' in hazmap)
 
-# All hazards should be in f()
+# All hazards should be in f() and loopy()
 assert(hazmap['cell2'].function == 'Cell* f()')
-assert(len(set(haz.function for haz in hazards)) == 1)
+print(len(set(haz.function for haz in hazards)))
+assert(len(set(haz.function for haz in hazards)) == 2)
 
 # Check that the correct GC call is reported for each hazard. (cell3 has a
 # hazard from two different GC calls; it doesn't really matter which is
 # reported.)
 assert(hazmap['cell2'].GCFunction == 'void halfSuppressedFunction()')
 assert(hazmap['cell3'].GCFunction in ('void halfSuppressedFunction()', 'void unsuppressedFunction()'))
 assert(hazmap['<returnvalue>'].GCFunction == 'void GCInDestructor::~GCInDestructor()')
 
 # Type names are handy to have in the report.
 assert(hazmap['cell2'].type == 'Cell*')
 assert(hazmap['<returnvalue>'].type == 'Cell*')
+
+# loopy hazards. See comments in source.
+assert('haz1' not in hazmap);
+assert('haz2' not in hazmap);
+assert('haz3' in hazmap);
+assert('haz4' in hazmap);
+assert('haz5' in hazmap);
+assert('haz6' not in hazmap);
+assert('haz7' not in hazmap);
+assert('haz8' in hazmap);