Ken Zadeck was my office mate at IBM Research for a bit, and told me these groups of people (Ron, etc and Mark/Kenny) essentially discovered they had solved eac

Ken Zadeck was my office mate at IBM Research for a bit, and told me these groups of people (Ron, etc and Mark/Kenny) essentially discovered they had solved each others problems (Ken/Mark needed a formalism and efficient computation, Ron, etc were looking to understand how to use this stuff more broadly) while wandering the halls of watson research and seeing a group of people whiteboarding something at the end of one of the halls. I"m sure it's not quite that simple (and it's been over a decade, so i may be misremembering some details anyway), but still pretty funny. Also explained why the paper often feels like two papers - it kinda is. Nowadays, of course, plenty of linear time algorithms exist for this. In fact, there is basically a whole class of linear time transforms that, when applied to code, will reduce some group of polynomial time algorithms to linear (like SSA does). LLVM, at least when i ran out of time to contribute a few years ago, was using a Sreedhar and Gao's computation algorithm. This is the fastest way to compute it i'm aware of on larger programs. Which is also interesting itself for a few reasons: 1. The paper/algorithm was ignored for many years because some more well known researchers painted it as "very slow in practice" in their papers/comparison charts - it turns out they had just done a really bad implementation. 2. The algorithm is dramatically easier to implement than the paper makes out once you understand what is going on. It's <100 lines of code: https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h https://github.com/llvm/llvm-project/blob/main/llvm/include/... (and this is the refactored version i made to support both forward and reverse iterated dominance frontiers. Cameron's original code was even simpler)