michael@0: /* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: 
michael@0: "use strict";
michael@0: 
michael@0: loadRelativeToScript('utility.js');
michael@0: 
michael@0: // Functions come out of sixgill in the form "mangled|readable". The mangled
michael@0: // name is Truth. One mangled name might correspond to multiple readable names,
michael@0: // for multiple reasons, including (1) sixgill/gcc doesn't always qualify types
michael@0: // the same way or de-typedef the same amount; (2) sixgill's output treats
michael@0: // references and pointers the same, and so doesn't distinguish them, but C++
michael@0: // treats them as separate for overloading and linking; (3) (identical)
michael@0: // destructors sometimes have an int32 parameter, sometimes not.
michael@0: //
michael@0: // The readable names are useful because they're far more meaningful to the
michael@0: // user, and are what should show up in reports and questions to mrgiggles. At
michael@0: // least in most cases, it's fine to have the extra mangled name tacked onto
michael@0: // the beginning for these.
michael@0: //
michael@0: // The strategy used is to separate out the pieces whenever they are read in,
michael@0: // create a table mapping mangled names to (one of the) readable names, and
michael@0: // use the mangled names in all computation.
michael@0: //
michael@0: // Note that callgraph.txt uses a compressed representation -- each name is
michael@0: // mapped to an integer, and those integers are what is recorded in the edges.
michael@0: // But the integers depend on the full name, whereas the true edge should only
michael@0: // consider the mangled name. And some of the names encoded in callgraph.txt
michael@0: // are FieldCalls, not just function names.
michael@0: 
michael@0: var readableNames = {}; // map from mangled name => list of readable names
michael@0: var mangledName = {}; // map from demangled names => mangled names. Could be eliminated.
michael@0: var calleeGraph = {}; // map from mangled => list of tuples of {'callee':mangled, 'suppressed':bool}
michael@0: var callerGraph = {}; // map from mangled => list of tuples of {'caller':mangled, 'suppressed':bool}
michael@0: var gcFunctions = {}; // map from mangled callee => reason
michael@0: var suppressedFunctions = {}; // set of mangled names (map from mangled name => true)
michael@0: var gcEdges = {};
michael@0: 
michael@0: function addGCFunction(caller, reason)
michael@0: {
michael@0:     if (caller in suppressedFunctions)
michael@0:         return false;
michael@0: 
michael@0:     if (ignoreGCFunction(caller))
michael@0:         return false;
michael@0: 
michael@0:     if (!(caller in gcFunctions)) {
michael@0:         gcFunctions[caller] = reason;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: function addCallEdge(caller, callee, suppressed)
michael@0: {
michael@0:     if (!(caller in calleeGraph))
michael@0:         calleeGraph[caller] = [];
michael@0:     calleeGraph[caller].push({callee:callee, suppressed:suppressed});
michael@0: 
michael@0:     if (!(callee in callerGraph))
michael@0:         callerGraph[callee] = [];
michael@0:     callerGraph[callee].push({caller:caller, suppressed:suppressed});
michael@0: }
michael@0: 
michael@0: // Map from identifier to full "mangled|readable" name. Or sometimes to a
michael@0: // Class.Field name.
michael@0: var functionNames = [""];
michael@0: 
michael@0: // Map from identifier to mangled name (or to a Class.Field)
michael@0: var idToMangled = [""];
michael@0: 
michael@0: function loadCallgraph(file)
michael@0: {
michael@0:     var suppressedFieldCalls = {};
michael@0:     var resolvedFunctions = {};
michael@0: 
michael@0:     var textLines = snarf(file).split('\n');
michael@0:     for (var line of textLines) {
michael@0:         var match;
michael@0:         if (match = line.charAt(0) == "#" && /^\#(\d+) (.*)/.exec(line)) {
michael@0:             assert(functionNames.length == match[1]);
michael@0:             functionNames.push(match[2]);
michael@0:             var [ mangled, readable ] = splitFunction(match[2]);
michael@0:             if (mangled in readableNames)
michael@0:                 readableNames[mangled].push(readable);
michael@0:             else
michael@0:                 readableNames[mangled] = [ readable ];
michael@0:             mangledName[readable] = mangled;
michael@0:             idToMangled.push(mangled);
michael@0:             continue;
michael@0:         }
michael@0:         var suppressed = false;
michael@0:         if (line.indexOf("SUPPRESS_GC") != -1) {
michael@0:             match = /^(..)SUPPRESS_GC (.*)/.exec(line);
michael@0:             line = match[1] + match[2];
michael@0:             suppressed = true;
michael@0:         }
michael@0:         var tag = line.charAt(0);
michael@0:         if (match = tag == 'I' && /^I (\d+) VARIABLE ([^\,]*)/.exec(line)) {
michael@0:             var mangledCaller = idToMangled[match[1]];
michael@0:             var name = match[2];
michael@0:             if (!indirectCallCannotGC(functionNames[match[1]], name) && !suppressed)
michael@0:                 addGCFunction(mangledCaller, "IndirectCall: " + name);
michael@0:         } else if (match = tag == 'F' && /^F (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) {
michael@0:             var caller = idToMangled[match[1]];
michael@0:             var csu = match[2];
michael@0:             var fullfield = csu + "." + match[3];
michael@0:             if (suppressed)
michael@0:                 suppressedFieldCalls[fullfield] = true;
michael@0:             else if (!fieldCallCannotGC(csu, fullfield))
michael@0:                 addGCFunction(caller, "FieldCall: " + fullfield);
michael@0:         } else if (match = tag == 'D' && /^D (\d+) (\d+)/.exec(line)) {
michael@0:             var caller = idToMangled[match[1]];
michael@0:             var callee = idToMangled[match[2]];
michael@0:             addCallEdge(caller, callee, suppressed);
michael@0:         } else if (match = tag == 'R' && /^R (\d+) (\d+)/.exec(line)) {
michael@0:             var callerField = idToMangled[match[1]];
michael@0:             var callee = idToMangled[match[2]];
michael@0:             addCallEdge(callerField, callee, false);
michael@0:             resolvedFunctions[callerField] = true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Initialize suppressedFunctions to the set of all functions, and the
michael@0:     // worklist to all toplevel callers.
michael@0:     var worklist = [];
michael@0:     for (var callee in callerGraph)
michael@0:         suppressedFunctions[callee] = true;
michael@0:     for (var caller in calleeGraph) {
michael@0:         if (!(caller in callerGraph)) {
michael@0:             suppressedFunctions[caller] = true;
michael@0:             worklist.push(caller);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Find all functions reachable via an unsuppressed call chain, and remove
michael@0:     // them from the suppressedFunctions set. Everything remaining is only
michael@0:     // reachable when GC is suppressed.
michael@0:     var top = worklist.length;
michael@0:     while (top > 0) {
michael@0:         name = worklist[--top];
michael@0:         if (!(name in suppressedFunctions))
michael@0:             continue;
michael@0:         delete suppressedFunctions[name];
michael@0:         if (!(name in calleeGraph))
michael@0:             continue;
michael@0:         for (var entry of calleeGraph[name]) {
michael@0:             if (!entry.suppressed)
michael@0:                 worklist[top++] = entry.callee;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Such functions are known to not GC.
michael@0:     for (var name in gcFunctions) {
michael@0:         if (name in suppressedFunctions)
michael@0:             delete gcFunctions[name];
michael@0:     }
michael@0: 
michael@0:     for (var name in suppressedFieldCalls) {
michael@0:         suppressedFunctions[name] = true;
michael@0:     }
michael@0: 
michael@0:     for (var gcName of [ 'jsgc.cpp:void Collect(JSRuntime*, uint8, int64, uint32, uint32)',
michael@0:                          'void js::MinorGC(JSRuntime*, uint32)' ])
michael@0:     {
michael@0:         assert(gcName in mangledName);
michael@0:         addGCFunction(mangledName[gcName], "GC");
michael@0:     }
michael@0: 
michael@0:     // Initialize the worklist to all known gcFunctions.
michael@0:     var worklist = [];
michael@0:     for (var name in gcFunctions)
michael@0:         worklist.push(name);
michael@0: 
michael@0:     // Recursively find all callers and add them to the set of gcFunctions.
michael@0:     while (worklist.length) {
michael@0:         name = worklist.shift();
michael@0:         assert(name in gcFunctions);
michael@0:         if (!(name in callerGraph))
michael@0:             continue;
michael@0:         for (var entry of callerGraph[name]) {
michael@0:             if (!entry.suppressed && addGCFunction(entry.caller, name))
michael@0:                 worklist.push(entry.caller);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Any field call that has been resolved to all possible callees can be
michael@0:     // trusted to not GC if all of those callees are known to not GC.
michael@0:     for (var name in resolvedFunctions) {
michael@0:         if (!(name in gcFunctions))
michael@0:             suppressedFunctions[name] = true;
michael@0:     }
michael@0: }