summaryrefslogtreecommitdiffstats
path: root/js/src/devtools/rootAnalysis/CFG.js
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
commit36d22d82aa202bb199967e9512281e9a53db42c9 (patch)
tree105e8c98ddea1c1e4784a60a5a6410fa416be2de /js/src/devtools/rootAnalysis/CFG.js
parentInitial commit. (diff)
downloadfirefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz
firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'js/src/devtools/rootAnalysis/CFG.js')
-rw-r--r--js/src/devtools/rootAnalysis/CFG.js1178
1 files changed, 1178 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..1b6f714279
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/CFG.js
@@ -0,0 +1,1178 @@
+/* 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;
+
+// When edge.Kind == "Pointer", these are the meanings of the edge.Reference field.
+var PTR_POINTER = 0;
+var PTR_REFERENCE = 1;
+var PTR_RVALUE_REF = 2;
+
+// 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());
+ }
+ }
+
+ // 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_value) { return true; }
+
+ // 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 do not continue to predecessors of this node, only continue with
+ // the remaining entries in the work queue. "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; }
+
+ // Default visit() implementation. Subclasses will usually leave this alone
+ // and use the other methods as extension points.
+ //
+ // Take a body, a point within that body, and the info computed by
+ // extend_path() for that point when traversing an edge. Return whether the
+ // search should continue ("continue"), the search should be pruned and
+ // other paths followed ("prune"), or that the whole search is complete and
+ // it is time to return a value ("done", and the value returned by
+ // merge_info() will be returned by the overall search).
+ //
+ // Persistently record the value computed so far at each point, and call
+ // (overridable) next_action() and merge_info() methods with the previous
+ // and freshly-computed value for each point.
+ //
+ // Often, extend_path() will decide how/whether to continue the search and
+ // will return the search action to take, and next_action() will blindly
+ // return it if the point has not yet been visited. (And if it has, it will
+ // prune this branch of the search so that no point is visited multiple
+ // times.)
+ visit(body, ppoint, info) {
+ const visited_value_table = this.visited_bodies.get(body);
+ const existing_value_if_visited = visited_value_table.get(ppoint);
+ const action = this.next_action(existing_value_if_visited, info);
+ const merged = this.merge_info(existing_value_if_visited, info);
+ visited_value_table.set(ppoint, merged);
+ return [action, merged];
+ }
+};
+
+function findMatchingBlock(bodies, blockId) {
+ for (const body of bodies) {
+ if (sameBlockId(body.BlockId, blockId)) {
+ return body;
+ }
+ }
+ assert(false);
+}
+
+// For a given function containing a set of bodies, each containing a set of
+// ppoints, perform a mostly breadth-first traversal through the complete graph
+// of all <body, ppoint> nodes throughout all the bodies of the function.
+//
+// When traversing, every <body, ppoint> node is associated with a value that
+// is assigned or updated whenever it is visited. The overall traversal
+// terminates when a given condition is reached, and an arbitrary custom value
+// is returned. If the search completes without the termination condition
+// being reached, it will return the value associated with the entrypoint
+// node, which is initialized to `entrypoint_fallback_value` (and thus serves as
+// the fallback return value if all search paths are pruned before reaching
+// the entrypoint.)
+//
+// The traversal is only *mostly* breadth-first because the visitor decides
+// whether to stop searching when it sees a node. If a node is visited for a
+// second time, the visitor can choose to continue (and thus revisit the node)
+// in order to find "better" paths that may include a node more than once.
+// The search is done in the "upwards" direction -- as in, it starts at the
+// exit point and searches through predecessors.
+//
+// Override visitor.visit() to return an action and a value. The action
+// determines whether the overall search should terminate ('done'), or
+// continues looking through the predecessors of the current node ('continue'),
+// or whether it should just continue processing the work queue without
+// looking at predecessors ('prune').
+//
+// This allows this function to be used in different ways. If the visitor
+// associates a value with each node that chains onto its forward-flow successors
+// (predecessors in the "upwards" search order), then a complete path through
+// the graph will be returned.
+//
+// Alternatively, BFS_upwards() can be used to test whether a condition holds
+// (eg "the exit point is reachable only after calling SomethingImportant()"),
+// in which case no path is needed and the visitor can compute a simple boolean
+// every time it encounters a point. Note that `entrypoint_fallback_value` will
+// still be returned if the search terminates without ever reaching the
+// entrypoint, which is useful for dominator analyses.
+//
+// See the Visitor base class's implementation of visit(), above, for the
+// most commonly used visit logic.
+function BFS_upwards(start_body, start_ppoint, bodies, visitor,
+ initial_successor_value = {},
+ entrypoint_fallback_value=null)
+{
+ let entrypoint_value = entrypoint_fallback_value;
+
+ const work = [[start_body, start_ppoint, null, initial_successor_value]];
+ if (TRACING) {
+ printErr(`BFS start at ${blockIdentifier(start_body)}:${start_ppoint}`);
+ }
+
+ while (work.length > 0) {
+ const [body, ppoint, edgeToAdd, successor_value] = work.shift();
+ if (TRACING) {
+ const s = edgeToAdd ? " : " + str(edgeToAdd) : "";
+ printErr(`prepending edge from ${ppoint} to state '${successor_value}'${s}`);
+ }
+ let value = visitor.extend_path(edgeToAdd, body, ppoint, successor_value);
+
+ const [action, merged_value] = visitor.visit(body, ppoint, value);
+ if (action === "done") {
+ return merged_value;
+ }
+ if (action === "prune") {
+ // Do not push anything else to the work queue, but continue processing
+ // other branches.
+ continue;
+ }
+ assert(action == "continue");
+ value = merged_value;
+
+ 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, value]);
+ // 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.)
+ }
+ work.push([body, edge.Index[0], edge, value]);
+ }
+
+ // 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, value]);
+ }
+
+ // This point is also preceded by the *end* of this loop, for the
+ // previous iteration.
+ work.push([body, body.Index[1], null, value]);
+ }
+
+ // Check for reaching the entrypoint of the function.
+ if (body === start_body && ppoint == body.Index[0]) {
+ entrypoint_value = value;
+ }
+ }
+
+ // 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 entrypoint_value will still be its initial
+ // value. (If entrypoint_value has been set, then we may still not have visited the
+ // entire graph, if some paths were pruned but at least one made it to the entrypoint.)
+ return entrypoint_value;
+}
+
+// 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;
+}
+
+// Returns whether decl is a body.DefineVariable[] entry for a non-temporary reference.
+function isReferenceDecl(decl) {
+ return decl.Type.Kind == "Pointer" && decl.Type.Reference != PTR_POINTER && decl.Variable.Kind != "Temp";
+}
+
+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.
+//
+// Certain references may be annotated to be live to the end of the function
+// as well (eg AutoCheckCannotGC&& parameters).
+//
+// Note that this returns a nonzero value only if the variable's incoming value is used.
+// So this would return 0 for 'obj':
+//
+// obj = someFunction();
+//
+// but these would return a positive value:
+//
+// obj = someFunction(obj);
+// obj->foo = someFunction();
+//
+function edgeUsesVariable(edge, variable, body, liveToEnd=false)
+{
+ if (ignoreEdgeUse(edge, variable, body))
+ return 0;
+
+ if (variable.Kind == "Return") {
+ liveToEnd = true;
+ }
+
+ if (liveToEnd && 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);
+ }
+}
+
+// If `decl` is the body.DefineVariable[] declaration of a reference type, then
+// return the expression without the outer dereference. Otherwise, return the
+// original expression.
+function maybeDereference(exp, decl) {
+ if (exp.Kind == "Drf" && exp.Exp[0].Kind == "Var") {
+ if (isReferenceDecl(decl)) {
+ return exp.Exp[0];
+ }
+ }
+ return exp;
+}
+
+function expressionIsVariable(exp, variable)
+{
+ return exp.Kind == "Var" && sameVariable(exp.Variable, variable);
+}
+
+// Similar to the above, except treat uses of a reference as if they were uses
+// of the dereferenced contents. This requires knowing the type of the
+// variable, and so takes its declaration rather than the variable itself.
+function expressionIsDeclaredVariable(exp, decl)
+{
+ exp = maybeDereference(exp, decl);
+ return expressionIsVariable(exp, decl.Variable);
+}
+
+function expressionIsMethodOnVariableDecl(exp, decl)
+{
+ // 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 expressionIsDeclaredVariable(exp, decl);
+}
+
+// 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 the result of a `matcher` callback on the call found in the given
+// `edge`, if the edge is a direct call to a named function (if not, return false).
+// `matcher` is given the name of the callee (actually, a tuple
+// [fully qualified name, base name]), an array of expressions containing the
+// arguments, and if the result of the call is assigned to a variable,
+// the expression representing that variable(the lhs).
+//
+// https://firefox-source-docs.mozilla.org/js/HazardAnalysis/CFG.html for
+// documentation of the data structure used here.
+function matchEdgeCall(edge, matcher) {
+ if (edge.Kind != "Call") {
+ return false;
+ }
+
+ const callee = edge.Exp[0];
+
+ if (edge.Type.Kind == 'Function' &&
+ edge.Exp[0].Kind == 'Var' &&
+ edge.Exp[0].Variable.Kind == 'Func') {
+ const calleeName = edge.Exp[0].Variable.Name;
+ const args = edge.PEdgeCallArguments;
+ const argExprs = args ? args.Exp : [];
+ const lhs = edge.Exp[1]; // May be undefined
+ return matcher(calleeName, argExprs, lhs);
+ }
+
+ return false;
+}
+
+function edgeMarksVariableGCSafe(edge, variable) {
+ return matchEdgeCall(edge, (calleeName, argExprs, _lhs) => {
+ // explicit JS_HAZ_VARIABLE_IS_GC_SAFE annotation
+ return (calleeName[1] == 'MarkVariableAsGCSafe' &&
+ calleeName[0].includes("JS::detail::MarkVariableAsGCSafe") &&
+ argExprs.length == 1 &&
+ expressionIsVariable(argExprs[0], variable));
+ });
+}
+
+// Match an optional <namespace>:: followed by the class name,
+// and then an optional template parameter marker.
+//
+// Example: mozilla::dom::UniquePtr<...
+//
+function parseTypeName(typeName) {
+ const m = typeName.match(/^(((?:\w|::)+::)?(\w+))\b(\<)?/);
+ if (!m) {
+ return undefined;
+ }
+ const [, type, raw_namespace, classname, is_specialized] = m;
+ const namespace = raw_namespace === null ? "" : raw_namespace;
+ return { type, namespace, classname, is_specialized }
+}
+
+// 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;
+
+ if (edgeMarksVariableGCSafe(edge, variable)) {
+ // explicit JS_HAZ_VARIABLE_IS_GC_SAFE annotation
+ return true;
+ }
+
+ const decl = lookupVariable(body, variable);
+
+ if (matchEdgeCall(edge, (calleeName, argExprs, lhs) => {
+ return calleeName[1] == 'move' && calleeName[0].includes('std::move(') &&
+ expressionIsDeclaredVariable(argExprs[0], decl) &&
+ lhs &&
+ lhs.Kind == 'Var' &&
+ lhs.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;
+ }
+
+ const callee = edge.Exp[0];
+
+ if (edge.Type.Kind == 'Function' &&
+ edge.Type.TypeFunctionCSU &&
+ edge.PEdgeCallInstance &&
+ expressionIsMethodOnVariableDecl(edge.PEdgeCallInstance.Exp, decl))
+ {
+ const typeName = edge.Type.TypeFunctionCSU.Type.Name;
+
+ // Synthesize a zero-arg constructor name like
+ // mozilla::dom::UniquePtr<T>::UniquePtr(). Note that the `<T>` is
+ // literal -- the pretty name from sixgill will render the actual
+ // constructor name as something like
+ //
+ // UniquePtr<T>::UniquePtr() [where T = int]
+ //
+ const parsed = parseTypeName(typeName);
+ if (parsed) {
+ const { type, namespace, classname, is_specialized } = parsed;
+
+ // special-case: the initial constructor that doesn't provide a value.
+ // Useful for things like Maybe<T>.
+ const template = is_specialized ? '<T>' : '';
+ const ctorName = `${namespace}${classname}${template}::${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;
+}
+
+// Look up a variable in the list of declarations for this body.
+function lookupVariable(body, variable) {
+ for (const decl of (body.DefineVariable || [])) {
+ if (sameVariable(decl.Variable, variable)) {
+ return decl;
+ }
+ }
+ return undefined;
+}
+
+function edgeMovesVariable(edge, variable, body)
+{
+ 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;
+
+ // Match an rvalue parameter.
+
+ if (!edge || !edge.PEdgeCallArguments || !edge.PEdgeCallArguments.Exp) {
+ return false;
+ }
+
+ for (const arg of edge.PEdgeCallArguments.Exp) {
+ if (arg.Kind != 'Drf') continue;
+ const val = arg.Exp[0];
+ if (val.Kind == 'Var' && sameVariable(val.Variable, variable)) {
+ // This argument is the variable we're looking for. Return true
+ // if it is passed as an rvalue reference.
+ const type = lookupVariable(body, variable).Type;
+ if (type.Kind == "Pointer" && type.Reference == PTR_RVALUE_REF) {
+ 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, body)) {
+ 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;
+}
+
+var PROP_REFCNT = 1 << 0;
+var PROP_SHARED_PTR_DTOR = 1 << 1;
+
+function getCalleeProperties(calleeName) {
+ let props = 0;
+
+ if (isRefcountedDtor(calleeName)) {
+ props |= PROP_REFCNT;
+ }
+ if (calleeName.includes("~shared_ptr()")) {
+ props |= PROP_SHARED_PTR_DTOR;
+ }
+ return props;
+}
+
+// Basic C++ ABI mangling: prefix an identifier with its length, in decimal.
+function mangle(name) {
+ return name.length + name;
+}
+
+var TriviallyDestructibleTypes = new Set([
+ // Single-token types from
+ // https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling-builtin
+ "void", "wchar_t", "bool", "char", "short", "int", "long", "float", "double",
+ "__int64", "__int128", "__float128", "char32_t", "char16_t", "char8_t",
+ // Remaining observed cases. These are types T in shared_ptr<T> that have
+ // been observed, where the types themselves have trivial destructors, and
+ // the custom deleter doesn't do anything nontrivial that we might care about.
+ "_IO_FILE"
+]);
+function synthesizeDestructorName(className) {
+ if (className.includes("<") || className.includes(" ") || className.includes("{")) {
+ return;
+ }
+ if (TriviallyDestructibleTypes.has(className)) {
+ return;
+ }
+ const parts = className.split("::");
+ const mangled_dtor = "_ZN" + parts.map(p => mangle(p)).join("") + "D2Ev";
+ const pretty_dtor = `void ${className}::~${parts.at(-1)}()`;
+ // Note that there will be a later check to verify that the function name
+ // synthesized here is an actual function, and assert if not (see
+ // assertFunctionExists() in computeCallgraph.js.)
+ return mangled_dtor + "$" + pretty_dtor;
+}
+
+function getCallEdgeProperties(body, edge, calleeName, functionBodies) {
+ let attrs = 0;
+ let extraCalls = [];
+
+ if (edge.Kind !== "Call") {
+ return { attrs, extraCalls };
+ }
+
+ const props = getCalleeProperties(calleeName);
+ if (props & PROP_REFCNT) {
+ // std::swap of two refcounted values thinks it can drop the
+ // ref count to zero. Or rather, it just calls operator=() in a context
+ // where the refcount will never drop to zero.
+ const blockId = blockIdentifier(body);
+ if (blockId.includes("std::swap") || blockId.includes("mozilla::Swap")) {
+ // Replace the refcnt release call with nothing. It's not going to happen.
+ attrs |= ATTR_REPLACED;
+ }
+ }
+
+ if (props & PROP_SHARED_PTR_DTOR) {
+ // Replace shared_ptr<T>::~shared_ptr() calls to T::~T() calls.
+ // Note that this will only apply to simple cases.
+ // Any templatized type, in particular, will be ignored and the original
+ // call tree will be left alone. If this triggers a hazard, then we can
+ // consider extending the mangling support.
+ //
+ // If the call to ~shared_ptr is not replaced, then it might end up calling
+ // an unknown function pointer. This does not always happen-- in some cases,
+ // the call tree below ~shared_ptr will invoke the correct destructor without
+ // going through function pointers.
+ const m = calleeName.match(/shared_ptr<(.*?)>::~shared_ptr\(\)(?: \[with T = ([\w:]+))?/);
+ assert(m);
+ let className = m[1] == "T" ? m[2] : m[1];
+ assert(className != "");
+ // cv qualification does not apply to destructors.
+ className = className.replace("const ", "");
+ className = className.replace("volatile ", "");
+ const dtor = synthesizeDestructorName(className);
+ if (dtor) {
+ attrs |= ATTR_REPLACED;
+ extraCalls.push({
+ attrs: ATTR_SYNTHETIC,
+ name: dtor,
+ });
+ }
+ }
+
+ if ((props & PROP_REFCNT) == 0) {
+ return { attrs, extraCalls };
+ }
+
+ 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 { attrs, extraCalls };
+ }
+
+ // 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 DominatorVisitor 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_value) {
+ 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).
+ const edgeIsNonReleasingDtor = !BFS_upwards(
+ body, edge.Index[0], functionBodies, visitor, "start",
+ false // Return value if we do not reach the root without finding a non-forget() use.
+ );
+ if (edgeIsNonReleasingDtor) {
+ attrs |= ATTR_GC_SUPPRESSED | ATTR_NONRELEASING;
+ }
+ return { attrs, extraCalls };
+}
+
+// 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);
+}