llvm dev - Nov 2013 - [LLVMdev] 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<https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_13/lib/Transforms/Scalar/PRE.cpp>),
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/017868c4/attachment.html>

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 
>
<https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_13/lib/Transforms/Scalar/PRE.cpp>),
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/b9a77888/attachment.html>

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
>