[LLVMdev] post dominance frontier fix

[Ryan M. Lefever]

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