Class Make::PhiReadNode

A phi-read node.

Phi-read nodes are like normal phi nodes, but they are inserted based on reads instead of writes, and only if the dominance-frontier block does not already contain a normal phi node.

The motivation for adding phi-reads is to improve performance of the use-use calculation in cases where there is a large number of reads that can reach the same join-point, and from there reach a large number of basic blocks. Example:

if (a)
  use(x);
else if (b)
  use(x);
else if (c)
  use(x);
else if (d)
  use(x);
// many more ifs ...

// phi-read for `x` inserted here

// program not mentioning `x`, with large basic block graph

use(x);

Without phi-reads, the analysis has to replicate reachability for each of the guarded uses of x. However, with phi-reads, the analysis will limit each conditional use of x to reach the basic block containing the phi-read node for x, and only that basic block will have to compute reachability through the remainder of the large program.

Another motivation for phi-reads is when a large number of reads can reach another large number of reads:

if (a)
  use(x);
else if (b)
  use(x);
else if (c)
  use(x);
else if (d)
  use(x);
// many more ifs ...

// phi-read for `x` inserted here

if (a)
  use(x);
else if (b)
  use(x);
else if (c)
  use(x);
else if (d)
  use(x);
// many more ifs ...

Without phi-reads, one needs to add n*m data-flow edges (assuming n reads before the phi-read and m reads after the phi-read), whereas if we include phi-reads in the data-flow graph, we only need to add n+m edges.

Like normal reads, each phi-read node phi-read can be reached from exactly one SSA definition (without passing through another definition): Assume, for the sake of contradiction, that there are two reaching definitions def1 and def2. Now, if both def1 and def2 dominate phi-read, then the nearest dominating definition will prevent the other from reaching phi-read. So, at least one of def1 and def2 cannot dominate phi-read; assume it is def1. Then def1 must go through one of its dominance-frontier blocks in order to reach phi-read. However, such a block will always start with a (normal) phi node, which contradicts reachability.

Also, like normal reads, the unique SSA definition def that reaches phi-read, will dominate phi-read. Assuming it doesn’t means that the path from def to phi-read goes through a dominance-frontier block, and hence a phi node, which contradicts reachability.