3 ms·

Does anyone have thoughts/opinions on the algorithm presented in "Simple and Efficient Construction of Static Single Assignment Form"[1] by Braun, et al? I'm mo

• cwzwarich 12y ago
  It's a well-regarded folklore algorithm, although that paper is the first publication with a detailed analysis. If I was designing a compiler frontend and optimizer/backend in concert I would definitely use it unless some other constraint prevented it. In addition to not having to generate a non-SSA program and then immediately throw it away, it allows you to do basic optimizations during SSA construction that you would probably do immediately after constructing SSA anyways. The two major downsides would be extra complexity in the frontend and the impossibility of using the algorithm for SSA repair after IR modifications. The extra complexity in the frontend can hopefully be hidden behind an abstraction, and a lot of serious compilers end up using a separate implementation of SSA construction for repair anyways, so I don't know how big of a deal these drawbacks really are. I am one of the authors of the "highly-optimized implementation of Cytron et al.'s algorithm" that is used in LLVM. That is a bit of a misattribution; I changed LLVM to use the DJ graph algorithm by Sreedhar and Gao before they took their measurements for the paper. I would have expected their approach to be even faster in comparison than what they measured, but it could just be that they didn't do serious performance analysis and tuning.