post dominance frontier fix

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: post dominance frontier fix

Chris Lattner
On Fri, 20 Apr 2007, Ryan M. Lefever wrote:
> 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.

It looks great, but unless the issues you mention are fixed, we really
can't integrate it... Maybe you can find time to do these small cleanups
when you are between other projects?

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: post dominance frontier fix

Ryan M. Lefever
Chris Lattner wrote:

> On Fri, 20 Apr 2007, Ryan M. Lefever wrote:
>
>>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.
>
>
> It looks great, but unless the issues you mention are fixed, we really
> can't integrate it... Maybe you can find time to do these small cleanups
> when you are between other projects?

Sure.  I would like to contribute back to LLVM.  When I have some spare
time I'll look at what exactly will need to be changed.

>
> -Chris
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev