llvm dev - Nov 2013 - [LLVMdev] DominanceFrontier/PostDominanceFrontier for PRE

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



On Fri, Nov 1, 2013 at 11:33 PM, Shuxin Yang <shuxin.llvm at gmail.com>
wrote:
> 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!!!!!
>
>   ---------------------------
>    Let DF(N) be { x | x is N's dom-frontier}
>    Let Dom(N) be { x | x is dominated by N}
>    "kid" = successor in dominator tree
>    "succ" = successor in CFG.
>
>    compute_df(function f) {
>        walk f's dominator tree from bottom up {
>            Let N be the node being visited.
>            1: DF(N) = union of DF(K) where K is N's immediate kid in
> dom-tree
>            2; DF(N) -= DOM(N)
>            3: DF(N) += { some N's immediate CFG succ which qualified as
DF.}
>        }
>    }
>    ---------------------------------------
>
>   I think the algorithm is almost linear because:
>     o. it walk the dom-tree only once.
>     o. the # of union in step 1 is exactly the # of edge in dom-tree.
>     o. step 2 is nothing if the cfg has no more than 100 basic-block (the
> set can be represented by some integers)
>     o. step 3 is nothing as normally a block only have two immediate succ.
>
>  Again  this algorithm is just random idea. It is at your own risk if you
> try it.
>
> On 11/1/13 9:18 PM, Christopher Wood wrote:
>
> 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
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> 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.
>
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.

On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131103/5d26eddf/attachment.html>

On 11/3/13 1:12 AM, Daniel Berlin wrote:
> On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>> 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.
>>
> 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.
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

On Sun, Nov 3, 2013 at 9:19 AM, Christopher Wood
<christopherwood07 at gmail.com> wrote:
> On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>>
>> 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.

>
>>
>>
>> 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