Movatterモバイル変換

13.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 clobbersof a resource in order to find the next set. The list is constructedin such a way that this can be done in amortized constant time.

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

1. uses by “real” nondebug instructions (seereal RTL SSA insns)
2. uses by real debug instructions
3. uses by phi nodes (seeRTL 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 inthe 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 definitionof a resource, which is commonly true for pseudo registers. However,things are more complex if code has a structure like the following:

// ebb2, bb2R =va;        // Aif (…)  {    // 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 fromA rather than C.

This is resolved by adding a phi node forebb4. All inputs to thisphi node have the same value, which in the example above is A’s definitionof R. In other circumstances, it would not be necessary to create a phinode 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 thisuse belongs to the third part of the use list described above andso does not form part of the linear sequence.

It is possible to “look through” any degenerate phi to the ultimatedefinition using the functionlook_through_degenerate_phi.Note that the input to a degenerate phi is never itself providedby a degenerate phi.

At present, the SSA form takes this principle one step furtherand guarantees that, for any given resourceres, one of thefollowing is true:

• The resource has a single definitiondef, which is not a phi node.Excluding uses of undefined registers, all uses ofres by realnondebug instructions use the value provided bydef.
• Excluding uses of undefined registers, all uses ofres usevalues provided by definitions that occur earlier in the sameextended basic block. These definitions might come from phi nodesor from real instructions.

Next:Using the RTL SSA framework to change instructions, Previous:RTL SSA Phi Nodes, Up:On-the-Side SSA Form for RTL   [Contents][Index]