{"parents":["beb6e1431ca53b6f20f69e40f1dbb95bbdc5095a"],"patch":"diff --git a\/compiler\/forget\/src\/HIR\/BuildDefUseGraph.ts b\/compiler\/forget\/src\/HIR\/BuildDefUseGraph.ts\ndeleted file mode 100644\nindex 04bef729f8..0000000000\n--- a\/compiler\/forget\/src\/HIR\/BuildDefUseGraph.ts\n+++ \/dev\/null\n@@ -1,644 +0,0 @@\n-\/**\n- * Copyright (c) Facebook, Inc. and its affiliates.\n- *\n- * This source code is licensed under the MIT license found in the\n- * LICENSE file in the root directory of this source tree.\n- *\/\n-\n-import { assertExhaustive } from \"..\/Common\/utils\";\n-import { invariant } from \"..\/CompilerError\";\n-import {\n- BasicBlock,\n- BlockId,\n- Capability,\n- HIRFunction,\n- IdentifierId,\n- Instruction,\n- InstructionValue,\n- Place,\n- Terminal,\n-} from \".\/HIR\";\n-import { mapTerminalSuccessors } from \".\/HIRBuilder\";\n-import { printMixedHIR, printPlace } from \".\/PrintHIR\";\n-\n-const HOOKS: Map = new Map([\n- [\"useState\", { kind: \"State\", capability: Capability.Freeze }],\n- [\"useRef\", { kind: \"Ref\", capability: Capability.Freeze }],\n-]);\n-\n-type HookKind = { kind: \"State\" } | { kind: \"Ref\" } | { kind: \"Custom\" };\n-type Hook = HookKind & { capability: Capability };\n-\n-\/**\n- * For every usage of a value in the given function, infers whether that usage\n- * is frozen, readonly, or mutable:\n- * - frozen: the value is known to be \"owned\" by React and is therefore permanently\n- * and transitively immutable.\n- * - readonly: the value is not frozen, but this usage of the value does not modify it.\n- * the value may be mutated by a subsequent reference. Examples include referencing\n- * the operands of a binary expression, or referencing the items\/properties of an\n- * array or object literal.\n- * - mutable: the value is not frozen and this usage *may* modify it. Examples include\n- * passing a value to as a function argument or assigning into an object.\n- *\n- * Note that the inference follows variable assignment, so assigning a frozen value\n- * to a different value will infer usages of the other variable as frozen as well.\n- *\n- * The inference assumes that the code follows the rules of React:\n- * - React function arguments are frozen (component props, hook arguments).\n- * - Hook arguments are frozen at the point the hook is invoked.\n- * - React function return values are frozen at the point of being returned,\n- * thus the return value of a hook call is frozen.\n- * - JSX represents invocation of a React function (the component) and\n- * therefore all values passed to JSX become frozen at the point the JSX\n- * is created.\n- *\n- * ## Algorithm\n- *\n- * The algorithm creates a \"use-use\" graph in which each usage of a variable links to\n- * the previous (incoming) and subsequent (outgoing) usages of that variable. The primary\n- * purpose of this graph is to perform inference of usages that are frozen vs not, including\n- * accounting for control-flow and reassignment, and to update the input *in place* to\n- * annotate `Place` with the appropriate capability. The set of vertexs is returned for\n- * debugging purposes.\n- *\n- * - First create a mapping of the first and last usages of each top-level identifier\n- * in each block, in isolation (ie without considering control-flow paths between\n- * blocks).\n- * - Then iterate over the blocks in control-flow order and link the last usage of\n- * identifiers in predecssor blocks with the first usage in successor blocks.\n- * - Then find all vertices corresponding to frozen usage of a value, and propagate\n- * that \"frozenness\" forward to all subsequent usages of that value.\n- *\/\n-export default function buildDefUseGraph(fn: HIRFunction): Array {\n- const graph = new UseGraph();\n-\n- const blockResults: Map = new Map();\n- for (const [blockId, block] of fn.body.blocks) {\n- const blockResult = buildInputsOutputsForBlock(graph, block);\n- blockResults.set(blockId, blockResult);\n- }\n-\n- const preambleBuilder = new BlockResultBuilder(graph);\n- for (const param of fn.params) {\n- const place: Place = {\n- kind: \"Identifier\",\n- memberPath: null,\n- value: param,\n- path: null as any, \/\/ TODO\n- capability: Capability.Freeze,\n- };\n- preambleBuilder.init(place, null, true);\n- }\n- const preambleResult = preambleBuilder.build();\n-\n- \/\/ Iterate over the CFG linking outputs of predecssor blocks to the inputs\n- \/\/ of successor blocks, stopping once all links have been established.\n- const queue: Array<{\n- blockId: BlockId;\n- prevResult: BlockResult;\n- }> = [{ blockId: fn.body.entry, prevResult: preambleResult }];\n- while (queue.length !== 0) {\n- const { blockId, prevResult } = queue.shift()!;\n-\n- \/\/ Link the previous block's outputs to the next block's inputs\n- const blockResult = blockResults.get(blockId)!;\n- const hasChange = linkPreviousNextBlock(graph, prevResult, blockResult);\n-\n- \/\/ If there were changes to this block's outgoing edges, update any\n- \/\/ successor blocks\n- if (hasChange || blockId === fn.body.entry) {\n- const block = fn.body.blocks.get(blockId)!;\n- \/\/ TODO: add a forEachSuccessor helper, this maps the terminal unnecessarily\n- const _ = mapTerminalSuccessors(\n- block.terminal,\n- (blockId, isFallthrough) => {\n- if (!isFallthrough) {\n- queue.push({ blockId, prevResult: blockResult });\n- }\n- return blockId;\n- }\n- );\n- }\n- }\n- const vertices = graph.build();\n- for (const vertex of vertices) {\n- invariant(\n- vertex.place === null || vertex.place.capability !== Capability.Unknown,\n- \"Expected all vertices to have a capability inferred\"\n- );\n-\n- \/\/ Vertices derived from a frozen value are also frozen\n- if (\n- vertex.place !== null &&\n- vertex.place.capability === Capability.Freeze\n- ) {\n- flowFrozennessForwards(vertex, 0);\n- }\n- \/\/ Join nodes are created before we know if they will be consumed,\n- \/\/ prune join nodes without any outgoing edges to aid visualization.\n- \/\/ note that this is not required for correctness.\n- if (vertex.place === null && vertex.outgoing.size === 0) {\n- for (const incoming of vertex.incoming) {\n- incoming.outgoing.delete(vertex);\n- }\n- vertex.incoming.clear();\n- }\n- }\n- return vertices;\n-}\n-\n-\/**\n- * Once a value is known to be frozen, all usages forward of that point must be frozen too.\n- *\/\n-function flowFrozennessForwards(vertex: Vertex, epoch: number) {\n- if (vertex.epoch === epoch) {\n- return;\n- }\n- vertex.epoch = epoch;\n- if (vertex.place !== null) {\n- vertex.place.capability = Capability.Freeze;\n- }\n- for (const outgoing of vertex.outgoing) {\n- flowFrozennessForwards(outgoing, epoch);\n- }\n-}\n-\n-\/**\n- * Link the last usages from a predecessor block to the first usages in a successor block,\n- * and propagate any values used in the predecessor but _unused_ in the successor.\n- *\/\n-function linkPreviousNextBlock(\n- graph: UseGraph,\n- prevBlock: BlockResult,\n- nextBlock: BlockResult\n-): boolean {\n- \/\/ are there any changes to the *outgoing* edges of `nextBlock`?\n- let hasChanges = false;\n-\n- \/\/ for each first usage of next block, link it to last usage from prev block.\n- for (const [id, nextVertex] of nextBlock.firstUsage) {\n- if (nextVertex.isReassignment) {\n- \/\/ nextVertex was a full reassignment, do not attach an edge.\n- continue;\n- }\n- const prevVertex = prevBlock.lastUsage.get(id);\n- if (prevVertex != null && prevVertex !== nextVertex) {\n- \/\/ Note: don't update hasChanges here bc these do not affect the *outgoing* edges\n- prevVertex.outgoing.add(nextVertex);\n- nextVertex.incoming.add(prevVertex);\n- }\n- }\n- \/\/ for each last usage in the prev block that was not already linked in the above\n- \/\/ loop, add an outgoing edge to pass-through the data. the value may be used by\n- \/\/ a later block.\n- for (const [id, prevVertex] of prevBlock.lastUsage) {\n- if (nextBlock.firstUsage.has(id)) {\n- \/\/ already handled in the above loop\n- continue;\n- }\n- const nextVertex = nextBlock.lastUsage.get(id);\n- if (nextVertex == null) {\n- \/\/ First time propagating a value for this id: use the prev vertex from\n- \/\/ the predecessor as the output of the successor\n- hasChanges = true;\n- nextBlock.lastUsage.set(id, prevVertex);\n- } else if (nextVertex === prevVertex) {\n- \/\/ already propagated\n- continue;\n- } else {\n- let joinVertex;\n- if (nextVertex.place === null) {\n- \/\/ A join vertex was already created, link the successor value to it\n- joinVertex = nextVertex;\n- } else {\n- \/\/ A normal vertex was propagated through on the previous visit, but\n- \/\/ now there is a different value that needs to be propagated through.\n- \/\/ swap the node for a \"join\" vertex, adding the previous node as an\n- \/\/ input to that node.\n- joinVertex = graph.join();\n- nextVertex.outgoing.add(joinVertex);\n- joinVertex.incoming.add(nextVertex);\n- nextBlock.lastUsage.set(id, joinVertex);\n- }\n- \/\/ the incoming node may itself be a join vertex, add its inputs to\n- \/\/ avoid linking join vertices to other join vertices.\n- if (prevVertex.place === null) {\n- for (const prev of prevVertex.incoming) {\n- hasChanges =\n- hasChanges ||\n- !joinVertex.incoming.has(prev) ||\n- !prev.outgoing.has(joinVertex);\n- joinVertex.incoming.add(prev);\n- prev.outgoing.add(joinVertex);\n- }\n- } else {\n- hasChanges =\n- hasChanges ||\n- !joinVertex.incoming.has(prevVertex) ||\n- !prevVertex.outgoing.has(joinVertex);\n- joinVertex.incoming.add(prevVertex);\n- prevVertex.outgoing.add(joinVertex);\n- }\n- }\n- }\n- return hasChanges;\n-}\n-\n-\/**\n- * Iterates over a single basic block and constructs a mapping of the first and last usages\n- * of each Place referenced in that block.\n- *\/\n-function buildInputsOutputsForBlock(\n- graph: UseGraph,\n- block: BasicBlock\n-): BlockResult {\n- const builder = new BlockResultBuilder(graph);\n-\n- for (const instr of block.instructions) {\n- const instrValue = instr.value;\n- let valueCapability = Capability.Readonly;\n- switch (instrValue.kind) {\n- case \"BinaryExpression\": {\n- valueCapability = Capability.Freeze;\n- builder.reference(instrValue.left, instrValue, Capability.Readonly);\n- builder.reference(instrValue.right, instrValue, Capability.Readonly);\n- break;\n- }\n- case \"ArrayExpression\": {\n- for (const element of instrValue.elements) {\n- builder.reference(element, instrValue, Capability.Readonly);\n- }\n- break;\n- }\n- case \"NewExpression\": {\n- builder.reference(instrValue.callee, instrValue, Capability.Mutable);\n- for (const arg of instrValue.args) {\n- builder.reference(arg, instrValue, Capability.Mutable);\n- }\n- break;\n- }\n- case \"CallExpression\": {\n- let capability = Capability.Mutable;\n- const hook = parseHookCall(instrValue.callee);\n- if (hook !== null) {\n- capability = hook.capability;\n- valueCapability = hook.capability;\n- }\n- builder.reference(instrValue.callee, instrValue, capability);\n- for (const arg of instrValue.args) {\n- builder.reference(arg, instrValue, capability);\n- }\n- break;\n- }\n- case \"ObjectExpression\": {\n- \/\/ Object construction captures but does not modify the key\/property values\n- if (instrValue.properties !== null) {\n- for (const [_key, value] of Object.entries(instrValue.properties)) {\n- builder.reference(value, instrValue, Capability.Readonly);\n- }\n- }\n- break;\n- }\n- case \"UnaryExpression\": {\n- valueCapability = Capability.Freeze; \/\/ TODO check that value must be a primitive, or make conditional based on the operator\n- builder.reference(instrValue.value, instrValue, Capability.Readonly);\n- break;\n- }\n- case \"OtherStatement\": {\n- \/\/ TODO: handle other statement kinds\n- break;\n- }\n- case \"JsxExpression\": {\n- builder.reference(instrValue.tag, instrValue, Capability.Freeze);\n- for (const [_prop, value] of Object.entries(instrValue.props)) {\n- builder.reference(value, instrValue, Capability.Freeze);\n- }\n- if (instrValue.children !== null) {\n- for (const child of instrValue.children) {\n- builder.reference(child, instrValue, Capability.Freeze);\n- }\n- }\n- break;\n- }\n- case \"JSXText\":\n- case \"Primitive\": {\n- valueCapability = Capability.Readonly;\n- break;\n- }\n- case \"Identifier\": {\n- builder.reference(instrValue, instrValue, Capability.Readonly);\n- valueCapability = instrValue.capability;\n- if (instr.lvalue !== null && instr.lvalue.place.memberPath === null) {\n- builder.assign(instr.lvalue.place, instr, instrValue);\n- instr.lvalue.place.capability = valueCapability;\n- continue;\n- }\n- break;\n- }\n- default: {\n- assertExhaustive(instrValue, \"Unexpected instruction kind\");\n- }\n- }\n- if (instr.lvalue !== null) {\n- if (instr.lvalue.place.memberPath == null) {\n- builder.init(instr.lvalue.place, instr, true);\n- instr.lvalue.place.capability = valueCapability;\n- } else {\n- builder.reference(instr.lvalue.place, instr, valueCapability);\n- }\n- }\n- }\n- switch (block.terminal.kind) {\n- case \"throw\": {\n- builder.reference(\n- block.terminal.value,\n- block.terminal,\n- Capability.Freeze\n- );\n- break;\n- }\n- case \"return\": {\n- if (block.terminal.value !== null) {\n- builder.reference(\n- block.terminal.value,\n- block.terminal,\n- Capability.Freeze\n- );\n- }\n- break;\n- }\n- case \"if\": {\n- builder.reference(\n- block.terminal.test,\n- block.terminal,\n- Capability.Readonly\n- );\n- break;\n- }\n- case \"switch\": {\n- builder.reference(\n- block.terminal.test,\n- block.terminal,\n- Capability.Readonly\n- );\n- for (const case_ of block.terminal.cases) {\n- if (case_.test !== null) {\n- builder.reference(case_.test, block.terminal, Capability.Readonly);\n- }\n- }\n- break;\n- }\n- case \"goto\": {\n- break;\n- }\n- default: {\n- assertExhaustive(\n- block.terminal,\n- `Unexpected terminal kind '${(block.terminal as any as Terminal).kind}'`\n- );\n- }\n- }\n-\n- return builder.build();\n-}\n-\n-function parseHookCall(place: Place): Hook | null {\n- if (place.memberPath !== null) {\n- \/\/ Hook calls must be statically resolved\n- return null;\n- }\n- const name = place.value.name;\n- if (name === null || !name.match(\/^_?use\/)) {\n- return null;\n- }\n- const hook = HOOKS.get(name);\n- if (hook != null) {\n- return hook;\n- }\n- return { kind: \"Custom\", capability: Capability.Freeze };\n-}\n-\n-type BlockResult = {\n- firstUsage: Map;\n- lastUsage: Map;\n-};\n-\n-class BlockResultBuilder {\n- #firstUsage: Map = new Map();\n- #lastUsage: Map = new Map();\n- #graph: UseGraph;\n-\n- constructor(graph: UseGraph) {\n- this.#graph = graph;\n- }\n-\n- build(): BlockResult {\n- return {\n- firstUsage: this.#firstUsage,\n- lastUsage: this.#lastUsage,\n- };\n- }\n-\n- \/**\n- * Represents assignment of a value to a Place. Unlike with `reference()`,\n- * this does *not* establish an edge between this usage of the place and\n- * previous usages, because the value is not the same.\n- *\/\n- init(\n- place: Place,\n- instr: Instruction | InstructionValue | Terminal | null,\n- isReassignment: boolean\n- ): Vertex {\n- const id = place.value.id;\n- const vertex = this.#graph.init(place, instr, isReassignment);\n- if (!this.#firstUsage.has(id)) {\n- this.#firstUsage.set(id, vertex);\n- }\n- this.#lastUsage.set(id, vertex);\n- return vertex;\n- }\n-\n- \/**\n- * Represents assigning a (new) value to @param target via the given @param instr,\n- * with @param value as the value being assigned.\n- *\n- * This breaks the use chain, such that this and subsequent usages of @param target\n- * are not associated to previous usages. This replicates SSA semantics, conceptually\n- * @param target is a new place now.\n- *\/\n- assign(target: Place, instr: Instruction, value: Place) {\n- const targetVertex = this.init(target, instr, true);\n- const valueVertex = this.#graph.get(value)!;\n- targetVertex.incoming.add(valueVertex);\n- valueVertex.outgoing.add(targetVertex);\n- }\n-\n- \/**\n- * Represents a reference (usage of) a Place. This establishes an edge\n- * with this usage and the previous usage\n- *\/\n- reference(\n- place: Place,\n- instr: Instruction | InstructionValue | Terminal,\n- capability: Capability\n- ) {\n- const id = place.value.id;\n- place.capability = capability;\n- const prevVertex = this.#lastUsage.get(id);\n- const vertex = this.init(place, instr, false);\n-\n- if (prevVertex != null) {\n- prevVertex.outgoing.add(vertex);\n- vertex.incoming?.add(prevVertex);\n- }\n- }\n-}\n-\n-class IdGenerator {\n- #value: number = 0;\n-\n- next(): number {\n- return this.#value++;\n- }\n-}\n-\n-class UseGraph {\n- #idGenerator: IdGenerator = new IdGenerator();\n- #verticesByPlace: Map = new Map();\n- #vertices: Array = [];\n-\n- get(place: Place): Vertex | null {\n- return this.#verticesByPlace.get(place) ?? null;\n- }\n-\n- init(\n- place: Place,\n- instr: Instruction | InstructionValue | Terminal | null,\n- isReassignment: boolean\n- ): Vertex {\n- let vertex = this.#verticesByPlace.get(place);\n- if (vertex == null) {\n- vertex = new Vertex(place, instr, this.#idGenerator, isReassignment);\n- this.#verticesByPlace.set(place, vertex);\n- this.#vertices.push(vertex);\n- }\n- return vertex;\n- }\n-\n- join(): Vertex {\n- const vertex = new Vertex(null, null, this.#idGenerator, false);\n- this.#vertices.push(vertex);\n- return vertex;\n- }\n-\n- build(): Array {\n- return this.#vertices;\n- }\n-}\n-\n-\/**\n- * Represents a distinct usage of a `Place` within a program. Note that\n- * vertices are only created for top-level identifiers, not for points\n- * within an object. So both `x` and `x.y` create vertices for `x`,\n- * though this is enforced by the _construction_ of vertices in UseGraph,\n- * not the implementation of Vertex itself.\n- *\/\n-class Vertex {\n- \/**\n- * the set of vertices where *this* place was previously referenced\n- *\/\n- incoming: Set = new Set();\n-\n- \/**\n- * the set of vertices where *this* place is subseqently referenced\n- *\/\n- outgoing: Set = new Set();\n-\n- \/**\n- * The place that is using the value.\n- *\/\n- place: Place | null;\n-\n- \/**\n- * The instruction where the reference occurs (for debugging)\n- *\/\n- instr: Instruction | InstructionValue | Terminal | null;\n-\n- \/**\n- * Does this vertex represent an assignment? If yes, incoming\n- * represents the set of values that are *assigned* to this vertex,\n- * and not previous usages.\n- *\/\n- isReassignment: boolean;\n-\n- \/**\n- * Unique identifier for this vertex (for debugging)\n- *\/\n- id: string;\n-\n- \/**\n- * The last epoch in which this vertex was visited. This is used during\n- * data-flow analysis post construction of the graph to ensure termination\n- * by avoiding revisiting the same nodes in a given pass.\n- *\/\n- epoch: number | null = null;\n-\n- constructor(\n- place: Place | null,\n- instr: Instruction | InstructionValue | Terminal | null,\n- idGenerator: IdGenerator,\n- isReassignment: boolean\n- ) {\n- this.place = place;\n- this.instr = instr;\n- this.id = `v${idGenerator.next()}`;\n- this.isReassignment = isReassignment;\n- }\n-}\n-\n-\/**\n- * Prints the graph into GraphViz DOT format.\n- * https:\/\/graphviz.org\/doc\/info\/lang.html\n- *\/\n-export function printGraph(vertices: Array): string {\n- const output = [];\n-\n- for (const vertex of vertices) {\n- if (\n- vertex.place === null &&\n- vertex.incoming.size === 0 &&\n- vertex.outgoing.size === 0\n- ) {\n- continue;\n- }\n- const vertexId = vertex.id;\n- output.push(\n- `${vertexId} [ label=\"${vertexId} (${\n- vertex.place ? printPlace(vertex.place) : \"\"\n- } @ ${\n- vertex.instr\n- ? printMixedHIR(vertex.instr).replaceAll('\"', '\\\\\"')\n- : \"\"\n- }) ${vertex.isReassignment ? \"\" : \"\"}\", shape=\"box\" ]`\n- );\n- for (const outgoing of vertex.outgoing) {\n- const outgoingId = outgoing.id;\n- output.push(`${vertexId} -> ${outgoingId}`);\n- }\n- }\n- const lines = output.map((line) => \" \" + line);\n- lines.unshift(\"digraph BuildDefUseGraph {\");\n- lines.push(\"}\");\n- return lines.join(\"\\n\");\n-}\n-\n-function mapToJson(map: Map): {\n- [key: string]: string;\n-} {\n- const result: { [key: string]: string } = {};\n- for (const [id, vertex] of map) {\n- result[id] = vertex.id;\n- }\n- return result;\n-}\n","body":"","files":[{"path":"compiler\/forget\/src\/HIR\/BuildDefUseGraph.ts","status":"D"}],"commit":{"authoredAt":"2022-10-11T12:00:45-07:00","subject":"[new-arch] Cleanup unused analysis (#651)","shortRevision":"94adcf91b1","authorName":"Joseph Savona","revision":"94adcf91b146504e6765029689a441d6e91ca998","authorEmail":"josephsavona@users.noreply.github.com"}}

dillon1000/react

Files changed