14.21.7 RTL SSA Access Lists ¶

All the definitions of a resource are chained together in reverse postorder. In general, this list can contain an arbitrary mix of both sets (rtl_ssa::set_info) and clobbers (rtl_ssa::clobber_info). However, it is often useful to skip over all intervening clobbers of a resource in order to find the next set. The list is constructed in such a way that this can be done in amortized constant time.

All uses (rtl_ssa::use_info) of a given set are also chained together into a list. This list of uses is divided into three parts:

1. uses by “real” nondebug instructions (see real RTL SSA insns)
2. uses by real debug instructions
3. uses by phi nodes (see RTL SSA Phi Nodes)

The first and second parts individually follow reverse postorder. The third part has no particular order.

The last use by a real nondebug instruction always comes earlier in the reverse postorder than the next definition of the resource (if any). This means that the accesses follow a linear sequence of the form:

• first definition of resource R
  • first use by a real nondebug instruction of the first definition of resource R
  • …
  • last use by a real nondebug instruction of the first definition of resource R
• second definition of resource R
  • first use by a real nondebug instruction of the second definition of resource R
  • …
  • last use by a real nondebug instruction of the second definition of resource R
• …
• last definition of resource R
  • first use by a real nondebug instruction of the last definition of resource R
  • …
  • last use by a real nondebug instruction of the last definition of resource R

(Note that clobbers never have uses; only sets do.)

This linear view is easy to achieve when there is only a single definition of a resource, which is commonly true for pseudo registers. However, things are more complex if code has a structure like the following:

// ebb2, bb2
R = va;        // A
if (…)
  {
    // ebb2, bb3
    use1 (R);  // B
    …
    R = vc;    // C
  }
else
  {
    // ebb4, bb4
    use2 (R);  // D
  }

The list of accesses would begin as follows:

• definition of R by A
  • use of A’s definition of R by B
• definition of R by C

The next access to R is in D, but the value of R that D uses comes from A rather than C.

This is resolved by adding a phi node for ebb4. All inputs to this phi node have the same value, which in the example above is A’s definition of R. In other circumstances, it would not be necessary to create a phi node when all inputs are equal, so these phi nodes are referred to as “degenerate” phi nodes.

The full list of accesses to R is therefore:

• definition of R by A
  • use of A’s definition of R by B
• definition of R by C
• definition of R by ebb4’s phi instruction, with the input coming from A
  • use of the ebb4’s R phi definition of R by B

Note that A’s definition is also used by ebb4’s phi node, but this use belongs to the third part of the use list described above and so does not form part of the linear sequence.

It is possible to “look through” any degenerate phi to the ultimate definition using the function look_through_degenerate_phi. Note that the input to a degenerate phi is never itself provided by a degenerate phi.

At present, the SSA form takes this principle one step further and guarantees that, for any given resource res, one of the following is true:

• The resource has a single definition def, which is not a phi node. Excluding uses of undefined registers, all uses of res by real nondebug instructions use the value provided by def.
• Excluding uses of undefined registers, all uses of res use values provided by definitions that occur earlier in the same extended basic block. These definitions might come from phi nodes or from real instructions.