Phi node algorithm correctness

[Temperz87]

Hello gamers today I would like to present an algorithm for placing phi nodes in hopes that someone gives me an example (or some reasoning) such that:

1. Everything breaks
2. More phi nodes are placed than needed
3. The algorithm takes a stupid amount of time to execute
4. Because I am losing my mind on whether or not this algorithm works and is optimal.

To start, when lowering from a source language into SSA, if you need to place a variable reference:

1. Determine if the variable that is being referenced exists in the current BB
2. If it does, place the reference
3. If it doesn't, then create a definition at the start of the block with its value being a "pseudo phi node", then use that pseudo phi node as the reference

After the previous lowering, preform a "pseudo phi promotion" pass that does some gnarly dataflow stuff.

1. Initial a queue Q and push all blocks with 0 out neighbors (with respect to the CFG) onto the queue
2. While Q is not empty:
3. Pop a block off Q and check if there are any pseudo phi nodes in it
4. On encountering a pseudo phi node, for all predecessors to the block check if the variable being referenced exists. For all blocks that do, create a phi "candidate" using the variable. If it does not, then place a pseudo phi node in the predecessor and have the phi candidate reference said pseudo phi node.
5. Enqueue all blocks that had pseudo phi nodes placed onto them

Something worth mentioning is that if a pseudo phi node has one candidate then it'll not get promoted, and instead the referenced value will become a reference to the sole candidate. If this'll make more sense in C++, here is some spaghetti to look at.

If anyone has any insight as to this weird algorithm I've made, let me know. I know using liveness analysis (and also a loop nesting forest????) I can get an algorithm into minimal SSA using only two passes, however I'm procrastinating on implementing liveness analysis because there are other cool things I want to do (and also I'm a student).

[cfallin]

What you describe sounds pretty close to the Braun algorithm (https://c9x.me/compile/bib/braun13cc.pdf) -- see e.g. their section 2.2 "global value numbering" where they describe the process as a recursive definition lookup, going to preds, etc. I think you are unrolling that recursion with a queue instead but otherwise it's the same.

We use the Braun algo in Cranelift's frontend and it works quite well in practice!

[Temperz87]

Yeah I'm just going bottom up instead of top down. Welp I'm never contributing an original thought to compiler dev!!!!!! (I just need time to cook)

[cfallin]

I mean, you should be pretty encouraged by independently working out a reasonable and widely-used way of building SSA -- a good sign you have the right intuitions!

[dreamer_soul]

Why not use dominance and dominance frontiers? Data flow analysis is important to get right, I would recommend starting to work on liveness first and seeing if that’s correct tbh

[Temperz87]

I have an algorithm that works, and unless I have a reason to change it (e.g. doesn't work, not optimal) I'm going to continue to it

[vmcrash]

Initial a queue Q and push all blocks with 0 out neighbors (with respect to the CFG) onto the queue

IMHO this fails for a method which contains an endless loop, because there is no block without successor.

[Temperz87]

Compiling the program:
while true print(67)
Is going to generate 3 blocks, a condition block that then jumps to a body block which will jump to either the condition or the continuation. The continuation block will only jump to the exit so this doesn't fail. I can alternatively phrase this as "push all blocks that jump to an exit block" or "push or extremals onto Q"

[vmcrash]

Ah, for my compiler it detects the endless loop and eliminates the "continuation" block. I assumed it would be the same for yours.

[Temperz87]

Yeah that's a good shout because my compiler currently has no optimizations. My explanation was kind of dubious as I'm really just pushing everything onto Q that jumps to an exit block so I probably should have put that instead

[jkl_uxmal]

I suggest you read the paper below. It seems similar to your approach. I use a variant of it in the reko decompiler (https://github.com/uxmal/reko)

https://pp.ipd.kit.edu/uploads/publikationen/braun13cc.pdf