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: loadRelativeToScript('annotations.js');
michael@0: loadRelativeToScript('CFG.js');
michael@0: 
michael@0: var sourceRoot = (environment['SOURCE'] || '') + '/'
michael@0: 
michael@0: var functionBodies;
michael@0: 
michael@0: if (typeof scriptArgs[0] != 'string' || typeof scriptArgs[1] != 'string')
michael@0:     throw "Usage: analyzeRoots.js <gcFunctions.lst> <gcEdges.txt> <suppressedFunctions.lst> <gcTypes.txt> [start end [tmpfile]]";
michael@0: 
michael@0: var gcFunctionsFile = scriptArgs[0];
michael@0: var gcEdgesFile = scriptArgs[1];
michael@0: var suppressedFunctionsFile = scriptArgs[2];
michael@0: var gcTypesFile = scriptArgs[3];
michael@0: var batch = (scriptArgs[4]|0) || 1;
michael@0: var numBatches = (scriptArgs[5]|0) || 1;
michael@0: var tmpfile = scriptArgs[6] || "tmp.txt";
michael@0: 
michael@0: var gcFunctions = {};
michael@0: var text = snarf("gcFunctions.lst").split("\n");
michael@0: assert(text.pop().length == 0);
michael@0: for (var line of text)
michael@0:     gcFunctions[mangled(line)] = true;
michael@0: 
michael@0: var suppressedFunctions = {};
michael@0: var text = snarf(suppressedFunctionsFile).split("\n");
michael@0: assert(text.pop().length == 0);
michael@0: for (var line of text) {
michael@0:     suppressedFunctions[line] = true;
michael@0: }
michael@0: text = null;
michael@0: 
michael@0: var gcEdges = {};
michael@0: text = snarf(gcEdgesFile).split('\n');
michael@0: assert(text.pop().length == 0);
michael@0: for (var line of text) {
michael@0:     var [ block, edge, func ] = line.split(" || ");
michael@0:     if (!(block in gcEdges))
michael@0:         gcEdges[block] = {}
michael@0:     gcEdges[block][edge] = func;
michael@0: }
michael@0: text = null;
michael@0: 
michael@0: var match;
michael@0: var gcThings = {};
michael@0: var gcPointers = {};
michael@0: 
michael@0: text = snarf(gcTypesFile).split("\n");
michael@0: for (var line of text) {
michael@0:     if (match = /^GCThing: (.*)/.exec(line))
michael@0:         gcThings[match[1]] = true;
michael@0:     if (match = /^GCPointer: (.*)/.exec(line))
michael@0:         gcPointers[match[1]] = true;
michael@0: }
michael@0: text = null;
michael@0: 
michael@0: function isUnrootedType(type)
michael@0: {
michael@0:     if (type.Kind == "Pointer") {
michael@0:         var target = type.Type;
michael@0:         if (target.Kind == "CSU")
michael@0:             return target.Name in gcThings;
michael@0:         return false;
michael@0:     }
michael@0:     if (type.Kind == "CSU")
michael@0:         return type.Name in gcPointers;
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: function expressionUsesVariable(exp, variable)
michael@0: {
michael@0:     if (exp.Kind == "Var" && sameVariable(exp.Variable, variable))
michael@0:         return true;
michael@0:     if (!("Exp" in exp))
michael@0:         return false;
michael@0:     for (var childExp of exp.Exp) {
michael@0:         if (expressionUsesVariable(childExp, variable))
michael@0:             return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: function edgeUsesVariable(edge, variable)
michael@0: {
michael@0:     if (ignoreEdgeUse(edge, variable))
michael@0:         return false;
michael@0:     switch (edge.Kind) {
michael@0: 
michael@0:     case "Assign":
michael@0:         if (expressionUsesVariable(edge.Exp[0], variable))
michael@0:             return true;
michael@0:         return expressionUsesVariable(edge.Exp[1], variable);
michael@0: 
michael@0:     case "Assume":
michael@0:         return expressionUsesVariable(edge.Exp[0], variable);
michael@0: 
michael@0:     case "Call":
michael@0:         if (expressionUsesVariable(edge.Exp[0], variable))
michael@0:             return true;
michael@0:         if (1 in edge.Exp && expressionUsesVariable(edge.Exp[1], variable))
michael@0:             return true;
michael@0:         if ("PEdgeCallInstance" in edge) {
michael@0:             if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable))
michael@0:                 return true;
michael@0:         }
michael@0:         if ("PEdgeCallArguments" in edge) {
michael@0:             for (var exp of edge.PEdgeCallArguments.Exp) {
michael@0:                 if (expressionUsesVariable(exp, variable))
michael@0:                     return true;
michael@0:             }
michael@0:         }
michael@0:         return false;
michael@0: 
michael@0:     case "Loop":
michael@0:         return false;
michael@0: 
michael@0:     default:
michael@0:         assert(false);
michael@0:     }
michael@0: }
michael@0: 
michael@0: function expressionIsVariableAddress(exp, variable)
michael@0: {
michael@0:     while (exp.Kind == "Fld")
michael@0:         exp = exp.Exp[0];
michael@0:     return exp.Kind == "Var" && sameVariable(exp.Variable, variable);
michael@0: }
michael@0: 
michael@0: function edgeTakesVariableAddress(edge, variable)
michael@0: {
michael@0:     if (ignoreEdgeUse(edge, variable))
michael@0:         return false;
michael@0:     if (ignoreEdgeAddressTaken(edge))
michael@0:         return false;
michael@0:     switch (edge.Kind) {
michael@0:     case "Assign":
michael@0:         return expressionIsVariableAddress(edge.Exp[1], variable);
michael@0:     case "Call":
michael@0:         if ("PEdgeCallArguments" in edge) {
michael@0:             for (var exp of edge.PEdgeCallArguments.Exp) {
michael@0:                 if (expressionIsVariableAddress(exp, variable))
michael@0:                     return true;
michael@0:             }
michael@0:         }
michael@0:         return false;
michael@0:     default:
michael@0:         return false;
michael@0:     }
michael@0: }
michael@0: 
michael@0: function edgeKillsVariable(edge, variable)
michael@0: {
michael@0:     // Direct assignments kill their lhs.
michael@0:     if (edge.Kind == "Assign") {
michael@0:         var lhs = edge.Exp[0];
michael@0:         if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
michael@0:             return true;
michael@0:     }
michael@0: 
michael@0:     if (edge.Kind != "Call")
michael@0:         return false;
michael@0: 
michael@0:     // Assignments of call results kill their lhs.
michael@0:     if (1 in edge.Exp) {
michael@0:         var lhs = edge.Exp[1];
michael@0:         if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
michael@0:             return true;
michael@0:     }
michael@0: 
michael@0:     // Constructor calls kill their 'this' value.
michael@0:     if ("PEdgeCallInstance" in edge) {
michael@0:         do {
michael@0:             var instance = edge.PEdgeCallInstance.Exp;
michael@0: 
michael@0:             // Kludge around incorrect dereference on some constructor calls.
michael@0:             if (instance.Kind == "Drf")
michael@0:                 instance = instance.Exp[0];
michael@0: 
michael@0:             if (instance.Kind != "Var" || !sameVariable(instance.Variable, variable))
michael@0:                 break;
michael@0: 
michael@0:             var callee = edge.Exp[0];
michael@0:             if (callee.Kind != "Var")
michael@0:                 break;
michael@0: 
michael@0:             assert(callee.Variable.Kind == "Func");
michael@0:             var calleeName = readable(callee.Variable.Name[0]);
michael@0: 
michael@0:             // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('.
michael@0:             var openParen = calleeName.indexOf('(');
michael@0:             if (openParen < 0)
michael@0:                 break;
michael@0:             calleeName = calleeName.substring(0, openParen);
michael@0: 
michael@0:             var lastColon = calleeName.lastIndexOf('::');
michael@0:             if (lastColon < 0)
michael@0:                 break;
michael@0:             var constructorName = calleeName.substr(lastColon + 2);
michael@0:             calleeName = calleeName.substr(0, lastColon);
michael@0: 
michael@0:             var lastTemplateOpen = calleeName.lastIndexOf('<');
michael@0:             if (lastTemplateOpen >= 0)
michael@0:                 calleeName = calleeName.substr(0, lastTemplateOpen);
michael@0: 
michael@0:             if (calleeName.endsWith(constructorName))
michael@0:                 return true;
michael@0:         } while (false);
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: function edgeCanGC(edge)
michael@0: {
michael@0:     if (edge.Kind != "Call")
michael@0:         return false;
michael@0:     var callee = edge.Exp[0];
michael@0:     if (callee.Kind == "Var") {
michael@0:         var variable = callee.Variable;
michael@0:         assert(variable.Kind == "Func");
michael@0:         var callee = mangled(variable.Name[0]);
michael@0:         if (callee in gcFunctions)
michael@0:             return "'" + variable.Name[0] + "'";
michael@0:         return null;
michael@0:     }
michael@0:     assert(callee.Kind == "Drf");
michael@0:     if (callee.Exp[0].Kind == "Fld") {
michael@0:         var field = callee.Exp[0].Field;
michael@0:         var csuName = field.FieldCSU.Type.Name;
michael@0:         var fullFieldName = csuName + "." + field.Name[0];
michael@0:         if (fieldCallCannotGC(csuName, fullFieldName))
michael@0:             return null;
michael@0:         return (fullFieldName in suppressedFunctions) ? null : fullFieldName;
michael@0:     }
michael@0:     assert(callee.Exp[0].Kind == "Var");
michael@0:     var varName = callee.Exp[0].Variable.Name[0];
michael@0:     return indirectCallCannotGC(functionName, varName) ? null : "*" + varName;
michael@0: }
michael@0: 
michael@0: function variableUseFollowsGC(suppressed, variable, worklist)
michael@0: {
michael@0:     // Scan through all edges following an unrooted variable use, using an
michael@0:     // explicit worklist. A worklist contains a following edge together with a
michael@0:     // description of where one of its predecessors GC'd (if any).
michael@0: 
michael@0:     while (worklist.length) {
michael@0:         var entry = worklist.pop();
michael@0:         var body = entry.body, ppoint = entry.ppoint;
michael@0: 
michael@0:         if (body.seen) {
michael@0:             if (ppoint in body.seen) {
michael@0:                 var seenEntry = body.seen[ppoint];
michael@0:                 if (!entry.gcInfo || seenEntry.gcInfo)
michael@0:                     continue;
michael@0:             }
michael@0:         } else {
michael@0:             body.seen = [];
michael@0:         }
michael@0:         body.seen[ppoint] = {body:body, gcInfo:entry.gcInfo};
michael@0: 
michael@0:         if (ppoint == body.Index[0]) {
michael@0:             if (body.BlockId.Kind == "Loop") {
michael@0:                 // propagate to parents that enter the loop body.
michael@0:                 if ("BlockPPoint" in body) {
michael@0:                     for (var parent of body.BlockPPoint) {
michael@0:                         var found = false;
michael@0:                         for (var xbody of functionBodies) {
michael@0:                             if (sameBlockId(xbody.BlockId, parent.BlockId)) {
michael@0:                                 assert(!found);
michael@0:                                 found = true;
michael@0:                                 worklist.push({body:xbody, ppoint:parent.Index,
michael@0:                                                gcInfo:entry.gcInfo, why:entry});
michael@0:                             }
michael@0:                         }
michael@0:                         assert(found);
michael@0:                     }
michael@0:                 }
michael@0:             } else if (variable.Kind == "Arg" && entry.gcInfo) {
michael@0:                 return {gcInfo:entry.gcInfo, why:entry};
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         var predecessors = getPredecessors(body);
michael@0:         if (!(ppoint in predecessors))
michael@0:             continue;
michael@0: 
michael@0:         for (var edge of predecessors[ppoint]) {
michael@0:             var source = edge.Index[0];
michael@0: 
michael@0:             if (edgeKillsVariable(edge, variable)) {
michael@0:                 if (entry.gcInfo)
michael@0:                     return {gcInfo:entry.gcInfo, why:entry};
michael@0:                 if (!body.minimumUse || source < body.minimumUse)
michael@0:                     body.minimumUse = source;
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             var gcInfo = entry.gcInfo;
michael@0:             if (!gcInfo && !(source in body.suppressed) && !suppressed) {
michael@0:                 var gcName = edgeCanGC(edge, body);
michael@0:                 if (gcName)
michael@0:                     gcInfo = {name:gcName, body:body, ppoint:source};
michael@0:             }
michael@0: 
michael@0:             if (edgeUsesVariable(edge, variable)) {
michael@0:                 if (gcInfo)
michael@0:                     return {gcInfo:gcInfo, why:entry};
michael@0:                 if (!body.minimumUse || source < body.minimumUse)
michael@0:                     body.minimumUse = source;
michael@0:             }
michael@0: 
michael@0:             if (edge.Kind == "Loop") {
michael@0:                 // propagate to exit points of the loop body, in addition to the
michael@0:                 // predecessor of the loop edge itself.
michael@0:                 var found = false;
michael@0:                 for (var xbody of functionBodies) {
michael@0:                     if (sameBlockId(xbody.BlockId, edge.BlockId)) {
michael@0:                         assert(!found);
michael@0:                         found = true;
michael@0:                         worklist.push({body:xbody, ppoint:xbody.Index[1],
michael@0:                                        gcInfo:gcInfo, why:entry});
michael@0:                     }
michael@0:                 }
michael@0:                 assert(found);
michael@0:                 break;
michael@0:             }
michael@0:             worklist.push({body:body, ppoint:source, gcInfo:gcInfo, why:entry});
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return null;
michael@0: }
michael@0: 
michael@0: function variableLiveAcrossGC(suppressed, variable)
michael@0: {
michael@0:     // A variable is live across a GC if (1) it is used by an edge, and (2) it
michael@0:     // is used after a GC in a successor edge.
michael@0: 
michael@0:     for (var body of functionBodies) {
michael@0:         body.seen = null;
michael@0:         body.minimumUse = 0;
michael@0:     }
michael@0: 
michael@0:     for (var body of functionBodies) {
michael@0:         if (!("PEdge" in body))
michael@0:             continue;
michael@0:         for (var edge of body.PEdge) {
michael@0:             if (edgeUsesVariable(edge, variable) && !edgeKillsVariable(edge, variable)) {
michael@0:                 var worklist = [{body:body, ppoint:edge.Index[0], gcInfo:null, why:null}];
michael@0:                 var call = variableUseFollowsGC(suppressed, variable, worklist);
michael@0:                 if (call)
michael@0:                     return call;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return null;
michael@0: }
michael@0: 
michael@0: // An unrooted variable has its address stored in another variable via
michael@0: // assignment, or passed into a function that can GC. If the address is
michael@0: // assigned into some other variable, we can't track it to see if it is held
michael@0: // live across a GC. If it is passed into a function that can GC, then it's
michael@0: // sort of like a Handle to an unrooted location, and the callee could GC
michael@0: // before overwriting it or rooting it.
michael@0: function unsafeVariableAddressTaken(suppressed, variable)
michael@0: {
michael@0:     for (var body of functionBodies) {
michael@0:         if (!("PEdge" in body))
michael@0:             continue;
michael@0:         for (var edge of body.PEdge) {
michael@0:             if (edgeTakesVariableAddress(edge, variable)) {
michael@0:                 if (edge.Kind == "Assign" || (!suppressed && edgeCanGC(edge)))
michael@0:                     return {body:body, ppoint:edge.Index[0]};
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return null;
michael@0: }
michael@0: 
michael@0: function computePrintedLines(functionName)
michael@0: {
michael@0:     assert(!system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile));
michael@0:     var lines = snarf(tmpfile).split('\n');
michael@0: 
michael@0:     for (var body of functionBodies)
michael@0:         body.lines = [];
michael@0: 
michael@0:     // Distribute lines of output to the block they originate from.
michael@0:     var currentBody = null;
michael@0:     for (var i = 0; i < lines.length; i++) {
michael@0:         var line = lines[i];
michael@0:         if (/^block:/.test(line)) {
michael@0:             if (match = /:(loop#[\d#]+)/.exec(line)) {
michael@0:                 var loop = match[1];
michael@0:                 var found = false;
michael@0:                 for (var body of functionBodies) {
michael@0:                     if (body.BlockId.Kind == "Loop" && body.BlockId.Loop == loop) {
michael@0:                         assert(!found);
michael@0:                         found = true;
michael@0:                         currentBody = body;
michael@0:                     }
michael@0:                 }
michael@0:                 assert(found);
michael@0:             } else {
michael@0:                 for (var body of functionBodies) {
michael@0:                     if (body.BlockId.Kind == "Function")
michael@0:                         currentBody = body;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         if (currentBody)
michael@0:             currentBody.lines.push(line);
michael@0:     }
michael@0: }
michael@0: 
michael@0: function findLocation(body, ppoint)
michael@0: {
michael@0:     var location = body.PPoint[ppoint - 1].Location;
michael@0:     var text = location.CacheString + ":" + location.Line;
michael@0:     if (text.indexOf(sourceRoot) == 0)
michael@0:         return text.substring(sourceRoot.length);
michael@0:     return text;
michael@0: }
michael@0: 
michael@0: function locationLine(text)
michael@0: {
michael@0:     if (match = /:(\d+)$/.exec(text))
michael@0:         return match[1];
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: function printEntryTrace(functionName, entry)
michael@0: {
michael@0:     if (!functionBodies[0].lines)
michael@0:         computePrintedLines(functionName);
michael@0: 
michael@0:     while (entry) {
michael@0:         var ppoint = entry.ppoint;
michael@0:         var lineText = findLocation(entry.body, ppoint);
michael@0: 
michael@0:         var edgeText = null;
michael@0:         if (entry.why && entry.why.body == entry.body) {
michael@0:             // If the next point in the trace is in the same block, look for an edge between them.
michael@0:             var next = entry.why.ppoint;
michael@0:             for (var line of entry.body.lines) {
michael@0:                 if (match = /\((\d+),(\d+),/.exec(line)) {
michael@0:                     if (match[1] == ppoint && match[2] == next)
michael@0:                         edgeText = line; // May be multiple
michael@0:                 }
michael@0:             }
michael@0:             assert(edgeText);
michael@0:         } else {
michael@0:             // Look for any outgoing edge from the chosen point.
michael@0:             for (var line of entry.body.lines) {
michael@0:                 if (match = /\((\d+),/.exec(line)) {
michael@0:                     if (match[1] == ppoint) {
michael@0:                         edgeText = line;
michael@0:                         break;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         print("    " + lineText + (edgeText ? ": " + edgeText : ""));
michael@0:         entry = entry.why;
michael@0:     }
michael@0: }
michael@0: 
michael@0: function isRootedType(type)
michael@0: {
michael@0:     return type.Kind == "CSU" && isRootedTypeName(type.Name);
michael@0: }
michael@0: 
michael@0: function typeDesc(type)
michael@0: {
michael@0:     if (type.Kind == "CSU") {
michael@0:         return type.Name;
michael@0:     } else if ('Type' in type) {
michael@0:         var inner = typeDesc(type.Type);
michael@0:         if (type.Kind == 'Pointer')
michael@0:             return inner + '*';
michael@0:         else if (type.Kind == 'Array')
michael@0:             return inner + '[]';
michael@0:         else
michael@0:             return inner + '?';
michael@0:     } else {
michael@0:         return '???';
michael@0:     }
michael@0: }
michael@0: 
michael@0: function processBodies(functionName)
michael@0: {
michael@0:     if (!("DefineVariable" in functionBodies[0]))
michael@0:         return;
michael@0:     var suppressed = (mangled(functionName) in suppressedFunctions);
michael@0:     for (var variable of functionBodies[0].DefineVariable) {
michael@0:         if (variable.Variable.Kind == "Return")
michael@0:             continue;
michael@0:         var name;
michael@0:         if (variable.Variable.Kind == "This")
michael@0:             name = "this";
michael@0:         else
michael@0:             name = variable.Variable.Name[0];
michael@0:         if (isRootedType(variable.Type)) {
michael@0:             if (!variableLiveAcrossGC(suppressed, variable.Variable)) {
michael@0:                 // The earliest use of the variable should be its constructor.
michael@0:                 var lineText;
michael@0:                 for (var body of functionBodies) {
michael@0:                     if (body.minimumUse) {
michael@0:                         var text = findLocation(body, body.minimumUse);
michael@0:                         if (!lineText || locationLine(lineText) > locationLine(text))
michael@0:                             lineText = text;
michael@0:                     }
michael@0:                 }
michael@0:                 print("\nFunction '" + functionName + "'" +
michael@0:                       " has unnecessary root '" + name + "' at " + lineText);
michael@0:             }
michael@0:         } else if (isUnrootedType(variable.Type)) {
michael@0:             var result = variableLiveAcrossGC(suppressed, variable.Variable);
michael@0:             if (result) {
michael@0:                 var lineText = findLocation(result.gcInfo.body, result.gcInfo.ppoint);
michael@0:                 print("\nFunction '" + functionName + "'" +
michael@0:                       " has unrooted '" + name + "'" +
michael@0:                       " of type '" + typeDesc(variable.Type) + "'" +
michael@0:                       " live across GC call " + result.gcInfo.name +
michael@0:                       " at " + lineText);
michael@0:                 printEntryTrace(functionName, result.why);
michael@0:             }
michael@0:             result = unsafeVariableAddressTaken(suppressed, variable.Variable);
michael@0:             if (result) {
michael@0:                 var lineText = findLocation(result.body, result.ppoint);
michael@0:                 print("\nFunction '" + functionName + "'" +
michael@0:                       " takes unsafe address of unrooted '" + name + "'" +
michael@0:                       " at " + lineText);
michael@0:                 printEntryTrace(functionName, {body:result.body, ppoint:result.ppoint});
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: if (batch == 1)
michael@0:     print("Time: " + new Date);
michael@0: 
michael@0: var xdb = xdbLibrary();
michael@0: xdb.open("src_body.xdb");
michael@0: 
michael@0: var minStream = xdb.min_data_stream()|0;
michael@0: var maxStream = xdb.max_data_stream()|0;
michael@0: 
michael@0: var N = (maxStream - minStream) + 1;
michael@0: var each = Math.floor(N/numBatches);
michael@0: var start = minStream + each * (batch - 1);
michael@0: var end = Math.min(minStream + each * batch - 1, maxStream);
michael@0: 
michael@0: for (var nameIndex = start; nameIndex <= end; nameIndex++) {
michael@0:     var name = xdb.read_key(nameIndex);
michael@0:     var functionName = name.readString();
michael@0:     var data = xdb.read_entry(name);
michael@0:     xdb.free_string(name);
michael@0:     var json = data.readString();
michael@0:     xdb.free_string(data);
michael@0:     functionBodies = JSON.parse(json);
michael@0: 
michael@0:     for (var body of functionBodies)
michael@0:         body.suppressed = [];
michael@0:     for (var body of functionBodies) {
michael@0:         for (var [pbody, id] of allRAIIGuardedCallPoints(body, isSuppressConstructor))
michael@0:             pbody.suppressed[id] = true;
michael@0:     }
michael@0:     processBodies(functionName);
michael@0: }