# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1437742389 -7200
# Node ID 610c1d8cec4db0cda3d681ff23a5bde371aa7448
# Parent  b93161ba3364d0dc70e00bde0d373142f3f89872
SSIUtil: document SSI form.

diff -r b93161ba3364 -r 610c1d8cec4d graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java
--- 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 &phi; and &sigma;</h2>
+ *
+ * There are no explicit &phi;/&sigma; {@link LIRInstruction}s. Instead, they are implemented as
+ * parallel copy that spans across a control-flow edge.
+ *
+ * The variables introduced by &phi;/&sigma; 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 &phi; or a &sigma; 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 &phi;/&sigma;. 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 &phi; definition).
+ *
+ * <h2>Examples</h2>
+ *
+ * <h3>Merge (&phi;)</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 (&sigma;)</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) {