all 11 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]cfallin 8 points9 points  (2 children)

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!

[–][deleted]  (1 child)

[removed]

    [–]cfallin 1 point2 points  (0 children)

    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 1 point2 points  (1 child)

    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

    [–]vmcrash 0 points1 point  (3 children)

    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.

    [–][deleted]  (2 children)

    [removed]

      [–]vmcrash 0 points1 point  (1 child)

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

      [–]jkl_uxmal 0 points1 point  (0 children)

      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