1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/devtools/rootAnalysis/loadCallgraph.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,193 @@
1.4 +/* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +
1.6 +"use strict";
1.7 +
1.8 +loadRelativeToScript('utility.js');
1.9 +
1.10 +// Functions come out of sixgill in the form "mangled|readable". The mangled
1.11 +// name is Truth. One mangled name might correspond to multiple readable names,
1.12 +// for multiple reasons, including (1) sixgill/gcc doesn't always qualify types
1.13 +// the same way or de-typedef the same amount; (2) sixgill's output treats
1.14 +// references and pointers the same, and so doesn't distinguish them, but C++
1.15 +// treats them as separate for overloading and linking; (3) (identical)
1.16 +// destructors sometimes have an int32 parameter, sometimes not.
1.17 +//
1.18 +// The readable names are useful because they're far more meaningful to the
1.19 +// user, and are what should show up in reports and questions to mrgiggles. At
1.20 +// least in most cases, it's fine to have the extra mangled name tacked onto
1.21 +// the beginning for these.
1.22 +//
1.23 +// The strategy used is to separate out the pieces whenever they are read in,
1.24 +// create a table mapping mangled names to (one of the) readable names, and
1.25 +// use the mangled names in all computation.
1.26 +//
1.27 +// Note that callgraph.txt uses a compressed representation -- each name is
1.28 +// mapped to an integer, and those integers are what is recorded in the edges.
1.29 +// But the integers depend on the full name, whereas the true edge should only
1.30 +// consider the mangled name. And some of the names encoded in callgraph.txt
1.31 +// are FieldCalls, not just function names.
1.32 +
1.33 +var readableNames = {}; // map from mangled name => list of readable names
1.34 +var mangledName = {}; // map from demangled names => mangled names. Could be eliminated.
1.35 +var calleeGraph = {}; // map from mangled => list of tuples of {'callee':mangled, 'suppressed':bool}
1.36 +var callerGraph = {}; // map from mangled => list of tuples of {'caller':mangled, 'suppressed':bool}
1.37 +var gcFunctions = {}; // map from mangled callee => reason
1.38 +var suppressedFunctions = {}; // set of mangled names (map from mangled name => true)
1.39 +var gcEdges = {};
1.40 +
1.41 +function addGCFunction(caller, reason)
1.42 +{
1.43 + if (caller in suppressedFunctions)
1.44 + return false;
1.45 +
1.46 + if (ignoreGCFunction(caller))
1.47 + return false;
1.48 +
1.49 + if (!(caller in gcFunctions)) {
1.50 + gcFunctions[caller] = reason;
1.51 + return true;
1.52 + }
1.53 +
1.54 + return false;
1.55 +}
1.56 +
1.57 +function addCallEdge(caller, callee, suppressed)
1.58 +{
1.59 + if (!(caller in calleeGraph))
1.60 + calleeGraph[caller] = [];
1.61 + calleeGraph[caller].push({callee:callee, suppressed:suppressed});
1.62 +
1.63 + if (!(callee in callerGraph))
1.64 + callerGraph[callee] = [];
1.65 + callerGraph[callee].push({caller:caller, suppressed:suppressed});
1.66 +}
1.67 +
1.68 +// Map from identifier to full "mangled|readable" name. Or sometimes to a
1.69 +// Class.Field name.
1.70 +var functionNames = [""];
1.71 +
1.72 +// Map from identifier to mangled name (or to a Class.Field)
1.73 +var idToMangled = [""];
1.74 +
1.75 +function loadCallgraph(file)
1.76 +{
1.77 + var suppressedFieldCalls = {};
1.78 + var resolvedFunctions = {};
1.79 +
1.80 + var textLines = snarf(file).split('\n');
1.81 + for (var line of textLines) {
1.82 + var match;
1.83 + if (match = line.charAt(0) == "#" && /^\#(\d+) (.*)/.exec(line)) {
1.84 + assert(functionNames.length == match[1]);
1.85 + functionNames.push(match[2]);
1.86 + var [ mangled, readable ] = splitFunction(match[2]);
1.87 + if (mangled in readableNames)
1.88 + readableNames[mangled].push(readable);
1.89 + else
1.90 + readableNames[mangled] = [ readable ];
1.91 + mangledName[readable] = mangled;
1.92 + idToMangled.push(mangled);
1.93 + continue;
1.94 + }
1.95 + var suppressed = false;
1.96 + if (line.indexOf("SUPPRESS_GC") != -1) {
1.97 + match = /^(..)SUPPRESS_GC (.*)/.exec(line);
1.98 + line = match[1] + match[2];
1.99 + suppressed = true;
1.100 + }
1.101 + var tag = line.charAt(0);
1.102 + if (match = tag == 'I' && /^I (\d+) VARIABLE ([^\,]*)/.exec(line)) {
1.103 + var mangledCaller = idToMangled[match[1]];
1.104 + var name = match[2];
1.105 + if (!indirectCallCannotGC(functionNames[match[1]], name) && !suppressed)
1.106 + addGCFunction(mangledCaller, "IndirectCall: " + name);
1.107 + } else if (match = tag == 'F' && /^F (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) {
1.108 + var caller = idToMangled[match[1]];
1.109 + var csu = match[2];
1.110 + var fullfield = csu + "." + match[3];
1.111 + if (suppressed)
1.112 + suppressedFieldCalls[fullfield] = true;
1.113 + else if (!fieldCallCannotGC(csu, fullfield))
1.114 + addGCFunction(caller, "FieldCall: " + fullfield);
1.115 + } else if (match = tag == 'D' && /^D (\d+) (\d+)/.exec(line)) {
1.116 + var caller = idToMangled[match[1]];
1.117 + var callee = idToMangled[match[2]];
1.118 + addCallEdge(caller, callee, suppressed);
1.119 + } else if (match = tag == 'R' && /^R (\d+) (\d+)/.exec(line)) {
1.120 + var callerField = idToMangled[match[1]];
1.121 + var callee = idToMangled[match[2]];
1.122 + addCallEdge(callerField, callee, false);
1.123 + resolvedFunctions[callerField] = true;
1.124 + }
1.125 + }
1.126 +
1.127 + // Initialize suppressedFunctions to the set of all functions, and the
1.128 + // worklist to all toplevel callers.
1.129 + var worklist = [];
1.130 + for (var callee in callerGraph)
1.131 + suppressedFunctions[callee] = true;
1.132 + for (var caller in calleeGraph) {
1.133 + if (!(caller in callerGraph)) {
1.134 + suppressedFunctions[caller] = true;
1.135 + worklist.push(caller);
1.136 + }
1.137 + }
1.138 +
1.139 + // Find all functions reachable via an unsuppressed call chain, and remove
1.140 + // them from the suppressedFunctions set. Everything remaining is only
1.141 + // reachable when GC is suppressed.
1.142 + var top = worklist.length;
1.143 + while (top > 0) {
1.144 + name = worklist[--top];
1.145 + if (!(name in suppressedFunctions))
1.146 + continue;
1.147 + delete suppressedFunctions[name];
1.148 + if (!(name in calleeGraph))
1.149 + continue;
1.150 + for (var entry of calleeGraph[name]) {
1.151 + if (!entry.suppressed)
1.152 + worklist[top++] = entry.callee;
1.153 + }
1.154 + }
1.155 +
1.156 + // Such functions are known to not GC.
1.157 + for (var name in gcFunctions) {
1.158 + if (name in suppressedFunctions)
1.159 + delete gcFunctions[name];
1.160 + }
1.161 +
1.162 + for (var name in suppressedFieldCalls) {
1.163 + suppressedFunctions[name] = true;
1.164 + }
1.165 +
1.166 + for (var gcName of [ 'jsgc.cpp:void Collect(JSRuntime*, uint8, int64, uint32, uint32)',
1.167 + 'void js::MinorGC(JSRuntime*, uint32)' ])
1.168 + {
1.169 + assert(gcName in mangledName);
1.170 + addGCFunction(mangledName[gcName], "GC");
1.171 + }
1.172 +
1.173 + // Initialize the worklist to all known gcFunctions.
1.174 + var worklist = [];
1.175 + for (var name in gcFunctions)
1.176 + worklist.push(name);
1.177 +
1.178 + // Recursively find all callers and add them to the set of gcFunctions.
1.179 + while (worklist.length) {
1.180 + name = worklist.shift();
1.181 + assert(name in gcFunctions);
1.182 + if (!(name in callerGraph))
1.183 + continue;
1.184 + for (var entry of callerGraph[name]) {
1.185 + if (!entry.suppressed && addGCFunction(entry.caller, name))
1.186 + worklist.push(entry.caller);
1.187 + }
1.188 + }
1.189 +
1.190 + // Any field call that has been resolved to all possible callees can be
1.191 + // trusted to not GC if all of those callees are known to not GC.
1.192 + for (var name in resolvedFunctions) {
1.193 + if (!(name in gcFunctions))
1.194 + suppressedFunctions[name] = true;
1.195 + }
1.196 +}
