CODEWITHSUNDEEP
compiler-constructiongraph-theoryssa
Jorayen
Jorayen

Reputation: 1971

SSA generation phi nodes placement

I'm generating SSA using Cytron's algorithm I have the following CFG: enter image description here It's basically an if - else if code.
Looking at block 0x3edc (else if block) it sets register w8 in it, if the condition is true it eventually gets to block 0x3ef0 which also sets register w8, if it's false then it jump straight to block 0x3f08 which exists the else if structure to the rest of the code.

Looking at the control-flow presented here I expect block 0x3f08 to have phi assignment for w8 with 2 possible values one from block 0x3edc and one from 0x3ef0, but according to Cytron's algorithm we only place phi assignment (and extend already existing phi assignments to more variable) if node Y is part of the dominance frontier set of node X we're currently processing in our worklist:

...
for each Y & DF(X) do
  if HasAlready(Y) < IterCount
  then do
    place (V = Φ(V,..., V)) at Y
...

Problem with that is only block 0x3ef0 has block 0x3f08 as part of its dominance frontier so we'll only have one phi variable in our assignment like so:

w8 = Φ(w8)

Where instead we should have:

w8 = Φ(w8, w8)

since we can have both values from either block following up to 0x3f08. I wonder if I'm missing something from the algorithm that I don't understand how it applies to this case and would appreciate clarification.

Upvotes: 0

Views: 107

Answers (0)

Related Questions