Mercurial > hg > graal-compiler
changeset 22359:610c1d8cec4d
SSIUtil: document SSI form.
| author | Josef Eisl <josef.eisl@jku.at> |
|---|---|
| date | Fri, 24 Jul 2015 14:53:09 +0200 |
| parents | b93161ba3364 |
| children | 05612742baa8 |
| files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java |
| diffstat | 1 files changed, 78 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java Fri Jul 24 13:50:38 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java Fri Jul 24 14:53:09 2015 +0200 @@ -33,6 +33,84 @@ import com.oracle.graal.lir.StandardOp.*; import com.oracle.graal.lir.ssa.SSAUtil.*; +/** + * Utilities for working with Static-Single-Information LIR form. + * + * <h2>Representation of φ and σ</h2> + * + * There are no explicit φ/σ {@link LIRInstruction}s. Instead, they are implemented as + * parallel copy that spans across a control-flow edge. + * + * The variables introduced by φ/σ of a specific {@linkplain AbstractBlockBase block} are + * {@linkplain LabelOp#setIncomingValues attached} to the {@link LabelOp} of the block. The outgoing + * values from the predecessor are {@linkplain BlockEndOp#setOutgoingValues input} to the + * {@link BlockEndOp} of the predecessor. + * + * When it does not matter whether we are talking about a φ or a σ we call the values that + * are defined by a label {@linkplain LabelOp#setIncomingValues incoming} and the values that are + * input to the {@link BlockEndOp} of the predecessor {@linkplain BlockEndOp#setOutgoingValues + * outgoing}. + * + * <h2>Implementation Details</h2> + * + * For our purposes we want a <em>maximal</em> SSI form, which means that all values that are alive + * across basic block boundaries are gated with a φ/σ. In other words the outgoing and + * incoming values of the {@link BlockEndOp} and {@link LabelOp} are equivalent to the live-out and + * live-in set of the corresponding block. + * + * As a side effect variables are local to a block. We reuse the name of the predecessor if they + * represent the same value (i.e. not a real φ definition). + * + * <h2>Examples</h2> + * + * <h3>Merge (φ)</h3> + * + * <pre> + * B0 -> B1 + * ... + * v0|i = ... + * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1 + * ________________________________________________ + * + * B2 -> B1 + * ... + * v1|i = ... + * v2|i = ... + * JUMP ~[v1|i, v2|i] destination: B2 -> B1 + * ________________________________________________ + * + * B1 <- B0,B2 + * [v3|i, v4|i] = LABEL + * ... + * </pre> + * + * Note: the outgoing values of a block can contain constants (see <code>B0</code>). + * + * <h3>Split (σ)</h3> + * + * <pre> + * B0 -> B1,B2 + * ... + * v0|i = ... + * v1|i = ... + * v2|i = ... + * TEST (x: v1|i, y: v1|i) + * BRANCH ~[v2|i, v0|j] condition: <, true: B1 false: B2 + * ________________________________________________ + * + * B1 <- B0 + * [-, v0|j] = LABEL + * ... + * ________________________________________________ + * + * B2 <- B0 + * [v2|i, v0|j] = LABEL + * ... + * </pre> + * + * Note: If a incoming value is not needed in a branch it is {@link Value#ILLEGAL ignored} (see + * <code>B1<code>). + */ public final class SSIUtil { public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) {