[LLVMdev] DominanceFrontier/PostDominanceFrontier for PRE

[Shuxin Yang]

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>