Dominator.ts — react Source File

Source Code

/**
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

import prettyFormat from 'pretty-format';
import {CompilerError} from '../CompilerError';
import {BlockId, GeneratedSource, HIRFunction} from './HIR';
import {eachTerminalSuccessor} from './visitors';

/*
 * Computes the dominator tree of the given function. The returned `Dominator` stores the immediate
 * dominator of each node in the function, which can be retrieved with `Dominator.prototype.get()`.
 *
 * A block X dominates block Y in the CFG if all paths to Y must flow through X. Thus the entry
 * block dominates all other blocks. See https://en.wikipedia.org/wiki/Dominator_(graph_theory)
 * for more.
 */
export function computeDominatorTree(fn: HIRFunction): Dominator<BlockId> {
  const graph = buildGraph(fn);
  const nodes = computeImmediateDominators(graph);
  return new Dominator(graph.entry, nodes);
}

/*
 * Similar to `computeDominatorTree()` but computes the post dominators of the function. The returned
 * `PostDominator` stores the immediate post-dominators of each node in the function.
 *
 * A block Y post-dominates block X in the CFG if all paths from X to the exit must flow through Y.
 * The caller must specify whether to consider `throw` statements as exit nodes. If set to false,
 * only return statements are considered exit nodes.
 */
export function computePostDominatorTree(
  fn: HIRFunction,
  options: {includeThrowsAsExitNode: boolean},
): PostDominator<BlockId> {
  const graph = buildReverseGraph(fn, options.includeThrowsAsExitNode);
  const nodes = computeImmediateDominators(graph);

  /*
   * When options.includeThrowsAsExitNode is false, nodes that flow into a throws
   * terminal and don't reach the exit node won't be in the node map. Add them
   * with themselves as dominator to reflect that they don't flow into the exit.
   */
  if (!options.includeThrowsAsExitNode) {
    for (const [id] of fn.body.blocks) {
      if (!nodes.has(id)) {
        nodes.set(id, id);
      }
    }
  }
  return new PostDominator(graph.entry, nodes);
}

type Node<T> = {
  id: T;
  index: number;
  preds: Set<T>;
// ... (228 more lines)