4 ms·

This looks helpful. I would love to find a simple method of generating SSA that can deal with goto statements. A paper that was suggested to me (not mentioned

This looks helpful. I would love to find a simple method of generating SSA that can deal with goto statements. A paper that was suggested to me (not mentioned in the linked blog post) is: "Practical Improvements to the Construction and Destruction of Static Single Assignment Form", by Preston Briggs, Keith D. Cooper, Timothy J. Harvey, I. Taylor Simpson all at Rice University SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 28(8), 1–28 (July 1998)

tekknolagi 2y ago
What source language are you working with that has go-to?
- swiftcoder 2y ago
  Doesn't every language with break-to-label (i.e. break out of multiple nested loops) effectively have goto, from an implementation standpoint?
  - tekknolagi 2y ago
    Yes but that is not what makes irreducible control flow graphs, I think. You'll still have structured control flow
    - matt_d 2y ago
      On that note, there's an ongoing discussion on allowing early exits currently not allowed in the MLIR's SCF (structured control flow) dialect, https://discourse.llvm.org/t/rfc-region-based-control-flow-with-early-exits-in-mlir/76998 https://discourse.llvm.org/t/rfc-region-based-control-flow-w..., https://github.com/google/heir/issues/922 https://github.com/google/heir/issues/922
- RossBencina 2y ago
  ISO C
barrkel 2y ago
Gotos are edges in a graph of basic blocks - runs of code with only one entry and one exit. Once you have your code in the form of basic blocks, there's lots of resources. See e.g. https://www.cs.cmu.edu/~fp/courses/15411-f13/lectures/06-ssa.pdf https://www.cs.cmu.edu/~fp/courses/15411-f13/lectures/06-ssa...
- ufo 2y ago
  I presume their question is about "simple" techniqyes. With goto, the most famous one needs to compute dominance frontiers.
  - rayiner 2y ago
    Simple as in low time complexity? Computing dominance frontiers is pretty easy: https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom14.pdf https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom1...
rayiner 2y ago
That one is pretty easy to implement. The Cooper & Torczon book describes the algorithm well and has worked examples. https://shop.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-815412-0 https://shop.elsevier.com/books/engineering-a-compiler/coope... Note also if you’re dealing with weird control flow you might get oddities in translating out of SSA form: https://www.tjhsst.edu/~rlatimer/papers/sreedharTranslatingOutOfStaticSingleAssignmentForm.pdf https://www.tjhsst.edu/~rlatimer/papers/sreedharTranslatingO.... Sreedhar’s algorithm for translating out of SSA form is relatively easy to implement. This is probably useless to you unless you know Common Lisp, but I put together a couple of toy implementations of these algorithms years ago to help myself learn them. There’s a couple of nits the papers gloss over that are noted in comments. You’ll need to compute liveness and dominance frontiers. Examples for those are in the project too. https://github.com/rayiner/portfolio/blob/master/ssa_analysis/ssa-conversion.lisp https://github.com/rayiner/portfolio/blob/master/ssa_analysi... https://github.com/rayiner/portfolio/blob/master/ssa_analysis/ssa-elimination.lisp https://github.com/rayiner/portfolio/blob/master/ssa_analysi...

tekknolagi 2y ago

What source language are you working with that has go-to?

swiftcoder 2y ago
Doesn't every language with break-to-label (i.e. break out of multiple nested loops) effectively have goto, from an implementation standpoint?
- tekknolagi 2y ago
  Yes but that is not what makes irreducible control flow graphs, I think. You'll still have structured control flow
  - matt_d 2y ago
    On that note, there's an ongoing discussion on allowing early exits currently not allowed in the MLIR's SCF (structured control flow) dialect, https://discourse.llvm.org/t/rfc-region-based-control-flow-with-early-exits-in-mlir/76998 https://discourse.llvm.org/t/rfc-region-based-control-flow-w..., https://github.com/google/heir/issues/922 https://github.com/google/heir/issues/922
RossBencina 2y ago
ISO C

barrkel 2y ago

Gotos are edges in a graph of basic blocks - runs of code with only one entry and one exit. Once you have your code in the form of basic blocks, there's lots of resources. See e.g. https://www.cs.cmu.edu/~fp/courses/15411-f13/lectures/06-ssa.pdf https://www.cs.cmu.edu/~fp/courses/15411-f13/lectures/06-ssa...

ufo 2y ago
I presume their question is about "simple" techniqyes. With goto, the most famous one needs to compute dominance frontiers.
- rayiner 2y ago
  Simple as in low time complexity? Computing dominance frontiers is pretty easy: https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom14.pdf https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom1...

rayiner 2y ago

That one is pretty easy to implement. The Cooper & Torczon book describes the algorithm well and has worked examples. https://shop.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-815412-0 https://shop.elsevier.com/books/engineering-a-compiler/coope... Note also if you’re dealing with weird control flow you might get oddities in translating out of SSA form: https://www.tjhsst.edu/~rlatimer/papers/sreedharTranslatingOutOfStaticSingleAssignmentForm.pdf https://www.tjhsst.edu/~rlatimer/papers/sreedharTranslatingO.... Sreedhar’s algorithm for translating out of SSA form is relatively easy to implement. This is probably useless to you unless you know Common Lisp, but I put together a couple of toy implementations of these algorithms years ago to help myself learn them. There’s a couple of nits the papers gloss over that are noted in comments. You’ll need to compute liveness and dominance frontiers. Examples for those are in the project too. https://github.com/rayiner/portfolio/blob/master/ssa_analysis/ssa-conversion.lisp https://github.com/rayiner/portfolio/blob/master/ssa_analysi... https://github.com/rayiner/portfolio/blob/master/ssa_analysis/ssa-elimination.lisp https://github.com/rayiner/portfolio/blob/master/ssa_analysi...