Bug 838029 - Import bhackett static rooting analysis into tree. r=bhackett
authorSteve Fink <sfink@mozilla.com>
Tue, 05 Mar 2013 14:48:13 -0800
changeset 131904 c132f3957827d443698dbd9bf722e4baa0897a87
parent 131903 5d18c9bfd37b81e9c620be2be88733aea791a03e
child 131905 08217bf1ddc78540f4201d856d67cb5e5c9e1a5a
push idunknown
push userunknown
push dateunknown
reviewersbhackett
bugs838029
milestone22.0a1
Bug 838029 - Import bhackett static rooting analysis into tree. r=bhackett
js/src/devtools/rootAnalysis/Makefile.in
js/src/devtools/rootAnalysis/README.txt
js/src/devtools/rootAnalysis/analyzeRoots.js
js/src/devtools/rootAnalysis/annotations.js
js/src/devtools/rootAnalysis/computeCallgraph.js
js/src/devtools/rootAnalysis/computeGCFunctions.js
js/src/devtools/rootAnalysis/computeGCTypes.js
js/src/devtools/rootAnalysis/gen-hazards.sh
js/src/devtools/rootAnalysis/loadCallgraph.js
js/src/devtools/rootAnalysis/run_complete
js/src/devtools/rootAnalysis/suppressedPoints.js
js/src/devtools/rootAnalysis/utility.js
--- a/js/src/devtools/rootAnalysis/Makefile.in
+++ b/js/src/devtools/rootAnalysis/Makefile.in
@@ -35,9 +35,41 @@ SIXGILL ?= @SIXGILL_PATH@
 
 # Path to the JS scripts that will perform the analysis, defaulting to the same
 # place as this Makefile.in, which is probably what you want.
 ANALYSIS_SCRIPT_DIR ?= $(srcdir)
 
 # Number of simultanous analyzeRoots.js scripts to run.
 JOBS ?= 6
 
-all: ; true
+all : rootingHazards.txt allFunctions.txt
+
+CALL_JS := time env PATH=$$PATH:$(SIXGILL)/bin XDB=$(SIXGILL)/bin/xdb.so $(JS) 
+
+src_body.xdb src_comp.xdb: run_complete
+	@echo Started compilation at $$(date)
+	$(ANALYSIS_SCRIPT_DIR)/run_complete --foreground --build-root=$(TARGET_JSOBJDIR) --work-dir=work -b $(SIXGILL)/bin $(shell pwd)
+	@echo Finished compilation at $$(date)
+
+callgraph.txt: src_body.xdb src_comp.xdb computeCallgraph.js
+	@echo Started computation of $@ at $$(date)
+	$(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeCallgraph.js > $@
+	@echo Finished computation of $@ at $$(date)
+
+gcFunctions.txt: callgraph.txt computeGCFunctions.js annotations.js
+	@echo Started computation of $@ at $$(date)
+	$(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeGCFunctions.js ./callgraph.txt > $@
+	@echo Finished computation of $@ at $$(date)
+
+gcTypes.txt: src_comp.xdb computeGCTypes.js annotations.js
+	@echo Started computation of $@ at $$(date)
+	$(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeGCTypes.js > $@
+	@echo Finished computation of $@ at $$(date)
+
+allFunctions.txt: src_body.xdb
+	@echo Started computation of $@ at $$(date)
+	time $(SIXGILL)/bin/xdbkeys $^ > $@
+	@echo Finished computation of $@ at $$(date)
+
+rootingHazards.txt: gcFunctions.txt gcTypes.txt analyzeRoots.js annotations.js gen-hazards.sh
+	@echo Started computation of $@ at $$(date)
+	time env JS=$(JS) ANALYZE="$(ANALYSIS_SCRIPT_DIR)/analyzeRoots.js" SIXGILL="$(SIXGILL)" "$(ANALYSIS_SCRIPT_DIR)/gen-hazards.sh" $(JOBS) > $@
+	@echo Finished computation of $@ at $$(date)
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/README.txt
@@ -0,0 +1,39 @@
+This directory contains scripts and a makefile for running Brian Hackett's
+static GC rooting analysis on a JS source directory.
+
+To use it:
+
+1. Download and compile sixgill. Make sure the gcc plugin is enabled. (The
+   configure output will tell you.)
+
+  - [sfink] I needed a couple of patches to get it work on Fedora 16/17/18.
+    Ask me if you need them.
+
+2. Compile an optimized JS shell that includes the patch at
+   <http://people.mozilla.org/~sfink/data/bug-835552-cwd-snarf>. This does not
+   need to be in the same source tree as you are running these scripts from.
+   Remember the full path to the resulting JS binary; we'll call it $JS_SHELL
+   below.
+
+3. |make clean| in the objdir of the JS source tree that you're going to be
+   analyzing. (These analysis scripts will default to the tree they are within,
+   but you can point them at another tree.)
+
+4. in $objdir/js/src/devtools/analysis, |make JS=$JS_SHELL
+   SIXGILL=.../path/to/sixgill...|. You may need one or more of the following
+   additional settings in addition to the |JS| already given:
+
+   - JSOBJDIR: if you are analyzing a different source tree, set this to the
+     objdir of the tree you want to analyze.
+
+   - ANALYSIS_SCRIPT_DIR: by default, the *.js files within the directory
+     containing this README will be used, but you can point to a different
+     directory full. At the time of this writing, there are some changes not in
+     bhackett's git repo that are necessary, and you'll also need the
+     gen-hazards.sh shell script.
+
+   - JOBS: set this to the number of parallel jobs you'd like to run the final
+     analysis pass with. This defaults to 6, somewhat randomly, which gave me a
+     large speedup even on a machine with only 2 cores.
+
+The results will be in rootingHazards.txt
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/analyzeRoots.js
@@ -0,0 +1,522 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+load('utility.js');
+load('annotations.js');
+load('suppressedPoints.js');
+
+var sourceRoot = null;
+
+var functionName;
+var functionBodies;
+
+if (typeof arguments[0] != 'string' || typeof arguments[1] != 'string')
+    throw "Usage: analyzeRoots.js <gcFunctions.txt> <gcTypes.txt> [start end [tmpfile]]";
+
+var gcFunctionsFile = arguments[0];
+var gcTypesFile = arguments[1];
+var start = arguments[2]|0;
+var end = arguments[3]|0;
+var tmpfile = arguments[4];
+if (!start)
+    start = 1;
+if (!tmpfile)
+    tmpfile = "tmp.txt";
+
+var gcFunctions = {};
+var suppressedFunctions = {};
+var gcFunctionsText = snarf(gcFunctionsFile).split('\n');
+for (var line of gcFunctionsText) {
+    if (match = /GC Function: (.*)/.exec(line))
+        gcFunctions[match[1]] = true;
+    if (match = /Suppressed Function: (.*)/.exec(line))
+        suppressedFunctions[match[1]] = true;
+}
+gcFunctionsText = null;
+
+var match;
+var gcThings = {};
+var gcPointers = {};
+
+var gcTypesText = snarf(gcTypesFile).split('\n');
+for (var line of gcTypesText) {
+    if (match = /GCThing: (.*)/.exec(line))
+        gcThings[match[1]] = true;
+    if (match = /GCPointer: (.*)/.exec(line))
+        gcPointers[match[1]] = true;
+}
+gcTypesText = null;
+
+function isUnrootedType(type)
+{
+    if (type.Kind == "Pointer") {
+        var target = type.Type;
+        if (target.Kind == "CSU")
+            return target.Name in gcThings;
+        return false;
+    }
+    if (type.Kind == "CSU")
+        return type.Name in gcPointers;
+    return false;
+}
+
+function expressionUsesVariable(exp, variable)
+{
+    if (exp.Kind == "Var" && sameVariable(exp.Variable, variable))
+        return true;
+    if (!("Exp" in exp))
+        return false;
+    for (var childExp of exp.Exp) {
+        if (expressionUsesVariable(childExp, variable))
+            return true;
+    }
+    return false;
+}
+
+function edgeUsesVariable(edge, variable)
+{
+    if (ignoreEdgeUse(edge, variable))
+        return false;
+    switch (edge.Kind) {
+    case "Assign":
+        if (expressionUsesVariable(edge.Exp[0], variable))
+            return true;
+        return expressionUsesVariable(edge.Exp[1], variable);
+    case "Assume":
+        return expressionUsesVariable(edge.Exp[0], variable);
+    case "Call":
+        if (expressionUsesVariable(edge.Exp[0], variable))
+            return true;
+        if (1 in edge.Exp && expressionUsesVariable(edge.Exp[1], variable))
+            return true;
+        if ("PEdgeCallInstance" in edge) {
+            if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable))
+                return true;
+        }
+        if ("PEdgeCallArguments" in edge) {
+            for (var exp of edge.PEdgeCallArguments.Exp) {
+                if (expressionUsesVariable(exp, variable))
+                    return true;
+            }
+        }
+        return false;
+    case "Loop":
+        return false;
+    default:
+        assert(false);
+    }
+}
+
+function edgeKillsVariable(edge, variable)
+{
+    // Direct assignments kill their lhs.
+    if (edge.Kind == "Assign") {
+        var lhs = edge.Exp[0];
+        if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
+            return true;
+    }
+
+    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))
+            return true;
+    }
+
+    // Constructor calls kill their 'this' value.
+    if ("PEdgeCallInstance" in edge) {
+        do {
+            var instance = edge.PEdgeCallInstance.Exp;
+
+            // 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;
+
+            var callee = edge.Exp[0];
+            if (callee.Kind != "Var")
+                break;
+
+            assert(callee.Variable.Kind == "Func");
+            var calleeName = 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);
+
+            var lastColon = calleeName.lastIndexOf('::');
+            if (lastColon < 0)
+                break;
+            var constructorName = calleeName.substr(lastColon + 2);
+            calleeName = calleeName.substr(0, lastColon);
+
+            var lastTemplateOpen = calleeName.lastIndexOf('<');
+            if (lastTemplateOpen >= 0)
+                calleeName = calleeName.substr(0, lastTemplateOpen);
+
+            if (calleeName.endsWith(constructorName))
+                return true;
+        } while (false);
+    }
+
+    return false;
+}
+
+function edgeCanGC(edge)
+{
+    if (functionName in suppressedFunctions)
+        return false;
+    if (edge.Kind != "Call")
+        return false;
+    var callee = edge.Exp[0];
+    if (callee.Kind == "Var") {
+        var variable = callee.Variable;
+        assert(variable.Kind == "Func");
+        if (variable.Name[0] in gcFunctions)
+            return "'" + variable.Name[0] + "'";
+        var otherName = otherDestructorName(variable.Name[0]);
+        if (otherName in gcFunctions)
+            return "'" + otherName + "'";
+        return null;
+    }
+    assert(callee.Kind == "Drf");
+    if (callee.Exp[0].Kind == "Fld") {
+        var field = callee.Exp[0].Field;
+        var csuName = field.FieldCSU.Type.Name;
+        var fieldName = field.Name[0];
+        return fieldCallCannotGC(csuName, fieldName) ? null : csuName + "." + fieldName;
+    }
+    assert(callee.Exp[0].Kind == "Var");
+    var calleeName = callee.Exp[0].Variable.Name[0];
+    return indirectCallCannotGC(functionName, calleeName) ? null : "*" + calleeName;
+}
+
+function computePredecessors(body)
+{
+    body.predecessors = [];
+    if (!("PEdge" in body))
+        return;
+    for (var edge of body.PEdge) {
+        var target = edge.Index[1];
+        if (!(target in body.predecessors))
+            body.predecessors[target] = [];
+        body.predecessors[target].push(edge);
+    }
+}
+
+function variableUseFollowsGC(variable, worklist)
+{
+    while (worklist.length) {
+        var entry = worklist.pop();
+        var body = entry.body, ppoint = entry.ppoint;
+
+        if (body.seen) {
+            if (ppoint in body.seen) {
+                var seenEntry = body.seen[ppoint];
+                if (!entry.gcInfo || seenEntry.gcInfo)
+                    continue;
+            }
+        } else {
+            body.seen = [];
+        }
+        body.seen[ppoint] = {body:body, gcInfo:entry.gcInfo};
+
+        if (ppoint == body.Index[0]) {
+            if (body.BlockId.Kind == "Loop") {
+                // propagate to parents which 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,
+                                               gcInfo:entry.gcInfo, why:entry});
+                            }
+                        }
+                        assert(found);
+                    }
+                }
+            } else if (variable.Kind == "Arg" && entry.gcInfo) {
+                return {gcInfo:entry.gcInfo, why:entry};
+            }
+        }
+
+        if (!body.predecessors)
+            computePredecessors(body);
+
+        if (!(ppoint in body.predecessors))
+            continue;
+
+        for (var edge of body.predecessors[ppoint]) {
+            var source = edge.Index[0];
+
+            if (edgeKillsVariable(edge, variable)) {
+                if (entry.gcInfo)
+                    return {gcInfo:entry.gcInfo, why:entry};
+                if (!body.minimumUse || source < body.minimumUse)
+                    body.minimumUse = source;
+                continue;
+            }
+
+            var gcInfo = entry.gcInfo;
+            if (!gcInfo && !(edge.Index[0] in body.suppressed)) {
+                var gcName = edgeCanGC(edge);
+                if (gcName)
+                    gcInfo = {name:gcName, body:body, ppoint:source};
+            }
+
+            if (edgeUsesVariable(edge, variable)) {
+                if (gcInfo)
+                    return {gcInfo:gcInfo, why:entry};
+                if (!body.minimumUse || source < body.minimumUse)
+                    body.minimumUse = source;
+            }
+
+            if (edge.Kind == "Loop") {
+                // propagate to exit points of the loop body, in addition to the
+                // predecessor of the loop edge itself.
+                var found = false;
+                for (var xbody of functionBodies) {
+                    if (sameBlockId(xbody.BlockId, edge.BlockId)) {
+                        assert(!found);
+                        found = true;
+                        worklist.push({body:xbody, ppoint:xbody.Index[1],
+                                       gcInfo:gcInfo, why:entry});
+                    }
+                }
+                assert(found);
+                break;
+            }
+            worklist.push({body:body, ppoint:source, gcInfo:gcInfo, why:entry});
+        }
+    }
+
+    return null;
+}
+
+function variableLiveAcrossGC(variable)
+{
+    for (var body of functionBodies) {
+        body.seen = null;
+        body.minimumUse = 0;
+    }
+    for (var body of functionBodies) {
+        if (!("PEdge" in body))
+            continue;
+        for (var edge of body.PEdge) {
+            if (edgeUsesVariable(edge, variable) && !edgeKillsVariable(edge, variable)) {
+                var worklist = [{body:body, ppoint:edge.Index[0], gcInfo:null, why:null}];
+                var call = variableUseFollowsGC(variable, worklist);
+                if (call)
+                    return call;
+            }
+        }
+    }
+    return null;
+}
+
+function computePrintedLines()
+{
+    assert(!system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile));
+    var lines = snarf(tmpfile).split('\n');
+
+    for (var body of functionBodies)
+        body.lines = [];
+
+    // Distribute lines of output to the block they originate from.
+    var currentBody = null;
+    for (var i = 0; i < lines.length; i++) {
+        var line = lines[i];
+        if (/^block:/.test(line)) {
+            if (match = /:(loop#[\d#]+)/.exec(line)) {
+                var loop = match[1];
+                var found = false;
+                for (var body of functionBodies) {
+                    if (body.BlockId.Kind == "Loop" && body.BlockId.Loop == loop) {
+                        assert(!found);
+                        found = true;
+                        currentBody = body;
+                    }
+                }
+                assert(found);
+            } else {
+                for (var body of functionBodies) {
+                    if (body.BlockId.Kind == "Function")
+                        currentBody = body;
+                }
+            }
+        }
+        if (currentBody)
+            currentBody.lines.push(line);
+    }
+}
+
+function findLocation(body, ppoint)
+{
+    var location = body.PPoint[ppoint - 1].Location;
+    var text = location.CacheString + ":" + location.Line;
+    if (text.indexOf(sourceRoot) == 0)
+        return text.substring(sourceRoot.length);
+    return text;
+}
+
+function locationLine(text)
+{
+    if (match = /:(\d+)$/.exec(text))
+        return match[1];
+    return 0;
+}
+
+function printEntryTrace(entry)
+{
+    if (!functionBodies[0].lines)
+        computePrintedLines();
+
+    while (entry) {
+        var ppoint = entry.ppoint;
+        var lineText = findLocation(entry.body, ppoint);
+
+        var edgeText = null;
+        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;
+            for (var line of entry.body.lines) {
+                if (match = /\((\d+),(\d+),/.exec(line)) {
+                    if (match[1] == ppoint && match[2] == next)
+                        edgeText = line; // May be multiple
+                }
+            }
+            assert(edgeText);
+        } else {
+            // Look for any outgoing edge from the chosen point.
+            for (var line of entry.body.lines) {
+                if (match = /\((\d+),/.exec(line)) {
+                    if (match[1] == ppoint) {
+                        edgeText = line;
+                        break;
+                    }
+                }
+            }
+        }
+
+        print("    " + lineText + (edgeText ? ": " + edgeText : ""));
+        entry = entry.why;
+    }
+}
+
+function isRootedType(type)
+{
+    return type.Kind == "CSU" && isRootedTypeName(type.Name);
+}
+
+function typeDesc(type)
+{
+    if (type.Kind == "CSU") {
+        return type.Name;
+    } else if ('Type' in type) {
+        var inner = typeDesc(type.Type);
+        if (type.Kind == 'Pointer')
+            return inner + '*';
+        else if (type.Kind == 'Array')
+            return inner + '[]';
+        else
+            return inner + '?';
+    } else {
+        return '???';
+    }
+}
+
+function processBodies()
+{
+    if (!("DefineVariable" in functionBodies[0]))
+        return;
+    for (var variable of functionBodies[0].DefineVariable) {
+        if (variable.Variable.Kind == "Return")
+            continue;
+        var name;
+        if (variable.Variable.Kind == "This")
+            name = "this";
+        else
+            name = variable.Variable.Name[0];
+        if (isRootedType(variable.Type)) {
+            if (!variableLiveAcrossGC(variable.Variable)) {
+                // The earliest use of the variable should be its constructor.
+                var lineText;
+                for (var body of functionBodies) {
+                    if (body.minimumUse) {
+                        var text = findLocation(body, body.minimumUse);
+                        if (!lineText || locationLine(lineText) > locationLine(text))
+                            lineText = text;
+                    }
+                }
+                print("\nFunction '" + functionName + "'" +
+                      " has unnecessary root '" + name + "' at " + lineText);
+            }
+        } else if (isUnrootedType(variable.Type)) {
+            var result = variableLiveAcrossGC(variable.Variable);
+            if (result) {
+                var lineText = findLocation(result.gcInfo.body, result.gcInfo.ppoint);
+                print("\nFunction '" + functionName + "'" +
+                      " has unrooted '" + name + "'" +
+                      " of type '" + typeDesc(variable.Type) + "'" +
+                      " live across GC call " + result.gcInfo.name +
+                      " at " + lineText);
+                printEntryTrace(result.why);
+            }
+        }
+    }
+}
+
+if (start == 1)
+    print("Time: " + new Date);
+
+var xdb = xdbLibrary();
+xdb.open("src_body.xdb");
+
+var minStream = xdb.min_data_stream()|0;
+var maxStream = xdb.max_data_stream()|0;
+
+start += minStream - 1;
+end += minStream - 1;
+
+// Find the source tree
+for (let nameIndex = minStream; nameIndex <= maxStream; nameIndex++) {
+    var name = xdb.read_key(nameIndex);
+    functionName = name.readString();
+    var data = xdb.read_entry(name);
+    functionBodies = JSON.parse(data.readString());
+    let filename = functionBodies[0].Location[0].CacheString;
+    let match = /(.*\/)js\/src\//.exec(filename);
+    if (match) {
+        sourceRoot = match[1];
+        printErr("sourceRoot = " + sourceRoot);
+        break;
+    }
+}
+assert(sourceRoot);
+
+for (var nameIndex = start; nameIndex <= end; nameIndex++) {
+    var name = xdb.read_key(nameIndex);
+    functionName = name.readString();
+    var data = xdb.read_entry(name);
+    functionBodies = JSON.parse(data.readString());
+
+    for (var body of functionBodies)
+        body.suppressed = [];
+    for (var body of functionBodies)
+        computeSuppressedPoints(body);
+     processBodies();
+
+    xdb.free_string(name);
+    xdb.free_string(data);
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/annotations.js
@@ -0,0 +1,98 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+function indirectCallCannotGC(caller, name)
+{
+    if (name == "mallocSizeOf")
+        return true;
+
+    // hook called during script finalization which cannot GC.
+    if (/CallDestroyScriptHook/.test(caller))
+        return true;
+
+    return false;
+}
+
+// classes to ignore indirect calls on.
+var ignoreClasses = [
+    "JSTracer",
+    "JSStringFinalizer",
+    "SprintfStateStr",
+    "JSLocaleCallbacks",
+    "JSC::ExecutableAllocator"
+];
+
+function fieldCallCannotGC(csu, field)
+{
+    for (var i = 0; i < ignoreClasses.length; i++) {
+        if (csu == ignoreClasses[i])
+            return true;
+    }
+    if (csu == "js::Class" && (field == "trace" || field == "finalize"))
+        return true;
+    if (csu == "JSRuntime" && field == "destroyPrincipals")
+        return true;
+    return false;
+}
+
+function shouldSuppressGC(name)
+{
+    // Various dead code that should only be called inside AutoEnterAnalysis.
+    // Functions with no known caller are by default treated as not suppressing GC.
+    return /TypeScript::Purge/.test(name)
+        || /StackTypeSet::addPropagateThis/.test(name)
+        || /ScriptAnalysis::addPushedType/.test(name)
+        || /IonBuilder/.test(name);
+}
+
+function ignoreEdgeUse(edge, variable)
+{
+    // Functions which should not be treated as using variable.
+    if (edge.Kind == "Call") {
+        var callee = edge.Exp[0];
+        if (callee.Kind == "Var") {
+            var name = callee.Variable.Name[0];
+            if (/~Anchor/.test(name))
+                return true;
+            if (/::Unrooted\(\)/.test(name))
+                return true;
+            if (/::~Unrooted\(\)/.test(name))
+                return true;
+            if (/~DebugOnly/.test(name))
+                return true;
+        }
+    }
+
+    return false;
+}
+
+function ignoreGCFunction(fun)
+{
+    // XXX modify refillFreeList<NoGC> to not need data flow analysis to understand it cannot GC.
+    if (/refillFreeList/.test(fun) && /\(js::AllowGC\)0u/.test(fun))
+        return true;
+    return false;
+}
+
+function isRootedTypeName(name)
+{
+    if (name.startsWith('struct '))
+        name = name.substr(7);
+    if (name.startsWith('class '))
+        name = name.substr(6);
+    if (name.startsWith('const '))
+        name = name.substr(6);
+    if (name.startsWith('js::'))
+        name = name.substr(4);
+    if (name.startsWith('JS::'))
+        name = name.substr(4);
+
+    return name.startsWith('Rooted');
+}
+
+function isSuppressConstructor(name)
+{
+    return /::AutoSuppressGC/.test(name)
+        || /::AutoEnterAnalysis/.test(name);
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/computeCallgraph.js
@@ -0,0 +1,158 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+load('utility.js');
+load('annotations.js');
+load('suppressedPoints.js');
+
+var subclasses = {};
+var classFunctions = {};
+
+function processCSU(csuName, csu)
+{
+    if (!("FunctionField" in csu))
+        return;
+    for (var field of csu.FunctionField) {
+        if (1 in field.Field) {
+            var superclass = field.Field[1].Type.Name;
+            var subclass = field.Field[1].FieldCSU.Type.Name;
+            assert(subclass == csuName);
+            if (!(superclass in subclasses))
+                subclasses[superclass] = [];
+            var found = false;
+            for (var sub of subclasses[superclass]) {
+                if (sub == subclass)
+                    found = true;
+            }
+            if (!found)
+                subclasses[superclass].push(subclass);
+        }
+        if ("Variable" in field) {
+            // Note: not dealing with overloading correctly.
+            var name = field.Variable.Name[0];
+            var key = csuName + ":" + field.Field[0].Name[0];
+            if (!(key in classFunctions))
+                classFunctions[key] = [];
+            classFunctions[key].push(name);
+        }
+    }
+}
+
+function findVirtualFunctions(csu, field)
+{
+    var functions = [];
+    var worklist = [csu];
+
+    while (worklist.length) {
+        var csu = worklist.pop();
+        var key = csu + ":" + field;
+
+        if (key in classFunctions) {
+            for (var name of classFunctions[key])
+                functions.push(name);
+        }
+
+        if (csu in subclasses) {
+            for (var subclass of subclasses[csu])
+                worklist.push(subclass);
+        }
+    }
+
+    return functions;
+}
+
+var memoized = {};
+var memoizedCount = 0;
+
+function memo(name)
+{
+    if (!(name in memoized)) {
+        memoizedCount++;
+        memoized[name] = "" + memoizedCount;
+        print("#" + memoizedCount + " " + name);
+    }
+    return memoized[name];
+}
+
+function processBody(caller, body)
+{
+    if (!('PEdge' in body))
+        return;
+    for (var edge of body.PEdge) {
+        if (edge.Kind != "Call")
+            continue;
+        var callee = edge.Exp[0];
+        var suppressText = (edge.Index[0] in body.suppressed) ? "SUPPRESS_GC " : "";
+        var prologue = suppressText + memo(caller) + " ";
+        if (callee.Kind == "Var") {
+            assert(callee.Variable.Kind == "Func");
+            var name = callee.Variable.Name[0];
+            print("D " + prologue + memo(name));
+            var otherName = otherDestructorName(name);
+            if (otherName)
+                print("D " + prologue + memo(otherName));
+        } else {
+            assert(callee.Kind == "Drf");
+            if (callee.Exp[0].Kind == "Fld") {
+                var field = callee.Exp[0].Field;
+                if ("FieldInstanceFunction" in field) {
+                    // virtual function call.
+                    var functions = findVirtualFunctions(field.FieldCSU.Type.Name, field.Name[0]);
+                    for (var name of functions)
+                        print("D " + prologue + memo(name));
+                } else {
+                    // indirect call through a field.
+                    print("F " + prologue +
+                          "CLASS " + field.FieldCSU.Type.Name +
+                          " FIELD " + field.Name[0]);
+                }
+            } else if (callee.Exp[0].Kind == "Var") {
+                // indirect call through a variable.
+                print("I " + prologue +
+                      "VARIABLE " + callee.Exp[0].Variable.Name[0]);
+            } else {
+                // unknown call target.
+                print("I " + prologue + "VARIABLE UNKNOWN");
+            }
+        }
+    }
+}
+
+var callgraph = {};
+
+var xdb = xdbLibrary();
+xdb.open("src_comp.xdb");
+
+var minStream = xdb.min_data_stream();
+var maxStream = xdb.max_data_stream();
+
+for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
+    var csu = xdb.read_key(csuIndex);
+    var data = xdb.read_entry(csu);
+    var json = JSON.parse(data.readString());
+    processCSU(csu.readString(), json[0]);
+
+    xdb.free_string(csu);
+    xdb.free_string(data);
+}
+
+xdb.open("src_body.xdb");
+
+var minStream = xdb.min_data_stream();
+var maxStream = xdb.max_data_stream();
+
+for (var nameIndex = minStream; nameIndex <= maxStream; nameIndex++) {
+    var name = xdb.read_key(nameIndex);
+    var data = xdb.read_entry(name);
+    functionBodies = JSON.parse(data.readString());
+    for (var body of functionBodies)
+        body.suppressed = [];
+    for (var body of functionBodies)
+        computeSuppressedPoints(body);
+    for (var body of functionBodies)
+        processBody(name.readString(), body);
+
+    xdb.free_string(name);
+    xdb.free_string(data);
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/computeGCFunctions.js
@@ -0,0 +1,28 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+load('utility.js');
+load('annotations.js');
+load('loadCallgraph.js');
+
+if (typeof arguments[0] != 'string')
+    throw "Usage: computeGCFunctions.js <callgraph.txt>";
+
+print("Time: " + new Date);
+
+loadCallgraph(arguments[0]);
+
+for (var name in gcFunctions) {
+    print("");
+    print("GC Function: " + name);
+    do {
+        name = gcFunctions[name];
+        print("    " + name);
+    } while (name in gcFunctions);
+}
+
+for (var name in suppressedFunctions) {
+    print("");
+    print("Suppressed Function: " + name);
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/computeGCTypes.js
@@ -0,0 +1,95 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+load('utility.js');
+load('annotations.js');
+
+function processCSU(csu, body)
+{
+    if (!("DataField" in body))
+        return;
+    for (var field of body.DataField) {
+        var type = field.Field.Type;
+        if (type.Kind == "Pointer") {
+            var target = type.Type;
+            if (target.Kind == "CSU")
+                addNestedPointer(csu, target.Name);
+        }
+        if (type.Kind == "CSU") {
+            // Ignore nesting in classes which are AutoGCRooters. We only consider
+            // types with fields that may not be properly rooted.
+            if (type.Name == "JS::AutoGCRooter")
+                return;
+            addNestedStructure(csu, type.Name);
+        }
+    }
+}
+
+function addNestedStructure(csu, inner)
+{
+    if (!(inner in structureParents))
+        structureParents[inner] = [];
+    structureParents[inner].push(csu);
+}
+
+function addNestedPointer(csu, inner)
+{
+    if (!(inner in pointerParents))
+        pointerParents[inner] = [];
+    pointerParents[inner].push(csu);
+}
+
+var structureParents = {};
+var pointerParents = {};
+
+var xdb = xdbLibrary();
+xdb.open("src_comp.xdb");
+
+var minStream = xdb.min_data_stream();
+var maxStream = xdb.max_data_stream();
+
+for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
+    var csu = xdb.read_key(csuIndex);
+    var data = xdb.read_entry(csu);
+    var json = JSON.parse(data.readString());
+    assert(json.length == 1);
+    processCSU(csu.readString(), json[0]);
+
+    xdb.free_string(csu);
+    xdb.free_string(data);
+}
+
+function addGCType(name)
+{
+    print("GCThing: " + name);
+    if (name in structureParents) {
+        for (var nested of structureParents[name])
+            addGCType(nested);
+    }
+    if (name in pointerParents) {
+        for (var nested of pointerParents[name])
+            addGCPointer(nested);
+    }
+}
+
+function addGCPointer(name)
+{
+    // Ignore types which are properly rooted.
+    if (isRootedTypeName(name))
+        return;
+    print("GCPointer: " + name);
+    if (name in structureParents) {
+        for (var nested of structureParents[name])
+            addGCPointer(nested);
+    }
+}
+
+addGCType('js::ObjectImpl');
+addGCType('JSString');
+addGCType('js::Shape');
+addGCType('js::BaseShape');
+addGCType('JSScript');
+addGCType('js::ion::IonCode');
+addGCPointer('JS::Value');
+addGCPointer('jsid');
new file mode 100755
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/gen-hazards.sh
@@ -0,0 +1,20 @@
+#!/bin/sh
+
+set -e
+
+JOBS="$1"
+
+N=$($SIXGILL/bin/xdbkeys src_body.xdb | wc -l)
+EACH=$(( $N / $JOBS ))
+START=1
+for j in $(seq $JOBS); do
+    END=$(( $START + $EACH ))
+    env PATH=$PATH:$SIXGILL/bin XDB=$SIXGILL/bin/xdb.so $JS $ANALYZE gcFunctions.txt gcTypes.txt $START $END tmp.$j > rootingHazards.$j &
+    START=$END
+done
+
+wait
+
+for j in $(seq $JOBS); do
+    cat rootingHazards.$j
+done
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/loadCallgraph.js
@@ -0,0 +1,120 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+var calleeGraph = {};
+var callerGraph = {};
+var gcFunctions = {};
+var suppressedFunctions = {};
+
+function addGCFunction(caller, reason)
+{
+    if (caller in suppressedFunctions)
+        return false;
+
+    if (ignoreGCFunction(caller))
+        return false;
+
+    if (!(caller in gcFunctions)) {
+        gcFunctions[caller] = reason;
+        return true;
+    }
+
+    return false;
+}
+
+function addCallEdge(caller, callee, suppressed)
+{
+    if (!(caller in calleeGraph))
+        calleeGraph[caller] = [];
+    calleeGraph[caller].push({callee:callee, suppressed:suppressed});
+
+    if (!(callee in callerGraph))
+        callerGraph[callee] = [];
+    callerGraph[callee].push({caller:caller, suppressed:suppressed});
+}
+
+var functionNames = [""];
+
+function loadCallgraph(file)
+{
+    var textLines = snarf(file).split('\n');
+    for (var line of textLines) {
+	    var match;
+        if (match = /^\#(\d+) (.*)/.exec(line)) {
+            assert(functionNames.length == match[1]);
+            functionNames.push(match[2]);
+            continue;
+        }
+	    var suppressed = false;
+	    if (/SUPPRESS_GC/.test(line)) {
+            match = /^(..)SUPPRESS_GC (.*)/.exec(line);
+            line = match[1] + match[2];
+            suppressed = true;
+	    }
+	    if (match = /^I (\d+) VARIABLE ([^\,]*)/.exec(line)) {
+            var caller = functionNames[match[1]];
+            var name = match[2];
+            if (!indirectCallCannotGC(caller, name) && !suppressed)
+		        addGCFunction(caller, "IndirectCall: " + name);
+	    } else if (match = /^F (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) {
+            var caller = functionNames[match[1]];
+            var csu = match[2];
+            var field = match[3];
+            if (!fieldCallCannotGC(csu, field) && !suppressed)
+		        addGCFunction(caller, "FieldCall: " + csu + "." + field);
+	    } else if (match = /^D (\d+) (\d+)/.exec(line)) {
+            var caller = functionNames[match[1]];
+            var callee = functionNames[match[2]];
+            addCallEdge(caller, callee, suppressed);
+	    }
+    }
+
+    var worklist = [];
+    for (var name in callerGraph)
+	    suppressedFunctions[name] = true;
+    for (var name in calleeGraph) {
+	    if (!(name in callerGraph)) {
+            suppressedFunctions[name] = true;
+            worklist.push(name);
+	    }
+    }
+    while (worklist.length) {
+	    name = worklist.pop();
+	    if (shouldSuppressGC(name))
+            continue;
+	    if (!(name in suppressedFunctions))
+            continue;
+	    delete suppressedFunctions[name];
+	    if (!(name in calleeGraph))
+            continue;
+	    for (var entry of calleeGraph[name]) {
+            if (!entry.suppressed)
+		        worklist.push(entry.callee);
+	    }
+    }
+
+    for (var name in gcFunctions) {
+	    if (name in suppressedFunctions)
+            delete gcFunctions[name];
+    }
+
+    var gcName = 'void js::GC(JSRuntime*, uint32, uint32)';
+    assert(gcName in callerGraph);
+    addGCFunction(gcName, "GC");
+
+    var worklist = [];
+    for (var name in gcFunctions)
+	    worklist.push(name);
+
+    while (worklist.length) {
+	    name = worklist.pop();
+	    assert(name in gcFunctions);
+	    if (!(name in callerGraph))
+            continue;
+	    for (var entry of callerGraph[name]) {
+            if (!entry.suppressed && addGCFunction(entry.caller, name))
+		        worklist.push(entry.caller);
+	    }
+    }
+}
new file mode 100755
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/run_complete
@@ -0,0 +1,344 @@
+#!/usr/bin/perl
+
+# Sixgill: Static assertion checker for C/C++ programs.
+# Copyright (C) 2009-2010  Stanford University
+# Author: Brian Hackett
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# do a complete run of the system from raw source to reports. this requires
+# various run_monitor processes to be running in the background (maybe on other
+# machines) and watching a shared poll_file for jobs. if the output directory
+# for this script already exists then an incremental analysis will be performed
+# and the reports will only reflect the changes since the earlier run.
+
+use strict;
+use IO::Handle;
+use File::Basename qw(dirname);
+use Getopt::Long;
+
+#################################
+# environment specific settings #
+#################################
+
+my $WORKDIR;
+my $SIXGILL_BIN;
+
+# poll file shared with the run_monitor script.
+my $poll_file;
+
+# root directory of the project.
+my $build_dir;
+
+# directory containing gcc wrapper scripts.
+my $wrap_dir;
+
+# optional file with annotations from the web interface.
+my $ann_file = "";
+
+# optional output directory to do a diff against.
+my $old_dir = "";
+
+# run in the foreground
+my $foreground;
+
+GetOptions("build-root|b=s" => \$build_dir,
+           "poll-file=s" => \$poll_file,
+           "work-dir=s" => \$WORKDIR,
+           "sixgill-binaries|binaries|b=s" => \$SIXGILL_BIN,
+           "wrap-dir=s" => \$wrap_dir,
+           "annotations-file|annotations|a=s" => \$ann_file,
+           "old-dir|old=s" => \$old_dir,
+           "foreground!" => \$foreground,
+           )
+    or die;
+
+if (not -d $build_dir) {
+    die "Need build directory: $build_dir\n";
+}
+if ($old_dir ne "" && not -d $old_dir) {
+    die "Old directory '$old_dir' does not exist\n";
+}
+
+$WORKDIR ||= "sixgill-work";
+$poll_file ||= "$WORKDIR/poll.file";
+$build_dir ||= "$WORKDIR/js-inbound-xgill";
+
+if (not -d $build_dir) {
+    die "Build root '$build_dir' does not exist\n";
+}
+
+if (!defined $SIXGILL_BIN) {
+    chomp(my $path = `which xmanager`);
+    if ($path) {
+        use File::Basename qw(dirname);
+        $SIXGILL_BIN = dirname($path);
+    } else {
+        die "Cannot find sixgill binaries. Use the -b option.";
+    }
+}
+
+$wrap_dir ||= "$WORKDIR/xgill-inbound/wrap_gcc";
+$wrap_dir = "$SIXGILL_BIN/../scripts/wrap_gcc" if not (-e "$wrap_dir/basecc");
+die "Bad wrapper directory: $wrap_dir" if not (-e "$wrap_dir/basecc");
+
+# code to clean the project from $build_dir.
+sub clean_project {
+    system("make clean");
+}
+
+# code to build the project from $build_dir.
+sub build_project {
+    if ($ENV{BUILD}) {
+        return system($ENV{BUILD});
+    } else {
+        return system("make -j4");
+    }
+}
+
+# commands to start the various xgill binaries. timeouts can be specified
+# for the backend analyses here, and a memory limit can be specified for
+# xmanager if desired (and USE_COUNT_ALLOCATOR is defined in util/alloc.h).
+my $xmanager = "$SIXGILL_BIN/xmanager";
+my $xsource = "$SIXGILL_BIN/xsource";
+my $xmemlocal = "$SIXGILL_BIN/xmemlocal -timeout=20";
+my $xinfer = "$SIXGILL_BIN/xinfer -timeout=60";
+my $xcheck = "$SIXGILL_BIN/xcheck -timeout=30";
+
+# prefix directory to strip off source files.
+my $prefix_dir = $build_dir;
+
+##########################
+# general purpose script #
+##########################
+
+# Prevent ccache from being used. I don't think this does any good. The problem
+# I'm struggling with is that if autoconf.mk still has 'ccache gcc' in it, the
+# builds fail in a mysterious way.
+$ENV{CCACHE_COMPILERCHECK} = 'date +%s.%N';
+delete $ENV{CCACHE_PREFIX};
+
+my $usage = "USAGE: run_complete result-dir\n";
+my $result_dir = shift or die $usage;
+
+if (not $foreground) {
+    my $pid = fork();
+    if ($pid != 0) {
+        print "Forked, exiting...\n";
+        exit(0);
+    }
+}
+
+# if the result directory does not already exist, mark for a clean build.
+my $do_clean = 0;
+if (not (-d $result_dir)) {
+    $do_clean = 1;
+    mkdir $result_dir;
+}
+
+open(OUT, ">> $result_dir/complete.log");
+OUT->autoflush(1);  # don't buffer writes to the main log.
+
+# redirect stdout and stderr to the log.
+STDOUT->fdopen(\*OUT, "w");
+STDERR->fdopen(\*OUT, "w");
+
+# pids to wait on before exiting. these are collating worker output.
+my @waitpids;
+
+chdir $result_dir;
+
+# to do a partial run, comment out the commands here you don't want to do.
+
+my $status = run_build();
+
+# end of run commands.
+
+close(OUT);
+
+for my $pid (@waitpids) {
+    waitpid($pid, 0);
+    $status ||= $?;
+}
+
+exit $status;
+
+# get the IP address which a freshly created manager is listening on.
+sub get_manager_address
+{
+    my $log_file = shift or die;
+
+    # give the manager one second to start, any longer and something's broken.
+    sleep(1);
+
+    my $log_data = `cat $log_file`;
+    $log_data =~ /Listening on ([\.\:0-9]*)/ or die;
+    return $1;
+}
+
+sub run_build
+{
+    print "build started: ";
+    print scalar(localtime());
+    print "\n";
+
+    # fork off a process to run the build.
+    defined(my $pid = fork) or die;
+
+    # log file for the manager.
+    my $log_file = "$result_dir/build_manager.log";
+
+    if (!$pid) {
+        # this is the child process, fork another process to run a manager.
+        defined(my $pid = fork) or die;
+        exec("$xmanager -terminate-on-assert > $log_file 2>&1") if (!$pid);
+
+        # open new streams to redirect stdout and stderr.
+        open(LOGOUT, "> $result_dir/build.log");
+        open(LOGERR, "> $result_dir/build_err.log");
+        STDOUT->fdopen(\*LOGOUT, "w");
+        STDERR->fdopen(\*LOGERR, "w");
+
+        my $address = get_manager_address($log_file);
+
+        # write the configuration file for the wrapper script.
+        open(CONFIG, "> $wrap_dir/xgill.config");
+        print CONFIG "$prefix_dir\n";
+        print CONFIG "$result_dir/build_xgill.log\n";
+        print CONFIG "$address\n";
+        print CONFIG "-fplugin-arg-xgill-annfile=$ann_file\n"
+          if ($ann_file ne "" && -e $ann_file);
+        close(CONFIG);
+
+        # update the PATH so that the build will see the wrappers.
+        $ENV{"PATH"} = "$wrap_dir:" . $ENV{"PATH"};
+
+        # do the build, cleaning if necessary.
+        chdir $build_dir;
+        clean_project() if ($do_clean);
+        my $exit_status = build_project();
+
+        # signal the manager that it's over.
+        system("$xsource -remote=$address -end-manager");
+
+        # wait for the manager to clean up and terminate.
+        print "Waiting for manager to finish...\n";
+        waitpid($pid, 0);
+
+        # build is finished, the complete run can resume.
+        # return value only useful if --foreground
+        exit $? || $exit_status;
+    }
+
+    # this is the complete process, wait for the build to finish.
+    waitpid($pid, 0);
+    my $status = $?;
+
+    print "build finished: ";
+    print scalar(localtime());
+    print "\n";
+
+    return $status;
+}
+
+sub run_pass
+{
+    my ($name, $command) = @_;
+    my $log_file = "$result_dir/manager.$name.log";
+
+    # extra commands to pass to the manager.
+    my $manager_extra = "";
+    $manager_extra .= "-modset-wait=10" if ($name eq "xmemlocal");
+
+    # fork off a manager process for the analysis.
+    defined(my $pid = fork) or die;
+    exec("$xmanager $manager_extra > $log_file 2>&1") if (!$pid);
+
+    my $address = get_manager_address($log_file);
+
+    # write the poll file for this pass.
+    if (! -d dirname($poll_file)) {
+        system("mkdir", "-p", dirname($poll_file));
+    }
+    open(POLL, "> $poll_file");
+    print POLL "$command\n";
+    print POLL "$result_dir/$name\n";
+    print POLL "$address\n";
+    close(POLL);
+
+    print "$name started: ";
+    print scalar(localtime());
+    print "\n";
+
+    waitpid($pid, 0);
+    unlink($poll_file);
+
+    print "$name finished: ";
+    print scalar(localtime());
+    print "\n";
+
+    # collate the worker's output into a single file. make this asynchronous
+    # so we can wait a bit and make sure we get all worker output.
+    defined(my $pid = fork) or die;
+
+    if (!$pid) {
+        sleep(20);
+        exec("cat $name.*.log > $name.log");
+    }
+
+    push(@waitpids, $pid);
+}
+
+# the names of all directories containing reports to archive.
+my $indexes;
+
+sub run_index
+{
+    my ($name, $kind) = @_;
+
+    return if (not (-e "report_$kind.xdb"));
+
+    print "$name started: ";
+    print scalar(localtime());
+    print "\n";
+
+    # make an index for the report diff if applicable.
+    if ($old_dir ne "") {
+        system("make_index $kind $old_dir > $name.diff.log");
+        system("mv $kind diff_$kind");
+        $indexes .= " diff_$kind";
+    }
+
+    # make an index for the full set of reports.
+    system("make_index $kind > $name.log");
+    $indexes .= " $kind";
+
+    print "$name finished: ";
+    print scalar(localtime());
+    print "\n";
+}
+
+sub archive_indexes
+{
+    print "archive started: ";
+    print scalar(localtime());
+    print "\n";
+
+    system("tar -czf reports.tgz $indexes");
+    system("rm -rf $indexes");
+
+    print "archive finished: ";
+    print scalar(localtime());
+    print "\n";
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/suppressedPoints.js
@@ -0,0 +1,97 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+var functionBodies;
+
+function suppressAllPoints(id)
+{
+    var body = null;
+    for (var xbody of functionBodies) {
+        if (sameBlockId(xbody.BlockId, id)) {
+            assert(!body);
+            body = xbody;
+        }
+    }
+    assert(body);
+
+    if (!("PEdge" in body))
+        return;
+    for (var edge of body.PEdge) {
+        body.suppressed[edge.Index[0]] = true;
+        if (edge.Kind == "Loop")
+            suppressAllPoints(edge.BlockId);
+    }
+}
+
+function isMatchingDestructor(constructor, edge)
+{
+    if (edge.Kind != "Call")
+        return false;
+    var callee = edge.Exp[0];
+    if (callee.Kind != "Var")
+        return false;
+    var variable = callee.Variable;
+    assert(variable.Kind == "Func");
+    if (!/::~/.test(variable.Name[0]))
+        return false;
+
+    var constructExp = constructor.PEdgeCallInstance.Exp;
+    assert(constructExp.Kind == "Var");
+
+    var destructExp = edge.PEdgeCallInstance.Exp;
+    if (destructExp.Kind != "Var")
+        return false;
+
+    return sameVariable(constructExp.Variable, destructExp.Variable);
+}
+
+// Compute the points within a function body where GC is suppressed.
+function computeSuppressedPoints(body)
+{
+    var successors = [];
+
+    if (!("PEdge" in body))
+        return;
+    for (var edge of body.PEdge) {
+        var source = edge.Index[0];
+        if (!(source in successors))
+            successors[source] = [];
+        successors[source].push(edge);
+    }
+
+    for (var edge of body.PEdge) {
+        if (edge.Kind != "Call")
+            continue;
+        var callee = edge.Exp[0];
+        if (callee.Kind != "Var")
+            continue;
+        var variable = callee.Variable;
+        assert(variable.Kind == "Func");
+        if (!isSuppressConstructor(variable.Name[0]))
+            continue;
+        if (edge.PEdgeCallInstance.Exp.Kind != "Var")
+            continue;
+
+        var seen = [];
+        var worklist = [edge.Index[1]];
+        while (worklist.length) {
+            var point = worklist.pop();
+            if (point in seen)
+                continue;
+            seen[point] = true;
+            body.suppressed[point] = true;
+            if (!(point in successors))
+                continue;
+            for (var nedge of successors[point]) {
+                if (isMatchingDestructor(edge, nedge))
+                    continue;
+                if (nedge.Kind == "Loop")
+                    suppressAllPoints(nedge.BlockId);
+                worklist.push(nedge.Index[1]);
+            }
+        }
+    }
+
+    return [];
+}
new file mode 100644
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/utility.js
@@ -0,0 +1,80 @@
+/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+
+"use strict";
+
+function assert(x)
+{
+    if (!x)
+        throw "assertion failed: " + (Error().stack);
+}
+
+function xprint(x, padding)
+{
+    if (!padding)
+        padding = "";
+    if (x instanceof Array) {
+        print(padding + "[");
+        for (var elem of x)
+            xprint(elem, padding + " ");
+        print(padding + "]");
+    } else if (x instanceof Object) {
+        print(padding + "{");
+        for (var prop in x) {
+            print(padding + " " + prop + ":");
+            xprint(x[prop], padding + "  ");
+        }
+        print(padding + "}");
+    } else {
+        print(padding + x);
+    }
+}
+
+function sameBlockId(id0, id1)
+{
+    if (id0.Kind != id1.Kind)
+        return false;
+    if (!sameVariable(id0.Variable, id1.Variable))
+        return false;
+    if (id0.Kind == "Loop" && id0.Loop != id1.Loop)
+        return false;
+    return true;
+}
+
+function sameVariable(var0, var1)
+{
+    assert("Name" in var0 || var0.Kind == "This" || var0.Kind == "Return");
+    assert("Name" in var1 || var1.Kind == "This" || var1.Kind == "Return");
+    if ("Name" in var0)
+	return "Name" in var1 && var0.Name[0] == var1.Name[0];
+    return var0.Kind == var1.Kind;
+}
+
+function otherDestructorName(name)
+{
+    // gcc's information for destructors can be pretty messed up. Some functions
+    // have destructors with no arguments, some have destructors with an int32
+    // argument, some have both, and which one matches what the programmer wrote
+    // is anyone's guess. Work around this by treating calls to one destructor
+    // form as a call to both destructor forms.
+    if (!/::~/.test(name))
+        return null;
+
+    if (/\(int32\)/.test(name))
+        return name.replace("(int32)","()");
+    if (/\(\)/.test(name))
+        return name.replace("()","(int32)");
+    return null;
+}
+
+function xdbLibrary()
+{
+    var lib = ctypes.open(environment['XDB']);
+    return {
+        open: lib.declare("xdb_open", ctypes.default_abi, ctypes.void_t, ctypes.char.ptr),
+        min_data_stream: lib.declare("xdb_min_data_stream", ctypes.default_abi, ctypes.int),
+        max_data_stream: lib.declare("xdb_max_data_stream", ctypes.default_abi, ctypes.int),
+        read_key: lib.declare("xdb_read_key", ctypes.default_abi, ctypes.char.ptr, ctypes.int),
+        read_entry: lib.declare("xdb_read_entry", ctypes.default_abi, ctypes.char.ptr, ctypes.char.ptr),
+        free_string: lib.declare("xdb_free", ctypes.default_abi, ctypes.void_t, ctypes.char.ptr)
+    };
+}