DominanceFrontier/PostDominanceFrontier for PRE

Hi all,

Does anyone know how to recreate the DominanceFronter and PostDominanceFrontier structures using the API of the latest release? To my knowledge, these are needed to implement a PRE pass (as done in the past), but they were removed a while ago for efficiency reasons. Is there a better way to implement PRE using the current API, or, alternatively, is there an easier way to construct these data structures?

Thanks in advance for any help you can provide.

Cheers,
Chris

Hi,

    I'm not able to answer your question. I'm wondering if you can create your own if it is just your own hobby project,
or a project that you don't have to commit to the main repository.

    Creating DominatorFrontier seems to be expensive. However, if you are using bit-vector to represent a basic-block-set, I
guess it can be done in linear time in practice. Following is the algorithm in my mind, I never see people implement
DF this way, and myself are lazying about implementing one. However, I don't see a problem. Maybe you can try
this one. !!!!!!Caveat: It is at your own risk, as this algorithm is not proved at all!!!!!

Is there a reason this is better than the modified algorithm created
by Ferrante?
It looks like yours has as bad a worst case time bound in reality.
That is, the algorithm runs in O(sum of the size of all the dominance
frontiers).

http://www.cs.rice.edu/~keith/Embed/dom.pdf

See figure 5. It will only touch nodes actually in the dominance frontier.

This is what GCC uses.

There are actually real almost linear dominance frontier algorithms
(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.202 is one
example. Sreedhar's classic dj-graphs paper on placing phi nodes in
linear time, shows also how to compute dominance frontier in same
time bound)

In practice, nobody implements these because the computation time of
dominance frontiers is just not that large most of the time.

In any case, to answer the original question, dominance frontiers are
not necessary to compute PRE dataflow problems.
Certain sparse formulations of PRE have papers that were written to
use dominance frontiers, but in all of those cases, they are really
using it as part of a phi-placement algorithm.
You could substitute any valid phi placement algorithm for that
portion of the algorithm (including any of the linear time phi
placements, or llvm's current phi placement). For example, in SSAPRE,
the part called DF(phis) could be replaced with such an algorithm
(though var phis could not).

As for a "better" way to implement PRE, it depends on what algorithm
you want to use. If you just want to write a PRE pass, that's easy
enough without dominance frontiers.

If you want to implement the original SSAPRE, i suggest looking at
http://jcse.kiise.org/posting/2-3/jcse_2-3_31.pdf

Note this is mostly rhetorical, as that the paper asserts about the
dominance frontier algorithm in figure 5: "we contend that the sets
cannot be built any more efficiently".
Given the paper's authors, I have a tendency to trust this assertion.

As for a "better" way to implement PRE, it depends on what algorithm
you want to use. If you just want to write a PRE pass, that's easy
enough without dominance frontiers.

I simply want to write a PRE pass to get a better understanding of the
transformation. Any tips on where to get started (beyond the papers you
provided) for someone -new- to the game?

If you want to implement the original SSAPRE, i suggest looking at
http://jcse.kiise.org/posting/2-3/jcse_2-3_31.pdf

Thanks - I will read through this paper.

Chris

APint can be considered as a dense bit set. Dose it look horrible to you :-)?
Sparse bit-set for base-blocks is not inefficient either. Of course, other sets
are scary, I agree.

Normally, a function have no more than 200 bb, making the cost of bit-set
operation almost negligible in practice. Another benefit of using bit-set is
the nice locality.

Anyway, it's just my random boring idea. I believe it maybe fundamentally flawed.
Thank you for sharing your insight. But since Christopher is asking something else,
let us don't discuss this algorithm to deviate the original topic:-)

Thanks
Shuxin

As for a "better" way to implement PRE, it depends on what algorithm
you want to use. If you just want to write a PRE pass, that's easy
enough without dominance frontiers.

I simply want to write a PRE pass to get a better understanding of the
transformation. Any tips on where to get started (beyond the papers you
provided) for someone -new- to the game?

Okay, well, SSAPRE is actually a fairly hard paper to implement
correctly if this is your first go-around.

If you want something that gives you an intro to PRE (though the
formulation is not "standard" compared to most papers), take a look at
http://researcher.watson.ibm.com/researcher/files/us-akundu/thesis-mtech.ps

It's implementable, and it'll work, and doesn't require a large amount
of detail discovery by the user.

Also, if you look at LLVM's svn history, there are old PRE
implementations that have been deleted:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/PRE.cpp?view=log&pathrev=25348
(e-path PRE, like the paper above)

http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/GVNPRE.cpp?revision=80766&view=markup&pathrev=83192
(GVNPRE)

Making a worthwhile PRE that is not slow tends to be quite an engineering task.

Sigh, the first PRE.cpp URL got munged.
Try
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/PRE.cpp?view=log&pathrev=25348

Also note that though this is an SSA based e-path PRE implementation,
I do *not* believe it is based on the actual SSA e-path PRE thesis i
linked you too.