1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/devtools/rootAnalysis/computeCallgraph.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,281 @@
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 +loadRelativeToScript('annotations.js');
1.10 +loadRelativeToScript('CFG.js');
1.11 +
1.12 +var subclasses = {};
1.13 +var superclasses = {};
1.14 +var classFunctions = {};
1.15 +
1.16 +var fieldCallSeen = {};
1.17 +
1.18 +function addClassEntry(index, name, other)
1.19 +{
1.20 + if (!(name in index)) {
1.21 + index[name] = [other];
1.22 + return;
1.23 + }
1.24 +
1.25 + for (var entry of index[name]) {
1.26 + if (entry == other)
1.27 + return;
1.28 + }
1.29 +
1.30 + index[name].push(other);
1.31 +}
1.32 +
1.33 +// CSU is "Class/Struct/Union"
1.34 +function processCSU(csuName, csu)
1.35 +{
1.36 + if (!("FunctionField" in csu))
1.37 + return;
1.38 + for (var field of csu.FunctionField) {
1.39 + if (1 in field.Field) {
1.40 + var superclass = field.Field[1].Type.Name;
1.41 + var subclass = field.Field[1].FieldCSU.Type.Name;
1.42 + assert(subclass == csuName);
1.43 + addClassEntry(subclasses, superclass, subclass);
1.44 + addClassEntry(superclasses, subclass, superclass);
1.45 + }
1.46 + if ("Variable" in field) {
1.47 + // Note: not dealing with overloading correctly.
1.48 + var name = field.Variable.Name[0];
1.49 + var key = csuName + ":" + field.Field[0].Name[0];
1.50 + if (!(key in classFunctions))
1.51 + classFunctions[key] = [];
1.52 + classFunctions[key].push(name);
1.53 + }
1.54 + }
1.55 +}
1.56 +
1.57 +function findVirtualFunctions(initialCSU, field, suppressed)
1.58 +{
1.59 + var worklist = [initialCSU];
1.60 +
1.61 + // Virtual call targets on subclasses of nsISupports may be incomplete,
1.62 + // if the interface is scriptable. Just treat all indirect calls on
1.63 + // nsISupports objects as potentially GC'ing, except AddRef/Release
1.64 + // which should never enter the JS engine (even when calling dtors).
1.65 + while (worklist.length) {
1.66 + var csu = worklist.pop();
1.67 + if (csu == "nsISupports" && (field == "AddRef" || field == "Release")) {
1.68 + suppressed[0] = true;
1.69 + return [];
1.70 + }
1.71 + if (isOverridableField(initialCSU, csu, field))
1.72 + return null;
1.73 +
1.74 + if (csu in superclasses) {
1.75 + for (var superclass of superclasses[csu])
1.76 + worklist.push(superclass);
1.77 + }
1.78 + }
1.79 +
1.80 + var functions = [];
1.81 + var worklist = [csu];
1.82 +
1.83 + while (worklist.length) {
1.84 + var csu = worklist.pop();
1.85 + var key = csu + ":" + field;
1.86 +
1.87 + if (key in classFunctions) {
1.88 + for (var name of classFunctions[key])
1.89 + functions.push(name);
1.90 + }
1.91 +
1.92 + if (csu in subclasses) {
1.93 + for (var subclass of subclasses[csu])
1.94 + worklist.push(subclass);
1.95 + }
1.96 + }
1.97 +
1.98 + return functions;
1.99 +}
1.100 +
1.101 +var memoized = {};
1.102 +var memoizedCount = 0;
1.103 +
1.104 +function memo(name)
1.105 +{
1.106 + if (!(name in memoized)) {
1.107 + memoizedCount++;
1.108 + memoized[name] = "" + memoizedCount;
1.109 + print("#" + memoizedCount + " " + name);
1.110 + }
1.111 + return memoized[name];
1.112 +}
1.113 +
1.114 +var seenCallees = null;
1.115 +var seenSuppressedCallees = null;
1.116 +
1.117 +// Return a list of all callees that the given edge might be a call to. Each
1.118 +// one is represented by an object with a 'kind' field that is one of
1.119 +// ('direct', 'field', 'indirect', 'unknown').
1.120 +function getCallees(edge)
1.121 +{
1.122 + if (edge.Kind != "Call")
1.123 + return [];
1.124 +
1.125 + var callee = edge.Exp[0];
1.126 + var callees = [];
1.127 + if (callee.Kind == "Var") {
1.128 + assert(callee.Variable.Kind == "Func");
1.129 + callees.push({'kind': 'direct', 'name': callee.Variable.Name[0]});
1.130 + } else {
1.131 + assert(callee.Kind == "Drf");
1.132 + if (callee.Exp[0].Kind == "Fld") {
1.133 + var field = callee.Exp[0].Field;
1.134 + var fieldName = field.Name[0];
1.135 + var csuName = field.FieldCSU.Type.Name;
1.136 + var functions = null;
1.137 + if ("FieldInstanceFunction" in field) {
1.138 + var suppressed = [ false ];
1.139 + functions = findVirtualFunctions(csuName, fieldName, suppressed);
1.140 + if (suppressed[0]) {
1.141 + // Field call known to not GC; mark it as suppressed so
1.142 + // direct invocations will be ignored
1.143 + callees.push({'kind': "field", 'csu': csuName, 'field': fieldName,
1.144 + 'suppressed': true});
1.145 + }
1.146 + }
1.147 + if (functions) {
1.148 + // Known set of virtual call targets. Treat them as direct
1.149 + // calls to all possible resolved types, but also record edges
1.150 + // from this field call to each final callee. When the analysis
1.151 + // is checking whether an edge can GC and it sees an unrooted
1.152 + // pointer held live across this field call, it will know
1.153 + // whether any of the direct callees can GC or not.
1.154 + var targets = [];
1.155 + for (var name of functions) {
1.156 + callees.push({'kind': "direct", 'name': name});
1.157 + targets.push({'kind': "direct", 'name': name});
1.158 + }
1.159 + callees.push({'kind': "resolved-field", 'csu': csuName, 'field': fieldName, 'callees': targets});
1.160 + } else {
1.161 + // Unknown set of call targets. Non-virtual field call,
1.162 + // or virtual call on an nsISupports object.
1.163 + callees.push({'kind': "field", 'csu': csuName, 'field': fieldName});
1.164 + }
1.165 + } else if (callee.Exp[0].Kind == "Var") {
1.166 + // indirect call through a variable.
1.167 + callees.push({'kind': "indirect", 'variable': callee.Exp[0].Variable.Name[0]});
1.168 + } else {
1.169 + // unknown call target.
1.170 + callees.push({'kind': "unknown"});
1.171 + }
1.172 + }
1.173 +
1.174 + return callees;
1.175 +}
1.176 +
1.177 +var lastline;
1.178 +function printOnce(line)
1.179 +{
1.180 + if (line != lastline) {
1.181 + print(line);
1.182 + lastline = line;
1.183 + }
1.184 +}
1.185 +
1.186 +function processBody(caller, body)
1.187 +{
1.188 + if (!('PEdge' in body))
1.189 + return;
1.190 +
1.191 + lastline = null;
1.192 + for (var edge of body.PEdge) {
1.193 + if (edge.Kind != "Call")
1.194 + continue;
1.195 + var edgeSuppressed = false;
1.196 + var seen = seenCallees;
1.197 + if (edge.Index[0] in body.suppressed) {
1.198 + edgeSuppressed = true;
1.199 + seen = seenSuppressedCallees;
1.200 + }
1.201 + for (var callee of getCallees(edge)) {
1.202 + var prologue = (edgeSuppressed || callee.suppressed) ? "SUPPRESS_GC " : "";
1.203 + prologue += memo(caller) + " ";
1.204 + if (callee.kind == 'direct') {
1.205 + if (!(callee.name in seen)) {
1.206 + seen[name] = true;
1.207 + printOnce("D " + prologue + memo(callee.name));
1.208 + }
1.209 + } else if (callee.kind == 'field') {
1.210 + var { csu, field } = callee;
1.211 + printOnce("F " + prologue + "CLASS " + csu + " FIELD " + field);
1.212 + } else if (callee.kind == 'resolved-field') {
1.213 + // Fully-resolved field call (usually a virtual method). Record
1.214 + // the callgraph edges. Do not consider suppression, since it
1.215 + // is local to this callsite and we are writing out a global
1.216 + // record here.
1.217 + //
1.218 + // Any field call that does *not* have an R entry must be
1.219 + // assumed to call anything.
1.220 + var { csu, field, callees } = callee;
1.221 + var fullFieldName = csu + "." + field;
1.222 + if (!(fullFieldName in fieldCallSeen)) {
1.223 + fieldCallSeen[fullFieldName] = true;
1.224 + for (var target of callees)
1.225 + printOnce("R " + memo(fullFieldName) + " " + memo(target.name));
1.226 + }
1.227 + } else if (callee.kind == 'indirect') {
1.228 + printOnce("I " + prologue + "VARIABLE " + callee.variable);
1.229 + } else if (callee.kind == 'unknown') {
1.230 + printOnce("I " + prologue + "VARIABLE UNKNOWN");
1.231 + } else {
1.232 + printErr("invalid " + callee.kind + " callee");
1.233 + debugger;
1.234 + }
1.235 + }
1.236 + }
1.237 +}
1.238 +
1.239 +var callgraph = {};
1.240 +
1.241 +var xdb = xdbLibrary();
1.242 +xdb.open("src_comp.xdb");
1.243 +
1.244 +var minStream = xdb.min_data_stream();
1.245 +var maxStream = xdb.max_data_stream();
1.246 +
1.247 +for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
1.248 + var csu = xdb.read_key(csuIndex);
1.249 + var data = xdb.read_entry(csu);
1.250 + var json = JSON.parse(data.readString());
1.251 + processCSU(csu.readString(), json[0]);
1.252 +
1.253 + xdb.free_string(csu);
1.254 + xdb.free_string(data);
1.255 +}
1.256 +
1.257 +xdb.open("src_body.xdb");
1.258 +
1.259 +printErr("Finished loading data structures");
1.260 +
1.261 +var minStream = xdb.min_data_stream();
1.262 +var maxStream = xdb.max_data_stream();
1.263 +
1.264 +for (var nameIndex = minStream; nameIndex <= maxStream; nameIndex++) {
1.265 + var name = xdb.read_key(nameIndex);
1.266 + var data = xdb.read_entry(name);
1.267 + functionBodies = JSON.parse(data.readString());
1.268 + for (var body of functionBodies)
1.269 + body.suppressed = [];
1.270 + for (var body of functionBodies) {
1.271 + for (var [pbody, id] of allRAIIGuardedCallPoints(body, isSuppressConstructor))
1.272 + pbody.suppressed[id] = true;
1.273 + }
1.274 +
1.275 + seenCallees = {};
1.276 + seenSuppressedCallees = {};
1.277 +
1.278 + var functionName = name.readString();
1.279 + for (var body of functionBodies)
1.280 + processBody(functionName, body);
1.281 +
1.282 + xdb.free_string(name);
1.283 + xdb.free_string(data);
1.284 +}
