EliminateRedundantPhi.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 {CompilerError} from '../CompilerError';
import {
  BlockId,
  GeneratedSource,
  HIRFunction,
  Identifier,
  Place,
} from '../HIR/HIR';
import {
  eachInstructionLValue,
  eachInstructionOperand,
  eachTerminalOperand,
} from '../HIR/visitors';

const DEBUG = false;

/*
 * Pass to eliminate redundant phi nodes:
 * - all operands are the same identifier, ie `x2 = phi(x1, x1, x1)`.
 * - all operands are the same identifier *or* the output of the phi, ie `x2 = phi(x1, x2, x1, x2)`.
 *
 * In both these cases, the phi is eliminated and all usages of the phi identifier
 * are replaced with the other operand (ie in both cases above, all usages of `x2` are replaced with `x1` .
 *
 * The algorithm is inspired by that in https://pp.ipd.kit.edu/uploads/publikationen/braun13cc.pdf
 * but modified to reduce passes over the CFG. We visit the blocks in reverse postorder. Each time a redundant
 * phi is encountered we add a mapping (eg x2 -> x1) to a rewrite table. Subsequent instructions, terminals,
 * and phis rewrite all their identifiers based on this table. The algorithm loops over the CFG repeatedly
 * until there are no new rewrites: for a CFG without back-edges it completes in a single pass.
 */
export function eliminateRedundantPhi(
  fn: HIRFunction,
  sharedRewrites?: Map<Identifier, Identifier>,
): void {
  const ir = fn.body;
  const rewrites: Map<Identifier, Identifier> =
    sharedRewrites != null ? sharedRewrites : new Map();

  /*
   * Whether or the CFG has a back-edge (a loop). We determine this dynamically
   * during the first iteration over the CFG by recording which blocks were already
   * visited, and checking if a block has any predecessors that weren't visited yet.
   * Because blocks are in reverse postorder, the only time this can occur is a loop.
   */
  let hasBackEdge = false;
  const visited: Set<BlockId> = new Set();

  /*
   * size tracks the number of rewrites at the beginning of each iteration, so we can
   * compare to see if any new rewrites were added in that iteration.
   */
  let size = rewrites.size;
  do {
// ... (118 more lines)