A while ago I reported a bug in the computation of the post-dominance frontier (PDF). I submitted it as http://llvm.org/bugs/show_bug.cgi?id=1069, and it is now marked as a duplicate of http://llvm.org/bugs/show_bug.cgi?id=1098, which is still an open bug.
I needed the PDF to compute control dependencies for code on which I'm working. I was not familiar with the algorithm used in LLVM and didn't have a lot of time to figure out how to fix it. So, I wrote my own PDF analysis based on the algorithm in "A Simple, Fast Dominance Algorithm" by K. D. Cooper, T. J. Harvey, and K. Kennedy (http://www.hipersoft.rice.edu/grads/publications/dom14.pdf). It is not the most algorithmically-efficient algorithm for computing dominance frontiers, but the authors claim that it runs faster in practice than other more algorithmically -efficient algorithms such as the Lengauer-Tarjan algorithm. The algorithm by Cooper, Harvey, and Kennedy also has the added benefit that it is easier to implement, and consequently easier to get correct.
I would like to contribute the code back to LLVM if you want it. However, there are a few points I should bring up.
1) I'm sure that I have not followed all of the LLVM coding standards. For example, I'm pretty sure I've used "using namespace std," and I have a policy of my own in which I put underscores in front of the names of member variables to distinguish them from local variables, etc. (Actually I'm not sure if the underscores go against LLVM coding standards, but it is certainly a different style than other LLVM code that I've seen.)
2) I did not implement the same interface as the llvm::PostDominanceFrontier.
3) My implementation uses a base node class wrapper which wraps basic blocks. I did that for 2 reasons. First, it makes it simple to reverse the CFG (control flow graph), so I can use the same algorithm/code used to compute the DF to also compute the PDF. (The PDF is the DF computed on the reverse CFG). Second, a base node class allows me to use a dummy entry and exit block as discussed in most literature. I know that the current LLVM implementations of dominance frontiers do not use the dummy entry and exit blocks, however in my project I needed to know which basic blocks contain those dummy blocks in their PDF and DF.
Unfortunately, the first two points above are artifacts due to strict time constraints concerning my current project. However, I believe that over time my code could be modified to meet LLVM coding standards and to conform to the current interface that LLVM exposes for the PDF.
Please advise on how I should proceed. Even though, as I mentioned, the code does not follow the LLVM coding standards and does not adhere to the llvm::PostDominanceFrontier interface, I figured it would be better to a working PDF than to not have it. Perhaps if you don't want to insert it into the regular LLVM code base, you could put it into a project.
Regards,
Ryan