src/third_party/mozjs-45/js/src/devtools/rootAnalysis/loadCallgraph.js

/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */

"use strict";

loadRelativeToScript('utility.js');

// Functions come out of sixgill in the form "mangled|readable". The mangled
// name is Truth. One mangled name might correspond to multiple readable names,
// for multiple reasons, including (1) sixgill/gcc doesn't always qualify types
// the same way or de-typedef the same amount; (2) sixgill's output treats
// references and pointers the same, and so doesn't distinguish them, but C++
// treats them as separate for overloading and linking; (3) (identical)
// destructors sometimes have an int32 parameter, sometimes not.
//
// The readable names are useful because they're far more meaningful to the
// user, and are what should show up in reports and questions to mrgiggles. At
// least in most cases, it's fine to have the extra mangled name tacked onto
// the beginning for these.
//
// The strategy used is to separate out the pieces whenever they are read in,
// create a table mapping mangled names to (one of the) readable names, and
// use the mangled names in all computation.
//
// Note that callgraph.txt uses a compressed representation -- each name is
// mapped to an integer, and those integers are what is recorded in the edges.
// But the integers depend on the full name, whereas the true edge should only
// consider the mangled name. And some of the names encoded in callgraph.txt
// are FieldCalls, not just function names.

var readableNames = {}; // map from mangled name => list of readable names
var mangledName = {}; // map from demangled names => mangled names. Could be eliminated.
var calleeGraph = {}; // map from mangled => list of tuples of {'callee':mangled, 'suppressed':bool}
var callerGraph = {}; // map from mangled => list of tuples of {'caller':mangled, 'suppressed':bool}
var gcFunctions = {}; // map from mangled callee => reason
var suppressedFunctions = {}; // set of mangled names (map from mangled name => true)
var gcEdges = {};

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});
}

// Map from identifier to full "mangled|readable" name. Or sometimes to a
// Class.Field name.
var functionNames = [""];

// Map from identifier to mangled name (or to a Class.Field)
var idToMangled = [""];

function loadCallgraph(file)
{
    var suppressedFieldCalls = {};
    var resolvedFunctions = {};

    for (var line of readFileLines_gen(file)) {
        line = line.replace(/\n/, "");

        var match;
        if (match = line.charAt(0) == "#" && /^\#(\d+) (.*)/.exec(line)) {
            assert(functionNames.length == match[1]);
            functionNames.push(match[2]);
            var [ mangled, readable ] = splitFunction(match[2]);
            if (mangled in readableNames)
                readableNames[mangled].push(readable);
            else
                readableNames[mangled] = [ readable ];
            mangledName[readable] = mangled;
            idToMangled.push(mangled);
            continue;
        }
        var suppressed = false;
        if (line.indexOf("SUPPRESS_GC") != -1) {
            match = /^(..)SUPPRESS_GC (.*)/.exec(line);
            line = match[1] + match[2];
            suppressed = true;
        }
        var tag = line.charAt(0);
        if (match = tag == 'I' && /^I (\d+) VARIABLE ([^\,]*)/.exec(line)) {
            var mangledCaller = idToMangled[match[1]];
            var name = match[2];
            if (!indirectCallCannotGC(functionNames[match[1]], name) && !suppressed)
                addGCFunction(mangledCaller, "IndirectCall: " + name);
        } else if (match = tag == 'F' && /^F (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) {
            var caller = idToMangled[match[1]];
            var csu = match[2];
            var fullfield = csu + "." + match[3];
            if (suppressed)
                suppressedFieldCalls[fullfield] = true;
            else if (!fieldCallCannotGC(csu, fullfield))
                addGCFunction(caller, "FieldCall: " + fullfield);
        } else if (match = tag == 'D' && /^D (\d+) (\d+)/.exec(line)) {
            var caller = idToMangled[match[1]];
            var callee = idToMangled[match[2]];
            addCallEdge(caller, callee, suppressed);
        } else if (match = tag == 'R' && /^R (\d+) (\d+)/.exec(line)) {
            var callerField = idToMangled[match[1]];
            var callee = idToMangled[match[2]];
            addCallEdge(callerField, callee, false);
            resolvedFunctions[callerField] = true;
        }
    }

    // Initialize suppressedFunctions to the set of all functions, and the
    // worklist to all toplevel callers.
    var worklist = [];
    for (var callee in callerGraph)
        suppressedFunctions[callee] = true;
    for (var caller in calleeGraph) {
        if (!(caller in callerGraph)) {
            suppressedFunctions[caller] = true;
            worklist.push(caller);
        }
    }

    // Find all functions reachable via an unsuppressed call chain, and remove
    // them from the suppressedFunctions set. Everything remaining is only
    // reachable when GC is suppressed.
    var top = worklist.length;
    while (top > 0) {
        name = worklist[--top];
        if (!(name in suppressedFunctions))
            continue;
        delete suppressedFunctions[name];
        if (!(name in calleeGraph))
            continue;
        for (var entry of calleeGraph[name]) {
            if (!entry.suppressed)
                worklist[top++] = entry.callee;
        }
    }

    // Such functions are known to not GC.
    for (var name in gcFunctions) {
        if (name in suppressedFunctions)
            delete gcFunctions[name];
    }

    for (var name in suppressedFieldCalls) {
        suppressedFunctions[name] = true;
    }

    for (var gcName of [ 'void js::gc::GCRuntime::collect(uint8, js::SliceBudget, uint32)',
                         'void js::gc::GCRuntime::minorGC(uint32)',
                         'void js::gc::GCRuntime::minorGC(uint32)' ])
    {
        assert(gcName in mangledName, "GC function not found: " + gcName);
        addGCFunction(mangledName[gcName], "GC");
    }

    // Initialize the worklist to all known gcFunctions.
    var worklist = [];
    for (var name in gcFunctions)
        worklist.push(name);

    // Recursively find all callers and add them to the set of gcFunctions.
    while (worklist.length) {
        name = worklist.shift();
        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);
        }
    }

    // Any field call that has been resolved to all possible callees can be
    // trusted to not GC if all of those callees are known to not GC.
    for (var name in resolvedFunctions) {
        if (!(name in gcFunctions))
            suppressedFunctions[name] = true;
    }
}