diff options
Diffstat (limited to 'js/src/devtools/rootAnalysis/CFG.js')
| -rw-r--r-- | js/src/devtools/rootAnalysis/CFG.js | 930 |
1 files changed, 930 insertions, 0 deletions
diff --git a/js/src/devtools/rootAnalysis/CFG.js b/js/src/devtools/rootAnalysis/CFG.js new file mode 100644 index 0000000000..f8e71fc818 --- /dev/null +++ b/js/src/devtools/rootAnalysis/CFG.js @@ -0,0 +1,930 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +// Utility code for traversing the JSON data structures produced by sixgill. + +"use strict"; + +var TRACING = false; + +// Find all points (positions within the code) of the body given by the list of +// bodies and the blockId to match (which will specify an outer function or a +// loop within it), recursing into loops if needed. +function findAllPoints(bodies, blockId, bits) +{ + var points = []; + var body; + + for (var xbody of bodies) { + if (sameBlockId(xbody.BlockId, blockId)) { + assert(!body); + body = xbody; + } + } + assert(body); + + if (!("PEdge" in body)) + return; + for (var edge of body.PEdge) { + points.push([body, edge.Index[0], bits]); + if (edge.Kind == "Loop") + points.push(...findAllPoints(bodies, edge.BlockId, bits)); + } + + return points; +} + +// Visitor of a graph of <body, ppoint> vertexes and sixgill-generated edges, +// where the edges represent the actual computation happening. +// +// Uses the syntax `var Visitor = class { ... }` rather than `class Visitor` +// to allow reloading this file with the JS debugger. +var Visitor = class { + constructor(bodies) { + this.visited_bodies = new Map(); + for (const body of bodies) { + this.visited_bodies.set(body, new Map()); + } + } + + // Returns whether we should keep going after seeing this <body, ppoint> + // pair. Also records it as visited. + visit(body, ppoint, info) { + const visited = this.visited_bodies.get(body); + const existing = visited.get(ppoint); + const action = this.next_action(existing, info); + const merged = this.merge_info(existing, info); + visited.set(ppoint, merged); + return [action, merged]; + } + + // Default implementation does a basic "only visit nodes once" search. + // (Whether this is BFS/DFS/other is determined by the caller.) + + // Override if you need to revisit nodes. Valid actions are "continue", + // "prune", and "done". "continue" means continue with the search. "prune" + // means stop at this node, only continue on other edges. "done" means the + // whole search is complete even if unvisited nodes remain. + next_action(prev, current) { return prev ? "prune" : "continue"; } + + // Update the info at a node. If this is the first time the node has been + // seen, `prev` will be undefined. `current` will be the info computed by + // `extend_path`. The node will be updated with the return value. + merge_info(prev, current) { return true; } + + // Prepend `edge` to the info stored at the successor node, returning + // the updated info value. This should be overridden by pretty much any + // subclass, as a traversal's semantics are largely determined by this method. + extend_path(edge, body, ppoint, successor_path) { return true; } +}; + +function findMatchingBlock(bodies, blockId) { + for (const body of bodies) { + if (sameBlockId(body.BlockId, blockId)) { + return body; + } + } + assert(false); +} + +// Perform a mostly breadth-first search through the graph of <body, ppoints>. +// This is only mostly breadth-first because the visitor decides whether to +// stop searching when it sees an already-visited node. It can choose to +// re-visit a node in order to find "better" paths that include a node more +// than once. +// +// The return value depends on how the search finishes. If a 'done' action +// is returned by visitor.visit(), use the information returned by +// that call. If the search completes without reaching the entry point of +// the function (the "root"), return null. If the search manages to reach +// the root, return the value of the `result_if_reached_root` parameter. +// +// This allows this function to be used in different ways. If the visitor +// associates a value with each node that chains onto its successors +// (or predecessors in the "upwards" search order), then this will return +// a complete path through the graph. But this can also be used to test +// whether a condition holds (eg "the exit point is reachable after +// calling SomethingImportant()"), in which case no path is needed and the +// visitor will cause the return value to be a simple boolean (or null +// if it terminates the search before reaching the root.) +// +// The information returned by the visitor for a node is often called +// `path` in the code below, even though it may not represent a path. +// +function BFS_upwards(start_body, start_ppoint, bodies, visitor, + initial_successor_info={}, + result_if_reached_root=null) +{ + const work = [[start_body, start_ppoint, null, initial_successor_info]]; + if (TRACING) { + printErr(`BFS start at ${blockIdentifier(start_body)}:${start_ppoint}`); + } + + let reached_root = false; + while (work.length > 0) { + const [body, ppoint, edgeToAdd, successor_path] = work.shift(); + if (TRACING) { + printErr(`prepending edge from ${ppoint} to state '${successor_path}'`); + } + let path = visitor.extend_path(edgeToAdd, body, ppoint, successor_path); + + const [action, merged_path] = visitor.visit(body, ppoint, path); + if (action === "done") { + return merged_path; + } + if (action === "prune") { + // Do not push anything else to the work queue, but continue processing + // other branches. + continue; + } + assert(action == "continue"); + path = merged_path; + + const predecessors = getPredecessors(body); + for (const edge of (predecessors[ppoint] || [])) { + if (edge.Kind == "Loop") { + // Propagate the search into the exit point of the loop body. + const loopBody = findMatchingBlock(bodies, edge.BlockId); + const loopEnd = loopBody.Index[1]; + work.push([loopBody, loopEnd, null, path]); + // Don't continue to predecessors here without going through + // the loop. (The points in this body that enter the loop will + // be traversed when we reach the entry point of the loop.) + } else { + work.push([body, edge.Index[0], edge, path]); + } + } + + // Check for hitting the entry point of a loop body. + if (ppoint == body.Index[0] && body.BlockId.Kind == "Loop") { + // Propagate to outer body parents that enter the loop body. + for (const parent of (body.BlockPPoint || [])) { + const parentBody = findMatchingBlock(bodies, parent.BlockId); + work.push([parentBody, parent.Index, null, path]); + } + + // This point is also preceded by the *end* of this loop, for the + // previous iteration. + work.push([body, body.Index[1], null, path]); + } + + // Check for reaching the root of the function. + if (body === start_body && ppoint == body.Index[0]) { + reached_root = true; + } + } + + // The search space was exhausted without finding a 'done' state. That + // might be because all search paths were pruned before reaching the entry + // point of the function, in which case reached_root will be false. (If + // reached_root is true, then we may still not have visited the entire + // graph, if some paths were pruned but at least one made it to the root.) + return reached_root ? result_if_reached_root : null; +} + +// Given the CFG for the constructor call of some RAII, return whether the +// given edge is the matching destructor call. +function isMatchingDestructor(constructor, edge) +{ + if (edge.Kind != "Call") + return false; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + var variable = callee.Variable; + assert(variable.Kind == "Func"); + if (variable.Name[1].charAt(0) != '~') + return false; + + // Note that in some situations, a regular function can begin with '~', so + // we don't necessarily have a destructor in hand. This is probably a + // sixgill artifact, but in js::wasm::ModuleGenerator::~ModuleGenerator, a + // templatized static inline EraseIf is invoked, and it gets named ~EraseIf + // for some reason. + if (!("PEdgeCallInstance" in edge)) + return false; + + var constructExp = constructor.PEdgeCallInstance.Exp; + assert(constructExp.Kind == "Var"); + + var destructExp = edge.PEdgeCallInstance.Exp; + if (destructExp.Kind != "Var") + return false; + + return sameVariable(constructExp.Variable, destructExp.Variable); +} + +// Return all calls within the RAII scope of any constructor matched by +// isConstructor(). (Note that this would be insufficient if you needed to +// treat each instance separately, such as when different regions of a function +// body were guarded by these constructors and you needed to do something +// different with each.) +function allRAIIGuardedCallPoints(typeInfo, bodies, body, isConstructor) +{ + if (!("PEdge" in body)) + return []; + + var points = []; + + for (var edge of body.PEdge) { + if (edge.Kind != "Call") + continue; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + continue; + var variable = callee.Variable; + assert(variable.Kind == "Func"); + const bits = isConstructor(typeInfo, edge.Type, variable.Name); + if (!bits) + continue; + if (!("PEdgeCallInstance" in edge)) + continue; + if (edge.PEdgeCallInstance.Exp.Kind != "Var") + continue; + + points.push(...pointsInRAIIScope(bodies, body, edge, bits)); + } + + return points; +} + +// Test whether the given edge is the constructor corresponding to the given +// destructor edge. +function isMatchingConstructor(destructor, edge) +{ + if (edge.Kind != "Call") + return false; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + var variable = callee.Variable; + if (variable.Kind != "Func") + return false; + var name = readable(variable.Name[0]); + var destructorName = readable(destructor.Exp[0].Variable.Name[0]); + var match = destructorName.match(/^(.*?::)~(\w+)\(/); + if (!match) { + printErr("Unhandled destructor syntax: " + destructorName); + return false; + } + var constructorSubstring = match[1] + match[2]; + if (name.indexOf(constructorSubstring) == -1) + return false; + + var destructExp = destructor.PEdgeCallInstance.Exp; + if (destructExp.Kind != "Var") + return false; + + var constructExp = edge.PEdgeCallInstance.Exp; + if (constructExp.Kind != "Var") + return false; + + return sameVariable(constructExp.Variable, destructExp.Variable); +} + +function findMatchingConstructor(destructorEdge, body, warnIfNotFound=true) +{ + var worklist = [destructorEdge]; + var predecessors = getPredecessors(body); + while(worklist.length > 0) { + var edge = worklist.pop(); + if (isMatchingConstructor(destructorEdge, edge)) + return edge; + if (edge.Index[0] in predecessors) { + for (var e of predecessors[edge.Index[0]]) + worklist.push(e); + } + } + if (warnIfNotFound) + printErr("Could not find matching constructor!"); + return undefined; +} + +function pointsInRAIIScope(bodies, body, constructorEdge, bits) { + var seen = {}; + var worklist = [constructorEdge.Index[1]]; + var points = []; + while (worklist.length) { + var point = worklist.pop(); + if (point in seen) + continue; + seen[point] = true; + points.push([body, point, bits]); + var successors = getSuccessors(body); + if (!(point in successors)) + continue; + for (var nedge of successors[point]) { + if (isMatchingDestructor(constructorEdge, nedge)) + continue; + if (nedge.Kind == "Loop") + points.push(...findAllPoints(bodies, nedge.BlockId, bits)); + worklist.push(nedge.Index[1]); + } + } + + return points; +} + +function isImmobileValue(exp) { + if (exp.Kind == "Int" && exp.String == "0") { + return true; + } + return false; +} + +function expressionIsVariableAddress(exp, variable) +{ + while (exp.Kind == "Fld") + exp = exp.Exp[0]; + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +function edgeTakesVariableAddress(edge, variable, body) +{ + if (ignoreEdgeUse(edge, variable, body)) + return false; + if (ignoreEdgeAddressTaken(edge)) + return false; + switch (edge.Kind) { + case "Assign": + return expressionIsVariableAddress(edge.Exp[1], variable); + case "Call": + if ("PEdgeCallArguments" in edge) { + for (var exp of edge.PEdgeCallArguments.Exp) { + if (expressionIsVariableAddress(exp, variable)) + return true; + } + } + return false; + default: + return false; + } +} + +// Look at an invocation of a virtual method or function pointer contained in a +// field, and return the static type of the invocant (or the containing struct, +// for a function pointer field.) +function getFieldCallInstanceCSU(edge, field) +{ + if ("FieldInstanceFunction" in field) { + // We have a 'this'. + const instanceExp = edge.PEdgeCallInstance.Exp; + if (instanceExp.Kind == 'Drf') { + // somevar->foo() + return edge.Type.TypeFunctionCSU.Type.Name; + } else if (instanceExp.Kind == 'Fld') { + // somevar.foo() + return instanceExp.Field.FieldCSU.Type.Name; + } else if (instanceExp.Kind == 'Index') { + // A strange construct. + // C++ code: static_cast<JS::CustomAutoRooter*>(this)->trace(trc); + // CFG: Call(21,30, this*[-1]{JS::CustomAutoRooter}.trace*(trc*)) + return instanceExp.Type.Name; + } else if (instanceExp.Kind == 'Var') { + // C++: reinterpret_cast<SimpleTimeZone*>(gRawGMT)->~SimpleTimeZone(); + // CFG: + // # icu_64::SimpleTimeZone::icu_64::SimpleTimeZone.__comp_dtor + // [6,7] Call gRawGMT.icu_64::SimpleTimeZone.__comp_dtor () + return field.FieldCSU.Type.Name; + } else { + printErr("------------------ edge -------------------"); + printErr(JSON.stringify(edge, null, 4)); + printErr("------------------ field -------------------"); + printErr(JSON.stringify(field, null, 4)); + assert(false, `unrecognized FieldInstanceFunction Kind ${instanceExp.Kind}`); + } + } else { + // somefar.foo() where somevar is a field of some CSU. + return field.FieldCSU.Type.Name; + } +} + +function expressionUsesVariable(exp, variable) +{ + if (exp.Kind == "Var" && sameVariable(exp.Variable, variable)) + return true; + if (!("Exp" in exp)) + return false; + for (var childExp of exp.Exp) { + if (expressionUsesVariable(childExp, variable)) + return true; + } + return false; +} + +function expressionUsesVariableContents(exp, variable) +{ + if (!("Exp" in exp)) + return false; + for (var childExp of exp.Exp) { + if (childExp.Kind == 'Drf') { + if (expressionUsesVariable(childExp, variable)) + return true; + } else if (expressionUsesVariableContents(childExp, variable)) { + return true; + } + } + return false; +} + +// Detect simple |return nullptr;| statements. +function isReturningImmobileValue(edge, variable) +{ + if (variable.Kind == "Return") { + if (edge.Exp[0].Kind == "Var" && sameVariable(edge.Exp[0].Variable, variable)) { + if (isImmobileValue(edge.Exp[1])) + return true; + } + } + return false; +} + +// If the edge uses the given variable's value, return the earliest point at +// which the use is definite. Usually, that means the source of the edge +// (anything that reaches that source point will end up using the variable, but +// there may be other ways to reach the destination of the edge.) +// +// Return values are implicitly used at the very last point in the function. +// This makes a difference: if an RAII class GCs in its destructor, we need to +// start looking at the final point in the function, not one point back from +// that, since that would skip over the GCing call. +// +// Note that this returns true only if the variable's incoming value is used. +// So this would return false for 'obj': +// +// obj = someFunction(); +// +// but these would return true: +// +// obj = someFunction(obj); +// obj->foo = someFunction(); +// +function edgeUsesVariable(edge, variable, body) +{ + if (ignoreEdgeUse(edge, variable, body)) + return 0; + + if (variable.Kind == "Return" && body.Index[1] == edge.Index[1] && body.BlockId.Kind == "Function") { + // The last point in the function body is treated as using the return + // value. This is the only time the destination point is returned + // rather than the source point. + return edge.Index[1]; + } + + var src = edge.Index[0]; + + switch (edge.Kind) { + + case "Assign": { + // Detect `Return := nullptr`. + if (isReturningImmobileValue(edge, variable)) + return 0; + const [lhs, rhs] = edge.Exp; + // Detect `lhs := ...variable...` + if (expressionUsesVariable(rhs, variable)) + return src; + // Detect `...variable... := rhs` but not `variable := rhs`. The latter + // overwrites the previous value of `variable` without using it. + if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable)) + return src; + return 0; + } + + case "Assume": + return expressionUsesVariableContents(edge.Exp[0], variable) ? src : 0; + + case "Call": { + const callee = edge.Exp[0]; + if (expressionUsesVariable(callee, variable)) + return src; + if ("PEdgeCallInstance" in edge) { + if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable)) { + if (edgeStartsValueLiveRange(edge, variable)) { + // If the variable is being constructed, then the incoming + // value is not used here; it didn't exist before + // construction. (The analysis doesn't get told where + // variables are defined, so must infer it from + // construction. If the variable does not have a + // constructor, its live range may be larger than it really + // ought to be if it is defined within a loop body, but + // that is conservative.) + } else { + return src; + } + } + } + if ("PEdgeCallArguments" in edge) { + for (var exp of edge.PEdgeCallArguments.Exp) { + if (expressionUsesVariable(exp, variable)) + return src; + } + } + if (edge.Exp.length == 1) + return 0; + + // Assigning call result to a variable. + const lhs = edge.Exp[1]; + if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable)) + return src; + return 0; + } + + case "Loop": + return 0; + + case "Assembly": + return 0; + + default: + assert(false); + } +} + +function expressionIsVariable(exp, variable) +{ + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +function expressionIsMethodOnVariable(exp, variable) +{ + // This might be calling a method on a base class, in which case exp will + // be an unnamed field of the variable instead of the variable itself. + while (exp.Kind == "Fld" && exp.Field.Name[0].startsWith("field:")) + exp = exp.Exp[0]; + + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +// Return whether the edge starts the live range of a variable's value, by setting +// it to some new value. Examples of starting obj's live range: +// +// obj = foo; +// obj = foo(); +// obj = foo(obj); // uses previous value but then sets to new value +// SomeClass obj(true, 1); // constructor +// +function edgeStartsValueLiveRange(edge, variable) +{ + // Direct assignments start live range of lhs: var = value + if (edge.Kind == "Assign") { + const [lhs, rhs] = edge.Exp; + return (expressionIsVariable(lhs, variable) && + !isReturningImmobileValue(edge, variable)); + } + + if (edge.Kind != "Call") + return false; + + // Assignments of call results start live range: var = foo() + if (1 in edge.Exp) { + var lhs = edge.Exp[1]; + if (expressionIsVariable(lhs, variable)) + return true; + } + + // Constructor calls start live range of instance: SomeClass var(...) + if ("PEdgeCallInstance" in edge) { + var instance = edge.PEdgeCallInstance.Exp; + + // Kludge around incorrect dereference on some constructor calls. + if (instance.Kind == "Drf") + instance = instance.Exp[0]; + + if (!expressionIsVariable(instance, variable)) + return false; + + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + + assert(callee.Variable.Kind == "Func"); + var calleeName = readable(callee.Variable.Name[0]); + + // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('. + var openParen = calleeName.indexOf('('); + if (openParen < 0) + return false; + calleeName = calleeName.substring(0, openParen); + + var lastColon = calleeName.lastIndexOf('::'); + if (lastColon < 0) + return false; + var constructorName = calleeName.substr(lastColon + 2); + calleeName = calleeName.substr(0, lastColon); + + var lastTemplateOpen = calleeName.lastIndexOf('<'); + if (lastTemplateOpen >= 0) + calleeName = calleeName.substr(0, lastTemplateOpen); + + if (calleeName.endsWith(constructorName)) + return true; + } + + return false; +} + +// Return whether an edge "clears out" a variable's value. A simple example +// would be +// +// var = nullptr; +// +// for analyses for which nullptr is a "safe" value (eg GC rooting hazards; you +// can't get in trouble by holding a nullptr live across a GC.) A more complex +// example is a Maybe<T> that gets reset: +// +// Maybe<AutoCheckCannotGC> nogc; +// nogc.emplace(cx); +// nogc.reset(); +// gc(); // <-- not a problem; nogc is invalidated by prev line +// nogc.emplace(cx); +// foo(nogc); +// +// Yet another example is a UniquePtr being passed by value, which means the +// receiver takes ownership: +// +// UniquePtr<JSObject*> uobj(obj); +// foo(uobj); +// gc(); +// +function edgeEndsValueLiveRange(edge, variable, body) +{ + // var = nullptr; + if (edge.Kind == "Assign") { + const [lhs, rhs] = edge.Exp; + return expressionIsVariable(lhs, variable) && isImmobileValue(rhs); + } + + if (edge.Kind != "Call") + return false; + + var callee = edge.Exp[0]; + + if (edge.Type.Kind == 'Function' && + edge.Exp[0].Kind == 'Var' && + edge.Exp[0].Variable.Kind == 'Func' && + edge.Exp[0].Variable.Name[1] == 'MarkVariableAsGCSafe' && + edge.Exp[0].Variable.Name[0].includes("JS::detail::MarkVariableAsGCSafe") && + expressionIsVariable(edge.PEdgeCallArguments.Exp[0], variable)) + { + // explicit JS_HAZ_VARIABLE_IS_GC_SAFE annotation + return true; + } + + if (edge.Type.Kind == 'Function' && + edge.Exp[0].Kind == 'Var' && + edge.Exp[0].Variable.Kind == 'Func' && + edge.Exp[0].Variable.Name[1] == 'move' && + edge.Exp[0].Variable.Name[0].includes('std::move(') && + expressionIsVariable(edge.PEdgeCallArguments.Exp[0], variable) && + edge.Exp[1].Kind == 'Var' && + edge.Exp[1].Variable.Kind == 'Temp') + { + // temp = std::move(var) + // + // If var is a UniquePtr, and we pass it into something that takes + // ownership, then it should be considered to be invalid. Example: + // + // consume(std::move(var)); + // + // where consume takes a UniquePtr. This will compile to something like + // + // UniquePtr* __temp_1 = &std::move(var); + // UniquePtr&& __temp_2(*temp_1); // move constructor + // consume(__temp_2); + // ~UniquePtr(__temp_2); + // + // The line commented with "// move constructor" is a result of passing + // a UniquePtr as a parameter. If consume() took a UniquePtr&& + // directly, this would just be: + // + // UniquePtr* __temp_1 = &std::move(var); + // consume(__temp_1); + // + // which is not guaranteed to move from the reference. It might just + // ignore the parameter. We can't predict what consume(UniquePtr&&) + // will do. We do know that UniquePtr(UniquePtr&& other) moves out of + // `other`. + // + // The std::move() technically is irrelevant, but because we only care + // about bare variables, it has to be used, which is fortunate because + // the UniquePtr&& constructor operates on a temporary, not the + // variable we care about. + + const lhs = edge.Exp[1].Variable; + if (basicBlockEatsVariable(lhs, body, edge.Index[1])) + return true; + } + + if (edge.Type.Kind == 'Function' && + edge.Type.TypeFunctionCSU && + edge.PEdgeCallInstance && + expressionIsMethodOnVariable(edge.PEdgeCallInstance.Exp, variable)) + { + const typeName = edge.Type.TypeFunctionCSU.Type.Name; + const m = typeName.match(/^(((\w|::)+?)(\w+))</); + if (m) { + const [, type, namespace,, classname] = m; + + // special-case: the initial constructor that doesn't provide a value. + // Useful for things like Maybe<T>. + const ctorName = `${namespace}${classname}<T>::${classname}()`; + if (callee.Kind == 'Var' && + typesWithSafeConstructors.has(type) && + callee.Variable.Name[0].includes(ctorName)) + { + return true; + } + + // special-case: UniquePtr::reset() and similar. + if (callee.Kind == 'Var' && + type in resetterMethods && + resetterMethods[type].has(callee.Variable.Name[1])) + { + return true; + } + } + } + + // special-case: passing UniquePtr<T> by value. + if (edge.Type.Kind == 'Function' && + edge.Type.TypeFunctionArgument && + edge.PEdgeCallArguments) + { + for (const i in edge.Type.TypeFunctionArgument) { + const param = edge.Type.TypeFunctionArgument[i]; + if (param.Type.Kind != 'CSU') + continue; + if (!param.Type.Name.startsWith("mozilla::UniquePtr<")) + continue; + const arg = edge.PEdgeCallArguments.Exp[i]; + if (expressionIsVariable(arg, variable)) { + return true; + } + } + } + + return false; +} + +function edgeMovesVariable(edge, variable) +{ + if (edge.Kind != 'Call') + return false; + const callee = edge.Exp[0]; + if (callee.Kind == 'Var' && + callee.Variable.Kind == 'Func') + { + const { Variable: { Name: [ fullname, shortname ] } } = callee; + const [ mangled, unmangled ] = splitFunction(fullname); + // Match a UniquePtr move constructor. + if (unmangled.match(/::UniquePtr<[^>]*>::UniquePtr\((\w+::)*UniquePtr<[^>]*>&&/)) + return true; + } + + return false; +} + +// Scan forward through the basic block in 'body' starting at 'startpoint', +// looking for a call that passes 'variable' to a move constructor that +// "consumes" it (eg UniquePtr::UniquePtr(UniquePtr&&)). +function basicBlockEatsVariable(variable, body, startpoint) +{ + const successors = getSuccessors(body); + let point = startpoint; + while (point in successors) { + // Only handle a single basic block. If it forks, stop looking. + const edges = successors[point]; + if (edges.length != 1) { + return false; + } + const edge = edges[0]; + + if (edgeMovesVariable(edge, variable)) { + return true; + } + + // edgeStartsValueLiveRange will find places where 'variable' is given + // a new value. Never observed in practice, since this function is only + // called with a temporary resulting from std::move(), which is used + // immediately for a call. But just to be robust to future uses: + if (edgeStartsValueLiveRange(edge, variable)) { + return false; + } + + point = edge.Index[1]; + } + + return false; +} + +function edgeIsNonReleasingDtor(body, edge, calleeName, functionBodies) { + if (edge.Kind !== "Call") { + return false; + } + if (!isRefcountedDtor(calleeName)) { + return false; + } + + let callee = edge.Exp[0]; + while (callee.Kind === "Drf") { + callee = callee.Exp[0]; + } + + const instance = edge.PEdgeCallInstance.Exp; + if (instance.Kind !== "Var") { + // TODO: handle field destructors + return false; + } + + // Test whether the dtor call is dominated by operations on the variable + // that mean it will not go to a zero refcount in the dtor: either because + // it's already dead (eg r.forget() was called) or because it can be proven + // to have a ref count of greater than 1. This is implemented by looking + // for the reverse: find a path scanning backwards from the dtor call where + // the variable is used in any way that does *not* ensure that it is + // trivially destructible. + + const variable = instance.Variable; + + const visitor = new class extends Visitor { + // Do not revisit nodes. For new nodes, relay the decision made by + // extend_path. + next_action(seen, current) { return seen ? "prune" : current; } + + // We don't revisit, so always use the new. + merge_info(seen, current) { return current; } + + // Return the action to take from this node. + extend_path(edge, body, ppoint, successor_path) { + if (!edge) { + // Dummy edge to join two points. + return "continue"; + } + + if (!edgeUsesVariable(edge, variable, body)) { + // Nothing of interest on this edge, keep searching. + return "continue"; + } + + if (edgeEndsValueLiveRange(edge, variable, body)) { + // This path is safe! + return "prune"; + } + + // Unsafe. Found a use that might set the variable to a + // nonzero refcount. + return "done"; + } + }(functionBodies); + + // Searching upwards from a destructor call, return the opposite of: is + // there a path to a use or the start of the function that does NOT hit a + // safe assignment like refptr.forget() first? + // + // In graph terms: return whether the destructor call is dominated by forget() calls (or similar). + return !BFS_upwards( + body, edge.Index[0], functionBodies, visitor, "start", + true // Return value if we reach the root without finding a non-forget() use. + ); +} + +// gcc uses something like "__dt_del " for virtual destructors that it +// generates. +function isSyntheticVirtualDestructor(funcName) { + return funcName.endsWith(" "); +} + +function typedField(field) +{ + if ("FieldInstanceFunction" in field) { + // Virtual call + // + // This makes a minimal attempt at dealing with overloading, by + // incorporating the number of parameters. So far, that is all that has + // been needed. If more is needed, sixgill will need to produce a full + // mangled type. + const {Type, Name: [name]} = field; + + // Virtual destructors don't need a type or argument count, + // and synthetic ones don't have them filled in. + if (isSyntheticVirtualDestructor(name)) { + return name; + } + + var nargs = 0; + if (Type.Kind == "Function" && "TypeFunctionArguments" in Type) + nargs = Type.TypeFunctionArguments.Type.length; + return name + ":" + nargs; + } else { + // Function pointer field + return field.Name[0]; + } +} + +function fieldKey(csuName, field) +{ + return csuName + "." + typedField(field); +} |