Static Single Assignment: not all possible paths define a variable - how to insert PHI?

Question

I am implementing SSA construction for a compiler I'm writing. There is something I don't understand in the SSA algorithms (using the Cytron paper and the book Modern Compiler Implementation in Java, second edition by A.W. Appel). What if a variable y is defined for the first time (and used) in one straight control flow path but never defined in another parallel path. Do I have to insert a PHI-function at the join point (the dominance frontier of the block defining y)?

x = 1;            // A
if (P)            // A
    y = x + 1;    // B
    y = y + 1;    // B
x = x + 1;        // C
return;           // C

For example, in block B there is the first definition of y. Do I have to insert a PHI instruction at the start of block C, with two operands (one for each incoming control flow path)? Then on SSA renaming: how would I name the operand coming from the path A -> C (not through B) where y is never defined?

Entry --- A --------- C --- Exit
           \         /
            \-- B --/

Answer 1

After reading through the materials again, I found a small hint in the book Modern Compiler Implementation in Java, second edition by A.W. Appel about an implicit definition of a variable c0. Further searching uncovered that the algorithms expect that all variables have an implicit definition just before the first basic block. This implicit definition represents the fact that the variable is global, a parameter or an uninitialized variable.

Adding this implicit definition solves my problem, and the example would become:

x1 = 1;           // A
if (P)            // A
    y1 = x1 + 1;  // B
    y2 = y1 + 1;  // B
y3 = φ(y0, y2)    // C
x2 = x1 + 1;      // C
return;           // C