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