compiler-constructiongraph-theoryssa

SSA generation using Cytron's algorithm

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: enter image description here

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:

enter image description here

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?

Solution

  • 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:

                            # Cases where node has a doiminator which also defines the symbol
                        # and both has the same frontier node (can happen in loop)
                        # and so the dominator dominates the definition of the symbol of the
                        # current node then we don't need to insert another variable to the
                        # phi assingment of the frontiner node
                        idom = node.idom
                        quit = False
                        while idom != None and idom != frontier_node:
                            if frontier_node in idom.dominance_frontier and idom in procedure.symbol_defs[sym]:
                                quit = True
                                break
                            idom = idom.idom
                        
                        if quit: # continue to the next node in the enacpsuling loop of phi nodes insertion
                            continue

    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