I'm trying to generate SSA using Cytron's algorithm Everything seems to work fine but for some test case I'm getting a problem. I have the following loop test example setup:
My problem arises with definition of w8
on node 0x100003f50
.
The nodes that has 0x100003f50
as a node in their dominance frontier set and have w8
as definition are:
0x100003f64
0x100003f50
0x100003fa8
NOTE that node 0x100003fa8
has not definitions initially, on the second iteration it does have w8
definition of the form of phi assignment from nodes 0x100003f90
and 0x100003f78
.
So after the phi function insertion step we have 3 arguments to phi assignment for definition w8
in node 0x100003f50
.
Next to the rename step, where we replace the phi variables with their corresponding definition from the predecessor of the block that defines a phi assignment, in this case 0x100003f50
, the 0x100003f50
node has only 2 predecessor, making the substitution of the phi arguments of w8
missing a rename, and not only that it doesn't make a-lot of sense to me to just iterate the successors of blocks to replace their phi function arguments with the corresponding block index, since in the classic example:
It seems to work fine that each of the predecessor of the block defining the phi function also has the block as its dominance frontier, in my example the predecessor of the test block defining the phi function for w8
, that is block 0x100003f50
, has the entry block and the loop edge node as predecessor, leaving out one of the phi arguments unchanged, so I wonder what am I missing here?
I don't know if it's the correct answer or I just missed something but I came up with the idea that if the current node has somewhere in the dominator tree a node which isn't the frontier node in question, which also has the same frontier node, then I don't insert another phi argument for this special case.
Here's a partial fix written in python:
EDIT: I actually found this presentation https://www.cs.toronto.edu/~pekhimenko/courses/cscd70-w20/docs/Lecture%204%20[SSA]%2002.03.2020.pdf
Which illustrate Cytron's algorithm on page 26 and states a condition for insertion of phi node (before describing the algorithm in terms of dominance frontiers):
S.t Pxz Union Pyz = { z } (Z is only common block along paths)
Which makes sense to what I've did with the coalescing