CodeQL library for C/C++
codeql/cpp-all 0.12.8-dev (changelog, source)
Search

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.

Import path

import codeql.ssa.Ssa

Direct supertypes

Indirect supertypes

Predicates

toString

Gets a textual representation of this SSA definition.

Inherited predicates

definesAt

Holds if this SSA definition defines v at index i in basic block bb. Phi nodes are considered to be at index -1, while normal variable writes are at the index of the control flow node they wrap.

from DefinitionExt
getBasicBlock

Gets the basic block to which this SSA definition belongs.

from DefinitionExt
getSourceVariable

Gets the source variable underlying this SSA definition.

from DefinitionExt