1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/devtools/rootAnalysis/analyzeRoots.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,576 @@
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 sourceRoot = (environment['SOURCE'] || '') + '/'
1.13 +
1.14 +var functionBodies;
1.15 +
1.16 +if (typeof scriptArgs[0] != 'string' || typeof scriptArgs[1] != 'string')
1.17 + throw "Usage: analyzeRoots.js <gcFunctions.lst> <gcEdges.txt> <suppressedFunctions.lst> <gcTypes.txt> [start end [tmpfile]]";
1.18 +
1.19 +var gcFunctionsFile = scriptArgs[0];
1.20 +var gcEdgesFile = scriptArgs[1];
1.21 +var suppressedFunctionsFile = scriptArgs[2];
1.22 +var gcTypesFile = scriptArgs[3];
1.23 +var batch = (scriptArgs[4]|0) || 1;
1.24 +var numBatches = (scriptArgs[5]|0) || 1;
1.25 +var tmpfile = scriptArgs[6] || "tmp.txt";
1.26 +
1.27 +var gcFunctions = {};
1.28 +var text = snarf("gcFunctions.lst").split("\n");
1.29 +assert(text.pop().length == 0);
1.30 +for (var line of text)
1.31 + gcFunctions[mangled(line)] = true;
1.32 +
1.33 +var suppressedFunctions = {};
1.34 +var text = snarf(suppressedFunctionsFile).split("\n");
1.35 +assert(text.pop().length == 0);
1.36 +for (var line of text) {
1.37 + suppressedFunctions[line] = true;
1.38 +}
1.39 +text = null;
1.40 +
1.41 +var gcEdges = {};
1.42 +text = snarf(gcEdgesFile).split('\n');
1.43 +assert(text.pop().length == 0);
1.44 +for (var line of text) {
1.45 + var [ block, edge, func ] = line.split(" || ");
1.46 + if (!(block in gcEdges))
1.47 + gcEdges[block] = {}
1.48 + gcEdges[block][edge] = func;
1.49 +}
1.50 +text = null;
1.51 +
1.52 +var match;
1.53 +var gcThings = {};
1.54 +var gcPointers = {};
1.55 +
1.56 +text = snarf(gcTypesFile).split("\n");
1.57 +for (var line of text) {
1.58 + if (match = /^GCThing: (.*)/.exec(line))
1.59 + gcThings[match[1]] = true;
1.60 + if (match = /^GCPointer: (.*)/.exec(line))
1.61 + gcPointers[match[1]] = true;
1.62 +}
1.63 +text = null;
1.64 +
1.65 +function isUnrootedType(type)
1.66 +{
1.67 + if (type.Kind == "Pointer") {
1.68 + var target = type.Type;
1.69 + if (target.Kind == "CSU")
1.70 + return target.Name in gcThings;
1.71 + return false;
1.72 + }
1.73 + if (type.Kind == "CSU")
1.74 + return type.Name in gcPointers;
1.75 + return false;
1.76 +}
1.77 +
1.78 +function expressionUsesVariable(exp, variable)
1.79 +{
1.80 + if (exp.Kind == "Var" && sameVariable(exp.Variable, variable))
1.81 + return true;
1.82 + if (!("Exp" in exp))
1.83 + return false;
1.84 + for (var childExp of exp.Exp) {
1.85 + if (expressionUsesVariable(childExp, variable))
1.86 + return true;
1.87 + }
1.88 + return false;
1.89 +}
1.90 +
1.91 +function edgeUsesVariable(edge, variable)
1.92 +{
1.93 + if (ignoreEdgeUse(edge, variable))
1.94 + return false;
1.95 + switch (edge.Kind) {
1.96 +
1.97 + case "Assign":
1.98 + if (expressionUsesVariable(edge.Exp[0], variable))
1.99 + return true;
1.100 + return expressionUsesVariable(edge.Exp[1], variable);
1.101 +
1.102 + case "Assume":
1.103 + return expressionUsesVariable(edge.Exp[0], variable);
1.104 +
1.105 + case "Call":
1.106 + if (expressionUsesVariable(edge.Exp[0], variable))
1.107 + return true;
1.108 + if (1 in edge.Exp && expressionUsesVariable(edge.Exp[1], variable))
1.109 + return true;
1.110 + if ("PEdgeCallInstance" in edge) {
1.111 + if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable))
1.112 + return true;
1.113 + }
1.114 + if ("PEdgeCallArguments" in edge) {
1.115 + for (var exp of edge.PEdgeCallArguments.Exp) {
1.116 + if (expressionUsesVariable(exp, variable))
1.117 + return true;
1.118 + }
1.119 + }
1.120 + return false;
1.121 +
1.122 + case "Loop":
1.123 + return false;
1.124 +
1.125 + default:
1.126 + assert(false);
1.127 + }
1.128 +}
1.129 +
1.130 +function expressionIsVariableAddress(exp, variable)
1.131 +{
1.132 + while (exp.Kind == "Fld")
1.133 + exp = exp.Exp[0];
1.134 + return exp.Kind == "Var" && sameVariable(exp.Variable, variable);
1.135 +}
1.136 +
1.137 +function edgeTakesVariableAddress(edge, variable)
1.138 +{
1.139 + if (ignoreEdgeUse(edge, variable))
1.140 + return false;
1.141 + if (ignoreEdgeAddressTaken(edge))
1.142 + return false;
1.143 + switch (edge.Kind) {
1.144 + case "Assign":
1.145 + return expressionIsVariableAddress(edge.Exp[1], variable);
1.146 + case "Call":
1.147 + if ("PEdgeCallArguments" in edge) {
1.148 + for (var exp of edge.PEdgeCallArguments.Exp) {
1.149 + if (expressionIsVariableAddress(exp, variable))
1.150 + return true;
1.151 + }
1.152 + }
1.153 + return false;
1.154 + default:
1.155 + return false;
1.156 + }
1.157 +}
1.158 +
1.159 +function edgeKillsVariable(edge, variable)
1.160 +{
1.161 + // Direct assignments kill their lhs.
1.162 + if (edge.Kind == "Assign") {
1.163 + var lhs = edge.Exp[0];
1.164 + if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
1.165 + return true;
1.166 + }
1.167 +
1.168 + if (edge.Kind != "Call")
1.169 + return false;
1.170 +
1.171 + // Assignments of call results kill their lhs.
1.172 + if (1 in edge.Exp) {
1.173 + var lhs = edge.Exp[1];
1.174 + if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
1.175 + return true;
1.176 + }
1.177 +
1.178 + // Constructor calls kill their 'this' value.
1.179 + if ("PEdgeCallInstance" in edge) {
1.180 + do {
1.181 + var instance = edge.PEdgeCallInstance.Exp;
1.182 +
1.183 + // Kludge around incorrect dereference on some constructor calls.
1.184 + if (instance.Kind == "Drf")
1.185 + instance = instance.Exp[0];
1.186 +
1.187 + if (instance.Kind != "Var" || !sameVariable(instance.Variable, variable))
1.188 + break;
1.189 +
1.190 + var callee = edge.Exp[0];
1.191 + if (callee.Kind != "Var")
1.192 + break;
1.193 +
1.194 + assert(callee.Variable.Kind == "Func");
1.195 + var calleeName = readable(callee.Variable.Name[0]);
1.196 +
1.197 + // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('.
1.198 + var openParen = calleeName.indexOf('(');
1.199 + if (openParen < 0)
1.200 + break;
1.201 + calleeName = calleeName.substring(0, openParen);
1.202 +
1.203 + var lastColon = calleeName.lastIndexOf('::');
1.204 + if (lastColon < 0)
1.205 + break;
1.206 + var constructorName = calleeName.substr(lastColon + 2);
1.207 + calleeName = calleeName.substr(0, lastColon);
1.208 +
1.209 + var lastTemplateOpen = calleeName.lastIndexOf('<');
1.210 + if (lastTemplateOpen >= 0)
1.211 + calleeName = calleeName.substr(0, lastTemplateOpen);
1.212 +
1.213 + if (calleeName.endsWith(constructorName))
1.214 + return true;
1.215 + } while (false);
1.216 + }
1.217 +
1.218 + return false;
1.219 +}
1.220 +
1.221 +function edgeCanGC(edge)
1.222 +{
1.223 + if (edge.Kind != "Call")
1.224 + return false;
1.225 + var callee = edge.Exp[0];
1.226 + if (callee.Kind == "Var") {
1.227 + var variable = callee.Variable;
1.228 + assert(variable.Kind == "Func");
1.229 + var callee = mangled(variable.Name[0]);
1.230 + if (callee in gcFunctions)
1.231 + return "'" + variable.Name[0] + "'";
1.232 + return null;
1.233 + }
1.234 + assert(callee.Kind == "Drf");
1.235 + if (callee.Exp[0].Kind == "Fld") {
1.236 + var field = callee.Exp[0].Field;
1.237 + var csuName = field.FieldCSU.Type.Name;
1.238 + var fullFieldName = csuName + "." + field.Name[0];
1.239 + if (fieldCallCannotGC(csuName, fullFieldName))
1.240 + return null;
1.241 + return (fullFieldName in suppressedFunctions) ? null : fullFieldName;
1.242 + }
1.243 + assert(callee.Exp[0].Kind == "Var");
1.244 + var varName = callee.Exp[0].Variable.Name[0];
1.245 + return indirectCallCannotGC(functionName, varName) ? null : "*" + varName;
1.246 +}
1.247 +
1.248 +function variableUseFollowsGC(suppressed, variable, worklist)
1.249 +{
1.250 + // Scan through all edges following an unrooted variable use, using an
1.251 + // explicit worklist. A worklist contains a following edge together with a
1.252 + // description of where one of its predecessors GC'd (if any).
1.253 +
1.254 + while (worklist.length) {
1.255 + var entry = worklist.pop();
1.256 + var body = entry.body, ppoint = entry.ppoint;
1.257 +
1.258 + if (body.seen) {
1.259 + if (ppoint in body.seen) {
1.260 + var seenEntry = body.seen[ppoint];
1.261 + if (!entry.gcInfo || seenEntry.gcInfo)
1.262 + continue;
1.263 + }
1.264 + } else {
1.265 + body.seen = [];
1.266 + }
1.267 + body.seen[ppoint] = {body:body, gcInfo:entry.gcInfo};
1.268 +
1.269 + if (ppoint == body.Index[0]) {
1.270 + if (body.BlockId.Kind == "Loop") {
1.271 + // propagate to parents that enter the loop body.
1.272 + if ("BlockPPoint" in body) {
1.273 + for (var parent of body.BlockPPoint) {
1.274 + var found = false;
1.275 + for (var xbody of functionBodies) {
1.276 + if (sameBlockId(xbody.BlockId, parent.BlockId)) {
1.277 + assert(!found);
1.278 + found = true;
1.279 + worklist.push({body:xbody, ppoint:parent.Index,
1.280 + gcInfo:entry.gcInfo, why:entry});
1.281 + }
1.282 + }
1.283 + assert(found);
1.284 + }
1.285 + }
1.286 + } else if (variable.Kind == "Arg" && entry.gcInfo) {
1.287 + return {gcInfo:entry.gcInfo, why:entry};
1.288 + }
1.289 + }
1.290 +
1.291 + var predecessors = getPredecessors(body);
1.292 + if (!(ppoint in predecessors))
1.293 + continue;
1.294 +
1.295 + for (var edge of predecessors[ppoint]) {
1.296 + var source = edge.Index[0];
1.297 +
1.298 + if (edgeKillsVariable(edge, variable)) {
1.299 + if (entry.gcInfo)
1.300 + return {gcInfo:entry.gcInfo, why:entry};
1.301 + if (!body.minimumUse || source < body.minimumUse)
1.302 + body.minimumUse = source;
1.303 + continue;
1.304 + }
1.305 +
1.306 + var gcInfo = entry.gcInfo;
1.307 + if (!gcInfo && !(source in body.suppressed) && !suppressed) {
1.308 + var gcName = edgeCanGC(edge, body);
1.309 + if (gcName)
1.310 + gcInfo = {name:gcName, body:body, ppoint:source};
1.311 + }
1.312 +
1.313 + if (edgeUsesVariable(edge, variable)) {
1.314 + if (gcInfo)
1.315 + return {gcInfo:gcInfo, why:entry};
1.316 + if (!body.minimumUse || source < body.minimumUse)
1.317 + body.minimumUse = source;
1.318 + }
1.319 +
1.320 + if (edge.Kind == "Loop") {
1.321 + // propagate to exit points of the loop body, in addition to the
1.322 + // predecessor of the loop edge itself.
1.323 + var found = false;
1.324 + for (var xbody of functionBodies) {
1.325 + if (sameBlockId(xbody.BlockId, edge.BlockId)) {
1.326 + assert(!found);
1.327 + found = true;
1.328 + worklist.push({body:xbody, ppoint:xbody.Index[1],
1.329 + gcInfo:gcInfo, why:entry});
1.330 + }
1.331 + }
1.332 + assert(found);
1.333 + break;
1.334 + }
1.335 + worklist.push({body:body, ppoint:source, gcInfo:gcInfo, why:entry});
1.336 + }
1.337 + }
1.338 +
1.339 + return null;
1.340 +}
1.341 +
1.342 +function variableLiveAcrossGC(suppressed, variable)
1.343 +{
1.344 + // A variable is live across a GC if (1) it is used by an edge, and (2) it
1.345 + // is used after a GC in a successor edge.
1.346 +
1.347 + for (var body of functionBodies) {
1.348 + body.seen = null;
1.349 + body.minimumUse = 0;
1.350 + }
1.351 +
1.352 + for (var body of functionBodies) {
1.353 + if (!("PEdge" in body))
1.354 + continue;
1.355 + for (var edge of body.PEdge) {
1.356 + if (edgeUsesVariable(edge, variable) && !edgeKillsVariable(edge, variable)) {
1.357 + var worklist = [{body:body, ppoint:edge.Index[0], gcInfo:null, why:null}];
1.358 + var call = variableUseFollowsGC(suppressed, variable, worklist);
1.359 + if (call)
1.360 + return call;
1.361 + }
1.362 + }
1.363 + }
1.364 + return null;
1.365 +}
1.366 +
1.367 +// An unrooted variable has its address stored in another variable via
1.368 +// assignment, or passed into a function that can GC. If the address is
1.369 +// assigned into some other variable, we can't track it to see if it is held
1.370 +// live across a GC. If it is passed into a function that can GC, then it's
1.371 +// sort of like a Handle to an unrooted location, and the callee could GC
1.372 +// before overwriting it or rooting it.
1.373 +function unsafeVariableAddressTaken(suppressed, variable)
1.374 +{
1.375 + for (var body of functionBodies) {
1.376 + if (!("PEdge" in body))
1.377 + continue;
1.378 + for (var edge of body.PEdge) {
1.379 + if (edgeTakesVariableAddress(edge, variable)) {
1.380 + if (edge.Kind == "Assign" || (!suppressed && edgeCanGC(edge)))
1.381 + return {body:body, ppoint:edge.Index[0]};
1.382 + }
1.383 + }
1.384 + }
1.385 + return null;
1.386 +}
1.387 +
1.388 +function computePrintedLines(functionName)
1.389 +{
1.390 + assert(!system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile));
1.391 + var lines = snarf(tmpfile).split('\n');
1.392 +
1.393 + for (var body of functionBodies)
1.394 + body.lines = [];
1.395 +
1.396 + // Distribute lines of output to the block they originate from.
1.397 + var currentBody = null;
1.398 + for (var i = 0; i < lines.length; i++) {
1.399 + var line = lines[i];
1.400 + if (/^block:/.test(line)) {
1.401 + if (match = /:(loop#[\d#]+)/.exec(line)) {
1.402 + var loop = match[1];
1.403 + var found = false;
1.404 + for (var body of functionBodies) {
1.405 + if (body.BlockId.Kind == "Loop" && body.BlockId.Loop == loop) {
1.406 + assert(!found);
1.407 + found = true;
1.408 + currentBody = body;
1.409 + }
1.410 + }
1.411 + assert(found);
1.412 + } else {
1.413 + for (var body of functionBodies) {
1.414 + if (body.BlockId.Kind == "Function")
1.415 + currentBody = body;
1.416 + }
1.417 + }
1.418 + }
1.419 + if (currentBody)
1.420 + currentBody.lines.push(line);
1.421 + }
1.422 +}
1.423 +
1.424 +function findLocation(body, ppoint)
1.425 +{
1.426 + var location = body.PPoint[ppoint - 1].Location;
1.427 + var text = location.CacheString + ":" + location.Line;
1.428 + if (text.indexOf(sourceRoot) == 0)
1.429 + return text.substring(sourceRoot.length);
1.430 + return text;
1.431 +}
1.432 +
1.433 +function locationLine(text)
1.434 +{
1.435 + if (match = /:(\d+)$/.exec(text))
1.436 + return match[1];
1.437 + return 0;
1.438 +}
1.439 +
1.440 +function printEntryTrace(functionName, entry)
1.441 +{
1.442 + if (!functionBodies[0].lines)
1.443 + computePrintedLines(functionName);
1.444 +
1.445 + while (entry) {
1.446 + var ppoint = entry.ppoint;
1.447 + var lineText = findLocation(entry.body, ppoint);
1.448 +
1.449 + var edgeText = null;
1.450 + if (entry.why && entry.why.body == entry.body) {
1.451 + // If the next point in the trace is in the same block, look for an edge between them.
1.452 + var next = entry.why.ppoint;
1.453 + for (var line of entry.body.lines) {
1.454 + if (match = /\((\d+),(\d+),/.exec(line)) {
1.455 + if (match[1] == ppoint && match[2] == next)
1.456 + edgeText = line; // May be multiple
1.457 + }
1.458 + }
1.459 + assert(edgeText);
1.460 + } else {
1.461 + // Look for any outgoing edge from the chosen point.
1.462 + for (var line of entry.body.lines) {
1.463 + if (match = /\((\d+),/.exec(line)) {
1.464 + if (match[1] == ppoint) {
1.465 + edgeText = line;
1.466 + break;
1.467 + }
1.468 + }
1.469 + }
1.470 + }
1.471 +
1.472 + print(" " + lineText + (edgeText ? ": " + edgeText : ""));
1.473 + entry = entry.why;
1.474 + }
1.475 +}
1.476 +
1.477 +function isRootedType(type)
1.478 +{
1.479 + return type.Kind == "CSU" && isRootedTypeName(type.Name);
1.480 +}
1.481 +
1.482 +function typeDesc(type)
1.483 +{
1.484 + if (type.Kind == "CSU") {
1.485 + return type.Name;
1.486 + } else if ('Type' in type) {
1.487 + var inner = typeDesc(type.Type);
1.488 + if (type.Kind == 'Pointer')
1.489 + return inner + '*';
1.490 + else if (type.Kind == 'Array')
1.491 + return inner + '[]';
1.492 + else
1.493 + return inner + '?';
1.494 + } else {
1.495 + return '???';
1.496 + }
1.497 +}
1.498 +
1.499 +function processBodies(functionName)
1.500 +{
1.501 + if (!("DefineVariable" in functionBodies[0]))
1.502 + return;
1.503 + var suppressed = (mangled(functionName) in suppressedFunctions);
1.504 + for (var variable of functionBodies[0].DefineVariable) {
1.505 + if (variable.Variable.Kind == "Return")
1.506 + continue;
1.507 + var name;
1.508 + if (variable.Variable.Kind == "This")
1.509 + name = "this";
1.510 + else
1.511 + name = variable.Variable.Name[0];
1.512 + if (isRootedType(variable.Type)) {
1.513 + if (!variableLiveAcrossGC(suppressed, variable.Variable)) {
1.514 + // The earliest use of the variable should be its constructor.
1.515 + var lineText;
1.516 + for (var body of functionBodies) {
1.517 + if (body.minimumUse) {
1.518 + var text = findLocation(body, body.minimumUse);
1.519 + if (!lineText || locationLine(lineText) > locationLine(text))
1.520 + lineText = text;
1.521 + }
1.522 + }
1.523 + print("\nFunction '" + functionName + "'" +
1.524 + " has unnecessary root '" + name + "' at " + lineText);
1.525 + }
1.526 + } else if (isUnrootedType(variable.Type)) {
1.527 + var result = variableLiveAcrossGC(suppressed, variable.Variable);
1.528 + if (result) {
1.529 + var lineText = findLocation(result.gcInfo.body, result.gcInfo.ppoint);
1.530 + print("\nFunction '" + functionName + "'" +
1.531 + " has unrooted '" + name + "'" +
1.532 + " of type '" + typeDesc(variable.Type) + "'" +
1.533 + " live across GC call " + result.gcInfo.name +
1.534 + " at " + lineText);
1.535 + printEntryTrace(functionName, result.why);
1.536 + }
1.537 + result = unsafeVariableAddressTaken(suppressed, variable.Variable);
1.538 + if (result) {
1.539 + var lineText = findLocation(result.body, result.ppoint);
1.540 + print("\nFunction '" + functionName + "'" +
1.541 + " takes unsafe address of unrooted '" + name + "'" +
1.542 + " at " + lineText);
1.543 + printEntryTrace(functionName, {body:result.body, ppoint:result.ppoint});
1.544 + }
1.545 + }
1.546 + }
1.547 +}
1.548 +
1.549 +if (batch == 1)
1.550 + print("Time: " + new Date);
1.551 +
1.552 +var xdb = xdbLibrary();
1.553 +xdb.open("src_body.xdb");
1.554 +
1.555 +var minStream = xdb.min_data_stream()|0;
1.556 +var maxStream = xdb.max_data_stream()|0;
1.557 +
1.558 +var N = (maxStream - minStream) + 1;
1.559 +var each = Math.floor(N/numBatches);
1.560 +var start = minStream + each * (batch - 1);
1.561 +var end = Math.min(minStream + each * batch - 1, maxStream);
1.562 +
1.563 +for (var nameIndex = start; nameIndex <= end; nameIndex++) {
1.564 + var name = xdb.read_key(nameIndex);
1.565 + var functionName = name.readString();
1.566 + var data = xdb.read_entry(name);
1.567 + xdb.free_string(name);
1.568 + var json = data.readString();
1.569 + xdb.free_string(data);
1.570 + functionBodies = JSON.parse(json);
1.571 +
1.572 + for (var body of functionBodies)
1.573 + body.suppressed = [];
1.574 + for (var body of functionBodies) {
1.575 + for (var [pbody, id] of allRAIIGuardedCallPoints(body, isSuppressConstructor))
1.576 + pbody.suppressed[id] = true;
1.577 + }
1.578 + processBodies(functionName);
1.579 +}
